BitBitJump
BitBitJump is one of the simplest OISC languages. It allows calculations by only bit copying process without using conventional logic operations like AND, OR, XOR, NAND, or NOT. Its instruction is to copy one bit from one address to another and jump.
The instruction has three operands
A B C
similar to Subleq but with a different meaning. A is the address of the bit to copy from. B is the address of the bit to copy into. C is the address to pass the execution after copying of the bit is done.
Basics
The abstract machine operates on an infinite array of memory. Memory consists of bits. Each bit has its own address. Addresses start from 0. Bits are grouped into words of the same size. Each word is a set of bits which can be treated as binary representation of the address. The abstract machine reads words from memory starting from the first word. Three subsequent words in memory constitute an instruction. Each word of the instruction is an address. The meaning of the instruction, which words are A B C, is: 1) copy a bit addressed by A to the bit addressed by B; 2) jump the execution control to the address C.
Consider the following code
19 20 8 0 0 -1
in 8-bit representation
[00010011] [00010100] [00001000] [00000000] [00000000] [11111111]
Note, that words presented in a conventional order of bits higher to lower, so the first bit in memory is 1 (address 0), the second bit is 1 (address 1), the third bit is 0 (address 2), and so on. The first instruction copies 19th bit, which is the 4th bit in the 3rd word, to 20th bit, which is the 5th bit in the 3rd word. The 3rd word becomes 24:
[00010011] [00010100] [00011000] [00000000] [00000000] [11111111]
The control execution is passed to the next instruction because 24 is the address of the first bit in the 4th word. This instruction copies bit 0 to itself and stops the program because the address is -1.
If the first instruction would be, for example,
20 20 8
The 3rd word would not be changed, and the next instruction to be executed is
20 8 0
which does not change memory (because it copies 0 to 0), but passes the control back to the address 0. This would result in infinite loop.
Grouping bits into words is a logical concept. The memory is the array of bits. If the control execution is passed to the address not aligned with the word boundary, it is up to the implementation whether to fail or continue treating words from the new alignment.
Assembly
To simplify the presentation of the language instruction let us use the following assembly notation. Each word is denoted as L:A’x, where L is a label and the address of this memory cell, A is the value of this memory, x is the bit offset within the word. The label and the bit offset are optional. Each instruction is written on a separate line. For example:
A’0 B’1 A
A:18 B:7 0
There are 2 instructions above. The first instruction copies the lowest bit of the cell A (which value is 18) into the second bit of the cell B (which value is 7), then jumps to the instruction addressed by A, which is the next instruction. After the first instruction is executed the value of the cell B is changed to 5.
The bit offset can be omitted. In this case it is considered to be 0. So, A is the same as A’0.
If C-operand is absent it is assumed to have the value of the next cell address, i. e.
A B
is the same as
A B C
C: ...
and is the same as
A B ?
Question mark (?) is the address of the next memory cell. Let’s denote (n?) as a multiple to cell size counted from the current position. So, (0?) means the address of this position; (1?) is the same as (?) and is the next cell; (2?) is one after the next cell; and (-2?) is one before the previous cell. For example, the instruction
A:B B -2?
is the same as
A:B B A
and is an infinite loop, because after the bit referenced by B is copied to the bit referenced by B the control is passed to the address of the cell A, which is the beginning of this same instruction.
To make a program description shorter and more readable let us define a macro substitution mechanism as the following:
.copy A B
...
.def copy X Y
X’0 Y’0
X’1 Y’1
...
X’w Y’w
.end
In the fragment above the first line is the macro command which is substituted by the body of macro definition starting with ".def" and ending with ".end". The name after ".def" becomes the name of the macro and all subsequent names are formal arguments to the macro. So that after macro substitution the code becomes:
A’0 B’0
A’1 B’1
...
A’w B’w
Here w is the index of the highest bit. It is equal to the size of memory cell minus one.
Simple programs
Since the program can copy only bits it is natural to define a stream of bits as bits copied to or from a particular address. One special address (-1) has already been introduced as the halt address – a program halts if the process control is passed to the address (-1). One can use the same address without ambiguity as:
.def out H
H'0 -1
H'1 -1
H'2 -1
H'3 -1
H'4 -1
H'5 -1
H'6 -1
H'7 -1
.end
.def in H
-1 H'0
-1 H'1
-1 H'2
-1 H'3
-1 H'4
-1 H'5
-1 H'6
-1 H'7
.end
Note, that only 8 lower bits are copied to and from the word. With this definition it is possible to write assembly code, word size of which is independent, and which inputs or outputs characters as 8-bit symbols.
The program
.out H
.out i
0 0 -1
H:72 i:105
prints "Hi".
This program echoes input to the output
start: .in X
.out X
0 0 start
X:0 0
Examples
Conditional jump
To achieve something more complicated a few additional macros are required. The first one is a macro testing a bit and jumping to one of two addresses depending on value of the bit:
Z0:0 Z1:0
.def test A bit K0 K1 : Z0 Z1
.copy L0 Z0
.copy L1 Z1
.jump01 A bit
L0:K0 L1:K1
.end
.def jump01 A b
A'b 2?'k
0 J'0
A'b 2?'k
1 J'1
A'b 2?'k
2 J'2
...
A'b 2?'k
(w-2) J'(w-2)
A'b 2?'k
(w-1) J'(w-1)
A'b 2?'k
w J'w J:0
.end
Where k is defined as 2k=w+1, and w is, as above, the index of the highest bit in the word. Macro jump01 is included inside macro test. This shows that macros can be included in each other. However with complex operations such as arithmetic the code blows up enormously. To avoid this functions can be used where the control is passed to the particular places and returned back. Functions are implemented in the library 'lib.bbj'. Note that macro test uses external references Z0 and Z1. They are not formal arguments to the macro hence they are delimited by colon (:).
Once the test is implemented, it is a matter of technique to implement increment operation, and then other arithmetic. It is handy to put all macros into a separate file and introduce a special command to include this file.
Hello, world!
Helloworld program in one library implementation may look like this:
Z0:0 Z1:0
start: .deref p X
.testH X print -1
print: .out X
.add p BASE p
0 0 start
p:H X:0
H:72 101 108
108 111 44
32 87 111
114 108 100
33 10 -1
.include lib.bbj
The first line in this example is necessary as the test macro defined to use the first 2 memory cells. The second line dereferences the pointer p into X (it code see below). testH is short for testing the highest bit. add is a macro adding 2 variables and storing the result into the third argument. BASE is a memory cell with a value equal to memory cell size defined in the library. lib.bbj is a library file with all macro definitions.
Dereferencing can be defined as the following:
.copy ONE ctr
.copy P A
.copy L B
begin: A:0 B:0
.testH ctr next End
next: .shiftL ctr
.inc A
.inc B
0 0 begin
End: ...
L:X ctr:0 ONE:1
If P is a pointer to some word, then the value of this word is copied to X.
Print string in reverse order
The following program uses unlimited memory after the code. The instruction under the label mem is conditional, so it is resolved at the end of the program.
Z0:0 Z1:0 start
.include lib.bbj
:mem:0 0 0
m0:mem m:mem
x:0 Z:0 m1:-1
start: .copy m1 x
.in x
.ifeq x m1 next store
store: .toref x m
.out x
.add m BASE m
0 0 start
next: .sub m BASE m
.deref m x
.out x
.ifeq m m0 -1 next
Note, that this simple program does not define the size of BitBitJump memory cell.
Brainfuck interpreter
Brainfuck interpreter is a straightforward implementation. First a brainfuck program is read from the input and stored in the memory after the program code. All the rest memory after the brainfuck program is given to the brainfuck program. The interpreter implements dbfi dialect. It is about 200 lines, so it is there. As in the example above, the interpreter in its assembly form is not bound to the memory limitation of the BitBitJump instruction.
Self-interpreter
Self-interpreter in BitBitJump is straightforward. For simplicity assume that the program to be emulated is behind the self-interpreter. The sequence of steps to be done is copy two operands of the instruction to the internal instruction and execute it, then load the third operand and set its value to the instruction pointer. There are only two complications: 1) values of the interpreted program have to be offset with the address - beginning of the program, and 2) if the value is less then 0 (i.e. special address for halt, input, or output), it must be copied without the program offset.
Z0:0 Z1:0 start
.include lib.bbj
:heap:0 0 0
ip:heap prog:heap x:0
.def map X offset Y
.testH X no yes
yes: .copy X Y
0 0 ret
no: .add X offset Y
ret: 0 0
.end
# move pointers to program
start:.add ip BASE ip
.add ip BASE ip
.add ip BASE ip
.add prog BASE prog
.add prog BASE prog
.add prog BASE prog
# load 2 operands
loop: .deref ip x
.map x prog i1
.add ip BASE ip
.deref ip x
.map x prog i2
# execute instruction
i1:0 i2:0
# load and do jump operand
.add ip BASE ip
.deref ip x
.map x prog ip
.testH ip loop -1
To run it compile self-interpreter and the program to be executed, concatenate them, then run in the emulator.
Macro Library
The following macros are defined in the library of the current implementation
| Name | Arguments | Description |
| copy | X Y | copy word X into Y |
| testL | A L0 L1 | same as testH, but tests the lowest bit |
| testH | A L0 L1 | test the highest bit of A and go to L0 if 0, or to L1 if it is 1 |
| test | A bit K0 K1 | test bit in A, and jump to K0 or K1 if bit is 0 or 1. |
| shiftL | X | shift bits in X from high to low |
| shiftR | X | shift bits in X from low to high |
| rollL | X | same as shiftL, but move popped bit back to the front |
| rollR | X | same as shiftR, but move popped bit back to the front |
| next | P | increment P by the word size |
| prev | P | decrement P by the word size |
| out | H | outputs 8 lower bits of H as ASCII |
| in | H | inputs 8 bits as ASCII and store in lower bit of H |
| ifeq | X Y yes no | test if X=Y, go to yes if true, otherwise go to no |
| ifzero | Z yes no | test if all Z bits are 0, go to yes if true, otherwise go to no |
| iflt | A B yes no | test if A is arithmetically less than B, go to yes if true, otherwise go to no |
| inc | X | increment X by 1 |
| dec | X | decrement X by 1 |
| deref | P R | same as C R=*P |
| toref | A P | same as C *P=A |
| add | X Y Z | Z=X+Y |
| sub | X Y Z | Z=X-Y |
| inv | X | invert all bits in X |
| div | X Y Z R | same as C Z=X/Y and R=X%Y |
| prn | X | print X as number (this involves division) |
| mul | X Y Z | Z=X*Y |
The library provides higher programming level and allows to write programs independent on the memory cell size.
How to run BitBitJump programs
BitBitJump assembler
Download windows executable (or C++ source) assembler. The command
bbjasm.exe hello.bbj
compiles assembly text into the code ready to be run on the emulator.
BitBitJump emulator
Download windows executable emulator (or C++ source). Running with no arguments it prints a brief help.
bbjrun.exe hello
BitBitJump variations
BitBitJump as described requires CPU to have program counter (PC) register and increment operation. Douglas W. Jones proposed the following two variations to this language.
PC in word zero
The instruction can be shorten to just two addresses if the program counter sits in zero memory address. The result is that moving an unknown bit into word zero is a conditional branch, while moving a known bit into word zero is an unconditional branch. The complication arising with this is that branching is forced to change PC by a power of two. At this point it is not clear how to design the language to overcome this problem.
One word instruction
Another approach is to eliminate the program counter by fetching the entire instruction as a single large word. For example, a 64-bit word can hold three 21-bit addresses addressing 2 megabits, which is 32768 64-bit words. Then the CPU has just one 64-bit register for the current instruction, plus a one bit register to hold the operand of the current instruction. No adder is required inside the CPU, but the instruction cannot modify itself (or rather if it modifies itself, the result will be executed the next time this instruction is fetched), which is a very minor limitation.
Featuring a Path Selector Bit (BBJ Machine)
Tweet-sized Summary, TLDR: a "copy&select" machine: copy 1 bit and select next instruction. the bit that selects one of the 2 possible next instructions can be written.
This paragraph is originally contributed by User:Arkenidar. Idea's novelty is unknown (the author hasn't found exact copies of this kind of BitBitJump machine design). The author has implemented various incarnations of this idea, for example with various source formats designs (mostly kind of syntactic sugar). The possible optimizations on the MicroCode are an interesting research area (again, contact User:Arkenidar for collaborations).
1 Path Selector Bit per machine (the specificity of the variation of BitBitJump machine). 2 Data Addresses + 2 Instruction Addresses for each instruction. Instruction Format (introductory explanation): uniform instruction set, one kind of instruction, 4 non-negative integers per instructions. A CommaSeparatedValue-like tabular source format can be used as an "intermediate representation" or directly. The 2 instruction addresses are the locations used for the bit copy (where to read and where to write). A specificity, possible novelty: In this version of BitBitJump conditional jump is implemented using 2 Instruction Addresses for each instruction and 1 Path Selector Bit. The Path Selector Bit is used to select which one of the 2 instructions will be the next instruction. The Path Selector Bit can be written by the program (it can be written like every other memory location can be written). In this way the program can vary its course (sequence of executed instructions). Note that, as a specificity, Self-Modification is not required but still available as an optional feature.
Computational class
Because all addresses in any particular BitBitJump program are of a fixed size, a BitBitJump program can only access a fixed amount of storage. That puts BitBitJump in the computational class of Bounded-storage machines, which is the class of real microprocessors.
It seems possible that BitBitJump with relative addressing (allowing addressing infinite amount of memory) or other modifications to memory cell and addressing would produce a Turing-complete language, but this might be difficult to prove.
BitBitJump assembly used with the library defined as a different symbolic language is Turing-complete, because algorithms can be programmed without specification of operand sizes or bit layouts, hence removing the finite-state limitation. See, for example, brainfuck interpreter implementation above.
See also
External resources
- Oleg Mazonka's BitBitJump assembler and emulator page
- Paper describing BitBitJump, Complex Systems Journal 2011, Vol 19, N3, pp. 263-285
- Maude Implementation