# 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

In any language it is important to be able to construct arbitrary conditionals.

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"). This value may be replaced by n in preparation for another test by extending the idiom as follows:

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

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>)------(/)
```

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 reference implementation of Burro 2.0 contains 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 is too limited -- it performs a destructive test which cannot be nested (because after the value has been tested it cannot be tested again). Thus the most complex Turing machine one could write using it would be a 2-state, 2-symbol Turing machine. The author is hoping to rewrite the description of the conversion process as a compiler in Haskell which generates the conditional idiom given above.