Forest

Forest is an esolang invented by User:Hakerh400 in 2021.
== Memory ==
=== Memory model ===
Memory is an infinite binary tree. Each node has exactly two children: left and right. Each node contains a single bit (0 or 1).
Memory contains a root node. All addressing are performed relative to the root node. An address consists of zero or more bits. Each bit represents which child to choose when descending accross the tree. For example, empty address represents the root node, address 0 represents the left child of the root node, address 1 represents the right child of the root node, address 01 represents the right child of the left child of the root node.
Two subtrees are considered to be equal iff all corresponding nodes contain same bits.
=== Initial memory configuration ===
Initially, the root node contains bit 1, the left subtree of the root node contains all zeros and the right subtree contains the input (see I/O format for details).
== Syntax ==
Source code consists of instructions and labels. A label is an identifier followed by a semicolon. An instruction can be one of:
* x?y - Here x and y are addresses (arrays of bits). If the subtree at address x is equal to the subtree at address y, then continue, otherwise skip the next instruction
* x.y - Copy the subtree from address x and assign it to address y
* :lab - Jump to label lab
When executing instruction x.y, if x is the same as y (literally the same address), then do nothing. Otherwise, if x is not a prefix of y, then simply make a copy of the subtree at address x and replace the current content from address y with that. However, if x is a prefix of y (for example 10.100), then also perform the substitution in the new copy as well. This is done recursively. A corollary of this is that we can alter infinitely many bits in a single instruction.
== I/O format ==
Input and output are binary strings. To convert a binary string to a node, do the following:
* If the string is empty, return a subtree with all zeros
* Otherwise, return a node whose bit is 1, the left node is L and the right node is R, where L is a node whose bit is equal to the first bit from the binary string, and both left and right child are all-zero subtrees, while R is obtained by converting the rest of the bits to a node
The node obtained this way is initially placed at address 1 (right child of the memory's root). After program halts, the output is parsed in the same way from the same address.
== Examples ==
=== Cat program ===
Try it online
=== Reverse bits ===
 init:
 .00
 01.000
 01.001
 00.0
 0.001
 01.0010
 
 reverse:
 1?000
 :output
 
 01.0011
 001.01
 000.0011
 10.010
 11.1
 
 :reverse
 
 output:
 01.1
Try it online
=== Invert bits ===
 init:
 .00
 01.000
 01.001
 00.0
 0.001
 01.0010
 
 reverse1:
 1?000
 :afterReverse1
 
 01.0011
 001.01
 000.0011
 
 10?000
 001.010
 
 11.1
 
 :reverse1
 
 afterReverse1:
 01.1
 000.01
 
 reverse2:
 1?000
 :output
 
 01.0011
 001.01
 000.0011
 10.010
 11.1
 
 :reverse2
 
 output:
 01.1
Try it online
=== Hello, World! ===
 .00 01.000 01.001 00.0 0.001 01.0010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011
 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011
 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010
 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010
 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011
 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011
 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011
 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010
 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011
 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011
 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010
 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01 000.0011
 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010
 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011
 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011
 01.0011 001.01 000.0011 01.0011 001.01 000.0011 001.010 01.0011 001.01 000.0011 01.0011 001.01
 000.0011 01.0011 001.01 000.0011 01.1 
Try it online
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:2021
Category:Implemented