The main motivation for designing this language is to prove that Bitwise Trance is Turing complete. It seems feasible (although it hasn't been achieved yet) to implement BitBounce interpreter in Bitwise Trance (with the exception that BitBounce program itself needs to generate extended copy of itself).
All characters except 0 and 1 are ignored. Then 0s and 1s are concatenated to form memory.
Like in Bitwise Trance, memory is infinite. However, at any point in time instructions can access only limited amount of memory.
Memory is divided into
2^n cells, where each cell is
n bits long (total number of accessible bits is therefore
n-4 is located at the begining of the first memory cell (at address 0) and is stored in the same format as addresses in Bitwise Trance. For example, if the memory looks like this:
11011001100111010100... then extract
110, parse as decimal number
2 and add 4, we obtain
n=6, so for the next instruction each memory cell will be
6 bits long.
All memory cells are interpreted as little-endian unsigned integers (little-endianess here refers to bits), so for example memory cell with value
n=4) will be interpreted as number 12.
The first cell in memory contains number
n-4. Note that
n cannot be less than 4. Also note that
n-4 will always fit in a single memory cell. Other bits in the first cell are ignored.
Second cell contains pointer to register array (PTR). There are only two registers: instruction pointer (IP) and stack pointer (SP). Register array is two cells long and IP is at the lower address. For example, if memory looks like this
0000010010101111, we can see that
n=4, PTR=2, IP=5, SP=15. One more important example is
0000111101010101, here we have
n=4, PTR=15, IP=0, SP=0. The difference here is that the address of IP is 15 and because memory is filled with zeros, its value is 0. However, since we have only 15 accessible cells, SP is actually located at address 0 and is equal to n (basically
PTR+1 overflows and we get address
0, which is the location os SP).
n, PTR, IP, SP are parsed before each instruction. If an instruction changes the first memory cell and affects number
n, nothing is really changed in the memory structure. It means that cells that are no longer accessible (due to smaller value of
n than before) aren't now filled with zeros. They stay in the memory and retain their values, but they will not be accessible until
n is increased again.
There are 16 different instructions. Instruction is parsed from the memory cells where IP points to. If
n>4, only 4 lowest bits are considered and other bits are ignored. This is the table
|Opcode||Alias||Description||Number of operands||Gives result|
||CONST||Put a constant onto the stack||0||Yes|
||JZ||Jump to the given address if the value on the stack is 0||2||No|
||CALL||Call the given procedure||1||Yes|
||RET||Return from the current procedure||1||No|
||PUSH||Duplicate the value on the top of the stack||0||Yes|
||POP||Pop the value from the top of the stack||1||No|
||GET||Push value relative to the stack pointer||1||Yes|
||SET||Modify value relative to the stack pointer||2||No|
||READ||Read value from absolute address and push to the stack||1||Yes|
||WRITE||Write value from the stack to the absolute address||2||No|
||NEG||Flip all bits of the given value||1||Yes|
||IMP||Given two numbers, calculate
||SHL||Interpret the second argument as signed integer, based on its sign shift the first argument left or right||2||Yes|
||ADD||Sum the two given numbers||2||Yes|
||IN||Read a bit, pad it with 0s to fill memory cell and push to the stack||0||Yes|
||OUT||Output the lowest bit of the given value||1||No|
This is not a formal specification. Since there are a lot of edge cases and details about how each of these instructions work in which situation, we will not try to explain each instruction in details. Instead, the implementation of the language that we provide can be considered as the formal specification.
The order of tasks for executing instructions is:
- Read all necessary data (n, PTR, IP, SP, memory[IP], memory[SP], memory[SP+1], ...). After this step nothing will be read from memory until next instruction.
- Calculate the new value of IP
- Calculate the new value of SP
- Calculate the result of evaluating the instruction
- Save the new value of IP to the location of IP
- If new SP is not old SP then
- Save new SP to the location of SP
- If the instruction gives result (const, call, push, get, read, neg, imp, shl, add, in) then
- Push the result to the stack
- If the instruction directly modifies memory (set, write) then
- Save the modified value to the given memory cell
"After this step nothing will be read from memory" means that if one of the steps modifies some characteristic value (n, PTR, ...) that value is not going to be reparsed in the same instruction. The order is important, since two steps may write to the same address.
Calculating new value of IP
const is two cells long. The first cell of course contains the opcode itself at the lower 4 bits. The next cell contain literal value that will be pushed to the stack. After this instruction, IP is increased by 2 (take care of integer overflow). After
jz, call, ret IP will have the value from the top of the stack. After all other instructions, IP is incremented by 1.
Calculating new value of SP
New value of SP is modified by difference between number of operands and 1 or 0 depending if the instruction gives the result or not. Operands are read from the top of the stack. Only if the new value of SP is different than the old value, then SP is saved to the address of SP. This is not the case for IP, since IP is always written to memory, even if we jump to the same address. Details about the order of operands and techincal details can be found in the implementation.
Stack is determined by SP. Before any instruction, SP points to the last allocated value on the stack and stack grows to lower addresses (after pushing to the stack, SP is decreased).
Input is converted to byte array, then each byte is converted to little-endian bit array of length 8 and concatenated. Before each bit of the input put 1 and after all bits put infinitely many zeros. For example, input
123 will be converted to
11101010111110101011101011111010111110101111101 and the rest are zeros.
Output is similar. Read pair of bits, if the first bit is
0 terminate the program, otherwise append the second bit to the output. Bytes in the output are also little-endian (same as input format).
Here we have a program that reads input string, flips the lowest bit of the first byte and outputs the modified string. This example should demonstrate the majority of instructions and how the stack works. This example uses constant number
n=8. All characters except 0 and 1 are ignored.
*** Header *** 1110.0000 ; Memory cell size: 8 0100.0000 ; Registers pointer: 2 1010.0000 ; Instruction pointer: 5 1111.1111 ; Stack pointer: 255 *** Program *** 1000.0000 ; flag 0111.0000 ; IN 1111.0000 ; OUT 0111.0000 ; IN 0000.0000 ; CONST SEVENTEEN 1000.1000 0100.0000 ; CALL (Function) 1111.0000 ; OUT 0000.0000 ; CONST ZERO 0000.0000 0000.0000 ; CONST FIVE 1010.0000 1000.0000 ; JZ Function: 0000.0000 ; CONST TWO 0100.0000 0110.0000 ; GET 0000.0000 ; CONST FOUR 0010.0000 0001.0000 ; READ 0000.0000 ; CONST ZERO 0000.0000 0000.0000 ; CONST FOUR 0010.0000 1001.0000 ; WRITE 1011.0000 ; ADD 0000.0000 ; CONST THREE 1100.0000 1110.0000 ; SET 1100.0000 ; RET
The language, although lacking formal proof, is probably Turing complete. Using instructions
read/write program can read its own source code, then write to a new location (use much larger
n initially, so the program can access enough space), then use shifting instructions to properly align instructions at the new memory location and prepare for increasing
n must be changed, but it also affects how the rest of memory is interpreted (increasing
n by 1 will implicitly divide PTR by 2). It means that after we copy expanded source code and align it properly, we need to prepare IP and SP that will be located on
PTR/2 and then increase
n by 1. If this is feasible and if the program can properly recover from this situation (and if it can be done for any
n), then it probably means it's Turing complete.