Classic Algorithms in Befunge

Why algorithms look different on a grid

In most languages an algorithm is a few lines of named variables, a loop and a condition. In Befunge you have none of those directly. There are no variable names and no while keyword. There is a stack of integers, a two-dimensional playfield of single-character cells, and an instruction pointer that moves one cell at a time in one of four directions.

Every classic algorithm therefore has to be rewritten in three layers:

1. Data lives on the stack, or in a spare cell of the grid that you read and write on purpose.
2. Decisions are made by instructions that pop a value and turn the pointer depending on whether it is zero.
3. Repetition comes from drawing a path that curves back on itself.

The algorithm itself, the sequence of arithmetic steps, usually stays the same as in any textbook. What changes is bookkeeping: where each number is at each moment, and where the pointer is heading.

The program stack as working memory

The program stack is last in, first out, and most arithmetic instructions pop their operands and push a result. That fits expressions well. Adding 3 and 7 is just the cells 3, 7, + and then . to print the result, and the whole program fits in one row: 37+.@ prints 10.

The trouble starts when an algorithm needs a value that is not on top. Dup (:) copies the top value and swap (\) exchanges the top two, but Befunge-93 has nothing that reaches three levels deep. Many classic algorithms, such as Euclid’s method and Fibonacci, naturally want to juggle three values. You have two options:

• Stay on the stack and redesign the algorithm so it never needs depth. Reversing a string works this way, because the stack’s own ordering does the job.
• Spill to a scratch cell with put (p) and get (g). You store a value at a coordinate you are not using for code, then read it back when needed. This is the idea behind grid variables, and it is what most of the programs in this cluster do.

Loops are shapes

A countdown or a repeated division needs a loop, and in Befunge a loop is a path that returns to a cell it already visited. The most common layout in this cluster is a small rectangle:

• the bottom edge runs east, ending in a vertical-if (|),
• the vertical-if sends the pointer up when the tested value is nonzero,
• the top edge runs west, doing the loop body,
• a down arrow (v) at the left end returns the pointer to the start of the bottom edge.

When the tested value is zero, the pointer drops downward out of the rectangle instead, and the finishing code goes there. Writing the body backward along the top edge looks odd at first, because the cells read right to left. It is simply the order in which the pointer meets them. Befunge loops are discussed in more depth elsewhere; the point here is that the same rectangle serves for nearly every algorithm.

A recipe for translating an algorithm

When you want to port a familiar algorithm, this order of work tends to avoid confusion:

1. Write the algorithm as steps on named variables, the way you would in pseudocode.
2. Decide which variables live on the stack and which live in a scratch cell. Keep as few stack values as possible.
3. For each step, write the stack contents before and after it, in brackets, as a comment on paper. Tracing by hand this way catches most mistakes before you ever run the program.
4. Choose a loop test that produces zero when the loop should stop, since the branching instructions treat zero as the special case.
5. Lay the code out in the rectangle shape, and put the finishing code below the vertical-if.
6. Test with a small input whose answer you already know.

What the rest of this cluster covers

Each of the following articles takes one algorithm through that recipe:

• A factorial routine that multiplies down a counter, with the stack contents listed for each pass.
• Repeated division to convert a number between bases, including the fact that digits come out in the wrong order and must be reversed.
• Euclid’s method for the greatest common divisor, built on the remainder instruction.
• A Fibonacci generator that needs a duplicate-and-rotate trick, here implemented with a scratch cell.
• Random direction with the question mark instruction, where the pointer itself becomes unpredictable.
• String reversal, where the stack does the real work.
• A small sort, where the lack of arrays becomes the main cost.
• Trial division for primes, which shows how quickly a tiny language runs into limits.
• A quine, a program whose output is its own source.

All of the examples are small, original programs. They are written for the classic Befunge-93 model, an 80 by 25 playfield with wrap-around edges, and they should behave the same on most interpreters. Details such as how an interpreter treats an empty stack or very large numbers can vary, so if something behaves oddly, check those first.

Limits worth knowing up front

Befunge is not designed to make algorithms pleasant, and some limits show up repeatedly:

• Number size. Interpreters often use fixed-width integers, so large results such as big factorials can overflow. The exact width varies.
• Input. Reading a number with the ampersand instruction is convenient, but reading text is character by character, and the end-of-input behavior differs between interpreters. Numeric input is handled separately from the algorithms themselves.
• Space. The classic playfield is 80 by 25 cells, which includes both your code and any data you store in it. A routine that writes data across the grid can overwrite its own instructions if you are careless.
• Debugging. There is no error message when a loop never ends. A single misplaced arrow can leave the pointer circling forever. Stepping through a program one cell at a time in an interpreter that shows the stack is the usual remedy.

If you want to run these programs, any standard Befunge interpreter will do. Writing a Befunge interpreter is also a good way to understand exactly what each instruction does, because the whole machine fits in a short program. Once the patterns in this cluster feel familiar, they are good raw material for puzzle programming, where the same tasks are repeated under tighter constraints.