I'm sure that in the friday pathological programming languages, I have a fondness for languages
that make your code beautiful: languages like [SNUSP][snusp], [Befunge][befunge], [Piet][piet], and such. Those languages all you two-dimensional layouts for their programs.
[snusp]: http://scienceblogs.com/goodmath/2006/08/beautiful_insanity_pathologica…
[befunge]: http://scienceblogs.com/goodmath/2006/07/friday_pathological_programmin…
[piet]: http://scienceblogs.com/goodmath/2006/11/programming_in_color_fixed.php
Among the nutters that make up the community of folks interested in this kind of thing, looking
at these languages led to a theoretical question, which was named *"the wire-crossing problem"*. The
basic question was:
>Is it possible to define a two-dimensional flow-based language which does *not* ever need
>one execution path to *cross* another execution path?
Alternatively:
>Is it possible to express every computable function as a two-dimensional graph
>where no edges ever cross?
This question raged for quite a while without an answer. Todays pathological language is
a very simple language designed for the sole purpose of demonstrating, once and for all, that
*yes*, you can write every computable function with no wire-crossing.
The language is called [Archway2][Archway2]. It's a very simple [Brainfuck][bf] derivative
that uses a two-dimensional program representation, and which has a regular translation
from brainfuck syntax to Archway2 syntax that does not require any wire crossing. Since BrainFuck is Turing complete, that means that every function *can* be written in Archway2 *without* wire-crossing by writing it in Brainfuck, and using the wire-cross-free translation to Archway2.
Like BrainFuck, Archway2 has 8 commands, but they're laid out in 2-dimensional format. execution
starts at the *bottom left* with the instruction pointer moving *right*. Any character that isn't a command is a no-op; if the instruction pointer exits the rectangular grid containing the program,
it halts.
Of the eight commands in Archway2, the first six are exactly the same as BF.
1. "`<`": move the tape-cell pointer left.
2. "`>`": move the tape-cell pointer right.
3. "`+`": add one to the current tape cell.
4. "`-`": subtract one from the current tape cell.
5. "`,`": read a byte from the input and write it into the current tape cell.
6. "`.`": write the value on the current tape cell to the output.
The last two are replacements for the looping operators "`[`" and "`]`" in BrainFuck. As a reminder, in BF, "`[`" means "if the current tape cell contains the value 0, jump to the statement after the matching "`]`", and "`]`" means if the current tape cell does *not* contain the value 0, jump
back to the statement after the matching "`[`".
In Archway2, the bracket loop controls are replaced by *directional* controls:
* "`\`": LURD (left-up,right-down); if the current tape cell contains 0, do nothing (execution continues moving in the same direction); otherwise, if the current execution direction is left, switch to up, right switch to down, down switch to right, and up switch to left.
* "`/`": RULD (right-up,left-down); if the current tape cell contains 0, do nothing (execution continues moving in the same direction); otherwise, if the current execution direction is right, switch to up, left switch to down, down switch to left, and up switch to right.
The trick that makes it work is that the the directional controls are very special. They *don't* run
when the cursor reaches them. If the cursor lands *on top of* a directional command, it's
treated as a no-op. But when it's executing any command, it looks at the *next* cell in the current direction, and if it's either LURD or RULD, then the effect of LURD or RULD is *added* to the
effect of the current cell.
So, for example, suppose in the code below, we were starting execution at the "$" moving right.
.. + $ +++/
What this will do is run the three "+" commands, so that the current tape cell contains the value
"3". Then it will switch direction to move *up*. If it did the RULD direction switch *on* the "`/`"
character, it would execution the fourth "+", and output 4. But the direction switch happens on the
cell "before" the RULD (that is, on the third "+"), so the program outputs "3".
There aren't many (or indeed *any*) interesting programs in Archway2; after all, it's just an awkward alternate syntax for Brainfuck. So any BF program can be translated into Archway2. The interesting
this is: how can we translate BF code into Archway2?
For everything except the loop commands, there *is* no translation at all; the BF and the Archway
commands are *exactly* the same. So the only question concerns loops.
Suppose we have a Brainfuck program, where "a", "b", "c", and "d" represent chunks of *non-looping* Brainfuck code. Then the Brainfuck program "`a[bc]d`" would turn into the following Archway2:
\
//
/ bc/+\
-a/\ + -d
+/ \
A quick walkthrough to help you understand it:
1. Add one to the current tape cell (making it non-zero); and then executing the RULD that's in the next cell. This causes the program to turn and start executing upwards.
2. No-op, but there's a RULD in the next cell, so turn right.
3. Subtract one from the current cell; this undoes the earlier increment, so we've got a blank tape like we did before the two direction changes that got us here. So we're reading to execute "a" with
a blank tape.
4. Execute a. At the end of it, if the current tape cell is zero, we just keep moving right; that will execute a "+" and a "-" which cancel each other, and then run "d", and terminate.
5. If the current cell was *not* zero after "a", then we switch upward, and do a NOP followed
by a RULD, and turn right, executing "b" and "c".
6. If the tape is zero, keep going right; do a plus, turn down, turn right, do a "-" (cancelling the earlier plus), execute "d" and then terminate.
7. If the tape after running "b" and "c" is non-zero, we turn up, do a couple of NOPs, turn left,
then turn down, so that we land back on the B. And we keep going.
It's mostly pretty simple - the trick is a combination of two things: using the lookahead property of Archway2, which gives us a bit of room to breathe; and relying to being able to much about with one of the tape cells without damaging anything. But since we always "undo" whatever we did to the cell - and after starting the program, we *only* actually use the cell after a test in which it was zero,
we can show that we never damage the state.
Just for kicks, let's look at one translation of a real program.
Here's a program that reverses its input, written in BF: "`>,[>,]<[.<]`".
We'll translate to Archway in two steps. First, a="`>,`" bc="`>,`", and d="`<[.<]`". So:
\
//
/ >,/+\
->,/\ + - <[.<]
+/ \
Now, we move over to the right, and look at translating the "d" part; a="`<`", bc="`.<`", and d="". So, we wind up with:
\
\ //
// / .</+\
/ >,/+\ -</\ + -
->,/\ + - +/
+/ \
And poof! The line-crossing problem is solved - at the cost of taking an already
unreadable line-noise language, and making it *even more* cryptic than it already was.
[Archway2]: http://www.esolangs.org/wiki/Archway
[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr…
- Log in to post comments
I really like the image of your first example code. If your rotate it through 90 you practically get an if/then/else statement:
+
+
+ .
\+.
looks like
if cond then do sth
else do sth'
Arrgh. Somebody changed your blog software so it takes over the entire screen of my browser when I look at it. This is a damn nuisance when my blog reader (NewsFox in Firefox) uses frames. Can you get that fixed? I dropped Seed magazine from the list of blogs I look at because of this behaviour.
Although I'm not certain of the exact definition of flow crossing in this context, you can also convert BrainF*ck programs into SNUSP programs in a similar manner.
a[bc]d turns into
a!/=?\d
\cb/
with c and b in reverse order, and this can, of course, be done recursively. I have a program on my website that does this: http://www.baumanfamily.com/john/bf2snusp.py
Note that one can exactly measure the line-crossing problem in Cartesian 2-space:
Wagner, Uli and Weisstein, Eric W. "Rectilinear Crossing Number." From MathWorld--A Wolfram Web Resource.
This has been addressed in the context of how brains work in Flatland, and alternative solutions have been given such as special crossing-cells that add a few states but allow horizontal and vertical signals to cross without interference.
Such solutions demolish a kind of dimensional Anthropic principle, which held that our universe has 3 spatial dimensions because otherwise brains couldn't work in the observers. [laughs].
Similar arguments claim that there must be an odd number of spatial dimensions for wave equations to work properly.
I had an interesting discussion with Lisa Randall once that 3- and 7-dimensional spaces are important because only they have cross products. She had just emphasized 3- and -7-brane theories in cosmology. She dismissed my comment as mere coincidence. But I still wonder...
At the risk of stating the obvious, you can simulate wire-crossing in a non-wire-crossing language.
Von Neumann automata (arguably one of the earliest pathological languages!), for example, invented the "coded channel". The basic idea is that you have a ring-shaped communication channel, with transceivers attached which transmit specific codes, and recognise others. You can send a bit of information by transmitting a code onto the channel and, when the receiver matches it, it transmits a bit on the other side.
In a way, this is the predecessor of Ethernet, with frames being only one bit in size.
I'm looking forward to a three-dimensional computer language.
I have been working sporadically on a 3-dimensional computer language. Somewhere in Good Math/Bad Math I gave examples of a growing 3-D array of integers with a read-write head that moves in 3-D according to the integers already written, and then re-read. In ASCII, it's awkward to have to show this slice-by-slice. The universe may have at least 3 spacial dimensions, but the paper and computer screens we use in describing it have just 2 spacial dimensions. If we meet extraterrestrial civilizaqtions that have a 3-D spoken and written language, we are in bad shape. There is a theory, by the way, that dolphons can transmit 3-D acoustic holograms to each other.
John Baez et al. point out at The n-Category Cafe
"one could use 3-dimensional structures to understand the process of computation. A key figure in this line of work is Yves Guiraud, and he just put some of his papers on this topic on the arXiv":
* Yves Guiraud, Termination orders for 3-dimensional rewriting, Journal of Pure and Applied Algebra 207 (2006), 341-371.
* Yves Guiraud, Termination orders for 3-polygraphs, Comptes-Rendus de l'Academie des Sciences Serie I, 342 (2006), 219-222.
* Yves Guiraud, Two polygraphic presentations of Petri nets, Theoretical Computer Science 360 (2006), 124-146.
* Yves Guiraud, The three dimensions of proofs, Annals of Pure and Applied Logic 141 (2006), 266-295.