Beets
The Beets programming language enables expressing calculations on infinite binary trees of bits.
Grammar
program = definition*
definition = identifier identifier* '=' expression '.'
expression = '(' expression ')' | parameter | call | tree | left-subtree | right-subtree | conditional
parameter = identifier
call = identifier expression*
tree = ('0' | '1') expression ',' expression
left-subtree = '<' expression
right-subtree = '>' expression
conditional = expression '?' expression ',' expression
Comments start with == and extend to the end of the line.
An identifier is an uninterrupted sequence of non-space characters, excluding =, ., ,, <, >, ?, (, ), and may not begin with 0 or 1.
Space characters separate identifiers and are otherwise ignored.
Expressions
Tree
Creates a new tree from a root bit, and two subtrees.
tree = ('0' | '1') expression ',' expression
For example, this tree has 1 at its head, with x as its left
subtree and y as its right subtree.
1x,y
Left subtree
The left subtree of a tree.
left-subtree = '<' expression
For example, this tree is the left subtree of t.
<t
Right subtree
The right subtree of a tree.
right-subtree = '>' expression
For example, this tree is the right subtree of t.
>t
Conditional
The conditional expression evaluates to the left expression if the
root bit of the condition evaluates to 0, otherwise it evaluates to
the right expression.
conditional = expression '?' expression ',' expression
For example, this evaluates to b.
(1x,y)?a,b
Note that without the parentheses, it is not specified whether the
condition is y or 1x,y. This document leaves the interpretation
of such ambiguous expressions to be defined by the implementation.
To avoid ambiguity, write (>a)?b,c or >(a?b,c) instead of writing
>a?b,c.
Examples
cat
cat x = x.
Hello world
(For one possible encoding scheme.)
z = 0z,z.
o rest = 1rest,z.
i rest = 1z,rest.
hello-world = o o o i o o i o i o i o o i i o o o i i o i i o o o i
i o i i o i i i i o i i o o o o o o i o o i i i o i i
i o i i i i o i i o o i o o i i i o o o i i o i i o o
o i o o i i o i o o o o i o o o i o i o o o o 1z,z.