{"id":804,"date":"2009-09-08T15:21:11","date_gmt":"2009-09-08T15:21:11","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/09\/08\/two-dimensional-pathology-befunge\/"},"modified":"2009-09-08T15:21:11","modified_gmt":"2009-09-08T15:21:11","slug":"two-dimensional-pathology-befunge","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/09\/08\/two-dimensional-pathology-befunge\/","title":{"rendered":"Two-Dimensional Pathology: Befunge"},"content":{"rendered":"

I’m currently away on a family vacation, and as soon as vacation is
\nover, I’m off on a business trip for a week. And along the way, I’ve got some
\ndeadlines for my book. So to fill in, I’m recycling some old posts. I decided
\nthat it’s been entirely too long since there was any pathological programming
\n’round these parts, so I’m going to repost some of my favorites.<\/em><\/p>\n

Today, we’re going to take a look at a brilliant language called Befunge<\/b><\/a>.
\nBefunge is the work of an evil genius named Chris Pressey. <\/p>\n

Normal programming languages are based on a basically one-dimensional
\nsyntax; the program is a string, a sequence of characters, and it’s processed
\nby reading that string in a straight-ahead fashion. But that’s not Befunge!
\nIt’s got a two-dimensional syntax. Befunge is something like a two-dimensional
\nturing machine: the program is written on a two dimensionaltorus<\/em> called the playfield. Each
\ninstruction in Befunge is a single character, and where it’s located on the
\ntorus is crucial – control is going to move either up\/down or left\/right
\non the torus. All of the control flow is expressed by just changing the direction that
\nthe head moves over the torus.<\/p>\n

(In case you’re not familiar with a torus, it’s what you get
\nif you take a very flexible sheet of paper, and roll it so that you connect
\nthe top edge to the bottom, and then roll that tube so that you connect the
\nleft edge to the right. You get a donut shape where moving up from what used
\nto be the top of the page puts you on the bottom of the page; moving left from
\nthe left edge of the page puts you on the right.) <\/p>\n

<\/p>\n

The basics of computation in Befunge are pretty straightforward. It’s a
\nstack based language. Operations take their parameters from the stack, and
\nleave their results on the stack. Nothing too complicated there. There are
\narithmetic operators, IO operators, control flow operators, all operating on
\nthe values on the stack. <\/p>\n

The arithmetic operators are the usual kinds of things: There are
\noperators for addition (+), subtraction (-), division (\/), multiplication (*),
\nmodulo (%), and logical negation (!). Digit characters are treated as
\noperators that push the numeric value of the digit onto the stack. (So “99”
\nwill create a stack with two nines.) Comparisons are done using “`”, which
\npops the top two values from the stack and compares them. So if the top of the
\nstack was “x”, and the value beneath it was “y”, then “`” would leave a “0” on
\nthe stack if x≤y, and 1 if x > y. <\/p>\n

For IO, there are four operators. “&” reads an integer from standard input
\nand pushes it onto the stack. “~” reads a single character from standard
\ninput, and leaves it on the stack. “.” pops a value off the stack and writes
\nit to standard out as an integer. “,” pops a value off the stack and writes it
\nto standard out as a character. <\/p>\n

Of course, we can’t have a stack-based language without some stack
\noperators: “:” makes a duplicate of the top value on the stack; “$” discards
\nthe top value on the stack; “” swaps the top two values of the stack.<\/p>\n<\/p>\n

So far, nothing has looked particularly pathological – in fact, nothing
\neven looks particularly strange, other that the fact that it’s pretty
\nillegible because of the single-character operators. But now, we get to
\ncontrol flow, and that<\/em> is where the insanity\/brilliance of Befunge
\nreveals itself. <\/p>\n

In Befunge, there’s a read-head that moves over the program. Each step, it
\nexecutes the instruction under the head. But instead of just moving left or
\nright, it can move left, right, up, or down. “>” is an instruction that tells
\nthe head to start moving to the right; “<” tells the head to start moving
\nleft; “^” means start moving up, and “v” means to start moving down. So, for
\nexample: <\/p>\n

\n>v\n^<\n<\/pre>\n
 Is a program that runs an infinite loop: the head will just cycle over
\nthose four characters. An even more interesting infinite loop (taken from the
\nbefunge documentation) is:<\/p>\n
\n>v>v\n>^\n^  <\n<\/pre>\n
 Conditionals work by picking the direction that the head will move: “_” pops the stack, and if the value is zero, then it makes the head move right (“>”); if it’s non-zero, it makes the head move left (“<"). Similarly, "|" pops a value, and makes the head move up if the value was non-zero, or down if it was zero.  To make things confusing, "#" means "skip the next instruction." (Actually, it's important for when a vertical and horizontal control flow cross.) And finally,
\n"@" is the exit command; it makes the head stop, and the program halt.\n<\/p>\n
 There’s also a little hack for strings. A double-quote character (“)
\nstarts a string; when one is encountered, the head keeps moving in the same
\ndirection, but instead of executing the characters as instuctions, it just
\npushes the character values onto the stack. When the second quote is found, it
\ngoes back to executing instructions.<\/p>\n
 Finally, just in case the basic two dimensional flow control isn’t
\npathological enough, there are two instructions for modifying cells on the
\nplayfield! “g” pops an X and Y value off the stack, and pushes the character
\nat (X,Y) onto the stack; “p” pops an X, Y, and a character off the stack, and
\nwrites the character onto location (X,Y) of the playfield. (The coordinates
\nare relative to the cell where the program started.)<\/p>\n
 So, let’s look at a couple of befunge programs. As usual, we start with
\nthe good old “hello world”.<\/p>\n
\nv\n>v\"Hello world!\"0<\n,:\n^_25*,@\n<\/pre>\n
We start at the top left, head moving right. It moves until it hits the “v”
\ncharacter, which makes it go down; then “<” makes it go left. 0 pushes a zero
\nonto the stack. Then we’ve got a quote – so it starts pushing characters onto
\nthe stack until the next quote. When we get to the next quote, if we wrote the
\nstack so that the top comes first, it would look like : (‘H’ ‘e’ ‘l’ ‘l’ ‘o’ ‘
\n‘ ‘w’ ‘o’ ‘r’ ‘l’ ‘d’ ‘!’ 0 ).<\/p>\n
 Then we hit a “v” which makes the head go down. This is the beginning of a
\nloop; the leftmost two characters of rows 2, 3, and 4 are a while loop! The
\nhead goes down to “:” which duplicates the top of the stack; then it hits “_”,
\nwhich turns left if the value on top of the stack is not zero; then the head
\nturns up, outputs a character, turns right, and we’re back at the start of the
\nloop. So the loop will output each character until we get the the “0” we
\npushed before the string; then at the “_”, we turn right. 2 and 5 are pushed
\non the stack and multiplied, leaving a 10, which is the linefeed character
\n(basically “n” for you C weenies). It outputs the linefeed, and then exits.\n<\/p>\n
 How about a truly pathological example? Here’s a self-reproducing program
\nin 12 bytes.<\/p>\n
 :0g,:93+`#@_1+ <\/pre>\n
Stepping through that:<\/p>\n
    \n
  1.  Dup the value on top of the stack.
    \nThat’ll produce a “0” if the stack is empty. (So first pass, stack=[0])<\/li>\n
  2.  “0” Push a zero on the stack. (First pass, stack=[0,0])<\/li>\n
  3.  “g”: Fetch the value at (x,y) on the stack; that’s (0,0) initially.
    \n(First pass, stack = [‘:’])<\/li>\n
  4.  “,”: Output it. So we printed the character at (0,0) (First pass, stack
    \n= [])<\/li>\n
  5.  “:” dup the stack top again. (First pass, stack = [0])<\/li>\n
  6.  “93+”. Get the number 12 onto the stack. (First pass, stack = [12,0])<\/li>\n
  7.  Compare what was on top of the stack to twelve. Leave a 0 there if it
    \nwas, or a 1 if it wasn’t. (First pass, stack = [0]).<\/li>\n
  8.  “#” skip over the next character.<\/li>\n
  9.  “_” go right if the top of stack is zero; left if it’s one. So if the
    \nvalue copied by the second “:” was greater than 12, then go left (in which
    \ncase you hit “@” and halt); otherwise, keep going right.<\/li>\n
  10.  “1+”: add one to the top of the stack (First pass, stack = ([1])). Then
    \nkeep going right until you hit the right edge, and the you jump back to the
    \nleft edge, so you’re at the first “:” again.<\/li>\n
  11.  Now the whole thing repeats, except that there’s a one on the stack. So
    \nthe “g” will fetch (1,0); the “12” will be compared to 1, and the “1+” on the
    \nend will leave “2” on the stack. So now it fetches and outputs (2,0). And so
    \non, until it reaches the “(_)” after outputting (12,0), when it halts. <\/li>\n<\/ol>\n
     One more, which I’ll let you figure out for yourself. Here’s a program
    \nthat prompts you for a number, and computes its factorial:<\/p>\n
    \nv\n>v\"Please enter a number (1-16) : \"0<\n,:             >$*99g1-:99p#v_.25*,@\n^_&:1-99p>:1-:!|10          <\n^     <\n<\/pre>\n
     So is Befunge Turing complete? The answer is less obvious than many other programming
    \nlanguages. In fact, it was a point of debate in the esolang community for a while.
    \nThe ultimate answer is that if<\/em> the stack can contain arbitrarily large
    \nnumbers, then it’s Turing complete. Otherwise, you’re stuck in pushdown-automata
    \nland. You’ve got unbounded storage on the stack, but you can only access
    \nthe top two elements – so you’ve got no random-access storage. If you’ve
    \ngot arbitrarily large numbers, you can put together a scheme for random-access
    \nstorage using data encoded into those big numbers. Want proof?<\/p>\n
    \n<v+**44_v        v88+*<v:!-\".\":!-\",\":!-\">\":!-\"<\":!-\"-\":!-\"+\":!-\"!\":~<+8\n0> :7`!^         >4**-v*>\"[\"-!\"]\"-!#v_  #v_  #v_  #v_  #v_  #v_  #v_  #v_!#^_\nv     $<             #*             >1+$>1+$>1+$>1+$>1+$>1+$>1+$>   ^\n>0:44*>\/44*%:7`#v_:00p8+44**>+:1`#v_$:888**\/888>**%:884**`!#v_        v\n      ^ *44:_@#:<    #^88$< ^ **44<                ^ 888\/**888:<         0\n$00g1-:0`#v_1-:0`#v_1-:0`#^_1-:0`#v_1-:0`#v_1-:0`#v_1-0`#v_v            >\nv_v        >$1+v -1$< $>      v+**488$<    v~<    v,:$<            >:884**`## <            >884**%       >>            >        >     >888* * *+^ +***888$:0:44*\/>44*%:7`#v_44*>*+:1`v        ^  p80+**562<0_^#!:  < :            v^           ^ \/*44:<     ^*44-8_$:44*>\/44*%:7`v ^2_^#      <            $`#v_8>+1`#v_v                            ^*44:    _$1:7>6+`!#v_77+`#v_1-:0\n-1<  ^8**44< +                                              ^ 7:$<1  <+1<\n^     0p80*84<\n$:0:44*>\/44*%:7`#v_44*>*+:1`v                                            >\n^ *44:    <     ^*44-8_$:44*>\/44*%:7`v\n#v_1-:#v_$\/8>44*\/:0`#v_$>`  #v_v       ^*44:    _44**+:1:4>4*%:5`!#v_6`!\n<   -1<    ^  +8**44<  ^+8**44< +                             ^ 4:\/*44$< 0+1\n^                         p80*84<\n<\/pre>\n
     That mess is a Brainfuck interpreter written in Befunge! And since
    \nBrainfuck is Turing complete, so is Befunge with bignums. Unfortunately, the
    \nsite from which I downloaded that was a geocities page that I can’t seem to access
    \nanymore. (If you know who the author is, please let me know so that I can provide
    \nattribution.)<\/p>\n","protected":false},"excerpt":{"rendered":"
    I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any […]<\/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-804","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-cY","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/804","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=804"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/804\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=804"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=804"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=804"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}