Self-Modifying Code on a Grid

Code and data in the same space

In many grid languages, the program is not kept in a separate, protected area. It sits in the same playfield that the program is allowed to read and write. Two instructions make this possible. One reads the character at a given position and pushes its code. The other takes a value and a position and stores the value there, replacing whatever was in that cell.

Because the pointer executes whatever character is in the cell it lands on, writing a cell changes the program. That is self-modifying code: the program as it exists later is different from the program as it was loaded. It is a direct consequence of using one grid for both instructions and data.

A small example

This one-row program replaces a cell before the pointer reaches it:

"@"80p1.9.@

Counting from zero, the columns are: the quote in column 0, the at-sign in column 1, the second quote in column 2, 8 in column 3, 0 in column 4, p in column 5, 1 in column 6, the dot in column 7, 9 in column 8, another dot in column 9, and the final @ in column 10.

Here is what happens:

1. The quote starts string mode. The @ character is not run; its code, 64, is pushed. The second quote ends string mode.
2. 8 and 0 are pushed. The stack, bottom to top, is 64, 8, 0.
3. p removes three values: a row of 0, a column of 8, and the value 64. It stores character code 64, which is @, in column 8 of row 0. That cell previously held 9.
4. 1 is pushed, and . prints it as a number: 1 .
5. The pointer then arrives at column 8. It is no longer 9, but @, so the program ends.

The output is 1 . Without the write, the pointer would have pushed 9 and printed it as well before reaching the final @. The written text of the program says “print one, print nine”, but the program that actually ran printed only one. That gap between what the source shows and what runs is the central feature, and the central problem, of this technique.

Why programmers use it

Self-modification has several uses, from small tricks to structural ones.

• Changing a branch. A program can overwrite an arrow or a conditional so that a path is taken differently from then on. This allows a one-time setup step followed by a different route.
• Counters stored in cells. A cell can hold a count that is read, changed and written back. This is similar to the idea of grid variables, where a number lives in a cell instead of on the stack.
• Building code from data. A program can compute an instruction’s character code and place it in a cell, creating code it did not contain at the start.
• Self-reproducing programs. A program that reads its own cells and prints them is a natural way to approach a quine, since the source is available in the playfield. The Befunge quine is a puzzle of its own, with details covered elsewhere.
• Saving space. In size-limited puzzles, editing a cell can replace a longer sequence of instructions.

The costs

The same property that makes self-modification powerful also makes programs harder to understand.

The source stops being the truth. When you read the grid as written, you see the program as loaded. You may need to simulate the writes to know what the program really looks like at any point. A cell that shows an arrow may hold something else by the time the pointer gets there.

Static analysis breaks down. Judging which cells are reachable, or what route the pointer might take, gets more complicated when cells change. The question of what a program can do becomes closer to the undecidable properties discussed in the theory section, and no simple picture of the paths holds for the whole run.

Debugging gets harder. Reproducing a bug may require the exact order of writes. Working through grid debugging with a snapshot of the grid at each step, not just the starting text, is usually necessary. A visual tool that highlights changed cells is a real help here.

Layout is no longer reliable. A cell may need to stay blank, or hold a stand-in value, to be overwritten later. A reader who tidies up that cell will break the program without any warning.

The result is code that is compact but opaque, and it is no surprise that the technique is common in obfuscated code and contests, and rarer in programs meant to be read.

Habits that reduce the pain

If you do use self-modification, a few habits help:

• Limit it to a few clearly identified cells and say so in notes kept beside the program.
• Prefer writing data to cells that are not on any route, rather than rewriting instructions.
• Write marker characters that make it plain a cell is meant to change, so nobody mistakes it for a normal instruction.
• Check the program with a tracing tool that shows the grid after each write.

Interpreter implications

A language implementation has to store the grid in a form that allows fast reads and writes while the program runs, which is one of the factors in choosing a playfield data structure. Writes outside the original program area may even be allowed, expanding the used part of the grid. How far a given language allows that varies, so it is best to read the rules of the language you are using before depending on it.