User:Rainwave/Drafts/Treplace

This is still a work in progress. It may be changed in the future.

Treplace is a tree-based esoteric programming language, a computational model, and an OISC created by User:Rainwave in 2026. The language's name is a combination of "tree" and "replace".

Semantics

The language operates on a binary tree where each node contains no other features other than its edges. There's no way to programmatically initialize the initial tree shape. Instead, the initial tree always has the following shape

   ( )
   / \
  /   \
( )   ( )

This shape is often called a cherry graph. In this page, we will refer to such a shape as "cherry" for short.

The program consists of a list of instructions which are executed in an implicit loop. There's only one kind of instruction, making Treplace a One Instruction Set Computer (OISC). Each instruction replaces a subtree with a copy of another subtree and is written as follows

subtree_dest = subtree_src

Here, subtree_dest and subtree_src identify two subtrees using subtree selector. In effect, the instruction replaces subtree_dest with a copy of subtree_src.

A subtree selector identifies a subtree using a path from the tree's root to the root of the subtree. The path starts from the root node, which is denoted with a *. Following that is a sequence of l and r, denoting that the path continues through the left child (l) or right child (r) of the current node. Whichever node the path stops at is the root of the selected subtree. The * may be omitted from the selector unless the selector targets the root node itself.

If at least one of the two subtrees in an instruction is invalid, the whole instruction fails and has no effect. A subtree is invalid when the path that identifies it goes through a nonexistent node.

The execution halts when the whole tree shrinks to just one node.

Examples

We'll use brackets notation to make tree illustrations more compact. Leaf nodes are written as () and non-leaf nodes are written as (xy). Therefore, the initial tree can be written as

(()())

Looping counter

Let's represent a number using the following encoding:

• A single node () represents the number 0.
• Larger numbers can be constructed in a similar fashion as Church numerals. (x()) is the successor of x. In other words, (x()) is the number that comes after x in our encoding scheme.

The following program increments the number by +1 every cycle

l = *

Addition (A + B)

Let's consider the following tree

((AB)(((()())(()()))C))

Here, A and B represent two numbers using the same encoding we used in the previous example. The following program calculates the sum of A and B and stores it in C.

rlr  = lrr
rlrl = ll
rlll = ll
ll   = rll
rlll = rllr
ll   = rlrl
lr   = lrl
rr   = ll
rlr  = rll

Although this program does not halt, it correctly stores the result in C, which we can inspect after running the program for sufficiently many cycles.

Constructing arbitrary initial trees

Since the initial tree is fixed to have a certain shape, it would be convenient to have a method that can systematically construct any initial tree that we want. The problem with Treplace is that the whole program runs in an implicit loop. Therefore, our tree initialization logic should only have an effect in the first cycle of the execution and should not interfere on later cycles.

To do this, we'll use a section of the tree as the working tree. Unlike the (actual) tree, the working tree can have any initial shape that we want, as long as there's no node with only 1 child. Although the working tree is technically a subtree, it makes sense to treat the working tree as some sort of virtual tree. This is because beyond the setup code, the main logic of the program will only consider nodes inside the working tree.

We'll use the following tree layout

((T())(t(()())))

where T is the working tree and t is a subtree used to temporarily save the state of T. Translating instructions that act on the virtual working tree into instructions that act on the actual tree can be done by prefixing all selectors with ll.

This is the base form of the layout, which contains the root of the working tree and the right branch which is used for initialization.

((()())(()(()())))

Constructing this base form can be done with the following code

l    = *
r    = *
rr   = *
rrl  = lr
rrr  = lr
rl   = lr

Using this base form, we can then initialize our working tree by incrementally replacing a leaf node with a cherry. Here, rr acts as a guaranteed source of cherries. For example, the working tree ((()(()()))(()())) can be constructed with the following code

ll   = rr
lll  = rr
llr  = rr
lllr = rr

Then, we need to save and load the working tree, otherwise the working tree will get overwritten on the next cycle by the initialization logic. To do that, we need to modify the initialization code by copying the working tree back and forth between ll and rl before an instruction that would otherwise overwrite the working tree.

rl  = ll
l   = *
ll  = rl
r   = *
rr  = *
rl  = lr
lr  = rlrl
ll  = lr
rrl = lr
rrr = lr
[working tree initialization code]
ll  = rll
rl  = lr

This achieves the desired outcome of an initialization logic that only has an effect on the first cycle of the program while leaving the working tree intact on subsequent cycles.

Computational class

Treplace is Turing complete as it can simulate The Exasperation Machine.

We'll use the following working tree layout

(((LF)R)((()(()()))(()())))

where F is the current cell (focus), L is a linked-list containing the cells to the left of the current cell and R is a linked-list containing the cells to the right of the current cell. This technique, where we represent a tape by keeping track of two lists and a single focus is known as a zipper.

Each TEM cell is represented like this:

• 0-cell: (x(()()))
• 1-cell: (x())

where x is the next cell in the linked-list if the cell belongs to either the left or right linked-list. If the cell is the focus, then x should be a leaf node instead.

Note that TEM requires an infinite tape, which we can't directly construct as the tree size is strictly finite. Instead, we'll expand the tape whenever our focus goes beyond the tape's boundaries. With this, the simplest choice for the initial working tree is setting L, F, and R to a single leaf node (), which creates the following initial working tree

(((()())())((()(()()))(()())))

We can then map each TEM instruction as follows:

TEM Instruction	Mapping
1	llrr = rrr
0	llrr = rr
<	rll = lr lr = llr lrl = rll llr = lll llrl = rrr lll = llll
>	rll = lll lll = llr llll = rll llr = lr llrl = rrr lr = lrl
\	rlrl = l rll = rlrlr rlrlr = rlrllr rlrlrl = rll rlrllr = rlrlll rlrllrl = rrr rlrlll = rlrllll rlr = llrrr l = rlrl rlr = rr
/	rlrl = l rll = rlrlll rlrlll = rlrllr rlrllll = rll rlrllr = rlrlr rlrllrl = rrr rlrlr = rlrlrl rlr = llrrr l = rlrl rlr = rr

Before each TEM instruction, we'll add the following code which will create a new 0-cell whenever we're out of the tape's boundary

rlrl  = rr
rlrlr = rr
rlrlr = llrr
llr   = rlrl
rlrl  = rrr

See also

• The Exasperation Machine
• Leafuck
• Lambda calculus