I’m sure that in the friday pathological programming languages, I have a fondness for languages
\nthat make your code beautiful: languages like [SNUSP][snusp], [Befunge][befunge], [Piet][piet], and such. Those languages all you two-dimensional layouts for their programs.
\n[snusp]: http:\/\/scienceblogs.com\/goodmath\/2006\/08\/beautiful_insanity_pathologica.php
\n[befunge]: http:\/\/scienceblogs.com\/goodmath\/2006\/07\/friday_pathological_programmin.php
\n[piet]: http:\/\/scienceblogs.com\/goodmath\/2006\/11\/programming_in_color_fixed.php
\nAmong the nutters that make up the community of folks interested in this kind of thing, looking
\nat these languages led to a theoretical question, which was named *”the wire-crossing problem”*. The
\nbasic question was:
\n>Is it possible to define a two-dimensional flow-based language which does *not* ever need
\n>one execution path to *cross* another execution path?
\nAlternatively:
\n>Is it possible to express every computable function as a two-dimensional graph
\n>where no edges ever cross?
\nThis question raged for quite a while without an answer. Todays pathological language is
\na very simple language designed for the sole purpose of demonstrating, once and for all, that
\n*yes*, you can write every computable function with no wire-crossing.<\/p>\n
\nThe language is called [Archway2][Archway2]. It’s a very simple [Brainfuck][bf] derivative
\nthat uses a two-dimensional program representation, and which has a regular translation
\nfrom 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.
\nLike BrainFuck, Archway2 has 8 commands, but they’re laid out in 2-dimensional format. execution
\nstarts 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,
\nit halts.
\nOf the eight commands in Archway2, the first six are exactly the same as BF.
\n1. ““”: move the tape-cell pointer right.
\n3. “`+`”: add one to the current tape cell.
\n4. “`-`”: subtract one from the current tape cell.
\n5. “`,`”: read a byte from the input and write it into the current tape cell.
\n6. “`.`”: write the value on the current tape cell to the output.
\nThe 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
\nback to the statement after the matching “`[`”.
\nIn Archway2, the bracket loop controls are replaced by *directional* controls:
\n* ““”: 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.
\n* “`\/`”: 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.
\nThe trick that makes it work is that the the directional controls are very special. They *don’t* run
\nwhen the cursor reaches them. If the cursor lands *on top of* a directional command, it’s
\ntreated 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
\neffect of the current cell.
\nSo, for example, suppose in the code below, we were starting execution at the “$” moving right.<\/p>\n
\n..\n+\n$ +++\/\n<\/pre>\nWhat this will do is run the three “+” commands, so that the current tape cell contains the value
\n“3”. Then it will switch direction to move *up*. If it did the RULD direction switch *on* the “`\/`”
\ncharacter, it would execution the fourth “+”, and output 4. But the direction switch happens on the
\ncell “before” the RULD (that is, on the third “+”), so the program outputs “3”.
\nThere 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
\nthis is: how can we translate BF code into Archway2?
\nFor everything except the loop commands, there *is* no translation at all; the BF and the Archway
\ncommands are *exactly* the same. So the only question concerns loops.
\nSuppose 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:<\/p>\n\n\n\/\/\n\/ bc\/+\n-a\/ + -d\n+\/ \n<\/pre>\nA quick walkthrough to help you understand it:
\n1. 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.
\n2. No-op, but there’s a RULD in the next cell, so turn right.
\n3. 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
\na blank tape.
\n4. 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.
\n5. If the current cell was *not* zero after “a”, then we switch upward, and do a NOP followed
\nby a RULD, and turn right, executing “b” and “c”.
\n6. 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.
\n7. If the tape after running “b” and “c” is non-zero, we turn up, do a couple of NOPs, turn left,
\nthen turn down, so that we land back on the B. And we keep going.
\nIt’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,
\nwe can show that we never damage the state.
\nJust for kicks, let’s look at one translation of a real program.
\nHere’s a program that reverses its input, written in BF: “`>,[>,]<[.,`” bc=”`>,`”, and d=”`<[.<]`". So:<\/p>\n\n\n\/\/\n\/ >,\/+\n->,\/ + - <[.<]\n+\/ \n<\/pre>\nNow, we move over to the right, and look at translating the “d” part; a=”`<`", bc="`.<`", and d="". So, we wind up with:<\/p>\n
\n\n \/\/\n\/\/ \/ .<\/+\n\/ >,\/+ -<\/ + -\n->,\/ + - +\/\n+\/ \n<\/pre>\nAnd poof! The line-crossing problem is solved – at the cost of taking an already
\nunreadable line-noise language, and making it *even more* cryptic than it already was.
\n[Archway2]: http:\/\/www.esolangs.org\/wiki\/Archway
\n[bf]: http:\/\/scienceblogs.com\/goodmath\/2006\/07\/gmbm_friday_pathological_progr.php<\/p>\n","protected":false},"excerpt":{"rendered":"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.php [befunge]: http:\/\/scienceblogs.com\/goodmath\/2006\/07\/friday_pathological_programmin.php [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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-230","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3I","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/230","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=230"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/230\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=230"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}