Loops Formed by Grid Geometry

A loop is a route that returns

In most languages, repetition is a named construct: for, while, or a call to a function that calls itself. A grid language usually has none of these. A loop appears when the pointer’s route comes back to a cell it has already visited, with the same heading. Once that happens, and unless something differs on the second trip, the pointer will repeat the same cells indefinitely.

So a loop in these languages is a shape. The smallest shape is a ring of arrows, as in this four-cell program:

>v
^<

The pointer moves right, down, left and up, then arrives back at the first arrow and does it again. There is no exit, and no output, but it is a complete loop, made of nothing but geometry.

Making a loop useful

An endless ring is only a starting point. For useful repetition, the ring needs two more things: some work done along the path, and a way out.

The work is just ordinary instructions placed in cells along the route. Each time around, the pointer executes them again. The exit is a conditional cell on the ring: one of its exits continues around, and the other leaves the ring altogether. The value tested is typically a counter that changes by one each time around.

Here is a counting loop in Befunge-style notation. It prints the numbers from five down to one:

5>:.1-:v
 ^     _@

Walking through it step by step:

1. 5 pushes the starting count. The > then sends the pointer right.
2. : duplicates the top value, so there are two copies of the count.
3. . prints one copy as a number, which leaves one copy on the stack.
4. 1- subtracts one from it. The counter is now one smaller.
5. : duplicates it again, so there is one copy to test and one to keep.
6. v sends the pointer down to the _ cell on the second row.
7. _ removes the test copy. If it is zero, the pointer goes right to @, and the program ends. If it is not zero, the pointer goes left.
8. Heading left along the second row, the pointer reaches the ^, which sends it up to the > at the top, and the cycle begins again.

The output is 5 4 3 2 1, each number followed by a space, since numeric output in Befunge-style languages usually adds one. The program ends with a leftover zero on the stack, which is harmless here.

The ring is formed by > at the top-left, the run along the top row, the v, the _, the run back along the second row, and the ^. The exit is the single right-hand branch off _. You can see the loop as a rectangle with one door in it.

Common loop shapes

Because loops are shapes, it is useful to know the common ones.

• The ring. A closed path, usually a rectangle, with a conditional cell somewhere on the loop. This is the shape of the example above, and the most common one.
• The back-and-forth line. Two facing arrows at the ends of a single row make the pointer shuttle between them. It is the simplest possible loop in terms of cells used, although it needs a conditional somewhere along the row to leave.
• The figure with a shared stretch. Two rings can share a section of path. The pointer takes one ring or the other based on a test, which makes a loop with two different bodies.
• The nested ring. A small ring sitting inside a larger one, where the inner loop finishes before the outer loop moves on. This is the grid version of a loop within a loop.

For a longer treatment of the practical patterns, the techniques section has a piece on Befunge loops, and the countdown program there is a close cousin of the example above.

Reading loops from the layout

One good thing about geometric loops is that you can often spot them by eye. Look for cells where the pointer turns and ask whether the turns, taken in order, would return to the start. A rectangle of arrows nearly always means a loop. A staircase of arrows that heads away from the start without returning does not.

The hard part is the exit. A ring with a conditional cell is only as good as its test. If the counter is never changed, or is changed in the wrong direction, the test never takes the exit, and the loop continues forever. You can’t tell this from the shape alone, which is part of why the halting problem matters in the general sense: from the picture of a loop you can’t always say whether it ends. For small programs, though, tracing by hand a few passes usually reveals the pattern.

Layout choices

The same loop can be drawn in many shapes. A long thin ring takes a lot of space but has plenty of room for instructions, while a compact ring is neat but leaves little room for modifications. Good code layout puts the loop body on one side and keeps the return path straight and uncluttered, so the loop can be recognized at a glance.

There is also a quieter point. A loop need not return to the very same cell. A pointer might enter a ring from the left, traverse it and exit from the bottom, and only a second loop-back path makes it repeat. Looking at the closed path in the route, rather than at any particular cell, is the most reliable way to see the repetition.

Contrasting with the iterate approach

Some Funge-98 programs avoid a geometric loop by using an instruction that repeats the next instruction a given number of times, called the iterate instruction. It is shorter for simple repetition, but it is not the main way programs repeat in these languages. Geometry stays the general tool, since it can repeat any amount of code, however complex.