Woodchuck

From Esolang
Jump to navigation Jump to search

Woodchuck is a brainfuck derivative by User:Rdococ.

Introduction

Woodchuck is a brainfuck derivative that operates on a binary tree. The tree is finite, but can grow without bounds. The nodes of the tree do not hold values. Instead, programs must encode values into the structure of the tree itself by creating and destroying tree nodes.

Instructions

Instruction Action
< Traverses down the left branch from the current node, creating a new node if none exists there.
> Traverses down the right branch, creating a new node if none exists.
^ Traverses back up to the parent node.
% Destroys the current node and all of its descendants, and traverses back up.
[...] Runs the code within the brackets while both the left and right branches exist.
+ 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
+ >>[>]>^<^[^]^
- >>[>]%<%^[^]^
< ^
> <
. >>[>+].^[^]^
[ >>[^^
] >>]^^
Woodchuck BF tree.png

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

An implementation of Woodchuck is available here.