Befunge: An Esoteric Story

June 11, 2018 · Original Post

There are a lot of programming languages out there, all of them interesting in their own way. Most of them are practical and designed to be used to solve actual problems. Others… have a different purpose. These are the esoteric languages. Esolang defines them as:

computer programming language[s] designed to experiment with weird ideas, to be hard to program in, or as a joke, rather than for practical use.

We could interpret this definition as stating that these languages are valueless, but that would be a mistake. The "weird ideas" are often quite fun to play with and can expose us to a new way of thinking. Their value lies in the expansion of what we know to be possible.

One of these languages that I really enjoyed exploring is Befunge, created in 1993 by Chris Pressey. The goal with Befunge was to create a language as difficult to compile as possible. One aspect of the language that lends itself to this goal is dimensionality - that is, an executing program has an instruction pointer that "moves" in cardinal directions as instructions are being processed.

I'm sorry, what?

Before we jump into moving around, let's establish some basics. Befunge is stack oriented – as its instruction pointer moves along, it pushes or pops values to or from the stack, or takes an action on the values at the top of the stack. Here's an example adding 6 and 4:

64+.@

Let's break this down step-by-step. In the following snippets, the down arrow ↓ represents the current position of the instruction pointer, the right arrow → represents the top of the stack, the stack values are within squares brackets [], and $> represents what's been printed to standard output. When the program starts, the instruction pointer is at the far left and moves to the right.

6 is a number literal. Processing this instruction pushes the number 6 onto the stack:
```
  ↓                                           → [6]
  64+.@

  $>
```

4 is also a number literal. Processing this instruction pushes the number 4 onto the stack:

   ↓                                          → [4]
  64+.@                                         [6]

  $>

+ is the addition instruction. It pops the top two values off of the stack, adds them together, and pushes the result, 10, onto the stack:
```
    ↓                                         → [10]
  64+.@

  $>
```
. pops the top value off of the stack and prints it as an integer value to standard output. Our stack is now empty and 10 has been printed:
```
     ↓                                          → []
  64+.@

  $> 10
```

@ terminates execution, halting our program:

      ↓                                         → []
  64+.@

  $> 10

Aren't you supposed to start with Hello, World?

A side effect of using a stack oriented language is that dealing with string literals can be awkward. For example, if our program looks like "Hello, World!", and our instruction pointer is moving left to right, it will add each character of our string to the stack one-by-one, resulting in the character ! being on top. Since operations can only interact with the top of the stack, if we started printing each character, we'd print the whole thing backwards! We could deal with this in our code by writing string literals backwards, or we could go left:

The < instruction tells the interpreter to begin moving left. Since there are no instructions to the left of its current position, it will wrap around to the "end" of the line, processing instructions from right to left:
```
  ↓                                             → []
  <>:#,_@#:"Hello, World!"+64

  $>
```

Our instruction pointer is now at the far right of our program, at the 4, and will travel to the left:

                            ↓                   → [4]
  <>:#,_@#:"Hello, World!"+64

  $>

The next couple of instructions are as we saw previously, adding 6 and 4, resulting in 10 on the stack. Next, the " instruction tells the interpreter to enter string mode:
```
                         ↓                      → [10]
  <>:#,_@#:"Hello, World!"+64

  $>
```

In string mode, every instruction is treated as a character literal and pushed onto the stack. When the next " instruction is encountered, we exit string mode:

           ↓                                    → [H]
  <>:#,_@#:"Hello, World!"+64                     [e]
                                                  [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $>                                              [10]

The : instruction duplicates the value at the top of the stack:

          ↓                                     → [H]
  <>:#,_@#:"Hello, World!"+64                     [H]
                                                  [e]
                                                  [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $>                                              [10]

The # instruction causes the instruction pointer to jump over the next instruction, skipping it entirely:

         ↓                                      → [H]
  <>:#,_@#:"Hello, World!"+64                     [H]
                                                  [e]
                                                  [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $>                                              [10]

This takes us to the _ instruction, which is an if-statement. It pops the top value off of the stack, then moves right if that value is 0 or if the stack was empty, and moves left otherwise:

       ↓                                        → [H]
  <>:#,_@#:"Hello, World!"+64                     [e]
                                                  [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $>                                              [10]

The , instruction pops the top value off the stack and prints it to standard output as an ASCII character:

      ↓                                         → [e]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> H                                            [10]

Here we see # again, which jumps over the next instruction:

     ↓                                          → [e]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> H                                            [10]

> is a close relative of the < we saw earlier. It tells our instruction pointer to begin moving to the right:

   ↓                                            → [e]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> H                                            [10]

Here we see : again, which duplicates the top of the stack. And again, it's followed up with # that skips over the next instruction.

    ↓                                           → [e]
  <>:#,_@#:"Hello, World!"+64                     [e]
                                                  [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> H                                            [10]

Here, for the first time, we have landed on a position we've been before – the _ that is our if-statement. Recall that it will pop the stack and move left, because the value is not 0 or empty:

       ↓                                        → [e]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> H                                            [10]

Now we see , again, which pops the stack and prints the value as an ASCII character:

      ↓                                         → [l]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> He                                           [10]

The # jumps over the next instruction:

     ↓                                          → [l]
  <>:#,_@#:"Hello, World!"+64                     [l]
                                                  [o]
                                                  [,]
                                                  [<space>]
                                                  [W]
                                                  [o]
                                                  [r]
                                                  [l]
                                                  [d]
                                                  [!]
  $> He                                           [10]

Which brings us back to >, sending the instruction pointer back to the right. If this feels like a loop, that's because it is! There is no defined instruction for looping, but we've accomplished it nonetheless:

   ↓                                             → [l]
  <>:#,_@#:"Hello, World!"+64                      [l]
                                                   [o]
                                                   [,]
                                                   [<space>]
                                                   [W]
                                                   [o]
                                                   [r]
                                                   [l]
                                                   [d]
                                                   [!]
  $> He                                            [10]

From here we'll duplicate the top of the stack :, then move on to the if-statement _, which will send us left, print the character, then loop again until the stack is empty.

Note: the value of 10 in ASCII is the newline character, so printing it with the , instruction will output a newline.

Once our stack is empty – we'll have printed each character and our if-statement will send us to the right, landing on the @ instruction, terminating the program.
```
        ↓                                       → []
  <>:#,_@#:"Hello, World!"+64

  $> Hello, World!
  $>
```

Technically a one-liner?

When I introduced Befunge above, I stated we could move in cardinal directions, but so far we've only seen left and right. If we want to go full cardinal, we'll need the ability to move up and down as well.

I'm going to skip the step-by-step analysis for this next example. We've covered most of it already, but the new stuff is:

The v instruction tells the interpreter to begin moving down. Not seen here is ^, which moves us up.
The | instruction is another if-statement, which will move up if the value on top of the stack is non-zero, and down otherwise.
Spaces are ignored - the interpreter will move on to the next instruction.

<                 v
v"Hello, World"+64<
  >,v
>:| >
  @

In this example, the movement instructions are a great indicator as to the flow of our program. Even the if-statements indicate their direction: _ for horizontal and | for vertical. Like arrows pointing the way, we can envision the instruction pointer's path wrapping around, doing a little loop, wrapping again, and repeating. It's an interesting and unorthodox way of reasoning about what a program is accomplishing.

I'm going to stop here, but there're more features to Befunge that you may enjoy exploring on your own (including changing the source code of the program itself, while it's running).

Well then

Befunge is pretty weird and fun and it's amazing that such a language exists. By itself, it's not very useful, but getting exposed to a different way of thinking about programming is certainly valuable.