Burro Tests

Here are some test cases that can serve as a check that an implementation of Burro (that is, Burro 2.x) is not grossly broken.

In fact, this test suite was not produced as a comprehensive test of all Burro semantics; it was produced as a side-effect of a search for an extensible idiom for conditionals in Burro, which in turn was in pursuit of defining a translation from Turing machines to Burro programs, in order to prove that Burro is Turing-complete. Taking this into account may help one understand why this test suite is written in the way that it is.

These tests are written in Falderal format. Each indented code block (generally preceded by a description) represents a test. All the lines of the code block up until the ===> line give the input to be tested; the text after ===> gives the expected output. ???> gives an expected error message, which is permitted to be a partial (substring) match.

Idiom for conditional execution

-> Tests for functionality "Run Burro Program"

-> Functionality "Run Burro Program" is implemented by
-> shell command "bin/burro run %(test-body-file)"

The basic idiom is the following

--(GT>/LT>)<

Call the number in the current cell of the tape n. We will assume n is odd. If n is greater than 2, GT is executed; if n is less than 2, LT is executed. Both GT and LT may modify the current cell to whatever they want (although note that it will not contain n initially - it will be zero initially). They may also move around and modify other parts of the tape. They should however return the tape head to the position it started in. (See below for what happens when we violate that constraint.)

In both GT and LT, a "work value" is written in the cell to the right of the current cell. This "work value" is 2 - n.

Try it with -3:

---
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [4] 5 ...), stack=(... [0] ...), halt=True }

Try it with -1:

-
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [4] 3 ...), stack=(... [0] ...), halt=True }

Try it with 1:

+
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [4] 1 ...), stack=(... [0] ...), halt=True }

Try it with 3:

+++
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [2] -1 ...), stack=(... [0] ...), halt=True }

Try it with 5:

+++++
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [2] -3 ...), stack=(... [0] ...), halt=True }

Try it with 7:

+++++++
--(
    ++
>/
    ++++
>)<
===> State{ tape=(... [2] -5 ...), stack=(... [0] ...), halt=True }

Note also that the work value is not available to us inside the branch, because it's on the stack, not on the tape. A trace makes this more obvious.

-> Tests for functionality "Trace Burro Program"

-> Functionality "Trace Burro Program" is implemented by
-> shell command "bin/burro debug %(test-body-file)"

+
--(
    ++
>/
    ++++
>)<
===> +--(++>/++++>)<
===> ... [0] ...         (... [0] ...)        [H] +
===> ... [1] ...         (... [0] ...)        [H] -
===> ... [0] ...         (... [0] ...)        [H] -
===> ... [-1] ...        (... [0] ...)        [H] (++>/++++>)
===> ... [0] ...         (... 1 [0] ...)      [H] [else] ++++>
===> ... [0] ...         (... 1 [0] ...)      [H] [else] +
===> ... [1] ...         (... 1 [0] ...)      [H] [else] +
===> ... [2] ...         (... 1 [0] ...)      [H] [else] +
===> ... [3] ...         (... 1 [0] ...)      [H] [else] +
===> ... [4] ...         (... 1 [0] ...)      [H] [else] >
===> ... 4 [1] ...       (... [0] ...)        [H] <
===> ::: HALT :::
===> ()

+++++
--(
    ++
>/
    ++++
>)<
===> +++++--(++>/++++>)<
===> ... [0] ...         (... [0] ...)        [H] +
===> ... [1] ...         (... [0] ...)        [H] +
===> ... [2] ...         (... [0] ...)        [H] +
===> ... [3] ...         (... [0] ...)        [H] +
===> ... [4] ...         (... [0] ...)        [H] +
===> ... [5] ...         (... [0] ...)        [H] -
===> ... [4] ...         (... [0] ...)        [H] -
===> ... [3] ...         (... [0] ...)        [H] (++>/++++>)
===> ... [0] ...         (... -3 [0] ...)     [H] [then] ++>
===> ... [0] ...         (... -3 [0] ...)     [H] [then] +
===> ... [1] ...         (... -3 [0] ...)     [H] [then] +
===> ... [2] ...         (... -3 [0] ...)     [H] [then] >
===> ... 2 [-3] ...      (... [0] ...)        [H] <
===> ::: HALT :::
===> ()

But it is available to us after the branch, so we can make another test.

The complication is that the value changed. But, at least the change is not because of the contents of GT or LT. We always know what the value changed to. In the case of testing against 1, it changed to 2 - n.

And in fact, because 2 - (2 - n) = n, we ought to be able to change it back, just by doing the same thing we just did, again.

-> Tests for functionality "Run Burro Program"

Try it with 1:

+
--(
    ++
>/
    ++++
>)--(/)<
===> State{ tape=(... [4] 1 ...), stack=(... [0] ...), halt=True }

Try it with 3:

