Friday Pathological Programming: Befunge, the 2-dimensional language

Today, we’re going to take a look at a brilliant language called Befunge. Befunge is the work of an evil genius named Chris Pressey.

Normal programming languages are based on a basically one-dimensional syntax; the program is a string, a sequence of characters, and it’s processed by reading that string in a straight-ahead fashion. But that’s not Befunge! Befunge is something like a two-dimensional turing machine: it says that the program and data are written on a two dimensionaltorus. Each instruction in Befunge is a single character, and where it’s located on the torus is crucial. (In case you’re not familiar with a torus, it’s what you get if you take a very flexible sheet of paper, and roll it so that you connect the top edge to the bottom, and then roll that tube so that you connect the left edge to the right. You get a donut shape where moving up from what used to be the top of the page puts you on the bottom of the page; moving left from the left edge of the page puts you on the right.) This torus is called the playfield.

The basics of computation in Befunge are pretty straightforward. It’s a stack based language. Operations take their parameters from the stack, and leave their results on the stack. Nothing too complicated there. There are arithmetic operators, IO operators, control flow operators, all operating on the values on the stack.

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

For IO, there are four operators. “&” reads an integer from standard input and pushes it onto the stack. “~” reads a single character from standard input, and leaves it on the stack. “.” pops a value off the stack and writes it to standard out as an integer. “,” pops a value off the stack and writes it to standard out as a character.

Of course, we can’t have a stack-based language without some stack operators: “:” makes a duplicate of the top value on the stack; “$” discards the top value on the stack; “” swaps the top two values of the stack.

So far, nothing has looked particularly pathological – in fact, nothing even looks particularly strange, other that the fact that it’s pretty illegible because of the single-character operators. But now, we get to control flow, and that is where the insanity/brilliance of Befunge reveals itself.

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

>v
^<

Is a program that runs an infinite loop: the head will just cycle over those four characters. An even more interesting infinite loop (taken from the befunge documentation) is:

>v>v
>^
^  <

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,
"@" is the exit command; it makes the head stop, and the program halt.

There’s also a little hack for strings. A double-quote character (“) starts a string; when one is encountered, the head keeps moving in the same direction, but instead of executing the characters as instuctions, it just pushes the character values onto the stack. When the second quote is found, it goes back to executing instructions.

Finally, just in case the basic two dimensional flow control isn’t pathological enough, there are two instructions for modifying cells on the playfield! “g” pops an X and Y value off the stack, and pushes the character at (X,Y) onto the stack; “p” pops an X, Y, and a character off the stack, and writes the character onto location (X,Y) of the playfield. (The coordinates are relative to the cell where the program started.)

So, let’s look at a couple of befunge programs. As usual, we start with the good old “hello world”.

v
>v"Hello world!"0<
,:
^_25*,@

We start at the top left, head moving right. It moves until it hits the “v” character, which makes it go down; then “<" makes it go left. 0 pushes a zero onto the stack. Then we've got a quote – so it starts pushing characters onto the stack until the next quote. When we get to the next quote, if we wrote the stack so that the top comes first, it would look like : ('H' 'e' 'l' 'l' 'o' ' ' 'w' 'o' 'r' 'l' 'd' '!' 0 ).

Then we hit a “v” which makes the head go down. This is the beginning of a loop; the leftmost two characters of rows 2, 3, and 4 are a while loop! The head goes down to “:” which duplicates the top of the stack; then it hits “_”, which turns left if the value on top of the stack is not zero; then the head turns up, outputs a character, turns right, and we’re back at the start of the loop. So the loop will output each character until we get the the “0” we pushed before the string; then at the “_”, we turn right. 2 and 5 are pushed on the stack and multiplied, leaving a 10, which is the linefeed character (basically “n” for you C weenies). It outputs the linefeed, and then exits.

How about a truly pathological example? Here’s a self-reproducing program in 12 bytes.

