Woodchuck
Woodchuck is a brainfuck derivative by User:Rdococ. Instead of the memory model being an infinite tape of numbers, it is an unlabelled binary tree.
Instructions
| Instruction | Action |
|---|---|
< |
Traverses the left branch. If there's no node, a new one is created. |
> |
Traverses the right branch. If there's no node, a new one is created. |
^ |
Traverses up to the parent node. |
% |
Destroys the current node and all of its descendants, traversing back up. |
[...] |
Runs the code within the brackets while both the left and right branches have nodes. |
+ |
Increments the accumulator. |
. |
Outputs the ASCII character corresponding to the accumulator's value and resets the accumulator to 0. |
Translation from BF
A translation from non-wrapping, unbounded brainfuck to woodchuck is as follows:
| brainfuck | woodchuck |
|---|---|
+ |
>>[>]>^<^[^]^
|
- |
>>[>]%<%^[^]^
|
< |
^
|
> |
<
|
. |
>>[>+].^[^]^
|
[ |
>>[^^
|
] |
>>]^^
|
On the right is the result of compiling +->+>+++>++<<< to Woodchuck and then running it. The red edges represent left edges, and the blue edges represent right edges.
A green node represents an unbounded bf cell. Going right takes you to its 'zero node', which always has a branch missing and serves as a stopping point for the incrementing, decrementing and looping constructs. Going right again is a chain of nodes, all of which have both branches.
The increment and decrement instructions are converted into code that continually follows this chain until it finds the last node, and either destroys it to shorten the chain and decrement the cell, or adds more branches to lengthen the chain and increment the cell. Then, it finds its way back up the chain, stopping when it reaches the zero node.
Loops are converted into code that only checks the start of the chain, as any positive cell will have both branches there, while a zero cell does not.
This translation is very slow, turning basic instructions into time-consuming scans across value chains. Far better performance could be gained by writing programs directly in Woodchuck, or possibly with a smarter translation algorithm that uses binary rather than unary to store cell values.
Implementation
A (maybe working) implementation of woodchuck is available here.