BitBounce

From Esolang
Jump to: navigation, search
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 Pust 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:

  1. 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.
  2. Calculate the new value of IP
  3. Calculate the new value of SP
  4. Calculate the result of evaluating the instruction
  5. Save the new value of IP to the location of IP
  6. If new SP is not old SP then
    1. Save new SP to the location of SP
  7. If the instruction gives result (const, call, push, get, read, neg, imp, shl, add, in) then
    1. Push the result to the stack
  8. If the instruction directly modifies memory (set, write) then
    1. 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).

Example

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

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.