:0g,:93+`#@_1+

Stepping through that:

  1. Dup the value on top of the stack. That’ll produce a “0” if the stack is empty. (So first pass, stack=[0])
  2. “0” Push a zero on the stack. (First pass, stack=[0,0])
  3. “g”: Fetch the value at (x,y) on the stack; that’s (0,0) initially. (First pass, stack = [‘:’])
  4. “,”: Output it. So we printed the character at (0,0) (First pass, stack = [])
  5. “:” dup the stack top again. (First pass, stack = [0])
  6. “93+”. Get the number 12 onto the stack. (First pass, stack = [12,0])
  7. Compare what was on top of the stack to twelve. Leave a 0 there if it was, or a 1 if it wasn’t. (First pass, stack = [0]).
  8. “#” skip over the next character.
  9. “_” go right if the top of stack is zero; left if it’s one. So if the value copied by the second “:” was greater than 12, then go left (in which case you hit “@” and halt); otherwise, keep going right.
  10. “1+”: add one to the top of the stack (First pass, stack = ([1])). Then keep going right until you hit the right edge, and the you jump back to the left edge, so you’re at the first “:” again.
  11. Now the whole thing repeats, except that there’s a one on the stack. So the “g” will fetch (1,0); the “12” will be compared to 1, and the “1+” on the end will leave “2” on the stack. So now it fetches and outputs (2,0). And so on, until it reaches the “(_)” after outputting (12,0), when it halts.

One more, which I’ll let you figure out for yourself. Here’s a program that prompts you for a number, and computes its factorial:

v
>v"Please enter a number (1-16) : "0$*99g1-:99p#v_.25*,@
^_&:1-99p>:1-:!|10          <
^     <

0 thoughts on “Friday Pathological Programming: Befunge, the 2-dimensional language

  1. Janne

    Thank you for the tour! You actually managed to make Befunge seem almost rational.
    I can’t wait for your explanation of Intercal 🙂

    Reply
  2. Daniel Martin

    Well, he already dismissed intercal in the comments to his previous post.
    I still want to see his writeup on Lazy-K, or maybe on the one instruction-set computer. (By the way, I’ve found reference to that in an ACM article from 1988, so it predates bf, but of course does not predate P” on which bf might be said to be based) And I’ll be really impressed if he lays a few Malbolge programs on us. (Although Malbolge is more an example of recreational cryptography than anything like programming per se)
    I seem to recall that the MIT Mystery Hunt a few years ago featured a bunch of esoteric programming languages… ah, there we are: Round two, puzzle 5 of 2002. The two pathological languages featured here so far are of course represented.

    Reply
  3. Mark C. Chu-Carroll

    Sorry guys, but I really *hate* intercal. The kinds of things that attract me to esoteric languages is that they have some kind of interesting idea behind them. It’s not necessarily a *good* idea, or a *useful* idea, but there’s some gem of beauty or elegance.
    Brainfuck has a beautiful mechanism – it’s almost like programming a cross between a turing machine and a minsky machine. It’s simple and consistent, with the flavor of the theoretical machines that CS folks are stuck dealing with.
    Befunge runs with the idea of two-dimensional layout: where you put things is as important as what they are. It makes a befunge program into a mix of programming and art. There are some truly beautiful befunge programs!
    Languages I’m looking forward to hitting are (among others) Iota (event systems), lazy-K (pure SKI combinator calculus), Rube (Something like a cellular automata language), Smith (a turing complete language with absolutely *no* jumps, *no* branches, *no* conditionals). And a few others.

    Reply
  4. Janne

    OK, I understand about Intercal. That said, you could make an argument that the beauty of Intercal, the idea it tries to encapsulate, is the questioning of a lot of implicit assumptions about how we view languages. Do languages actually have to be deterministic; do they have to be expressed in the imperative tense when ordinary languages rarely use it; do control flow statement have to be expressed from the viewpoint of the actor/execution pointer?

    Reply
  5. Ithika

    Could someone explain the while-loop part to me in the Hello World example. It seems to me that the process goes like:
    1. Fill stack with desired string [‘H’,’e’,’l’ …]
    2. Dupe top value on stack [‘H’,’H’,’e’,’l’ …]
    3. Cmp top of stack with zero; move left [‘H’,’H’,’e’,’l’ …]
    4. Print top of stack [‘H’,’H’,’e’,’l’ …]
    Won’t this just fill up the stack with whatever appears at the top, if the old stuff doesn’t get popped? Or do (:) and (,) also discard their values?

    Reply
  6. matt

    Did you see this year’s ICFP contest? There were a couple interesting pathalogical languages: A term rewriting system (with an evil twist), and an ascii art language.
    Also there was a funny implementation of BASIC where all the numbers were roman numerals!

    Reply
  7. Xanthir

    I like the Piet language. It’s essentially a Befunge variant, but rather than read characters off of a textfile, it reads color transitions off of a bitmap. As the readhead moves around the picture, the magnitude of the color change between colored zones defines a command, which can manipulate the stack or change the direction of the readhead.
    With some ingenuity, you can pull out some quite pretty programs. There are several variants of Hello World on DangerMouse’s site, located here:
    http://www.dangermouse.net/esoteric/piet/samples.html

    Reply
  8. Nathanael Nerode

    The great idea in Intercal is COME FROM. Well, OK, it’s only a great idea when it’s used in *threaded Intercal* for parallel programming. There it’s really worth thinking about.

    Reply
  9. llewelly

    The great idea in Intercal is COME FROM.

    COME FROM inspired the semantics of exception handling in several popular programming languages. However, historians of computer programming languages are so ashamed of this fact that they will strenuously deny it. Worse, only 23 days ago, a paper establishing this historical fact was published in History Of Programming Languages, but it was immediately expunged from the records. If you don’t believe me, try reading some Java code out loud, replacing each instance of ‘catch’ or ‘finally’ with ‘come from’ .

    Reply

Leave a Reply