+++
--(
    ++
>/
    ++++
>)--(/)<
===> State{ tape=(... [2] 3 ...), stack=(... [0] ...), halt=True }

Try it with 5:

+++++
--(
    ++
>/
    ++++
>)--(/)<
===> State{ tape=(... [2] 5 ...), stack=(... [0] ...), halt=True }

As you can see, after the test, the contents of the current tape cell are the same as the value we originally tested against.

But once we've tested a value against 1, it's unlikely that we'll want to do that again. What about the case of testing against other numbers? Consider the following:

----(GT>/LT>)----(/)<

Now, if n is greater than 4, GT is executed; if n is less than 4, LT is executed. And again, we end up with a work value in the cell to the right, but this time it's 4 - n, but again we reverse it to obtain the original value we tested against.

Try it with 3:

+++
----(
    ++
>/
    ++++
>)----(/)<
===> State{ tape=(... [4] 3 ...), stack=(... [0] ...), halt=True }

Try it with 5:

+++++
----(
    ++
>/
    ++++
>)----(/)<
===> State{ tape=(... [2] 5 ...), stack=(... [0] ...), halt=True }

The next step will be combining these conditionals so that we can build a test that tests for multiple cases.

We've already noted that the original value being tested against isn't available inside the conditional -- it's "hiding" on the stack during that period.

This rules out being able to test multiple cases by nesting conditionals. So instead of nesting conditionals, we'll chain them one after another.

But there are some implications for this, when it's combined with the fact that we don't have conditional tests for equality, only tests for greater than and less then.

We'll revert to a more conventional syntax to try to devise how we can overcome those implications.

Say the value to be tested is either 1, 3, or 5, and say we want to execute a if it's 1, b if it's 3, or c if it's 5. We could try to write our chain like this:

if value > 0:
    A
endif
if value > 2:
    B
endif
if value > 4:
    C
endif

The problem is that A, B, and C don't match up exactly to a, b, and c. Instead we have:

• If value is 1 then A is executed.
• If value is 3 then A is executed then B is executed.
• If value is 5 then A then B then C is executed.

But we can overcome this by defining what A, B, and C are, in terms of a, b, and c, and code that undoes a, b, and c. Using the notation x′ to mean code that undoes x, we can choose the following equations:

• A = a
• B = a′ b
• C = b′ c

And we can restate the scenario like

• If value is 1 then a is executed.
• If value is 3 then a is executed then a′ b is executed.
  • a a′ b = b, so in effect, only b is executed.
• If value is 5 then a then a′ b then b′ c is executed.
  • a a′ b b′ c = c, so in effect, only c is executed.

