Wednesday, December 31, 2008

One Bit Manipulation - A Reduced Instruction Set Computer

The esoteric computer programming language, brainfuck, a reduced instruction set language and slight variation of p prime prime, uses a set of only eight instructions to perform universal computation. In otherwords, it can perform operations equivalent in complexity to any other computer, regardless of the fact that most modern processors use instruction sets consisting of several thousands of commands. Brainfuck uses basic operations to control both it's program counter and it's one and only memory pointer. By moving the memory and program pointers back and forth and incrementing and decrementing the values contained within up and down with conditional control, the limited language is capable of solving any algorithmically expressable problem. The 8 instructions are:
+ (increment value at pointer)
- (decrement value at pointer)
> (move pointer right)
< (move pointer left)
[ (jump forward to the matcing "]" *they can be nested if value at pointer is zero
] (jump backward to the command after the matching "[" if the value at the pointer is non zero
. (output the value at the pointer)
, (accept an input and store it in the location pointed to by the pointer)

Although this set may seem already maximally reduced, it can be decreased further! Firstly, the input and output commands are completely unnecessary. They simply provide a convenient method of transfering data between the processor and the external world. Other methods exists, such as memory mapping, and because of this, they can be eliminated.

On top of that, the brainfuck language assumes that the registers comprising the memory locations are 8 bit, however 8 bit wide registers are not necessary and reducing them to the logical extreme of only one bit allows for the + and - commands to be reduced to a single instruction. Since incrementing or decrementing a 1 bit value simple reverses the current value, for example ones turns to zeros and a zeros turns to ones, only one command is necessary and so for purposes of this article we can express it as "x", meaning to flip the current bit.

With this modified language, constructed from only 5 opcodes, one can create an even less efficient way of solving any problem. Is it possible to reduce the instruction set even further? Actually, surprisingly, the answer is yes. By the inclusions of more complicated internal architecture and addition of parameter based operations, the instruction set can be reduced to only one instruction. This impractical system doesn't do much more than to illustrate the methods by which a single instruction computer can work, however, it greatly reduces the quantity of transistors required to fabricate the processor and assuming that one day transistor switching times are reduced sufficiently, it could very well become cost effective.

No comments: