100 Languages Speedrun: Episode 10: Befunge

The goal of esoteric programming languages is to challenge common assumptions, and source code being a flat line-by-line text file is about the most basic of them.

Befunge source code is a 2D array of characters. Let's see what that looks like!

Interestingly unlike Ada we tried in previous episode, Befunge is fully supported on OSX, you just need to do brew install befunge93 and it install its bef interpretter.

Infinite loop

Here's an infinite loop in Befunge:

>v
^<

What's going on here?

we start at top left corner, facing right
we keep going in whichever direction we've been going, until arrow (ASCII >, <, v, ^ - it predates Unicode) tells it to change direction

Amazingly, Befunge comes with a builtin visual debugger. If you run this code as bef -d loop.befunge you can see the grid on the screen, with highlight moving around in the loop.

Math

Befunge doesn't have strings, only integers. We'll get to Hello, World!, but it's best if we start with some math first.

Here's a program that prints 12:

48+.@

What's going on here:

individual digits like 4 or 8 are instructions to push a number to the stack - there's on way to get numbers outside 0 to 9 range there directly
+ adds top two numbers on the stack and pushes the result there - you can probably guess what *, /, -, and % do
. prints top of the stack as a number
@ exits the program - if it doesn't hit @, the program will just go around the screen and never stop (it won't go to the next line, it will go to beginning of the same line again)

Roll Dice 1 to 6

Let's actually do some 2D programming. Here's a program that rolls a 6-sided die:

>    v
 v <   > v
   3   6
 v2?<?>?5v
   1   4
 > >   > >.@

the program starts in top left corner, then turns down into the hole between two halves
the central ? sends the program in a random direction - it can go left for 1-3, right for 4-6, top or bottom - the top is obviously going to hit v and bounce back, but what about the bottom direction? It turns out it will just keep going until it reaches end of the program, and wrap around, continuing from top of the screen of same column. Either top or bottom will end up rerolling ?.

If it goes left, it will go in random direction:

top pushes 3, then goes around to the bottom line
left pushes 2, then goes down to the bottom line
bottom pushes 1, then goes down to the bottom line
right steps on < and bounces back to ?

And the right case for 4-6 is completely symmetrical.

Once it reaches the bottom row the program prints the number with . and quits with @.

By the way the Befunge interpretter from homebrew uses current time for random seed, so if you run it multiple times during same full second, you'll get identical results.

This program can obviously be "optimized" in many ways.

Hello, World!

There are many fun ways to print Hello, World!

Befunge , command prints top number on the stack as ASCII value. We cannot put 101 for e directly in source code, but 101 is just 9*9 + 9*2 + 2 and so on.

So let's do something really simple - each line will calculate ASCII value of one character of "Hello, World!\n", then next line will go back to the start. Pretty much missing the whole point of 2D programming, but we need to start somewhere:

98*     ,v
v        <
>92+9*2+,v
v        <
>93+9*  ,v
v        <
>93+9*  ,v
v        <
>93+9*3+,v
v        <
>94*8+  ,v
v        <
>93*5+  ,v
v        <
>99*6+  ,v
v        <
>93+9*3+,v
v        <
>93+9*6+,v
v        <
>93+9*  ,v
v        <
>92+9*1+,v
v        <
>93*6+  ,v
v        <
>91+    ,@

And it doesn't work! Turns out the original Befunge-93 we're using limits program size to 80x25. This is a limitation later removed in Befunge-98.

All right, so let's double space.

Let's just put two of them per line:

98*     , 92+9*2+,v
v                 <
>93+9*  , 93+9*  ,v
v                 <
>93+9*3+, 94*8+  ,v
v                 <
>93*5+  , 99*6+  ,v
v                 <
>93+9*3+, 93+9*6+,v
v                 <
>93+9*  , 92+9*1+,v
v                 <
>93*6+  , 91+    ,@

And it works!

$ bef hello.befunge
Befunge-93 Interpreter/Debugger v2.25
Hello, World!

Better Hello, World!

Let's do a better one. First, most ASCII numbers are quite close to each other, so we don't need to calculate all the way from 0.

The most useful command for this is : which duplicates whatever's on top of the stack, so we can.

