Writing a Quine in a Grid Language

What a quine is

A quine is a program that prints its own source code and nothing else. The usual rule is that it may not read its source from a file, since that would make the task trivial. In most languages the standard trick is to store a copy of the program as a string and print it twice, once as data and once with the extra code wrapped around it.

A grid language offers a different route. In Befunge, code lives in the playfield, and the get instruction (g) can read any cell of that playfield at run time, including the cells that hold the program itself. So a program can print itself by walking across its own cells and printing each one. The code is its own data, and there is no need for a duplicate copy.

The program

:0g,:66+`#@_1+

It is a single row of 14 characters, and its output is exactly those 14 characters. The first cell is a colon and the last is a plus sign.

How it works, cell by cell

The program keeps one number on the stack: the column of the next cell to print. The first time through, the stack is empty. Dup on an empty stack produces zeros, which Befunge-93 treats as the value 0, so the counter starts at 0 without any setup. This is a deliberate use of what would otherwise be a stack underflow, and interpreters differ in how they treat an empty stack, so the program relies on the common behavior.

With the counter i on top of the stack, the pointer moves east:

1. : duplicates it, giving [i, i].
2. 0 pushes a row number of 0, giving [i, i, 0].
3. g pops the row and column and pushes the character code at that cell, giving [i, code].
4. , pops the code and prints it as a character, giving [i].
5. : duplicates, giving [i, i].
6. 66+ pushes 6 + 6 = 12, giving [i, i, 12].
7. The backtick pops 12 and i and pushes 1 if i is greater than 12, otherwise 0, giving [i, flag].
8. # skips the next cell, @. This is the trampoline instruction at work.
9. _ pops the flag. If it is zero the pointer continues east, if nonzero it turns west.
10. If the pointer continued east, 1 and + add 1 to the counter, giving [i + 1].

At the right edge, the pointer wraps around to the left side of the same row, as it does on a toroidal playfield, and the cycle starts again at the colon with the new counter. The loop is made by the wrap-around, with no loop-back arrow.

When the flag is nonzero, the pointer turns west from the horizontal-if, and the next cell it meets is @, because the # only skipped over it when moving east. The program ends. That occurs when i is 13, after the character at column 13 has been printed. The characters at columns 0 through 13 have all been printed, which is the whole program.

Checking the numbers

The program has 14 cells, numbered 0 to 13. The counter has to print every one of them, so the loop must stop right after printing cell 13. The test happens after printing, and the flag is 1 only when i is greater than 12. Cell 12 gives 12 > 12, which is false, so the loop continues; cell 13 gives 13 > 12, which is true, so it ends. If you change the limit to 13 (67+), the program prints one extra character, a space, because it prints cell 14, which is empty. Getting this off-by-one wrong is the most common mistake when writing such a quine.

The limit constant is itself part of the program, so changing it can change the length. Here 66+ takes three cells, and so would 67+. If a limit ever needed a different number of cells, the length would change and the limit would have to be recomputed, which is the small puzzle at the heart of quine writing.

Is it a fair quine?

The program does not read a file. It reads the interpreter’s in-memory playfield. Some purists prefer quines that do not inspect their own code at all, since in a language with a get instruction that approach feels like it sidesteps the challenge. Others argue that the playfield is simply part of the language’s data model, and using it is the point of a grid language. It is a matter of taste, so if you are entering a contest, check its rules.

Quines that avoid get typically use string mode (quote mode), which pushes a copy of the code’s characters onto the stack, then print the stack in the right order and add the missing quote characters. They are longer and harder to get right, but they are closer to the traditional string-copying approach.

Related ideas

• Code golf. A shorter quine is a popular goal, though claiming a record needs care; this one is just a clear example, not a record.
• Obfuscated code. Quines are a favorite of obfuscation fans, because they are small, odd and satisfying.
• Self-modifying code. The program only reads its cells. A program that writes into its own cells with put is a different kind of self-reference, and it is harder to trace.
• Tracing by hand. Writing the stack as a row after each cell, for the first two or three passes, is the best way to see that the counter is doing its job.

Quines are also a standard example in computability theory, because a program that can refer to its own description sits at the heart of several classic arguments, though this simple version does not need any of that machinery.