Forest

Forest

Paradigm(s)	Imperative
Designed by	User:Hakerh400
Appeared in	2021
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.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

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