98*     :, 93*+2+ :,v
v                   <
>7+     :,        :,v
v                   <
>3+     :, 97*-4- :,v
v                   <
>9-3-   :, 96*+1+ :,v
v                   <
>83*+   :, 3+     :,v
v                   <
>6-     :, 8-     :,v
v                   <
>93*6+  ,  91+     ,@

Except for the last two characters (!\n) I replaced each calculation by duplication of previous number and a difference. For lower case characters it's quite decent. When we change from lower case to punctuation or upper case, we don't really have any significant savings.

Well, let's stop the returns, and just put every line to good use. Odd lines will go left to right, even lines will go right to left. That cuts number of line is half. Also it destroys whatever readability we had so far, but for Befunge that's actually a good thing.

98*     :, 93*+2+ :,v
v,:        ,:     +7<
>3+     :, 97*-4- :,v
v,: +1+*69 ,:   -3-9<
>83*+   :, 3+     :,v
v,:     -8 ,:     -6<
>93*6+  ,  91+     ,@

Of course you can arrange instructions in a spiral, or a zigzag, or some logo, or whatever else you want. The arrows make it very flexible.

There's also a "boring" way to do "Hello, World!". As a concession to all your likely string needs, Befunge has ASCII mode. " command goes into ASCII mode and for every character it encounters it just pushes its value to the stack, until hitting the next ". The only two special things we need to do is calculate 10 for new line, and put everything backwards.

55+"!dlroW ,olleH",,,,,,,,,,,,,,@

Fibonacci

I'm going to skip Fibonacci numbers. Befunge-93 has some serious limitations - it can hold 32 bit integers on stack, but it can only operate on top two elements of the stack, optionally swapping top with second top with \ command.

It has sort of "memory", as p and g can put and get any cell of the program, but that only stores ASCII values -128 to +127.

We need 3 variables to do Fibonacci calculations in a normal way. If we could either store regular sized integers in memory, or access stack a bit deeper, these could be used for reasonable Fibonacci program.

I even checked online for some Fibonacci programs in Befunge, and the best I could find was one that encoded both numbers we need to keep track of as 512*a+b, and then extracted one or the other by essentially num%512 and num/512. Obviously it had to stop before the numbers reached 512.

Here it is edited somewhat for clarity:

1.01>:888***++\1+:67+`#@_\:888**%\888**/\:.v
    ^                                      <

Extra commands it uses are greater-than `, skip next instruction #, and "horizontal if" _, which will turn left and hit the skipped @ once limit has been reached.

Print numbers 1 to 100

Before we get to FizzBuzz, let's do something simpler, and print all numbers 1 to 100.

0v
v<         <
          @
>1+:554**`|
v         <
>:.55+,    ^

First line just pushes 0 and goes to the loop. The rest of the program is a literal loop, counter-clockwise. Along the loop we increment the number with 1+, check if it's already greater than 100 with :554**\`, then with vertical if | we either send the program up to its exit @, or send it down to continue the loop.

The bottom line of the loop prints the number with :., then prints newline with 55+,.

I think this should all be understandable.

FizzBuzz

Now that we know how to loop, how to print numbers and strings, and we know that % is modulo operation, we can do the FizzBuzz easily.

0v
v<                                <
          @
>1+:554**`|
v         <
       >"zzuBzziF",,,,,,,,v
>:53*%!|
v      <
     >"zzuB",,,,v
>:5%!|
v    <
     >"zziF",,,,v
>:3%!|
v    <
:
.
>               >         >   55+,^

It might look complicated, but it has some distinct parts we already know.

There's a big loop around the program. During the loop, the following things happen:

number is incremented with 1+
number is checked to be greater than 100 with :554**`|, sending it to exit @
number is checked if it's zero modulo 15 with :53*%!|, if so printing FizzBuzz and going to the bottom line skipping the rest of the iteration
number is checked if it's zero modulo 5 with :5%!|, if so printing Buzz and going to the bottom line skipping the rest of the iteration
number is checked if it's zero modulo 3 with :3%!|, if so printing Fizz and going to the bottom line skipping the rest of the iteration
if none of that happens, number is printed with :.
bottom line prints the newline with 55+,

Should you try Befunge?

Befunge is highly influential esoteric programming language, which spawned a whole new family of 2D programming languages.

Most use flexible program size instead of fixed 80x25. As I already mentioned, a few extra instructions either allowing storing arbitrary numbers in cells, or accessing stack other than top two items, would greatly improve what can be expressed.

I definitely recommend giving it a try.