# Forest

Paradigm(s) Imperative User:Hakerh400 2021 Turing complete Interpreter `.txt`

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

```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
```

```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
```

### 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
```