BTree
BTree is an esoteric language invented by User:TuxCrafting where programs are formatted as binary trees.
Syntax
Programs are made of nodes, which contain one or more instruction.
Nodes are organized as abbccccdddddddd... where a is the root, b are the children of the root, the first two c are the children of the first b, and the last two are the children of the second b, etc...
Nodes are matched by the regex (;.)*. (semicolons are not included in the final tree).
Whitespace is ignored and comments are wrapped in { curly braces }.
Programs are padded with no-ops.
Semantics
There are two accumulators, A and B, and a deque. The basic data type is a balanced ternary digit.
Execution starts at the root node. All the instructions in the currently selected node are executed, and the next selected node is based on the content of the accumulator:
- -1: Left child
- 0: Parent
- 1: Right child
In case the selected node doesn't exist (child of a leaf or parent of the root), execution halts.
Instructions
| Instruction | Description |
|---|---|
0 |
Set A to 0.
|
- |
Set A to -1.
|
+ |
Set A to 1.
|
^ |
Exchange the content of A and B
|
a |
Insert the content of A at the end of the deque.
|
A |
Remove the element at the start of the deque and put it in B, or 0 if the deque is empty.
|
b |
Insert the content of A at the start of the deque.
|
B |
Remove the element at the end of the deque and put it in B, or 0 if the deque is empty.
|
& |
Set A to the minimum of A and B (ternary AND).
|
| |
Set A to the maximum of A and B (ternary OR).
|
= |
Set A to 1 if A and B are equal, else -1.
|
! |
Multiply A by -1 (ternary NOT).
|
i |
Input a ternary number (-, 0 or +) and put it in A.
|
o |
Output the content of A (-, 0 or +).
|
Any other instruction is a no-op.
Examples
Truth machine
{ BTree truth machine }
{ "-" is 0 and "+" is 1 }
;i;aA
o ;^;o;^-
. . 0
Turing-completeness
BTree is turing complete by compiling a Cyclic tag system into it. Compiler.
The way it works is by separating the productions into separate instructions, accessible through a tree. Each production is compiled to a pair of "Pop first bit and jump depending on its value" and "Push a bitstring", with the "pop" instructions addressing into a two-element jump table.