BitBounce

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
Try it online
The same program, but without comments:
 1110000001000000101000001111111110000000011100001111000001110000000000001000100001000000111100000000
 0000000000000000000010100000100000000000000001000000011000000000000000100000000100000000000000000000
 0000000000100000100100001011000000000000110000001110000011000000
Try it online
=== Cat program ===
 1110000001000000101000001111111100000000011100001111000001110000000000001000100001000000111100000000
 0000000000000000000010100000100000000000000001000000011000000000000000100000000100000000000000000000
 0000000000100000100100001011000000000000110000001110000011
Try it online
=== 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
Try it online
== 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.
== Interpreters ==
* Interpreter
Category:Languages
Category:String-rewriting_paradigm
Category:Unknown_computational_class
Category:Implemented
Category:2019