We must also remember that each successive test happens one cell to the right of the previous test (the cell being tested is the work 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.

So it looks like the idiom works out. Let's write out some test cases to check that it actually does.

Again we say the value to be tested is either 1, 3, or 5, and say we want to write 9 if it's 1, write 13 if it's 3, or write 7 if it's 5.

The first part of this will be:

(
    +++++++++
>/
>)(/)

The second part will be

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

The third part will be

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

Put it all together and try it with 1:

+
(
    +++++++++
>/
>)(/)
--(
    <
    ---------
    +++++++++++++
    >
>/
>)--(/)
----(
    <<
    -------------
    +++++++
    >>
>/
>)----(/)<<<
===> State{ tape=(... [9] 0 0 1 ...), stack=(... [0] ...), halt=True }

Try it with 3:

+++
(
    +++++++++
>/
>)(/)
--(
    <
    ---------
    +++++++++++++
    >
>/
>)--(/)
----(
    <<
    -------------
    +++++++
    >>
>/
>)----(/)<<<
===> State{ tape=(... [13] 0 0 3 ...), stack=(... [0] ...), halt=True }

Try it with 5:

+++++
(
    +++++++++
>/
>)(/)
--(
    <
    ---------
    +++++++++++++
    >
>/
>)--(/)
----(
    <<
    -------------
    +++++++
    >>
>/
>)----(/)<<<
===> State{ tape=(... [7] 0 0 5 ...), stack=(... [0] ...), halt=True }

Using and Re-using the Idiom

In the context of using this conditional idiom in a Turing machine simulator:

The construction above can be used to rewrite the value on the tape at one spot. But to do so, it needs several "scratch cells" adjacent to the tape cell - one for each conditional test. With a defined tape encoding, this is not difficult. However, the contents of these cells do matter. We leave the original value being tested in the rightmost one, for example. We will need to clean up after ourselves and ensure that we have fresh scratch cells for the next go 'round.

I think that's as straightforward as subtracting the original test value from the final value of the "current cell" before we move off of it.

+++++
(
    +++++++++
>/
>)(/)
--(
    <
    ---------
    +++++++++++++
    >
>/
>)--(/)
----(
    <<
    -------------
    +++++++
    >>
>/
>)----(/)-----<<<
===> State{ tape=(... [7] ...), stack=(... [0] ...), halt=True }

Multiple instances of this value-rewriting construction must also appear. This is because the rules for rewriting a tape cell are different in every state. We need to be able to select which value-rewriting construction to use.

We don't see why we can't re-use the principle we've already established, to create this selector construction. As we noted, if we have a sequence of greater-than comparisons, we account for the overlapping execution of multiple blocks by having each block undo the previous block (if any):

if stateId > 0:
    a
endif
if stateId > 2:
    a′ b
endif
if stateId > 4:
    b′ c
endif

The main complication here is that to obtain the inverses here, we must do a lot more than just swap +'s and -'s. The construction that we want to invert, is itself a large structure of multiple conditionals.

That is no problem in principle, because every Burro program has an inverse, which can be obtained in a straightforward manner. However, obtaining and maintaining these inverses by hand would be tiresome and error-prone. So it would be beneficial to have them be machine-generated.

Kondey

To that end, a facility to generate these conditional structures has been implemented. In fact, a mini-language for describing these structures, Kondey, has been defined, and we have implemented a compiler from Kondey to Burro.

-> Tests for functionality "Compile Kondey Program"

-> Functionality "Compile Kondey Program" is implemented by
-> shell command "bin/burro compile-kondey %(test-body-file)"

Kondey is a proper superset of Burro. Every Burro program is a Kondey program, but not vice versa.

Kondey adds a conditional structure to Burro, which looks like this:

{.../.../...}

where each ... is a Kondey subprogram, i.e. it is a /-delimited list of Kodey subprograms written inside curly braces. This conditional form maps to a Burro conditional structure following this pattern:

• if the current cell is greater than 0, then execute the 1st fragment
• if the current cell is greater than 2, then undo the 1st fragment and execute the 2nd fragment
• if the current cell is greater than 4, then undo the 2nd fragment and execute the 3rd fragment

So, we can rewrite the conditional structure shown in the "Notes" section above in a more concise and readable (such as it is) fashion:

+++++
{
    +++++++++
    /
    +++++++++++++
    /
    +++++++
}
-----<<<
===> +++++(+++++++++>/>)(/)--(<---------+++++++++++++>>/>)--(/)----(<<-------------+++++++>>>/>)----(/)-----<<<

Once the Kondey program has been compiled to Burro, we can run the Burro, to further confirm the behaviour is what we expect.

-> Tests for functionality "Compile and Run Kondey Program"

-> Functionality "Compile and Run Kondey Program" is implemented by
-> shell command "bin/burro run-kondey %(test-body-file)"

+++++
{
    +++++++++
    /
    +++++++++++++
    /
    +++++++
}
-----<<<
===> State{ tape=(... [7] ...), stack=(... [0] ...), halt=True }

-> Tests for functionality "Compile Kondey Program"

Kondey conditional forms can be nested. That was, kind of, the whole point of definition Kondey; without some syntax and some automatic translation, we would need to write these things by hand in Burro, and that's horrible and we wanted to avoid that.

{
    +++++++++
    /
    >>>>>
    {
        +
        /
        ++
    }
    <<<<<
    /
    +++++++
}
===> (+++++++++>/>)(/)--(<--------->>>>>(+>/>)(/)--(<-++>>/>)--(/)<<<<<>>/>)--(/)----(<<>>>>>(/)++(</<<--+>)++(/)(</<-)<<<<<+++++++>>>/>)----(/)

Exiting a Conditional with the Tape Head at a Different Spot

It will be useful if we can have the tape head move conditionally, that is, different branches of a conditional leave the tape head at different spots.

The conditional idiom was not designed with this in mind, so there is some doubt that it supports it.

What happens if we try, with the basic conditional?

-> Tests for functionality "Run Burro Program"

Try it with 1:

+
--(
    ++>>>>++++++++
>/
    ++++
>)--(/)<
===> State{ tape=(... [4] 1 ...), stack=(... [0] ...), halt=True }

Try it with 3:

+++
--(
    ++>>>>++++++++
>/
    ++++
>)<
===> State{ tape=(... 2 0 0 0 [8] -1 ...), stack=(... [0] ...), halt=True }

So this seems harmless enough on its own. But will it combine well with the cascading-and-successively-undoing nature of the extensible conditional idiom? There's one way to find out...

-> Tests for functionality "Compile and Run Kondey Program"

Try it with 1:

+
{
    +++++++++
    /
    +++++++++++++>>>>+++
    /
    +++++++
}
-----<<<
===> State{ tape=(... [9] 0 0 -4 ...), stack=(... [0] ...), halt=True }

Try it with 3:

+++
{
    +++++++++
    /
    +++++++++++++>>>>+++
    /
    +++++++
}
-----<<<
===> State{ tape=(... 13 0 0 0 [3] 0 0 -2 ...), stack=(... [0] ...), halt=True }

Try it with 5:

+++++
{
    +++++++++
    /
    +++++++++++++>>>>+++
    /
    +++++++
}
-----<<<
===> State{ tape=(... [7] ...), stack=(... [0] ...), halt=True }

So... this works? It leaves different junk in the temporary cells, but since we don't care about the contents of those cells (pretty sure we don't), this... might be sufficient?

Translating Turing machines to Kondey

The next step is to show how we can translate an arbitrary Turing machine to a Kondey program. Our Kondey program will consist of one big loop (as befitting Burro's approach to control flow), and each iteration of that loop will simulate processing one step of the Turing machine.

As mentioned (obliquely) above, each cell on the Turing machine's tape is represented by a sequence of adjacent cells on the Burro tape. We treat this sequence like a data record, and call it a CellStruct. A CellStruct must consist of at least:

• state, the TM state stored locally, represented as an even integer
• tmps_1..tmps_n, n scratch cells for executing the conditional
• cell, the symbol written at position on the TM tape, also represented as an even integer
• tmpc_1..tmpc_m, another m scratch cells for executing the inner conditional

n in the above is the number of states of the TM, while m is the number of possible symbols in a tape cell. k = n + m + 2 Burro tape cells are needed to store each CellStruct, and the TM instruction "Move Right" is a sequence of k > instructions, while the TM instruction "Move Left" is a sequence of k < instructions.

Within the same CellStruct, moving from the state cell to the cell cell uses n + 1 > instructions - and suchlike for other internal moves.

For convenience we will also refer to the start of a CellStruct, which is the Burro cell containing the first field, which also happens to be state.

The set of TM states is finite, as is the set of symbols that can appear on cells of the TM tape. This will allow us to work with these values with finite program structures which do not contain loops.

At any point there is a current CellStruct. This is indicated by where the current Burro tape cell is. Whichever CellStruct it is inside, is the current CellStruct.

The TM state exists locally in the current CellStruct, so that we may execute a conditional branch on it. But when we move to a new CellStruct, we need to copy the current state to that new cell, as it will not have the correct value. In fact, we can be more accurate and, noting that when we move to a new cell we also move to a new TM state, we need only write the new TM state into the new current CellStruct.

Because the initial Burro tape consists entirely of zero-valued cells, it behooves us to represent a blank CellStruct as a sequence of four zero-valued Burro cells, so that we do not need to detect and initialize blank cells when we first encounter them. And this would in turn imply that the Turing machine must start in state 0 in our representation, and that blank Turing machine cells are represented by 0 cells in our representation.

However, this runs up against a problem in the simulation, namely, that our conditional idiom works on odd values only.

We can address this by storing the Turing machine cells as even numbers on the Burro tape, but bumping up the contents of the Burro tape by one (+) whenever we move to a new CellStruct, to ensure that they are odd when we perform tests on them, and bumping them back down (-) when leaving the CellStruct. This gives us a tape that is (virtually) filled with 1's initially. We need to do this even-to-odd-and-back adjustment for both the tape contents and the state kept locally in the CellStruct.

Another problem this runs up against is that we do want to be able to, in a conditional, leave the tape in a different place than we started; we want to move left or right on the simulated tape. The extensible conditional idiom was not designed to handle that. The tests above suggest that it does, though, so we should move forward with it, and see.

Pseudocode

while (not halted) {
    (assertion: the head is at the "state" part of the current CellStruct)
    bump up the state id by 1, to make it odd
    if state == 1 {
        move to "cell" part of current CellStruct
        bump up the cell value by 1, to make it odd
        if cell == 1 {
            write new (even) value of cell (adjust 0 using +'s)
            move to "state" part of the CellStruct
            write 0 into "state" value (using -'s)
            move left or right to adjacent CellStruct as appropriate
            (assertion: the head is at the "state" part of the new CellStruct)
            write the new (even) state id in the "state" cell.
            toggle the halt flag if the new state is "halt"
        }
        elseif cell == 3 {
            write new (even) value of cell (adjust 0 using +'s)
            move to "state" part of the CellStruct
            write 0 into "state" value (using -'s)
            move left or right to adjacent CellStruct as appropriate
            (assertion: the head is at the "state" part of the new CellStruct)
            write the new (even) state id in the "state" cell
            toggle the halt flag if the new state is "halt"
        }
        elseif cell == 5 {
            ....
        }
    }
    elseif state == 3 {
        ...
    }
    elseif state == 5 {
        ...
    }
}

In conclusion, this is the method by which we propose that arbitrary Turing machines could be translated to Kondey, and thence to Burro, thus establishing that Burro is Turing-complete. However, we defer presenting this as an actual Turing-completeness proof until such time as the method can be vetted in a more formal and/or mechanical manner.