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. [Falderal]: https://catseye.tc/node/Falderal 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](Kondey-Tests.md).