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.

This saga is continued in the Kondey tests.