Leaf: A Tree Based Turing Tarpit

Tutorial

Children

Leaf is a Tree Based Turing Tar Pit. The only datastructure is one binary tree and a number of operations to manipulate trees. Let's jump right in with the interpreter.

+ creates a left child and * creates a right child. Try it out by pressing Step below:

As you can see, the interpreter displays what is happening on the right - first a left hand child is made (helpfully coloured green) then a right one (coloured orange). Run will go through until the program finishes.

Movement

> will move to the right child and < will move to the left child. If there are no children it will stay where it is. ^ will ascent to the parent, if one exists. Note the node marked green is the currently selected node.

Deletion

The - character removes the currently selected node and all it's children. The topmost node cannot be deleted.

Loops

To make a loop, enclose some instructions in ( and ), ie (+^). The instructions inside the loop are executed and the condition is the last instruction (analogous to a do-while loop)

• Movement instructions ie < > ^ will fail if there is no child/parent to move to.
• + and * will always succeed. - will fail if it is the topmost node

For example, (^) will move up to each parent until the topmost, (>) will move to the rightmost child each iteration until it is at the rightmost node in the current subtree and similarly for (<) but to the left.

The example below makes a string of right children then goes back to the top, descends via the right children and adds a left child to each node.

Rebasing

The { sets the current root node (coloured purple on the visulisation) and } sets it back to what it was. This means you can make program fragments work on only parts of the tree, enabling operation like addition and multiplication.

We do the same example as previously except that we rebase onto the third node down, preventing the ones below it from being changed.

Conditional

? will break out of a loop (ie advance to the properly nested '(' character) if the current selected node is the current root node. It sees if you are the top of the tree, if you are it breaks out the loop. We can make a simple test to see if a left node:

Numerals

We can encode a number n as a numeral by having a tree with n nodes, all right children. Ie we can encode 4 as:

Numerals

Using this, we can define addition as taking a numeral n on the right subtree and a numeral m on the left subtree and leaving a numeral (n+m):

Lists

Lists are similar to numerals - we use a numeral as a 'backbone' and 'hand' other things off each node's left subtree. The encoding of the list [0,1,2,3]:

Playground

See here for a large playground to play with leaf