| 0 | 0 |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
|
1 |
<!-- encoding: UTF-8 -->
|
| 1 | 2 |
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
|
| 2 | 3 |
<head>
|
| 3 | 4 |
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
|
|
| 25 | 26 |
But the first version is close enough for jazz, and rolls off the tongue more easily...)</p>
|
| 26 | 27 |
|
| 27 | 28 |
<p>Anyway, what does it mean? It means that, among other things, every Burro program has
|
| 28 | |
an <em>antiprogram</em> — a series of instructions that can be appended to it
|
|
29 |
an <em>antiprogram</em> — a series of instructions that can be appended to it
|
| 29 | 30 |
to annihilate its behavior. The resulting catenated program has the
|
| 30 | |
same semantics as no program at all — a "no-op," or a zero-length program.</p>
|
|
31 |
same semantics as no program at all — a "no-op," or a zero-length program.</p>
|
| 31 | 32 |
|
| 32 | 33 |
<p>Why is this at all remarkable? Well, take the Brainfuck program fragment <code>[-]+[]</code>.
|
| 33 | 34 |
What could you append to it to it to make it into a "no-op" program?
|
|
| 51 | 52 |
|
| 52 | 53 |
<p>Recall (or go look up in an abstract algebra textbook) that a <em>group</em> is
|
| 53 | 54 |
a pair of a set <var>S</var> and a binary operation
|
| 54 | |
· : <var>S</var> × <var>S</var> → <var>S</var>
|
|
55 |
· : <var>S</var> × <var>S</var> → <var>S</var>
|
| 55 | 56 |
that obeys the following three axioms:</p>
|
| 56 | 57 |
|
| 57 | 58 |
<ul>
|
| 58 | 59 |
|
| 59 | 60 |
<li>For any three elements <var>a</var>, <var>b</var>, and <var>c</var> of
|
| 60 | |
the set <var>S</var>, (<var>a</var> · <var>b</var>) · <var>c</var> =
|
| 61 | |
<var>a</var> · (<var>b</var> · <var>c</var>). In other words,
|
|
61 |
the set <var>S</var>, (<var>a</var> · <var>b</var>) · <var>c</var> =
|
|
62 |
<var>a</var> · (<var>b</var> · <var>c</var>). In other words,
|
| 62 | 63 |
the operation is "associative." Parentheses don't matter, and we generally leave them out.</li>
|
| 63 | 64 |
|
| 64 | 65 |
<li>There exists some element of <var>S</var>, which we call <b>e</b>, such that
|
| 65 | |
<var>a</var> · <b>e</b> = <b>e</b> · <var>a</var> = <var>a</var>
|
|
66 |
<var>a</var> · <b>e</b> = <b>e</b> · <var>a</var> = <var>a</var>
|
| 66 | 67 |
for every element <var>a</var> of <var>S</var>. Think of
|
| 67 | 68 |
<b>e</b> as a "neutral" element that just doesn't contribute anything.</li>
|
| 68 | 69 |
|
| 69 | 70 |
<li>For every element <var>a</var> of <var>S</var> there is an element
|
| 70 | |
<var>a'</var> of <var>S</var> such that <var>a</var> · <var>a'</var> = <b>e</b>.
|
|
71 |
<var>a'</var> of <var>S</var> such that <var>a</var> · <var>a'</var> = <b>e</b>.
|
| 71 | 72 |
That is, for any element, you can find some element that "annihilates" it.</li>
|
| 72 | 73 |
|
| 73 | 74 |
</ul>
|
| 74 | 75 |
|
| 75 | |
<p>There are lots of examples of groups — the integers under the operation of
|
|
76 |
<p>There are lots of examples of groups — the integers under the operation of
|
| 76 | 77 |
addition, for example, where <b>e</b> is 0, and the annihilator for any integer
|
| 77 | 78 |
is simply its negative (because <var>x</var> + (-<var>x</var>) always equals 0.)</p>
|
| 78 | 79 |
|
| 79 | 80 |
<p>There are also lots of things you can prove are true about any group
|
| 80 | 81 |
(that is, about groups in general.) For instance, that <b>e</b> is unique: if
|
| 81 | |
<var>a</var> · <var>x</var> = <var>a</var> and
|
| 82 | |
<var>a</var> · <var>y</var> = <var>a</var> then
|
|
82 |
<var>a</var> · <var>x</var> = <var>a</var> and
|
|
83 |
<var>a</var> · <var>y</var> = <var>a</var> then
|
| 83 | 84 |
<var>x</var> = <var>y</var> = <b>e</b>. (This particular property will
|
| 84 | 85 |
become relevant very soon, so keep it in mind as you read the next section.)</p>
|
| 85 | 86 |
|
|
| 107 | 108 |
<p>This distinction becomes important with respect to treating programs
|
| 108 | 109 |
as elements of a group, like we're doing in Burro. Some program will
|
| 109 | 110 |
be the neutral element <b>e</b>. But either <em>many</em> programs will
|
| 110 | |
be equivalent to this program — in which case <b>e</b> is not unique, contrary to
|
| 111 | |
what group theory tells us — or we are talking about abstract programs
|
|
111 |
be equivalent to this program — in which case <b>e</b> is not unique, contrary to
|
|
112 |
what group theory tells us — or we are talking about abstract programs
|
| 112 | 113 |
independent of any programming language, in which case our goal of defining a particular
|
| 113 | 114 |
language called "Burro" for this purpose seems a bit futile.</p>
|
| 114 | 115 |
|
|
| 125 | 126 |
<p>To this end, let's examine the idea of a <em>group over an equivalence relation</em>.
|
| 126 | 127 |
All this is, really, is being specific about what constitutes "equals" in those
|
| 127 | 128 |
group axioms I listed earlier. In mathematics there is a well-established notion of
|
| 128 | |
an <em>equivalence relation</em> — a relationship between elements
|
|
129 |
an <em>equivalence relation</em> — a relationship between elements
|
| 129 | 130 |
which paritions a set into
|
| 130 | 131 |
disjoint equivalence classes, where every element in a class is considered
|
| 131 | 132 |
equivalent to every other element in that same class (and inequivalent to any
|
|
| 153 | 154 |
interchangably with respect to the group axioms.</p>
|
| 154 | 155 |
|
| 155 | 156 |
<p>I'll summarize the modified definition here. A <em>group over an equivalence relation</em>
|
| 156 | |
is a triple ⟨<var>S</var>,·,≡⟩ where:</p>
|
|
157 |
is a triple 〈<var>S</var>,·,≡〉 where:</p>
|
| 157 | 158 |
<ul>
|
| 158 | 159 |
<li><var>S</var> is a set</li>
|
| 159 | |
<li>· : <var>S</var> × <var>S</var> → <var>S</var> is a binary operation over <var>S</var></li>
|
| 160 | |
<li>≡ is a reflexive, transitive, and symmetrical binary relation over <var>S</var></li>
|
|
160 |
<li>· : <var>S</var> × <var>S</var> → <var>S</var> is a binary operation over <var>S</var></li>
|
|
161 |
<li>≡ is a reflexive, transitive, and symmetrical binary relation over <var>S</var></li>
|
| 161 | 162 |
</ul>
|
| 162 | 163 |
<p>where the following axioms are also satisfied:</p>
|
| 163 | 164 |
<ul>
|
| 164 | |
<li>∀ <var>a</var>, <var>b</var>, <var>c</var> ∈ <var>S</var>: (<var>a</var> · <var>b</var>) · <var>c</var> ≡
|
| 165 | |
<var>a</var> · (<var>b</var> · <var>c</var>)</li>
|
| 166 | |
<li>∃ <b>e</b> ∈ <var>S</var>: ∀ <var>a</var> ∈ <var>S</var>: <var>a</var> · <b>e</b> ≡ <b>e</b> · <var>a</var> ≡ <var>a</var></li>
|
| 167 | |
<li>∀ <var>a</var> ∈ <var>S</var>: ∃ <var>a'</var> ∈ <var>S</var>: <var>a</var> · <var>a'</var> ≡ <b>e</b></li>
|
|
165 |
<li>∀ <var>a</var>, <var>b</var>, <var>c</var> ∈ <var>S</var>: (<var>a</var> · <var>b</var>) · <var>c</var> ≡
|
|
166 |
<var>a</var> · (<var>b</var> · <var>c</var>)</li>
|
|
167 |
<li>∃ <b>e</b> ∈ <var>S</var>: ∀ <var>a</var> ∈ <var>S</var>: <var>a</var> · <b>e</b> ≡ <b>e</b> · <var>a</var> ≡ <var>a</var></li>
|
|
168 |
<li>∀ <var>a</var> ∈ <var>S</var>: ∃ <var>a'</var> ∈ <var>S</var>: <var>a</var> · <var>a'</var> ≡ <b>e</b></li>
|
| 168 | 169 |
</ul>
|
| 169 | 170 |
|
| 170 | 171 |
<p>Every theorem that applies to groups should be easy to modify to be applicable
|
| 171 | |
to a group over an equivalence relation: just replace = with ≡. So what
|
|
172 |
to a group over an equivalence relation: just replace = with ≡. So what
|
| 172 | 173 |
we have, for example, is that while any given <b>e</b> itself might not be unique, the
|
| 173 | |
equivalence class <b>E</b> ⊆ <var>S</var> that contains it is:
|
|
174 |
equivalence class <b>E</b> ⊆ <var>S</var> that contains it is:
|
| 174 | 175 |
<b>E</b> is the only equivalence class that contains
|
| 175 | 176 |
elements like <b>e</b> and, for the purposes of the group, all of these elements are
|
| 176 | 177 |
interchangeable.</p>
|
|
| 253 | 254 |
<table border="1" cellpadding="5">
|
| 254 | 255 |
<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
|
| 255 | 256 |
<tr><td align="center"><code><i>b</i>+</code></td><td align="center"><code>-<i>b'</i></code></td>
|
| 256 | |
<td align="center"><code><i>b</i>+-<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
257 |
<td align="center"><code><i>b</i>+-<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 257 | 258 |
<tr><td align="center"><code><i>b</i>-</code></td><td align="center"><code>+<i>b'</i></code></td>
|
| 258 | |
<td align="center"><code><i>b</i>-+<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
259 |
<td align="center"><code><i>b</i>-+<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 259 | 260 |
<tr><td align="center"><code><i>b</i>></code></td><td align="center"><code><<i>b'</i></code></td>
|
| 260 | |
<td align="center"><code><i>b</i>><<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
261 |
<td align="center"><code><i>b</i>><<i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 261 | 262 |
<tr><td align="center"><code><i>b</i><</code></td><td align="center"><code>><i>b'</i></code></td>
|
| 262 | |
<td align="center"><code><i>b</i><><i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 263 | |
<tr><td align="center"><code><i>b</i>e</code> ≡ <code><i>b</i></code></td><td align="center"><code>e<i>b'</i></code> ≡ <code><i>b'</i>e</code> ≡ <code><i>b'</i></code></td>
|
|
263 |
<td align="center"><code><i>b</i><><i>b'</i></code> ≡ <code><i>b</i>e<i>b'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
264 |
<tr><td align="center"><code><i>b</i>e</code> ≡ <code><i>b</i></code></td><td align="center"><code>e<i>b'</i></code> ≡ <code><i>b'</i>e</code> ≡ <code><i>b'</i></code></td>
|
| 264 | 265 |
<td align="center"><code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 265 | 266 |
</table>
|
| 266 | 267 |
|
|
| 271 | 272 |
<table border="1" cellpadding="5">
|
| 272 | 273 |
<tr><th>Instruction</th><th>Inverse</th><th>Concatenation</th><th>Net effect</th></tr>
|
| 273 | 274 |
<tr><td align="center"><code>+<i>b</i></code></td><td align="center"><code><i>b'</i>-</code></td>
|
| 274 | |
<td align="center"><code>+<i>bb'</i>-</code> ≡ <code>+e-</code> ≡ <code>+-</code></td><td align="center"><code>e</code></td></tr>
|
|
275 |
<td align="center"><code>+<i>bb'</i>-</code> ≡ <code>+e-</code> ≡ <code>+-</code></td><td align="center"><code>e</code></td></tr>
|
| 275 | 276 |
<tr><td align="center"><code>-<i>b</i></code></td><td align="center"><code><i>b'</i>+</code></td>
|
| 276 | |
<td align="center"><code>-<i>bb'</i>+</code> ≡ <code>-e+</code> ≡ <code>-+</code></td><td align="center"><code>e</code></td></tr>
|
|
277 |
<td align="center"><code>-<i>bb'</i>+</code> ≡ <code>-e+</code> ≡ <code>-+</code></td><td align="center"><code>e</code></td></tr>
|
| 277 | 278 |
<tr><td align="center"><code>><i>b</i></code></td><td align="center"><code><i>b'</i><</code></td>
|
| 278 | |
<td align="center"><code>><i>bb'</i><</code> ≡ <code>>e<</code> ≡ <code>><</code></td><td align="center"><code>e</code></td></tr>
|
|
279 |
<td align="center"><code>><i>bb'</i><</code> ≡ <code>>e<</code> ≡ <code>><</code></td><td align="center"><code>e</code></td></tr>
|
| 279 | 280 |
<tr><td align="center"><code><<i>b</i></code></td><td align="center"><code><i>b'</i>></code></td>
|
| 280 | |
<td align="center"><code><<i>bb'</i>></code> ≡ <code><e></code> ≡ <code><></code></td><td align="center"><code>e</code></td></tr>
|
| 281 | |
<tr><td align="center"><code>e<i>b</i></code> ≡ <code><i>b</i></code></td><td align="center"><code><i>b'</i>e</code> ≡ <code>e<i>b'</i></code> ≡ <code><i>b'</i></code></td>
|
|
281 |
<td align="center"><code><<i>bb'</i>></code> ≡ <code><e></code> ≡ <code><></code></td><td align="center"><code>e</code></td></tr>
|
|
282 |
<tr><td align="center"><code>e<i>b</i></code> ≡ <code><i>b</i></code></td><td align="center"><code><i>b'</i>e</code> ≡ <code>e<i>b'</i></code> ≡ <code><i>b'</i></code></td>
|
| 282 | 283 |
<td align="center"><code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 283 | 284 |
</table>
|
| 284 | 285 |
|
|
| 293 | 294 |
the construction of infinite loops that we can't invert by concatenation.</p>
|
| 294 | 295 |
|
| 295 | 296 |
<p>We could insist that all loops be finite, but that would make
|
| 296 | |
Burro less powerful than Brainfuck — it would only be capable of expressing
|
|
297 |
Burro less powerful than Brainfuck — it would only be capable of expressing
|
| 297 | 298 |
the primitive recursive functions. The real challenge is in having Burro be Turing-complete,
|
| 298 | 299 |
like Brainfuck.</p>
|
| 299 | 300 |
|
| 300 | 301 |
<p>This situation looks dire, but there turns out to be a way. What we
|
| 301 | 302 |
do is borrow the trick used in languages like L00P and Version (and probably
|
| 302 | 303 |
many others.) We put a single, implicit loop around the whole program.
|
| 303 | |
(There is a classic formal proof that this is sufficient — the interested
|
|
304 |
(There is a classic formal proof that this is sufficient — the interested
|
| 304 | 305 |
reader is referred to the paper "Kleene algebra with tests"<sup><a href="#1">1</a></sup>,
|
| 305 | 306 |
which gives a brief history, references, and its own proof.)</p>
|
| 306 | 307 |
|
|
| 326 | 327 |
<tr><td align="center"><code>!</code></td><td align="center"><code>!</code></td>
|
| 327 | 328 |
<td align="center"><code>!!</code></td><td align="center"><code>e</code></td></tr>
|
| 328 | 329 |
<tr><td align="center"><code>!<i>b</i></code></td><td align="center"><code><i>b'</i>!</code></td>
|
| 329 | |
<td align="center"><code>!<i>bb'</i>!</code> ≡ <code>!e!</code> ≡ <code>!!</code></td><td align="center"><code>e</code></td></tr>
|
|
330 |
<td align="center"><code>!<i>bb'</i>!</code> ≡ <code>!e!</code> ≡ <code>!!</code></td><td align="center"><code>e</code></td></tr>
|
| 330 | 331 |
<tr><td align="center"><code><i>b</i>!</code></td><td align="center"><code>!<i>b'</i></code></td>
|
| 331 | |
<td align="center"><code><i>b</i>!!<i>b'</i></code> ≡ <code><i>beb'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
332 |
<td align="center"><code><i>b</i>!!<i>b'</i></code> ≡ <code><i>beb'</i></code> ≡ <code><i>bb'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 332 | 333 |
</table>
|
| 333 | 334 |
|
| 334 | 335 |
<p>Seems so. Now we can write Burro programs that halt, and Burro programs that loop
|
|
| 379 | 380 |
semantics of "no-op", then every Burro program has a trivial annihilator: just
|
| 380 | 381 |
tack on an unmatching parenthesis. Similarly, if malformed programs are
|
| 381 | 382 |
considered to loop forever, how do you invert them? So, for these reasons,
|
| 382 | |
Burro has some small amount of syntax — a bit more than Brainfuck is usually
|
|
383 |
Burro has some small amount of syntax — a bit more than Brainfuck is usually
|
| 383 | 384 |
considered to have, but not much.)</p>
|
| 384 | 385 |
|
| 385 | 386 |
<p>Now, it turns out we will have to do a fair bit of work on <code>()</code> in order
|
|
| 387 | 388 |
bit of code that includes <code>()</code>.</p>
|
| 388 | 389 |
|
| 389 | 390 |
<p>We can't just make it a "plain old if", because by the time we've finished executing an "if",
|
| 390 | |
we don't know which branch was executed — so we have no idea what the "right"
|
|
391 |
we don't know which branch was executed — so we have no idea what the "right"
|
| 391 | 392 |
inverse of it would be. For example,</p>
|
| 392 | 393 |
|
| 393 | 394 |
<ul><li><code>(-/e)</code></li></ul>
|
|
| 397 | 398 |
inside the "if"... or is it because it was 1 before
|
| 398 | 399 |
the <code>(</code> was encountered, and decremented to 0 by the <code>-</code>
|
| 399 | 400 |
instruction inside the "if"?
|
| 400 | |
It could be either, and we don't know — so we can't find an inverse.</p>
|
|
401 |
It could be either, and we don't know — so we can't find an inverse.</p>
|
| 401 | 402 |
|
| 402 | 403 |
<p>We remedy this in a somewhat disappointingly uninteresting way: we make a copy of
|
| 403 | 404 |
the value being tested and squirrel it away for future reference, so that pending code
|
|
| 408 | 409 |
It's not a full-bodied continuation, as the term continuation is often used, in the
|
| 409 | 410 |
sense of "function representing the entire remainder of the computation."
|
| 410 | 411 |
But, it's a bit of context that is retained during execution that is intended to affect
|
| 411 | |
some future control flow decision — and that's the basic purpose of a continuation.
|
|
412 |
some future control flow decision — and that's the basic purpose of a continuation.
|
| 412 | 413 |
So, I will call it a continuation, although it is perhaps a diminished sort of continuation.
|
| 413 | 414 |
(In this sense, the machine stack where arguments and
|
| 414 | 415 |
return addresses are stored in a language like C is also a kind of continuation.)</p>
|
|
| 423 | 424 |
<p>To actually accomplish this latter action we need to define the control structure
|
| 424 | 425 |
for undoing conditional tests. We introduce the construct
|
| 425 | 426 |
<code>{\}</code>, which works just like <code>(/)</code>, except that the value that it tests
|
| 426 | |
doesn't come from the tape — instead, it comes from the continuation. We establish similar
|
|
427 |
doesn't come from the tape — instead, it comes from the continuation. We establish similar
|
| 427 | 428 |
syntactic rules about matching every <code>{</code> with a <code>}</code> and an
|
| 428 | 429 |
intervening <code>\</code>, in addition to a rule that says every <code>{\}</code>
|
| 429 | 430 |
must be preceded by a <code>(/)</code>.</p>
|
|
| 434 | 435 |
|
| 435 | 436 |
<p>If the current cell contains 0 after <code>(-/e)</code>, the continuation will contain either
|
| 436 | 437 |
a 1 or a 0 (the original contents of the cell.) If the continuation contains a 0, the "else" part of
|
| 437 | |
<code>{+\e}</code> will be executed — i.e. nothing will happen. On the other hand, if the
|
|
438 |
<code>{+\e}</code> will be executed — i.e. nothing will happen. On the other hand, if the
|
| 438 | 439 |
continuation contains a 1, the "then" part of <code>{+\e}</code> will be executed.
|
| 439 | 440 |
Either way, the tape is correctly restored to its original (pre-<code>(-/e)</code>) state.</p>
|
| 440 | 441 |
|
|
| 513 | 514 |
<table border="1" cellpadding="5">
|
| 514 | 515 |
<tr><th>Instruction</th><th>Inverse</th><th>Test result</th><th>Concatenation</th><th>Net effect</th></tr>
|
| 515 | 516 |
<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>
|
| 516 | |
<td align="center">zero</td><td align="center"><code><i>acdd'c'a'</i></code> ≡ <code><i>acc'a'</i></code> ≡ <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
517 |
<td align="center">zero</td><td align="center"><code><i>acdd'c'a'</i></code> ≡ <code><i>acc'a'</i></code> ≡ <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 517 | 518 |
<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>
|
| 518 | |
<td align="center">non-zero</td><td align="center"><code><i>abdd'b'a'</i></code> ≡ <code><i>abb'a'</i></code> ≡ <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
|
|
519 |
<td align="center">non-zero</td><td align="center"><code><i>abdd'b'a'</i></code> ≡ <code><i>abb'a'</i></code> ≡ <code><i>aa'</i></code></td><td align="center"><code>e</code></td></tr>
|
| 519 | 520 |
</table>
|
| 520 | 521 |
|
| 521 | 522 |
<p>There you have it: every Burro program has an inverse.</p>
|
|
| 542 | 543 |
are placed on the tape initially, starting from the head-start position, extending right.
|
| 543 | 544 |
All unspecified cells are considered to contain 0 initially.</p>
|
| 544 | 545 |
|
| 545 | |
<p>When the program has halted, all tape cells that were "touched" — either given initially as
|
| 546 | |
part of the input, or passed over by the tape head — are output to standard output.</p>
|
|
546 |
<p>When the program has halted, all tape cells that were "touched" — either given initially as
|
|
547 |
part of the input, or passed over by the tape head — are output to standard output.</p>
|
| 547 | 548 |
|
| 548 | 549 |
<p>The meanings of the flags are as follows:</p>
|
| 549 | 550 |
|
|
| 601 | 602 |
to other esolangs in an attempt to understand.</p>
|
| 602 | 603 |
|
| 603 | 604 |
<p>Well, it's not reversible in the sense that
|
| 604 | |
<a href="http://esolangs.org/wiki/Befreak">Befreak</a> is reversible —
|
|
605 |
<a href="http://esolangs.org/wiki/Befreak">Befreak</a> is reversible —
|
| 605 | 606 |
you can't pause it at any point, change the direction of execution, and watch it
|
| 606 | 607 |
"go backwards". Specifically, you can't "undo" a loop in Burro by executing
|
| 607 | 608 |
20 iterations, then turning around and "un-executing" those 20 iterations; instead,
|
|
| 614 | 615 |
the right". But, I haven't pondered on this approach much at all.</p>
|
| 615 | 616 |
|
| 616 | 617 |
<p>Conversely, the concatenation concept doesn't have a clear
|
| 617 | |
correspondence in a two-dimensional language like Befreak — how do you put two programs
|
|
618 |
correspondence in a two-dimensional language like Befreak — how do you put two programs
|
| 618 | 619 |
next to each other? Side-by-side, top-to-bottom? You would probably need multiple
|
| 619 | 620 |
operators, which would definately complicate things.</p>
|
| 620 | 621 |
|
| 621 | 622 |
<p>It's also not reversible in the same way that
|
| 622 | |
<a href="http://esolangs.org/wiki/Kayak">Kayak</a> is reversible —
|
|
623 |
<a href="http://esolangs.org/wiki/Kayak">Kayak</a> is reversible —
|
| 623 | 624 |
Burro programs need not be palindromes, for instance. In fact, I specifically made
|
| 624 | 625 |
the "then" and "else" components of both <code>(/)</code> and <code>{\}</code>
|
| 625 | 626 |
occur in the same order, so as to break the reflectional symmetry somewhat, and
|
|
| 637 | 638 |
in such a way that any previous state of the computation can always be reconstructed
|
| 638 | 639 |
given a description of the current state.</p></blockquote>
|
| 639 | 640 |
|
| 640 | |
<p>Burro appears to qualify by this definition — <em>almost</em>. The requirement
|
|
641 |
<p>Burro appears to qualify by this definition — <em>almost</em>. The requirement
|
| 641 | 642 |
that we can reconstruct <em>any</em> previous state is a bit heavy. We can definately
|
| 642 | 643 |
reconstruct states up to the start of the last loop iteration, if we want to, due to the mechanism
|
| 643 | 644 |
(continuations) that we've defined to remember what the program state was before any given
|