Burro

Burro is a brainfuck-like language, the set of whose programs form an algebraic group under the operation of concatenation and over the equivalence relation "computes the same function". Burro was designed by Chris Pressey between 2005 and 2007, and revised in 2010.

The fact that Burro programs form an algebraic group means that every program has an inverse that, when concatenated with it, results in a nop. This is a form of reversible computing.

Language overview

This section describes Burro 2.0, the revision published in 2010.

Each of the symbols e, !, +, -, <, and > are Burro programs, as are the constructions (a/b) and ab, where a and b are Burro programs. Anything not constructed from this definition is not a Burro program.

Program state consists of two tapes, a data tape and a stack tape (each unbounded on left and right), and a Boolean halt flag, initially 1 (for true). Each tape cell holds an integer value, initially 0, which is unbounded and can be positive or negative. The commands (and constructions) work as follows:

Command	Inverse	Description
e	e	Do nothing; nop.
!	!	Toggle halt flag.
+	-	Increment value under tape head on data tape.
-	+	Decrement value under tape head on data tape.
<	>	Move data tape head one cell left.
>	<	Move data tape head one cell right.
(a/b)	(b'/a')	Conditional construct (see below).
ab	b'a'	Effect of executing a followed by b.

The inverses are given on the assumption that a and b are Burro programs, and that their inverses are a' and b' respectively.

The conditional construct (a/b) works as follows:

1. The value of the current cell on the data tape is saved (as x, let's say) while this construct is run.
2. The current data cell and stack cell are swapped.
3. The current stack cell is negated.
4. The stack tape's head moves one cell to the right.
5. With this starting state, a is executed if x > 0; b is executed if x < 0; nothing is done if x = 0.
6. The stack tape's head moves one cell to the left.
7. The current data cell and stack cell are again swapped.

When the end of the code is reached, if the halt flag is still 1, the program halts. Otherwise, the code is executed again from the beginning (without resetting program state).

Constructing Conditionals

It is often valuable for a language to support the expression of arbitrary conditional statements.

With the (a/b), if a and b has the same amount of > as < and data pointer's value where the pointer starts before the conditional is unchanged by a and b then, the space under the pointer will be set to its negative.

Because of this, (e/e) will just negate the data under the pointer.

(e/e)(b/a) removes the negating effect of the condition.

x = 0 can be achieved by using (a'/a')a, a must start at the conditional's start

x >= 0 with (e/a')a, a must start at the conditional's start

x <= 0 with (a'/e)a, a must start at the conditional's start

All the rest of the comparing conditionals can be done by starting with a sequence of - with the same number of + afterwards or a sequence of + with the same number if - afterwards

Extensible Idiom for Conditionals

The following basic idiom can be used to perform simple tests on the assumption that only odd values will be tested.

--(G>/L>)<

Call the value in the current tape cell n. This will execute G if n > 2 or will execute L if n < 2.

Both G and L will see a zero in the current tape cell when they start executing (it came from the stack tape). Both G and L can move around and modify several parts of the tape, but they should return to where they started. Neither G nor L has access to the original value being tested against while executing.

After the conditional is finished, 2 - n will be written into the cell to the right of the current cell (which we will call the "scratch cell"). Because 2 - (2 - n) = n, we may, by repeating the gymnastics that got us 2 - n, replace the value in the scratch cell with n:

--(G>/L>)--(/)

This prepares us to make another test against n, as long as we account for the fact the n is now stored in one cell to the right of where it originally was.

The idiom can also be extended to branch on greater or less than 4, 6 and so forth, in a straightforward manner:

----(G>/L>)----(/)

------(G>/L>)------(/)

It is not practical to nest these conditionals (the n being tested is not available inside them) so to test a value against multiple cases it is necessary to chain these conditionals together. However these tests are only for greater or less than, not equality. The value 5, for example, is greater than 2, and also greater than 4. So it will cause the G branch to be taken on multiple conditionals in the chain.

One effective way to deal with this is to have each conditional test for a larger value, and to undo the effect of the previous conditional.

We must also remember that each successive test happens one cell to the right of the previous test (the cell being tested is the scratch cell of the previous test). So we may have to wrap the contents of the conditional with < and > one or more times, if we want all the conditionals to operate on the same cell.

For example, say the current tape cell is assumed to hold either 1, 3, or 5. We want to do the following: if it's 1, write 9; if it's 3, write 13; or if it's 5, write 7. We can write:

(
    +++++++++
>/
>)(/)
--(
    <
    ---------
    +++++++++++++
    >
>/
>)--(/)
----(
    <<
    -------------
    +++++++
    >>
>/
>)----(/)<<<

Significance

Chris Pressey's documentation for version 2.0 contains a proof that every Burro program has an inverse, or "annihilator", such that the concatenation of a program and its annihilator results in a nop. This is the most important of four properties (the other three being fairly trivial) required to prove the "central theorem of Burro": "The set of all Burro programs forms a group over computational equivalence under the operation of concatenation."

Computational class

The documentation accompanying the reference implementation of Burro 2.0 originally contained a sketch of how one could convert an arbitrary Turing machine to a Burro program. However, the idiom for the conditional used in that conversion performs a destructive test which cannot be nested (because after the value has been tested it cannot be tested again), limiting it to simulating at most a 2-state, 2-symbol Turing machine.

The author is hoping to find the time to rewrite the description of the conversion process using the conditional idiom given above, allowing it to simulate Turing machines with an arbitrary number of states and/or symbols, which would show that Burro 2.0 is Turing-complete.

See also

• Cabra, a followup which attempted to have its set of programs form an algebraic ring
• Revaver2pi, which is also believed by its author to form a group

External resources

• Burro project at Cat's Eye Technologies