Random Choice with the Question Mark Instruction

What the question mark does

Most Befunge instructions that change direction are deterministic: an arrow always points the same way. The question mark is different. When the pointer reaches it, the interpreter picks one of the four directions, up, down, left or right, and the pointer direction changes to match and the pointer continues that way. In Befunge-93, the instruction is described as sending the pointer in a random direction. Interpreters typically pick each direction with equal likelihood, but the language definition does not promise any particular distribution, and the quality of the random number source varies between interpreters.

That makes the question mark the only source of randomness in classic Befunge. It is an example of nondeterministic programs in the practical sense: the same source can behave differently on each run.

Designing around four exits

A question mark has four neighbors, and the pointer will leave through any of them. A well-formed program therefore needs something sensible in all four directions. There are three common ways to handle that.

• Use all four exits. Each one leads to a different outcome, as in a four-way menu.
• Bounce unused exits. Put an arrow in the unused neighbor cell that sends the pointer straight back to the question mark. This re-rolls the choice until a useful direction comes up.
• Mirror exits. Send two or more directions to the same code, so the choice matters less.

Leaving an exit as empty space is risky. The pointer would walk along it, perhaps wrap around the playfield, and arrive somewhere you did not intend. This is similar to the unexpected paths covered in the discussion of dead code and wrap-around.

A coin flip

The program below prints H or T with roughly equal chance.

>       v
        v
   @,"T"?>"H",@
        ^

Where each piece goes:

• Entry. The right arrow in the top-left corner sends the pointer east along the first row. The v at column 8 turns it down. A second v in row 1 passes it on, and it enters the question mark moving down.
• Right exit. The cell to the right of ? is an arrow that points right, followed by a string. The cells "H" push the character code of H, the comma prints it, and @ ends the program.
• Left exit. The cells on the left are written backward because the pointer travels west. Reading right to left, the pointer meets the quote, T, the quote, the comma and @. It prints T and stops.
• Up exit. The cell above the question mark is the v in row 1. If the pointer goes up into it, the arrow immediately sends it back down to the question mark, a re-roll.
• Down exit. The cell below is ^. If the pointer goes down into it, it is sent straight back up into the question mark, another re-roll.

Because two of the four directions just loop back, the program eventually takes one of the printing exits. Each time the pointer reaches the question mark it picks left or right half the time and up or down the other half. As long as the chances for left and right are equal, H and T are equally likely. The bounces only delay the result.

Termination is only probable

It might seem odd, but there is no strict upper limit on how long this program runs. If the random choice kept selecting up or down, the pointer would bounce forever. With fair choices, the chance of that happening shrinks quickly: after k trips through the question mark, the chance that all of them were bounces is (1/2) to the power k, which gets small very fast. In practice the program ends almost at once. But that is “almost surely” rather than “certainly,” and a biased or broken random source could make a difference.

Testing programs with randomness

Output that differs from run to run is awkward for ordinary tests, which expect fixed output. A few approaches help:

• Check properties, not exact output. Run the coin flip many times and confirm that every result is H or T, never anything else. Do not require a particular sequence.
• Use a fixed seed if the interpreter supports one. Some interpreters let you choose a seed, so runs can be repeated. Not all do. If you are writing your own Befunge interpreter, adding a seed option is a cheap way to make tests repeatable, which is a recurring idea in interpreter testing.
• Trace each exit separately. For every direction, tracing by hand shows where the pointer ends up. If you can describe all four paths, the randomness no longer hides anything.
• Count outcomes loosely. After a few hundred runs, both outcomes should appear. An exact 50/50 split is not expected, and a result like 6 H out of 10 should not surprise anyone.

When something does go wrong, the usual cause is a missing bounce on an exit. Grid debugging with a trace of every cell the pointer visits makes this visible: the pointer will be seen wandering into a region you forgot about.

Beyond a coin

The same pattern extends to other choices:

• Four-way menu. Give each direction its own code, so the program prints one of four messages. This needs no bounce cells.
• Random walk. Put the question mark in a loop that moves a counter up, down, left or right, and print the position. This is closer to simulation than to a typical algorithm, but it is a natural use.
• Weighted outcomes. Send two directions to the same exit to make one result twice as likely as another, in principle. Treat the weights as approximate, since they depend on the interpreter’s random source.

Funge-98 keeps the question mark, and in more than two dimensions the set of directions grows. The idea of designing every exit remains the same.