Arborealis
Arborealis is a binary-tree based esoteric language with some ties to brainfuck. The initial data structure is the root node, with a value of zero, and nothing else. The tree can be extended via certain commands, and all new nodes are initialized with a value of zero.
Instruction Set
> If the right child of the current node exists, move to it. If it does not, does nothing.
< If the left child of the current node exists, move to it. If it does not, does nothing.
( Left paradox function. See section below.
) Right paradox function. See section below.
/ If the left child of the current node does not exist, create it. Otherwise, do nothing.
\ If the right child of the current node does not exist, create it. Otherwise, do nothing.
[ If the value of the current node is 0, skip to the matching ]. Otherwise, continue execution. (BF loop)
] If the value of the current node is greater then 0, skip to the previous matching [. Otherwise, do nothing. (BF loop)
{ Set the value of the current node to 1 if the left child exists, otherwise set it to zero.
} Set the value of the current node to 1 if the right child exists, otherwise set it to zero.
+ Increment the value of the current node by 1.
- Decrement the value of the current node by 1.
! and ? Conditional Movers (left and right favoring, respectively) The following are checked in order, and the first true one is executed.
If the left (right) child does not exist, create it and move to it.
If the left (right) child does exist, and the value of the current cell is 0, move to it.
If the right (left) child does not exist, create it and move to it.
If the right (left) child does exist, and the value of the current cell is greater than 0, move to it.
~ Moves the pointer to the root node.
. and , Same as BF.
Paradox Functions
When ( or ) are used, they make the left and right child (respectively), provided it doesn't exist, of the parent node its grandfather. If the child node does exist, then this command does nothing. An illustrated example:
A / \ B C / \ \ D E F
When ( is called from the C node, the new structure looks like this:
A
/ \
B C
/ \ / \
D E A F
/ \
B C
/ \ / \
D E A F
And so on, recursively. This is because the A node is both the parent and the child of the C node. This is implemented by treating the transversal of the C node's left child as teleportation to the A node.
Implementation Specifics
All node values must be between 0 and 255, inclusive. The implementation should allow wrap-around of node values. Like in brainfuck, there is no well-defined way to handle an EOF in input. Interpreters often assign EOF the value 0 as a de facto standard.
Turing Completeness
Arborealis is Turing-complete by reduction from brainfuck. It approximates the tape with a tree in which left child of a node is the node's parent. No setup is needed, and all brainfuck commands can be used unchanged except the > command which must be replaced with \>( to grow the tape when it reaches the end.
Algorithms
Dead-End Cell Behavior
The following code snippet iterates through all right-hand children, stopping and performing the inner loop A only when a node without a right child is reached. This code relies being run on a 'tape' as constructed above.
[[(!]}-[+A]]
Cat
,[\>,]\~[.>]
A shorter, one-node version would be ,[.,] but the program above showcases the language better.