This chapter is about a machine that does not exist. It has eight instructions, one data stack, three registers, and it is defined entirely by the fifty lines of C that interpret it.
That is not a limitation — it is the point. Because the machine is small enough to hold in your head, whatever it prints for a program is, by definition, what that program means. Everything else in this compiler is checked against it.
Eight instructions
typedef enum {
fn_lit, /* push the literal in the address field */
fn_opr, /* perform the operation the address field selects */
fn_lod, /* push the variable at (level, address) */
fn_sto, /* pop into the variable at (level, address) */
fn_cal, /* call the procedure whose code begins at the address field */
fn_int, /* raise the stack top by the address field, making room */
fn_jmp, /* jump to the address field */
fn_jpc /* pop, and jump to the address field when the value was zero */
} Function;Every instruction has the same shape:
typedef struct {
Function function; /* what to do */
int level; /* how many nesting levels out the operand lies */
int address; /* a value, an address, an offset, or an operation selector */
} Instruction;Eight instructions are enough for a block-structured language with nested procedures and non-local variable access. Seeing that is worth more than any improvement to it.
Arithmetic and comparison are not instructions — they are selectors of opr:
enum {
opr_return = 0, opr_negate = 1, opr_add = 2, opr_subtract = 3,
opr_multiply = 4, opr_divide = 5, opr_odd = 6,
opr_equal = 8, opr_not_equal = 9, opr_less = 10,
opr_greater_or_equal = 11, opr_greater = 12, opr_less_or_equal = 13,
};Notice 7 is missing. Wirth numbered these and left selector 7 unused. The gap is kept rather than closed, so a listing produced by these twins can be read beside a listing in the book. That is a small decision with a real cost — a reader will wonder — and it is worth it, because a teaching program’s job includes being comparable to its source.
Reading the listing
Now the listing from chapter 2 can be
read completely. Here it is again, for square.pl0:
0 jmp 0 8 ← jump over the procedure, into the main body
1 jmp 0 2 ← the procedure's own entry jump
2 int 0 3 ← procedure 'square' begins: make room for its frame
3 lod 1 3 ← push arg (1 level out, offset 3)
4 lod 1 3 ← push arg again
5 opr 0 4 ← multiply
6 sto 1 4 ← pop into result (1 level out, offset 4)
7 opr 0 0 ← return
8 int 0 5 ← the main body: frame of 3 header cells + 2 variables
9 lit 0 1 ← push 1
10 sto 0 3 ← arg := 1
11 lod 0 3 ← push arg ┐
12 lit 0 10 ← push 10 │ while arg < max
13 opr 0 10 ← less-than │
14 jpc 0 21 ← if false, leave ┘
15 cal 0 2 ← call square
16 lod 0 3 ← push arg ┐
17 lit 0 1 ← push 1 │ arg := arg + 1
18 opr 0 2 ← add │
19 sto 0 3 ← ┘
20 jmp 0 11 ← back to the test
21 opr 0 0 ← return: the program endsTwenty-two instructions for the whole program. Three things to notice:
Offsets start at 3. arg is at offset 3, not 0, because every activation
record begins with three housekeeping cells. That is the next section.
lod 1 3 inside the procedure, lod 0 3 outside it. Same variable, same
offset — different level differences, because the procedure is one level
deeper than where arg was declared.
Line 14’s jpc 0 21 was emitted before line 21 existed. That is the
backpatch from chapter 6, resolved.
The activation record
When a procedure is called, it gets a frame on the stack. Wirth’s frame has three housekeeping cells below the variables:
│ ... │
├────────────────┤
base+4 │ variable 2 │ ← offsets 3, 4, … are the declared variables
base+3 │ variable 1 │
├────────────────┤
base+2 │ return address │ ← where to resume when this procedure returns
base+1 │ dynamic link │ ← the CALLER's base — used to pop the frame
base+0 │ static link │ ← the DECLARING block's base — used to find variables
└────────────────┘Here is the call, in the interpreter:
case fn_cal:
/* the new frame's housekeeping: the static link reaches the declaring block's frame, the
* dynamic link reaches the caller's, and the return address is where to resume */
stack[top + 1] = frame_base(stack, base, instruction.level);
stack[top + 2] = base;
stack[top + 3] = program;
base = top + 1;
program = instruction.address;
break;Three stores and two register updates. That is a procedure call.
The two links, and why there are two
This is the idea PL/0 exists to demonstrate, and it is the one that most often gets glossed over.
The dynamic link points at the caller’s frame. It answers “who called me?”, and it is used to pop the frame on return.
The static link points at the frame of the block that lexically encloses this procedure. It answers “where do my non-local variables live?”.
They are different pointers because they answer different questions, and the
difference is visible whenever a procedure is called from somewhere other than
its immediate parent. In staticlinks.pl0, inner is called from middle, so
its two links happen to agree — but if middle called some third procedure that
called inner, the dynamic chain would run through that third procedure while
the static chain would still go straight to middle.
Follow the dynamic chain to unwind. Follow the static chain to find data. Confusing the two is a classic compiler bug, and it produces exactly the symptom you would expect: a program that works until a procedure is called from an unusual place.
The static-link walk
/* The base of the activation record the given number of nesting levels out, found by walking the
* static links. This is how a block-structured language reaches a variable it did not declare, and it
* is the single idea PL/0 exists to demonstrate. */
static int frame_base(const int64_t* stack, int base, int levels) {
for (; levels > 0; levels--) {
base = (int)stack[base];
}
return base;
}Four lines. levels is the level difference the front end computed from the
symbol table back in chapter 5 —
level - entry->level, a subtraction of two integers.
So a variable access is:
case fn_lod:
if (top >= STACK_SIZE - 1) {
return (RunResult){.steps = steps, .error = "the stack overflowed: 500 cells is the machine's limit"};
}
top++;
stack[top] = stack[frame_base(stack, base, instruction.level) + instruction.address];
break;Walk level links, add address, load. A local (level 0) walks nothing and
is one addition. A variable two levels out is two pointer hops.
That cost is real, and it is why later languages made different choices — displays, closures, flat lambda-lifted environments. But this is the mechanism they are all alternatives to, and it is four lines.
Every store prints
case fn_sto: {
int64_t value = stack[top];
stack[frame_base(stack, base, instruction.level) + instruction.address] = value;
top--;
/* the language's only output: every store announces the value it stored */
fprintf(output, "%lld\n", (long long)value);
break;
}There it is: the store, and then the print. PL/0’s entire observable behaviour
is that one fprintf, and it is what makes the machine an oracle rather than
just an interpreter — every state change is visible, in order, without the
program having to cooperate.
Wirth’s arithmetic, made explicit
One place where the twins deliberately differ from the original.
Wirth’s interpreter is written in Pascal, so s[t] := s[t] * s[t+1] means
whatever Pascal’s * meant on the machine it ran on — including on overflow,
where the answer was “whatever the hardware did”. That is not a definition, and
an oracle needs one.
So the twins define it:
static int64_t wrap_multiply(int64_t left, int64_t right) {
return (int64_t)((uint64_t)left * (uint64_t)right);
}Signed overflow is undefined behaviour in C, so the multiplication is done in
the unsigned domain — where wrapping is defined — and converted back. The
oracle now says exactly what arg * arg means for every input, including the
ones that overflow.
An oracle must be total. If the reference implementation has undefined behaviour, then “the two back ends agree” is a claim about nothing.
The one thing that can go wrong
case fn_cal:
if (top + ACTIVATION_RECORD_HEADER >= STACK_SIZE) {
return (RunResult){.steps = steps,
.error = "the stack overflowed: 500 cells is the machine's limit"};
}500 cells, Wirth’s own number, and hitting it produces a sentence rather than a crash. Try it:
printf 'procedure p;\nbegin\n call p\nend;\nbegin\n call p\nend.\n' > /tmp/inf.pl0
../build/c/pl0 run /tmp/inf.pl0the stack overflowed: 500 cells is the machine's limitAn infinitely recursive procedure is a perfectly legal PL/0 program, and an interpreter that segfaulted on it would be an interpreter you could not trust to tell you what a program means.
What this back end is for
It is slow. It is an interpreter for an idealized machine, it allocates no registers, and it will never run production code.
It is also the specification. When the Dragon road and this machine disagree about a program, the Dragon road is wrong — not because it is more complicated, but because this one is simple enough to audit by eye, and that is the only property that makes a reference useful.
Keeping a slow, obviously-correct implementation alongside a fast, hard one is a technique worth carrying into any project where correctness is checkable rather than provable. Chapter 10 is what you do with it.
Next: 9 — The Dragon road, where the same parse produces real machine code.