BitBounce
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Unknown |
| Major implementations | Interpreter |
| File extension(s) | .txt |
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).
Source code
All characters except 0 and 1 are ignored. Then 0s and 1s are concatenated to form memory.
Memory structure
Like in Bitwise Trance, memory is infinite. However, at any point in time instructions can access only limited amount of memory.
Cell size
Memory is divided into 2^n cells, where each cell is n bits long (total number of accessible bits is therefore n*2^n). Number 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 0011 (for n=4) will be interpreted as number 12.
Characteristic cells
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).
Memory transformation
Numbers 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.
Instructions
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 |
|---|---|---|---|---|
0
|
CONST | Put a constant onto the stack | 0 | Yes |
1
|
JZ | Jump to the given address if the value on the stack is 0 | 2 | No |
2
|
CALL | Call the given procedure | 1 | Yes |
3
|
RET | Return from the current procedure | 1 | No |
4
|
PUSH | Duplicate the value on the top of the stack | 0 | Yes |
5
|
POP | Pop the value from the top of the stack | 1 | No |
6
|
GET | Push value relative to the stack pointer | 1 | Yes |
7
|
SET | Modify value relative to the stack pointer | 2 | No |
8
|
READ | Read value from absolute address and push to the stack | 1 | Yes |
9
|
WRITE | Write value from the stack to the absolute address | 2 | No |
10
|
NEG | Flip all bits of the given value | 1 | Yes |
11
|
IMP | Given two numbers, calculate ~n1 | n2
|
2 | Yes |
12
|
SHL | Interpret the second argument as signed integer, based on its sign shift the first argument left or right | 2 | Yes |
13
|
ADD | Sum the two given numbers | 2 | Yes |
14
|
IN | Read a bit, pad it with 0s to fill memory cell and push to the stack | 0 | Yes |
15
|
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.
Evaluation
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
Instruction 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
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).
I/O format
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).
Examples
Flip the first bit
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 same program, but without comments:
1110000001000000101000001111111110000000011100001111000001110000000000001000100001000000111100000000 0000000000000000000010100000100000000000000001000000011000000000000000100000000100000000000000000000 0000000000100000100100001011000000000000110000001110000011000000
Cat program
1110000001000000101000001111111100000000011100001111000001110000000000001000100001000000111100000000 0000000000000000000010100000100000000000000001000000011000000000000000100000000100000000000000000000 0000000000100000100100001011000000000000110000001110000011
Hello, World!
1111000000010000000000100000001111111111000000000010000000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000001000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000000000000011110000000010000000111100000000000000000000000000 1111000000001000000011110000000000000000100000000011110000000010000000111100000000000000000000000000 11110000000010000000111100000000000000000000000000111100000000000000001111
Turing completeness
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. Then 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.