Anonymous avatar Anonymous committed 446494e

Initial import of Burro version 1.0 revision 2007.1026 sources.

Comments (0)

Files changed (9)

+<html><head><title>The Burro programming language</title></head>
+<body>
+
+<h1>Burro</h1>
+
+<p>October 2007, Chris Pressey, Cat's Eye Technologies.</p>
+
+<h2>1. Introduction</h2>
+
+<p><em>Burro</em> is a Brainfuck-like programming language whose programs form an
+algebraic group under concatenation.</p>
+
+<p>(At least, that is how I originally would have described it.  But that description
+turns out to be not entirely precise, because the technical meanings of "group" and
+"program" come into conflict.  A more precise statement would be: "Burro is
+a semi-formal programming language, the set of whose program texts, paired with the operation
+of concatenation, forms an algebraic group over a semantic equivalence relation."
+But the first version is close enough for jazz, and rolls off the tongue more easily...)</p>
+
+<p>Anyway, what does it mean?  It means that, among other things, every Burro program has
+an <em>antiprogram</em> &mdash; a series of instructions that can be appended to it
+to annihilate its behavior.  The resulting catenated program has the
+same semantics as no program at all &mdash; a "no-op," or a zero-length program.</p>
+
+<p>Why is this at all remarkable?  Well, take the Brainfuck program fragment <code>[-]+[]</code>.
+What could you append to it to it to make it into a "no-op" program?
+Evidently <em>nothing</em>, because once the interpreter enters an infinite loop, it's not
+going to care what instructions you've put after the loop.  And a program that loops forever
+isn't the same as one that does nothing at all.</p>
+
+<p>So not all Brainfuck programs have antiprograms.  Despite that, Brainfuck does embody a lot of
+symmetry. Group theory, too, is a branch of
+mathematics particularly suited to the study of symmetry.  And as you might imagine,
+there is a distinct relation between symmetrical programming languages and reversible
+programming (even though it may not be immediatly clear exactly what that relationship is.) 
+These are some of the factors that encouraged me to design Burro.</p>
+
+<h2>2. Background</h2>
+
+<p>Before explaining Burro, a short look of group theory and of the theory of
+computation would probably be helpful.</p>
+
+<h3>Group Theory</h3>
+
+<p>Recall (or go look up in an abstract algebra textbook) that a <em>group</em> is
+a pair of a set <var>S</var> and a binary operation
+&middot; : <var>S</var> &times; <var>S</var> &rarr; <var>S</var>
+that obeys the following three axioms:</p>
+
+<ul>
+
+<li>For any three elements <var>a</var>, <var>b</var>, and <var>c</var> of
+the set <var>S</var>, (<var>a</var> &middot; <var>b</var>) &middot; <var>c</var> =
+<var>a</var> &middot; (<var>b</var> &middot; <var>c</var>).  In other words,
+the operation is "associative."  Parentheses don't matter, and we generally leave them out.</li>
+
+<li>There exists some element of <var>S</var>, which we call <b>e</b>, such that
+<var>a</var> &middot; <b>e</b> = <b>e</b> &middot; <var>a</var> = <var>a</var>
+for every element <var>a</var> of <var>S</var>.  Think of
+<b>e</b> as a "neutral" element that just doesn't contribute anything.</li>
+
+<li>For every element <var>a</var> of <var>S</var> there is an element
+<var>a'</var> of <var>S</var> such that <var>a</var> &middot; <var>a'</var> = <b>e</b>.
+That is, for any element, you can find some element that "annihilates" it.</li>
+
+</ul>
+
+<p>There are lots of examples of groups &mdash; the integers under the operation of
+addition, for example, where <b>e</b> is 0, and the annihilator for any integer
+is simply its negative (because <var>x</var> + (-<var>x</var>) always equals 0.)</p>
+
+<p>There are also lots of things you can prove are true about any group
+(that is, about groups in general.) For instance, that <b>e</b> is unique: if
+<var>a</var> &middot; <var>x</var> = <var>a</var> and
+<var>a</var> &middot; <var>y</var> = <var>a</var> then
+<var>x</var> = <var>y</var> = <b>e</b>.  (This particular property will
+become relevant very soon, so keep it in mind as you read the next section.)</p>
+
+<p>The set on which a group is based can have any number of elements.  Research
+and literature in group theory often concentrates on finite groups, because these
+are in some ways more interesting, and they are useful in error-correcting
+codes and other applications.  However, the set of Burro programs is countably
+infinite, so we will be dealing with infinite groups here.</p>
+
+<h3>Theory of Computation</h3>
+
+<p>I don't need to call on a lot of theory of computation here except to point
+out one fact: for any program, there are an infinite number of equivalent programs.
+There are formal proofs of this, but they can be messy, and it's something
+that should be obvious to most programmers.  Probably the simplest example, in Brainfuck,
+is that <code>+-</code>, <code>++--</code>, <code>+++---</code>, <code>++++----</code>,
+etc., all have the same effect.</p>
+
+<p>To be specific, by "program" here I mean "program text" in a
+particular language; if we're talking about "abstract programs" in no particular
+language, then you could well say that there is only and exactly one program that
+does any one thing, it's just that there are an infinite number of concrete
+representations of it.</p>
+
+<p>This distinction becomes important with respect to treating programs
+as elements of a group, like we're doing in Burro.  Some program will
+be the neutral element <b>e</b>.  But either <em>many</em> programs will
+be equivalent to this program &mdash; in which case <b>e</b> is not unique, contrary to
+what group theory tells us &mdash; or we are talking about abstract programs
+independent of any programming language, in which case our goal of defining a particular
+language called "Burro" for this purpose seems a bit futile.</p>
+
+<p>There are a couple of ways this could be resolved.  We could foray into
+domain theory, and try to impose a group structure on the semantics of programs
+irrespective of the language they are in.  Or we could venture into representation
+theory, and see if the program texts can act as generators of the group elements.
+Both of these approaches could be interesting, but I chose an approach that I
+found to be less of a distraction, and possibly more intuitive, at the cost of
+introducing a slight variation on the notion of a group.</p>
+
+<h3>Group Theory, revisited</h3>
+
+<p>To this end, let's examine the idea of a <em>group over an equivalence relation</em>.
+All this is, really, is being specific about what constitutes "equals" in those
+group axioms I listed earlier.  In mathematics there is a well-established notion of
+an <em>equivalence relation</em> &mdash; a relationship between elements
+which paritions a set into
+disjoint equivalence classes, where every element in a class is considered
+equivalent to every other element in that same class (and inequivalent to any
+element in any other class.)</p>
+
+<p>We can easily define an equivalence relation on programs (that is,
+program texts.)  We simply say that two programs are
+equivalent if they have the same semantics: they map the same inputs to the
+same outputs, they compute the same function, they "do the same thing" as
+far as an external observer can tell, assuming he or she is unconcerned with
+performance issues. As you can imagine, this relation will be very useful for
+our purpose.</p>
+
+<p>We can also reformulate the group axioms using an equivalence relation.
+At the very least, I can't see why it should be invalid to do so.  (Indeed, this seems to
+be the general idea behind using "quotients" in abstract algebra.  In our case, we
+have a set of program texts and a "semantic" equivalence relation "are equivalent
+programs", and the quotient set is the set of all computable functions
+regardless of their concrete representation.)</p>
+
+<p>So let's go ahead and take that liberty.  The resulting algebraic structure
+should be quite similar to what we had before,
+but with the equivalence classes becoming the real "members" of the group,
+and with each class containing many individual elements which are treated
+interchangably with respect to the group axioms.</p>
+
+<p>I'll summarize the modified definition here.  A <em>group over an equivalence relation</em>
+is a triple &lang;<var>S</var>,&middot;,&equiv;&rang; where:</p>
+<ul>
+<li><var>S</var> is a set</li>
+<li>&middot; : <var>S</var> &times; <var>S</var> &rarr; <var>S</var> is a binary operation over <var>S</var></li>
+<li>&equiv; is a reflexive, transitive, and symmetrical binary relation over <var>S</var></li>
+</ul>
+<p>where the following axioms are also satisfied:</p>
+<ul>
+<li>&forall; <var>a</var>, <var>b</var>, <var>c</var> &isin; <var>S</var>: (<var>a</var> &middot; <var>b</var>) &middot; <var>c</var> &equiv;
+<var>a</var> &middot; (<var>b</var> &middot; <var>c</var>)</li>
+<li>&exist; <b>e</b> &isin; <var>S</var>: &forall; <var>a</var> &isin; <var>S</var>: <var>a</var> &middot; <b>e</b> &equiv; <b>e</b> &middot; <var>a</var> &equiv; <var>a</var></li>
+<li>&forall; <var>a</var> &isin; <var>S</var>: &exist; <var>a'</var> &isin; <var>S</var>: <var>a</var> &middot; <var>a'</var> &equiv; <b>e</b></li>
+</ul>
+
+<p>Every theorem that applies to groups should be easy to modify to be applicable
+to a group over an equivalence relation: just replace = with &equiv;.  So what
+we have, for example, is that while any given <b>e</b> itself might not be unique, the
+equivalence class <b>E</b> &sube; <var>S</var> that contains it is:
+<b>E</b> is the only equivalence class that contains
+elements like <b>e</b> and, for the purposes of the group, all of these elements are
+interchangeable.</p>
+
+<h2>3. Syntax and Semantics</h2>
+
+<h3>Five-instruction Foundation</h3>
+
+<p>Burro is intended to be Brainfuck-like, so we could start by examining which
+parts of Brainfuck are already suitable for Burro and which parts will have to
+be modified or rejected.</p>
+
+<p>First, note that Brainfuck is traditionally very lenient about what
+constitutes a "no-op" instruction.  Just about any symbol that isn't explicitly
+mentioned in the instruction set is treated as a no-op (and this behaviour turns
+out to be useful for inserting comments in programs.)  In Burro, however, we'll
+strive for better clarity by defining an explicit "no-op" instruction.  For
+consistency with the group theory side of things, we'll call it <code>e</code>.
+(Of course, we won't forget that <code>e</code> lives in an equivalence class
+with other things like <code>+-</code> and the zero-length program, and all
+of these things are semantically interchangeable.  But <code>e</code> gives
+us a nice, single-symbol, canonical program form when we want to talk about it.)</p>
+
+<p>Now let's consider the basic Brainfuck instructions <code>+</code>, <code>-</code>,
+<code>&lt;</code>, and <code>&gt;</code>.  They have a nice, symmetrical
+organization that is ideally suited to group structure, so we will adopt them
+in our putative Burro design.</p>
+
+<p>On the other hand, the instructions <code>.</code> and <code>,</code> will require
+devising some kind of annihilator for interactive input and output.  This seems
+difficult at least, and not really necessary if we're willing to forego writing
+"Hunt the Wumpus" in Burro, so we'll leave them out for now.  The only input for a
+Burro program is, instead, the initial state of the tape, and the only output is the
+final state.</p>
+
+<p>In addition, <code>[</code> and <code>]</code> will cause problems, because
+as we saw in the introduction, <code>[-]+[]</code> is an infinite loop, and it's
+not clear what we could use to annihilate it.  We'll defer this question for later
+and for the meantime leave these instructions out, too.</p>
+
+<p>What we're left in our "Burro-in-progress" is essentially a very weak subset of
+Brainfuck, with only the five instructions <code>+-&gt;&lt;e</code>.  But this is
+a starting point that we can use to see if we're on the right track.  Do the
+programs formed from strings of these instructions form a group under concatenation
+over the semantic equivalence relation?  i.e.,  Does every Burro program so far
+have an inverse?</p>
+
+<p>Let's see.  For every <i>single-instruction</i> Burro
+program, we can evidently find another Burro instruction that, when appended to
+it, "cancels it out" and makes a program with the same semantics as <code>e</code>:</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
+<tr><td align="center"><code>+</code></td><td align="center"><code>-</code></td>
+    <td align="center"><code>+-</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>-</code></td><td align="center"><code>+</code></td>
+    <td align="center"><code>-+</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>&gt;</code></td><td align="center"><code>&lt;</code></td>
+    <td align="center"><code>&gt;&lt;</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>&lt;</code></td><td align="center"><code>&gt;</code></td>
+    <td align="center"><code>&lt;&gt;</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>e</code></td><td align="center"><code>e</code></td>
+    <td align="center"><code>ee</code></td><td align="center"><code>e</code></td></tr>
+</table>
+
+<p>Note that we once again should be more explicit about our requirements than
+Brainfuck.  We need to have a tape which is infinite in both directions, or else
+<code>&lt;</code> wouldn't always be the inverse of <code>&gt;</code> (because sometimes
+it'd fail in some way like falling off the edge of the tape.)  And, so that we don't have
+to worry about overflow and all that rot,
+let's say cells can take on any unbounded negative or positive integer value, too.</p>
+
+<p>But does this hold for <em>any</em> Burro program?  We can use structural
+induction to determine this.
+Can we find inverses for every Burro program, concatenated with a given
+instruction?  (In the following table,
+<i>b</i> indicates any Burro program, and <i>b'</i> its inverse.
+Also note that <i>bb'</i> is, by definition, <code>e</code>.)</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
+<tr><td align="center"><code><i>b</i>+</code></td><td align="center"><code>-<i>b'</i></code></td>
+    <td align="center"><code><i>b</i>+-<i>b'</i></code> &equiv; <code><i>b</i>e<i>b'</i></code> &equiv; <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>b</i>-</code></td><td align="center"><code>+<i>b'</i></code></td>
+    <td align="center"><code><i>b</i>-+<i>b'</i></code> &equiv; <code><i>b</i>e<i>b'</i></code> &equiv; <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>b</i>&gt;</code></td><td align="center"><code>&lt;<i>b'</i></code></td>
+    <td align="center"><code><i>b</i>&gt;&lt;<i>b'</i></code> &equiv; <code><i>b</i>e<i>b'</i></code> &equiv; <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>b</i>&lt;</code></td><td align="center"><code>&gt;<i>b'</i></code></td>
+    <td align="center"><code><i>b</i>&lt;&gt;<i>b'</i></code> &equiv; <code><i>b</i>e<i>b'</i></code> &equiv; <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>b</i>e</code> &equiv; <code><i>b</i></code></td><td align="center"><code>e<i>b'</i></code> &equiv; <code><i>b'</i>e</code> &equiv; <code><i>b'</i></code></td>
+    <td align="center"><code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+</table>
+
+<p>Looks good.  However, this isn't an abelian group, and concatenation is definately not
+commutative.  So, to be complete, we need a table going in the other direction, too: concatenation of a
+given instruction with any Burro program.</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
+<tr><td align="center"><code>+<i>b</i></code></td><td align="center"><code><i>b'</i>-</code></td>
+    <td align="center"><code>+<i>bb'</i>-</code> &equiv; <code>+e-</code> &equiv; <code>+-</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>-<i>b</i></code></td><td align="center"><code><i>b'</i>+</code></td>
+    <td align="center"><code>-<i>bb'</i>+</code> &equiv; <code>-e+</code> &equiv; <code>-+</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>&gt;<i>b</i></code></td><td align="center"><code><i>b'</i>&lt;</code></td>
+    <td align="center"><code>&gt;<i>bb'</i>&lt;</code> &equiv; <code>&gt;e&lt; &equiv; <code>&gt;&lt;</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>&lt;<i>b</i></code></td><td align="center"><code><i>b'</i>&gt;</code></td>
+    <td align="center"><code>&lt;<i>bb'</i>&gt;</code> &equiv; <code>&lt;e&gt; &equiv; <code>&lt;&gt;</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>e<i>b</i></code> &equiv; <code><i>b</i></code></td><td align="center"><code><i>b'</i>e</code> &equiv; <code>e<i>b'</i></code> &equiv; <code><i>b'</i></code></td>
+   <td align="center"><code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+</table>
+
+<p>So far, so good, I'd say.  Now we can address to the problem of how to
+restrengthen the language so that it remains as powerful as Brainfuck.</p>
+
+<h3>Loops</h3>
+
+<p>Obviously, in order for Burro to be as capable as Brainfuck,
+we would like to see some kind of looping mechanism in it. But, as we've
+seen, Brainfuck's is insufficient for our purposes, because it allows for
+the construction of infinite loops that we can't invert by concatenation.</p>
+
+<p>We could insist that all loops be finite, but that would make
+Burro less powerful than Brainfuck &mdash; it would only be capable of expressing
+the primitive recursive functions.  The real challenge is in having Burro be Turing-complete,
+like Brainfuck.</p>
+
+<p>This situation looks dire, but there turns out to be a way.  What we
+do is borrow the trick used in languages like L00P and Version (and probably
+many others.)  We put a single, implicit loop around the whole program.
+(There is a classic formal proof that this is sufficient &mdash; the interested
+reader is referred to the paper "Kleene algebra with tests"<sup><a href="#1">1</a></sup>,
+which gives a brief history, references, and its own proof.)</p>
+
+<p>This single implicit loop will be conditional on a special flag, which
+we'll call the "halt flag", and we'll stipulate is initially set.
+If this flag is still set when the end of the program is reached, the program halts.
+But if it is unset when the end of the program is reached, the flag is reset
+and the program repeats from the beginning.  (Note that although the halt flag
+is reset, all other program state (i.e. the tape) is left alone.)</p>
+
+<p>To manipulate this flag, we introduce a new instruction:</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Semantics</th></tr>
+<tr><td align="center"><code>!</code></td><td>Toggle halt flag</td></tr>
+</table>
+
+<p>Then we check that adding this instruction to Burro's instruction set
+doesn't change the fact that Burro programs form a group:</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
+<tr><td align="center"><code>!</code></td><td align="center"><code>!</code></td>
+    <td align="center"><code>!!</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code>!<i>b</i></code></td><td align="center"><code><i>b'</i>!</code></td>
+    <td align="center"><code>!<i>bb'</i>!</code> &equiv; <code>!e!</code> &equiv; <code>!!</code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>b</i>!</code></td><td align="center"><code>!<i>b'</i></code></td>
+    <td align="center"><code><i>b</i>!!<i>b'</i></code> &equiv; <code><i>beb'</i></code> &equiv; <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
+</table>
+
+<p>Seems so.  Now we can write Burro programs that halt, and Burro programs that loop
+forever.  What we need next is for the program to be able to decide this behaviour
+for itself.</p>
+
+<h3>Conditionals</h3>
+
+<p>OK, this is the ugly part.</p>
+
+<p>Let's add a simple control structure to Burro.  Since we already have repetition, this
+will only be for conditional execution.  To avoid confusion with Brainfuck, we'll avoid <code>[]</code>
+entirely; instead, we'll use <code>()</code>
+to indicate "execute the enclosed code (once) if and only if the current cell is non-zero".</p>
+
+<p>Actually, let's make it a bit fancier, and allow an "else" clause to be inserted in it,
+like so: <code>(/)</code> where the code before the <code>/</code> is executed iff the cell
+is non-zero, and the code after the <code>/</code> is executed iff it is zero.</p>
+
+<p>(The reasons for this design choice are subtle.  They come down to the fact that
+in order to find an inverse of a conditional, we need to invert the sense of the test.
+In a higher-level language, we could use a Boolean NOT operation for this.  However, in
+Brainfuck, writing a NOT requires a loop, and thus a conditional.  Then we're stuck
+with deciding how to invert the sense of <em>that</em> conditional, and so forth.  By
+providing NOT-like behaviour as a built-in courtesy of <code>/</code>, we dodge the
+problem entirely.  If you like, you can think of it as meeting the aesthetic demands of
+a symmetrical language: the conditional structures are symmetrical too.)</p>
+
+<p>A significant difference here with Brainfuck is that, while Brainfuck is a bit
+lacksidaisical about matching up <code>[</code>'s with <code>]</code>'s, we explicitly
+<em>disallow</em> parentheses that do not nest correctly in Burro.  A Burro program with mismatched
+parentheses is an ill-formed Burro program, and thus not really a Burro program at all.
+We turn up our nose at it; we aren't even interested in whether we can find an
+inverse of it, because we don't acknowledge it.  This applies to the placement of
+<code>/</code> outside of parentheses, or the absence of <code>/</code> in parentheses,
+as well.</p>
+
+<p>(The reasons for this design choice are also somewhat subtle.  I originally wanted
+to deal with this by saying that <code>(</code>, <code>/</code>, and <code>)</code>
+could come in any order, even a nonsensical one, and still make a valid Burro program,
+only with the semantics of "no-op" or "loop forever" or something equally representative of
+"broken."  You see this quite often in toy formal languages, and the resulting lack of
+syntax would seem to allow the set of Burro instructions to be a "free generator" of
+the group of Burro programs, which sounds like it might have very nice
+abstract-algebraical properties.
+The problem is that it potentially interferes with the whole "finding an
+antiprogram" thing.  If a Burro program with mismatched parentheses has the
+semantics of "no-op", then every Burro program has a trivial annihilator: just
+tack on an unmatching parenthesis.  Similarly, if malformed programs are
+considered to loop forever, how do you invert them?  So, for these reasons,
+Burro has some small amount of syntax &mdash; a bit more than Brainfuck is usually
+considered to have, but not much.)</p>
+
+<p>Now, it turns out we will have to do a fair bit of work on <code>()</code> in order
+to make it so that we can always find a bit of code that is the inverse of some other
+bit of code that includes <code>()</code>.</p>
+
+<p>We can't just make it a "plain old if", because by the time we've finished executing an "if",
+we don't know which branch was executed &mdash; so we have no idea what the "right"
+inverse of it would be.  For example,</p>
+
+<ul><code>(-/e)</code></ul>
+
+<p>After this has finished executing, the current cell could contain 0 - but is that because it
+was already 0 before the <code>(</code> was encountered, and nothing happened to it
+inside the "if"... or is it because it was 1 before
+the <code>(</code> was encountered, and decremented to 0 by the <code>-</code>
+instruction inside the "if"?
+It could be either, and we don't know &mdash; so we can't find an inverse.</p>
+
+<p>We remedy this in a somewhat disappointingly uninteresting way: we make a copy of
+the value being tested and squirrel it away for future reference, so that pending code
+can look at it and tell what decision was made, and in so doing, act appropriately to
+invert it.</p>
+
+<p>This information that we squirrel away is, I would say, a kind of <em>continuation</em>.
+It's not a full-bodied continuation, as the term continuation is often used, in the
+sense of "function representing the entire remainder of the computation."
+But, it's a bit of context that is retained during execution that is intended to affect
+some future control flow decision &mdash; and that's the basic purpose of a continuation.
+So, I will call it a continuation, although it is perhaps a diminished sort of continuation.
+(In this sense, the machine stack where arguments and
+return addresses are stored in a language like C is also a kind of continuation.)</p>
+
+<p>These continuations that we maintain, these pieces of information that tell us how
+to undo things in the future, do need to have an orderly relationship with each other.
+Specifically, we need to remember to undo the more recent conditionals first.  So, we
+retain the continuations in a FIFO discipline, like a stack.  Whenever a <code>(</code> is
+executed, we "push" a continuation into storage, and when we need to invert the effect
+of a previous conditional, we "pop" a continuation from storage.</p>
+
+<p>To actually accomplish this latter action we need to define the control structure
+for undoing conditional tests.  We introduce the construct
+<code>{\}</code>, which works just like <code>(/)</code>, except that the value that it tests
+doesn't come from the tape &mdash; instead, it comes from the continuation.  We establish similar
+syntactic rules about matching every <code>{</code> with a <code>}</code> and an
+intervening <code>\</code>, in addition to a rule that says every <code>{\}</code>
+must be preceded by a <code>(/)</code>.</p>
+
+<p>With this, we're very close to having an inverse for conditionals.  Consider:</p>
+
+<ul><code>(-/e){+\e}</code></ul>
+
+<p>If the current cell contains 0 after <code>(-/e)</code>, the continuation will contain either
+a 1 or a 0 (the original contents of the cell.)  If the continuation contains a 0, the "else" part of
+<code>{+\e}</code> will be executed &mdash; i.e. nothing will happen.  On the other hand, if the
+continuation contains a 1, the "then" part of <code>{+\e}</code> will be executed.
+Either way, the tape is correctly restored to its original (pre-<code>(-/e)</code>) state.</p>
+
+<p>There are still a few details to clean up, though.
+Specifically, we need to address nesting.  What if we're given</p>
+
+<ul><code>(&gt;(&lt;+/e)/e)</code></ul>
+
+<p>How do we form an inverse of this?  How would the following work?</p>
+
+<ul><code>(&gt;(&lt;+/e)/e){{-&gt;\e}&lt;\e}</code></ul>
+
+<p>The problem with this, if we collect continuations using only a naive stack arrangement,
+is that we don't remember how many times a <code>(</code> was encountered before a
+matching <code>)</code>.  The retention of continuations is still FIFO, but we need
+more control over the relationships between the continuations.</p>
+
+<p>The nested structure of the <code>(/)</code>'s suggests a nested structure
+for collecting continuations.  
+Whenever we encounter a <code>(</code> and we "push" a continuation into storage,
+that continuation becomes the root for a new collection of continuations
+(those that occur <em>inside</em> the present conditional, up to the matching
+<code>)</code>.)  Since each continuation is both part of some FIFO series of
+continuations, and has the capacity to act as the root of it's <em>own</em> FIFO series
+of continuations, the continuations are arranged in a structure that is
+more a binary tree than a stack.</p>
+
+<p>This is perhaps a little complicated, so I'll summarize it in this table.
+Since this is a fairly operational description, I'll use the term "tree node"
+instead of continuation to help you visualize it.  Keep in mind that at any
+given time there is a "current continuation" and thus a current tree node.</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Semantics</th></tr>
+<tr><td align="center"><code>(</code></td><td>
+<ul>
+<li>Create a new tree node with the contents of the current cell</li>
+<li>Add that new node as a child of the current node</li>
+<li>Make that new node the new current node</li>
+<li>If the current cell is zero, skip one instruction past the matching <code>/</code></li>
+</ul>
+</td></tr>
+<tr><td align="center"><code>/</code></td><td>
+<ul>
+<li>Skip to the matching <code>)</code></li>
+</ul>
+</td></tr>
+<tr><td align="center"><code>)</code></td><td>
+<ul>
+<li>Make the parent of the current node the new current node</li>
+</ul>
+</td></tr>
+<tr><td align="center"><code>{</code></td><td>
+<ul>
+<li>Make the most recently added child of the current node the new current node</li>
+<li>If the value of the current node is zero, skip one instruction past the matching <code>\</code></li>
+</ul>
+</td></tr>
+<tr><td align="center"><code>\</code></td><td>
+<ul>
+<li>Skip to the matching <code>}</code></li>
+</ul>
+</td></tr>
+<tr><td align="center"><code>}</code></td><td>
+<ul>
+<li>Make the parent of the current node the new current node</li>
+<li>Remove the old current node and all of its children</li>
+</ul>
+</td></tr>
+</table>
+
+<p>Now, keeping in mind that the continuation structure
+remains constant across all Burro programs equivalent to <code>e</code>,
+we can show that control structures have inverses:</p>
+
+<table border=1 cellpadding=5>
+<tr><th>Instruction</th><th>Inverse</th><th>Test result</th><th>Concatenation</th><th>Net effect</th></tr>
+<tr><td align="center"><code><i>a</i>(<i>b</i>/<i>c</i>)<i>d</i></code></td><td align="center"><code><i>d'</i>{<i>b'</i>\<i>c'</i>}<i>a'</i></code></td>
+    <td align="center">zero</td><td align="center"><code><i>acdd'c'a'</i></code> &equiv; <code><i>acc'a'</i></code> &equiv; <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
+<tr><td align="center"><code><i>a</i>(<i>b</i>/<i>c</i>)<i>d</i></code></td><td align="center"><code><i>d'</i>{<i>b'</i>\<i>c'</i>}<i>a'</i></code></td>
+    <td align="center">non-zero</td><td align="center"><code><i>abdd'b'a'</i></code> &equiv; <code><i>abb'a'</i></code> &equiv; <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
+</table>
+
+<p>There you have it: every Burro program has an inverse.</p>
+
+<h2>4. Implementations</h2>
+
+<p>There are two reference interpreters for Burro.  <code>burro.c</code> is
+written in ANSI C, and <code>burro.hs</code> is written in Haskell.
+Both are BSD licensed.
+Hopefully at least one of them is faithful to the execution model.</p>
+
+<h3><code>burro.c</code></h3>
+
+<p>The executable produced by compiling <code>burro.c</code> takes the
+following command-line arguments:</p>
+
+<ul><code>burro [-d] srcfile.bur</code></ul>
+
+<p>The named file is loaded as Burro source code.  All characters in this file except for
+<code>&gt;&lt;+-(/){\}e!</code> are ignored.</p>
+
+<p>Before starting the run, the interpreter will read a series of whitespace-separated
+integers from standard input.  These integers
+are placed on the tape initially, starting from the head-start position, extending right.
+All unspecified cells are considered to contain 0 initially.</p>
+
+<p>When the program has halted, all tape cells that were "touched" &mdash; either given initially as
+part of the input, or passed over by the tape head &mdash; are output to standard output.</p>
+
+<p>The meanings of the flags are as follows:</p>
+
+<ul>
+<li>The <code>-d</code> flag causes debugging information to be sent to standard error.</li>
+</ul>
+
+<p>The C implementation performs no syntax-checking.  It approximates the unbounded Burro tape
+with a tape of finite size (defined by <code>TAPE_SIZE</code>, by default 64K) with
+cells each capable of containing a C language <code>long</code>.</p>
+
+<h3><code>burro.hs</code></h3>
+
+<p>The Haskell version of the reference implementation is meant to be executed from
+within an interactive Haskell environment, such as Hugs.  As such, there is no
+command-line syntax; the user simply invokes the function <code>burro</code>,
+which has the signature <code>burro :: String -&gt; Tape -&gt; Tape</code>.
+A convenience constructor <code>tape :: [Integer] -> Tape</code> creates a tape
+from the given list of integers, with the head positioned over the leftmost cell.</p>
+
+<p>The Haskell implementation performs no syntax-checking. Because Haskell supports
+unbounded lists and arbitrary-precision integers, the Burro tape is modelled faithfully.</p>
+
+<h2>Discussion</h2>
+
+<p>I hadn't intended to come up with anything in particular when I started
+designing Burro.  I'm hardly a mathematician, and I didn't know anything
+about abstract algebra except that I found it intriguing.  I suppose that algebraic
+structures have some of the same appeal as programming languages, what with
+both dealing with primitive operators, equivalent expression forms, and so forth.</p>
+
+<p>I was basically struck by the variety of objects that could be shown to have
+this or that algebraic structure, and I wanted to see how well it would
+hold up if you tried to apply these structures to programs.</p>
+
+<p>Why groups?  Well, the original design goal for Burro was actually to create a Brainfuck-like language 
+where the set of possible programs forms the most <em>restricted</em>
+possible magma (i.e. the one with the most additional axioms) under concatenation.  It can
+readily been seen that the set of Brainfuck programs forms a semigroup,
+even a monoid, under concatenation (left as an exercise for the interested
+reader.)  At the other extreme, if the set of programs forms an abelian group under
+concatenation, the language probably isn't going to be very Brainfuck-like
+(since insisting that concatenation be commutative is tantamount to saying
+that the order of instructions in a program doesn't matter.)
+This leaves a group as the reasonable target to aim for, so that's what I
+aimed for.</p>
+
+<p>But the end result turns out to be related to <em>reversible computing</em>.
+This shouldn't have been a surprise, since groups are one of the simplest
+foundations for modelling symmetry; it should have been obvious to me that trying to
+make programs conform to them, would make them (semantically) symmetrical, and
+thus reversible.  But, it wasn't.</p>
+
+<p>We may ask: in what sense is Burro reversible?  And we may compare it
+to other esolangs in an attempt to understand.</p>
+
+<p>Well, it's not reversible in the sense that 
+<a href="http://esolangs.org/wiki/Befreak">Befreak</a> is reversible &mdash;
+you can't pause it at any point, change the direction of execution, and watch it
+"go backwards".  Specifically, you can't "undo" a loop in Burro by executing
+20 iterations, then turning around and "un-executing" those 20 iterations; instead,
+you "undo" the loop by neutralizing the toggling of the halt flag.  With this approach,
+inversion is instead <em>like the loop never existed in the first place</em>.</p>
+
+<p>If one did want to make a Brainfuck-like language which was reversible more in
+the sense that Befreak is reversible, one approach might be to add rules like
+"<code>+</code> acts like <code>-</code> if the program counter is incoming from
+the right". But, I haven't pondered on this approach much at all.</p>
+
+<p>Conversely, the concatenation concept doesn't have a clear
+correspondence in a two-dimensional language like Befreak &mdash; how do you put two programs
+next to each other?  Side-by-side, top-to-bottom?  You would probably need multiple
+operators, which would definately complicate things.</p>
+
+<p>It's also not reversible in the same way that
+<a href="http://esolangs.org/wiki/Kayak">Kayak</a> is reversible &mdash;
+Burro programs need not be palindromes, for instance.  In fact, I specifically made
+the "then" and "else" components of both <code>(/)</code> and <code>{\}</code>
+occur in the same order, so as to break the reflectional symmetry somewhat, and
+add some translational similarity.</p>
+
+<p>Conversely, Kayak doesn't cotton to concatenation too well either.
+In order to preserve the palindrome nature, concatenation would have to
+occur both at the beginning and the end simultaneously.
+I haven't given this idea much thought, and I'm not sure where it'd get you.</p>
+
+<p>Lastly, we could go outside the world of esolangs and use the
+definition of reversible computing given by Mike Frank<sup><a href="#2">2</a></sup>:</p>
+
+<blockquote>When we say reversible computing, we mean performing computation
+in such a way that any previous state of the computation can always be reconstructed
+given a description of the current state.</blockquote>
+
+<p>Burro appears to qualify by this definition &mdash; <em>almost</em>.  The requirement
+that we can reconstruct <em>any</em> previous state is a bit heavy.  We can definately
+reconstruct states up to the start of the last loop iteration, if we want to, due to the mechanism
+(continuations) that we've defined to remember what the program state was before any given
+conditional.</p>
+
+<p>But what about <em>before</em> the last loop iteration?  Each time we reach the end
+of the program text with halt flag unset, we repeat execution from the beginning, and
+when this happens, there might still be one or more continuations in storage that were the
+result of executing <code>(/)</code>'s that did not have
+matching <code>{\}</code>'s.</p>
+
+<p>We didn't say what happens to these "leftover" continuations.  In fact, computationally
+speaking, it doesn't matter: since syntactically no
+<code>{\}</code> can precede any <code>(/)</code>, those leftover continuations
+couldn't actually have any affect during the next iteration.  Any <code>{\}</code> that
+might consume them next time 'round must be preceded by a <code>(/)</code> which will
+produce one for it to consume instead.</p>
+
+<p>And indeed, discarding any continuation that remains when a Burro program loops
+means that continuations need occupy only a bounded amount of space during execution (because there
+is only a fixed number of conditionals in any given Burro program.)  This
+is a desirable thing in a practical implementation, and
+both the C and Haskell reference implementations do just this.</p>
+
+<p>But this is an implementation choice, and it would be equally valid to write an interpreter
+which retains all these leftover continuations.  And such an interpreter would qualify as a
+reversible computer under Mike Frank's definition, since these continuations would allow one
+to reconstruct the entire computation history of the program.</p>
+
+<p>On this last point, it's interesting to note the similarity between Burro's continuations
+and Kayak's bit bucket.  Although Burro continuations record the value tested, they really
+don't <em>need</em> to; they <em>could</em> just
+contain bits indicating whether the tests were successes or failures.  Both emptying
+the bit bucket, and discarding continuations, results in a destruction of information that
+prevents reversibility (and thermodynamically "generates heat") but allows for a limit on the amount of
+storage required.</p>
+
+<h2>History</h2>
+
+<p>I began formulating Burro in the summer of 2005.
+The basic design of Burro was finished by winter of 2005, as was the C implementation.
+But its release was delayed for several reasons.  Mainly, I was busy with other (ostensibly more
+important) things, like schoolwork.  However, I also had the nagging feeling that certain parts of
+the language were not quite described correctly.  These doubts led me to introduce the
+concept of a group over an equivalence relation, and to decide that Burro needed
+real syntax rules (lest inverting a Burro program was "too easy.")  So it wasn't until spring of 2007
+that I had a general description that I was satisfied with.
+I also wanted a better reference implementation, in something a bit more abstract and
+rigorous than C. So I wrote the Haskell version over the summer of 2007.</p>
+
+<p>In addition, part of me wanted to write a publishable paper on Burro.
+After all, group theory and reversible computing are valid and relatively mainstream
+research topics, so why not?  But in the end, considering doing this was really a
+waste of my time.  Densening my writing style to conform to acceptable academic
+standards of impermeability, and puffing up my "discovery" to acceptable academic
+standards of self-importance, really didn't appeal to me.  There's no sense pretending,
+in high-falutin' language, that Burro represents some profound advance in human
+knowledge.  It's just something neat that I built!  And in the end it seemed
+just as valuable, if not moreso, to try to turn esolangers on to group theory than
+to turn academics on to Brainfuck...</p>
+
+<p>Happy annihilating!</p>
+
+<p>-Chris Pressey
+<br>Cat's Eye Technologies
+<br>October 26, 2007
+<br>Windsor, Ontario, Canada</p>
+
+<h2>Footnotes</h2>
+
+<ul>
+<li><a name="1"><sup>1</sup>Dexter Kozen. <a href="http://www.cs.cornell.edu/~kozen/papers/ckat.ps">Kleene algebra with tests</a>. <i>Transactions on Programming Languages and
+Systems</i>, 19(3):427-443, May 1997.</a></li>
+<li><a name="2"><sup>2</sup>Michael Frank.  What's Reversible Computing? <code><a href="http://www.cise.ufl.edu/~mpf/rc/what.html">http://www.cise.ufl.edu/~mpf/rc/what.html</a></code></a></li>
+
+</ul>
+
+</body></html>

eg/countdown-nullified.bur

+(-!/e){!+/e}
+
+
+(-!/e)
+(->(->(-/e)</e)</e)>(-/e)>(-/e)
+# Makefile for burro.
+
+CC?=gcc
+OBJS=burro.o tree.o
+PROG=burro
+
+all: $(PROG)
+
+$(PROG): $(OBJS)
+	$(CC) $(OBJS) -o $(PROG)
+
+burro.o: burro.c tree.h
+	$(CC) -Wall -c burro.c -o burro.o
+
+tree.o: tree.c tree.h
+	$(CC) -Wall -c tree.c -o tree.o
+
+clean:
+	rm -rf $(OBJS) $(PROG)
+/*
+ * Copyright (c)2005-2007 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ *   Redistributions of source code must retain the above copyright
+ *   notices, this list of conditions and the following disclaimer.
+ *
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notices, this list of conditions, and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ *   Neither the names of the copyright holders nor the names of their
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * burro.c
+ *
+ * A quick-and-dirty interpreter for the Burro programming language,
+ * where the set of possible programs is a group under concatenation
+ * (roughly speaking; see burro.html for the full story.)
+ *
+ * $Id: burro.c 10 2007-10-10 01:17:52Z catseye $
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>	/* for getopt() */
+
+#include "tree.h"
+
+/* constants */
+
+#ifndef TAPE_SIZE
+#define TAPE_SIZE 65536
+#endif
+
+#define TAPE_START	(TAPE_SIZE / 2)		/* for entry and dump */
+#define TAPE_END	(TAPE_START + 100)	/* for dumps only */
+
+#ifndef PROG_SIZE
+#define	PROG_SIZE 65536
+#endif
+
+/* globals */
+
+char prog[PROG_SIZE];
+int pc;
+
+long tape[TAPE_SIZE];
+int th;
+
+int halt_flag;
+
+int debug_flag = 0;
+
+FILE *f;
+
+struct tree *root;	/* structure into which we save test results */
+
+/********* debugging *********/
+
+void
+debug_state(void)
+{
+	if (!debug_flag)
+		return;
+
+	fprintf(stderr,
+	    "OP='%c' PC=%3d TH=%3d TC=%4ld HF=%1d ",
+	    prog[pc], pc, th - TAPE_START, tape[th], halt_flag);
+}
+
+void
+debug_tree(struct tree *t, struct tree *s)
+{
+	if (!debug_flag)
+		return;
+	tree_dump(stderr, t, s);
+}
+
+void
+debug_newline(void)
+{
+	if (debug_flag)
+		fprintf(stderr, "\n");
+}
+
+/**** usage info ****/
+
+void
+usage(void)
+{
+	fprintf(stderr, "Usage: burro [-d] filename\n");
+	exit(1);
+}
+
+/**** MAIN ****/
+
+int
+main(int argc, char **argv)
+{
+	int ch;			/* getopt character */
+	struct tree *save;
+	int i;
+
+	/* get cmdline args */
+	while ((ch = getopt(argc, argv, "d")) != -1) {
+		switch ((char)ch) {
+		case 'd':
+			debug_flag++;
+			break;
+		case '?':
+		default:
+			usage();
+		}
+	}
+	argv += optind;
+	argc -= optind;
+
+	if (argc < 1)
+		usage();
+
+	/* load */
+
+	f = fopen(argv[0], "r");
+	if (f == NULL) {
+		fprintf(stderr, "Couldn't open '%s'\n", argv[0]);
+		exit(1);
+	}
+	pc = 0;
+	for (;;) {
+		if (pc >= PROG_SIZE) break;
+		prog[pc] = fgetc(f);
+		if (feof(f)) break;
+		if (strchr("+-<>(/){\\}!e", prog[pc]) == NULL) continue;
+		pc++;
+	}
+	prog[pc] = '\0';
+	fclose(f);
+
+	/* initialize tape */
+
+	for (th = 0; th < TAPE_SIZE; th++)
+		tape[th] = 0;
+
+	/* read tape from input */
+
+	th = TAPE_START;
+	for (;;) {
+		scanf("%ld", &tape[th]);
+		if (feof(stdin)) {
+			tape[th] = 0;
+			break;
+		}
+		if (debug_flag) {
+			fprintf(stderr,
+			    "Writing %ld into position %d\n",
+			    tape[th], th);
+		}
+		th++;
+	}
+
+	/* initialize decision-save-tree */
+
+	root = tree_new(NULL, 0);
+	save = root;
+
+	/* run */
+
+	th = TAPE_START;
+
+	do {
+		/* once through */
+		halt_flag = 1;
+		for (pc = 0; prog[pc] != '\0'; pc++) {
+			switch (prog[pc]) {
+			case '>':
+				th++;
+				break;
+			case '<':
+				th--;
+				break;
+			case '+':
+				tape[th]++;
+				break;
+			case '-':
+				tape[th]--;
+				break;
+			case '(':
+				save = tree_grow(save, tape[th]);
+				if (tape[th] == 0) {
+					/* skip to matching / or ) */
+					int bc = 1;
+
+					pc++;
+					for (; prog[pc] != '\0'; pc++) {
+						if (prog[pc] == '(')
+							bc++;
+						if (prog[pc] == '/' && bc == 1)
+							break;
+						if (prog[pc] == ')') {
+							bc--;
+							if (bc == 0) {
+								save = tree_ascend(save);
+								break;
+							}
+						}
+					}
+				}
+				break;
+			case '/':
+				/* skip to matching ) */
+				{
+					int bc = 1;
+
+					pc++;
+					for (; prog[pc] != '\0'; pc++) {
+						if (prog[pc] == '(')
+							bc++;
+						if (prog[pc] == ')') {
+							bc--;
+							if (bc == 0) {
+								save = tree_ascend(save);
+								break;
+							}
+						}
+					}
+				}
+				break;
+			case ')':
+				save = tree_ascend(save);
+				break;
+			case '{':
+				save = tree_descend(save);
+				if (tree_value(save) == 0) {
+					/* skip to matching \ or } */
+					int bc = 1;
+
+					pc++;
+					for (; prog[pc] != '\0'; pc++) {
+						if (prog[pc] == '{')
+							bc++;
+						if (prog[pc] == '\\' && bc == 1)
+							break;
+						if (prog[pc] == '}') {
+							bc--;
+							if (bc == 0) {
+								save = tree_prune(save);
+								break;
+							}
+						}
+					}
+				}
+				break;
+			case '\\':
+				/* skip to matching } */
+				{
+					int bc = 1;
+
+					pc++;
+					for (; prog[pc] != '\0'; pc++) {
+						if (prog[pc] == '{')
+							bc++;
+						if (prog[pc] == '}') {
+							bc--;
+							if (bc == 0) {
+								save = tree_prune(save);
+								break;
+							}
+						}
+					}
+				}
+				break;
+			case '}':
+				save = tree_prune(save);
+				break;
+			case '!':
+				halt_flag = !halt_flag;
+				break;
+			case 'e':
+				/* nop */
+				break;
+			}
+			debug_state();
+			debug_tree(root, save);
+			debug_newline();
+		}
+		if (debug_flag) {
+			fprintf(stderr, "Reached end of program; %s.\n",
+			    halt_flag ? "halting" : "looping");
+		}
+		/* clear savetree */
+		save = tree_chop_down(root);
+	} while (!halt_flag);
+
+	/* dump tape to output */
+
+	for (i = TAPE_START; i < TAPE_END; i++) {
+		if (i == th)
+			printf(">%ld< ", tape[i]);
+		else
+			printf("%ld ", tape[i]);
+	}
+	printf("\n");
+
+	return 0;
+}
+--
+-- burro.hs
+-- Reference Interpreter for the Burro Programming Language
+-- Chris Pressey, Cat's Eye Technologies
+--
+-- $Id: burro.hs 10 2007-10-10 01:17:52Z catseye $
+--
+
+--
+-- Copyright (c)2007 Cat's Eye Technologies.  All rights reserved.
+--
+-- Redistribution and use in source and binary forms, with or without
+-- modification, are permitted provided that the following conditions
+-- are met:
+--
+--  1. Redistributions of source code must retain the above copyright
+--     notices, this list of conditions and the following disclaimer.
+--  2. Redistributions in binary form must reproduce the above copyright
+--     notices, this list of conditions, and the following disclaimer in
+--     the documentation and/or other materials provided with the
+--     distribution.
+--  3. Neither the names of the copyright holders nor the names of their
+--     contributors may be used to endorse or promote products derived
+--     from this software without specific prior written permission. 
+--
+-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+-- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+-- FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+-- COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+-- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+-- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+-- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+-- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+-- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+-- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+-- POSSIBILITY OF SUCH DAMAGE.
+--
+
+-----------------------------------------------------------------------
+-- ========================== Data types =========================== --
+-----------------------------------------------------------------------
+
+import Char
+
+data Instruction = Block [Instruction]
+                 | Nop
+                 | Inc
+                 | Dec
+                 | GoLeft
+                 | GoRight
+                 | ToggleHalt
+                 | Test [Instruction] [Instruction]
+                 | UnTest [Instruction] [Instruction]
+    deriving (Show, Read, Eq)
+
+--
+-- Our abstract data type for representing the tape.  We represent the
+-- tape as two stacks (lists).  The first list contains the cell under
+-- the tape head, and everything left of the tape head (in reverse
+-- order as it appears on the tape.)  The second list contains everything
+-- to the right of the tape head, in the same order as it appears on the
+-- tape.  A convenience function for creating an inital tape is also
+-- provided.
+--
+
+data Tape = Tape [Integer] [Integer]
+    deriving (Show, Read, Eq)
+
+tape :: [Integer] -> Tape
+tape x = Tape [head x] (tail x)
+
+--
+-- Our abstract data type for representing continuations.
+--
+-- A null continuation (NullCont) represents nothing more to be
+-- done.
+--
+-- A test continuation (TestCont) represents the fact that a
+-- conditional was performed, and remembers the value so tested
+-- for future possible use in an UnTest that will undo the effect
+-- of the conditional.
+--
+-- Test continuations can be composed in two ways:
+--
+-- One, when one conditional occurs after another, the test
+-- continuations are sequentially stacked.  The continutation
+-- representing the conditional test that happened most recently
+-- is on the "outside", with the earlier continuation linked into
+-- it, like so:
+--   TestCont 2 (TestCont 1 NullCont)
+--
+-- Two, when one conditional occurs inside another, the test
+-- continuations are hierarchically organized.  Because this
+-- interpreter is recursive, (specifically because it recursively
+-- executes the sequences of instructions inside each conditional,)
+-- this hierarchical organization need not be explicitly represented
+-- in our continuation structures.
+--
+
+data Continuation = TestCont Integer Continuation
+                  | NullCont
+    deriving (Show, Read, Eq)
+
+
+-----------------------------------------------------------------------
+-- ============================= Parser ============================ --
+-----------------------------------------------------------------------
+
+parse string =
+    let
+        (rest, acc) = parseProgram string []
+    in
+        acc
+
+parseProgram [] acc =
+    ([], acc)
+parseProgram ('e':rest) acc =
+    parseProgram rest acc
+parseProgram ('+':rest) acc =
+    parseProgram rest (acc ++ [Inc])
+parseProgram ('-':rest) acc =
+    parseProgram rest (acc ++ [Dec])
+parseProgram ('<':rest) acc =
+    parseProgram rest (acc ++ [GoLeft])
+parseProgram ('>':rest) acc =
+    parseProgram rest (acc ++ [GoRight])
+parseProgram ('!':rest) acc =
+    parseProgram rest (acc ++ [ToggleHalt])
+
+parseProgram ('(':rest) acc =
+    let
+        (rest',  thenprog) = parseProgram rest []
+        (rest'', elseprog) = parseProgram rest' []
+        test = Test thenprog elseprog
+    in
+        parseProgram rest'' (acc ++ [test])
+parseProgram ('/':rest) acc =
+    (rest, acc)
+parseProgram (')':rest) acc =
+    (rest, acc)
+
+parseProgram ('{':rest) acc =
+    let
+        (rest',  thenprog) = parseProgram rest []
+        (rest'', elseprog) = parseProgram rest' []
+        untest = UnTest thenprog elseprog
+    in
+        parseProgram rest'' (acc ++ [untest])
+parseProgram ('\\':rest) acc =
+    (rest, acc)
+parseProgram ('}':rest) acc =
+    (rest, acc)
+
+
+-----------------------------------------------------------------------
+-- =========================== Execution =========================== --
+-----------------------------------------------------------------------
+
+burro :: String -> Tape -> Tape
+
+burro program tape =
+    let
+        internalRep = parse program
+    in
+        run internalRep internalRep tape True NullCont
+
+run :: [Instruction] -> [Instruction] -> Tape -> Bool -> Continuation -> Tape
+
+run [] origprog tape True cont =
+    tape
+run [] origprog tape False cont =
+    run origprog origprog tape True NullCont
+
+run (inst:insts) origprog tape halt cont =
+    let
+        (tape', halt', cont') = execute inst tape halt cont
+    in
+        run insts origprog tape' halt' cont'
+
+execute :: Instruction -> Tape -> Bool -> Continuation -> (Tape, Bool, Continuation)
+
+execute instr (Tape [] right) halt cont =
+    execute instr (Tape [0] right) halt cont
+execute Nop tape halt cont =
+    (tape, halt, cont)
+execute Inc (Tape (cell:left) right) halt cont =
+    (Tape (cell + 1 : left) right, halt, cont)
+execute Dec (Tape (cell:left) right) halt cont =
+    (Tape (cell - 1 : left) right, halt, cont)
+execute GoLeft (Tape (cell:left) right) halt cont =
+    (Tape left (cell:right), halt, cont)
+execute GoRight (Tape left []) halt cont =
+    (Tape (0:left) [], halt, cont)
+execute GoRight (Tape left (cell:right)) halt cont =
+    (Tape (cell:left) right, halt, cont)
+execute ToggleHalt tape halt cont =
+    (tape, not halt, cont)
+execute (Test con alt) tape@(Tape (0:left) right) halt cont =
+    let
+        (tape', halt', cont') = runSub alt tape halt NullCont
+    in
+        (tape', halt', TestCont 0 cont')
+execute (Test con alt) tape@(Tape (cell:left) right) halt cont =
+    let
+        (tape', halt', cont') = runSub con tape halt NullCont
+    in
+        (tape', halt', TestCont cell cont')
+execute (UnTest con alt) tape halt cont@(TestCont 0 prevcont) =
+    runSub alt tape halt prevcont
+execute (UnTest con alt) tape halt cont@(TestCont cell prevcont) =
+    runSub con tape halt prevcont
+
+runSub :: [Instruction] -> Tape -> Bool -> Continuation -> (Tape, Bool, Continuation)
+
+runSub [] tape halt cont =
+    (tape, halt, cont)
+runSub (inst:insts) tape halt cont =
+    let
+        (tape', halt', cont') = execute inst tape halt cont
+    in
+        runSub insts tape' halt' cont'
+
+
+-----------------------------------------------------------------------
+-- =========================== Test Cases ========================== --
+-----------------------------------------------------------------------
+
+testCase 0 = "e"
+testCase 1 = "!"
+testCase 2 = "(-!/e)"
+testCase 3 = "(-!/e){!+/e}"
+testCase 4 = "(->(->(-/e)</e)</e)>(-/e)>(-/e)"
+/*
+ * Copyright (c)2005-2007 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ *   Redistributions of source code must retain the above copyright
+ *   notices, this list of conditions and the following disclaimer.
+ *
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notices, this list of conditions, and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ *   Neither the names of the copyright holders nor the names of their
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * tree.c
+ *
+ * Decision-saving trees (continuations) for Burro.
+ *
+ * $Id: tree.c 9 2007-10-10 00:42:35Z catseye $
+ */
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "tree.h"
+
+/* private structures */
+
+struct tree {
+	struct tree *		parent;
+	struct child_list *	children;
+	long			value;
+};
+
+struct child_list {
+	struct child_list *	next;
+	struct tree *		child;
+};
+
+/* private methods */
+
+static struct child_list *
+child_list_new(struct tree *child)
+{
+	struct child_list *cl;
+
+	cl = malloc(sizeof(struct child_list));
+	assert(cl != NULL);
+	cl->next = NULL;
+	cl->child = child;
+
+	return cl;
+}
+
+static void
+child_list_free(struct child_list *cl)
+{
+	if (cl == NULL)
+		return;
+	child_list_free(cl->next);
+	tree_free(cl->child);
+}
+
+/* public methods */
+
+struct tree *
+tree_new(struct tree *parent, long value)
+{
+	struct tree *t;
+
+	t = malloc(sizeof(struct tree));
+	assert(t != NULL);
+	t->parent = parent;
+	t->children = NULL;
+	t->value = value;
+
+	return t;
+}
+
+void
+tree_free(struct tree *t)
+{
+	if (t == NULL)
+		return;
+	child_list_free(t->children);
+	free(t);
+}
+
+int
+tree_value(struct tree *t)
+{
+	assert(t != NULL);
+	return t->value;
+}
+
+/*
+ * Add a degenerate subtree to the current level of the tree.
+ */
+struct tree *
+tree_grow(struct tree *parent, long value)
+{
+	struct tree *t;
+	struct child_list *cl;
+
+	assert(parent != NULL);
+
+	/* create new node and new child entry */
+	t = tree_new(parent, value);
+	cl = child_list_new(t);
+
+	/* add new child at start of children list */
+	/* this makes it a lot like a stack... */
+	cl->next = parent->children;
+	parent->children = cl;
+
+	return t;
+}
+
+/*
+ * Return the parent of the given subtree.
+ */
+struct tree *
+tree_ascend(struct tree *t)
+{
+	assert(t != NULL);
+	return t->parent;
+}
+
+/*
+ * Return the last (most recently added) subtree.
+ */
+struct tree *
+tree_descend(struct tree *t)
+{
+	assert(t != NULL);
+	assert(t->children != NULL);
+	return t->children->child;
+}
+
+/*
+ * Remove the given subtree from the tree.
+ */
+struct tree *
+tree_prune(struct tree *t)
+{
+	struct tree *p;
+	struct child_list *cl, *ocl;
+
+	assert(t != NULL);
+	assert(t->parent != NULL);
+
+	p = t->parent;
+
+	/* find the correct child */
+	cl = p->children;
+	ocl = NULL;
+	while (cl != NULL && cl->child != t) {
+		ocl = cl;
+		cl = cl->next;
+	}
+	assert(cl != NULL);
+	if (ocl != NULL) {
+		ocl->next = cl->next;
+	} else {
+		p->children = cl->next;
+	}
+	child_list_free(cl);
+
+	return p;
+}
+
+/*
+ * Dispose of everything except the root.
+ */
+struct tree *
+tree_chop_down(struct tree *root)
+{
+	child_list_free(root->children);
+
+	root->children = NULL;
+
+	return root;
+}
+
+/*
+ * Dump a representation of the tree to a file.
+ */
+void
+tree_dump(FILE *f, struct tree *t, struct tree *save)
+{
+	struct child_list *cl;
+
+	if (t == NULL)
+		return;
+	if (t == save)
+		fprintf(f, "->");
+	if (t->parent == NULL) {
+		fprintf(f, "(R ");
+	} else {
+		fprintf(f, "(%ld ", t->value);
+	}
+	cl = t->children;
+	while (cl != NULL) {
+		tree_dump(f, cl->child, save);
+		cl = cl->next;
+	}
+	fprintf(f, ")");
+}
+/*
+ * tree.h
+ * $Id: tree.h 9 2007-10-10 00:42:35Z catseye $
+ */
+
+#ifndef _BURRO_TREE_H_
+#define _BURRO_TREE_H_
+
+/* prototypes */
+
+struct tree;
+
+struct tree *	tree_new(struct tree *, long);
+void		tree_free(struct tree *);
+int		tree_value(struct tree *);
+struct tree *	tree_grow(struct tree *, long);
+struct tree *	tree_prune(struct tree *);
+struct tree *	tree_ascend(struct tree *);
+struct tree *	tree_descend(struct tree *);
+struct tree *	tree_chop_down(struct tree *);
+
+void		tree_dump(FILE *, struct tree *, struct tree *);
+
+#endif
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.