Dorian Brown

Finding signal and escaping the noise

Rube Goldberg Machine of Coding Languages
April 5, 2018
Categories:
Programming

Opening Remarks

Recently I stumbled onto an article about the well-known Brainfuck coding language, and I found it fascinating that someone would spend time and energy to create a totally impractical programming language.

To quote the wikipedia page on befunge:

… it is not intended for practical use, but to challenge and amuse programmers.

After further reading I found out Brainfuck is what some people call an “esoteric programming language”. Although it was one of the first and most (in)famous, there are many more of these wacky creations.

And while browsing through this list of monstrosities, I discovered the beautiful and weird language that is Befunge.

Hello Befunge

Let’s get down to how Befunge works. The easiest way to explain how it’s run by an interpreter, is to show a working example. What way is better than a Hello World program:

The stack is LIFO, so we need to reverse the text

There are a few things to notice here:

  1. Code is interpreted by the orange cursor, which starts at the top left cell moving to the right. When it moves across a character, something happens.
  2. A " character initiates a string, until the cursor encounters another one. Within a string any characters encountered are put onto a stack, letter by letter. These are used when a print statement is called.
  3. The , character is a kind of print or echo. It removes the first character in the stack, and prints it to the console.
  4. Finally the @ character terminates the cursor, and ends the program.

Simple enough right? Now to bend your mind we’ll show you another, more creative, hello world:

The stack is LIFO, so we need to reverse the text

Try to import that into python! This is the core of befunge’s wackiness. You can actually steer your cursor using certain characters.

  1. The >,v,<,^ characters can steer the cursor in each of the four possible directions.
  2. A random direction can be given by ?.
  3. The | and _ characters pop from the stack, and move the cursor down/right if the popped value was 0, and up/left otherwise.
  4. The p character can change the code of the program. It pops the first 3 values $(x_1,x_2,x_3) = (y,x,v)$ and uses these to set the character at coordinates $(x,y)$ to value $v$.

There are many more instructions which allow you to manipulate the stack in handy ways, but these are the ones that make Befunge a unique language.

One last thing you might wonder, what happens when the cursor goes off the “grid”? What the creators of the language did, is gave that grid the topology of a torus. This basically means the left wraps to the right, and the top to the bottom. See an example of that here:

A torus is a donut, in case you forgot.

Code Examples

So with a short introduction to the basics, you can already write some interesting bits of code, which can do some simple things. The fun part about coding in befunge is that you have to get creative to accomplish tasks that would be simple in other languages. Here are some neat examples of befunge, either solving standard coding excercises or showcasing the cool things you can do with the language.

Looping Looping…

So what about things like loops? Well we can just construct that from the arrows and conditional arrows. The code below contains two loops, the inner loop to print out the string, and the outer loop to fill the stack with the string once it’s empty.

We don't need loops. We make loops.

We use the : symbol to double the first character on the stack, since the conditional _ character pops a character when it checks. This way we just pop the character we added with :, and we still print the full string.

Random Number Generator

Another standard example is a random number generator, and in befunge it’s an extra cool one. We use a whole bunch of ?’s to guide the cursor into one of the 9 strategically placed digits.

Since the ? character can send the cursor in any of the 4 directions, we need to be a little careful that we don’t let the cursor escape our construction. If it did escape every now and then, our generator probably wouldn’t be uniformly distributed. But befunge probably won’t be used for much production code. Lets hope.

We don't need loops. We make loops.

Examples from Reddit

After posting this article on reddit, I got some really cool examples of programs using befunge. Here’s a list of some of the cool ones:

  • Befunge Chess, a chessboard which is displayed in the “program space” and uses the p operator to update the chessboard.
  • BefBef, a befunge interpreter which is written in befunge. The “program space” of which is being interpreted is actually a subset of the interpreters “program space”. Really awesome!
  • Conway’s Game of Life, because a programming language isn’t complete without an implementation of the Game of Life.

Try it out

Finally I want to include a javascript interpreter, which you can use to try out the language and all the neat things shown above. I used this interpreter to create all the gifs shown in the post, and a larger version with a visible stack can be found on this site. Shoutout to Xueqiao Xu for the website and for writing this interpreter in javascript for a really weird language.

Please share any cool programs you make in the comments, and I’ll see if I can update the post with them in the future!

Edit the Codes Below Output