Zero Address
Front Panel is assembly language on real silicon, entered by hand. This is assembly language for a processor that was never built, which is how one file ran on a 6502, a Z-80 and a PDP-11 without being compiled again.
The machine
1 Compile: an expression becomes one fixed postfix sequence, with nothing to choose
2 Push: operands go on a stack, because a zero-address machine has nothing to name
3 Step: the interpreter is a loop small enough to fit a machine with almost nothing in it
4 Pay: it runs slower than the silicon underneath, and that was the deal
Before running it, the shape of this expression says the stack will need 3 slots. It has used 0 so far.
Checked when this page loaded: across 10 expressions, the depth worked out from the shape disagreed with the depth actually used 0 time(s). The deepest of them needed 4 slots.
A processor nobody built
In 1977 a team at the University of California, San Diego, under Kenneth Bowles, took a compiler that emitted machine code for nothing in particular and shipped it anyway. Pascal compiled to p-code, and p-code ran on any machine somebody had written a small interpreter for. The same file ran on the Apple II, on Z-80 machines and on a PDP-11. By 1981 IBM was offering the p-System as one of the operating systems you could buy with a PC.
That is write-once-run-anywhere, and it is fifteen years before anybody made a slogan of it.
Nothing to name
The trick underneath it is smaller than the idea on top. In the standard description, a p-machine's instructions “take their operands from a stack, and place results back on the stack”, so that “the add instruction replaces the two topmost elements of the stack with their sum”.
Read that again for what it does not say. It does not say which two. There is no room in the instruction to say which two, and no need: there is exactly one pair it could mean. An 8080's ADD has to name a register. adi names nothing, and that is what zero-address means.
So an arithmetic instruction is an opcode and nothing else. The machine above counts the operand fields for whatever you type: the arithmetic carries none at all, against three apiece if each had to name a destination and two sources. The same article notes the resulting code is “smaller than the same program translated to machine code”, and this is why.
It also means the compiler has nothing to decide. An expression has one tree; a tree has one left-then-right-then-operator ordering; that is the program. A register machine at this point still has to choose what lives where, and can choose badly enough to matter.
The depth is in the shape
Because the stack is the only place values can be, how deep it goes is decided entirely by the expression rather than by the machine, and you can work it out without running anything. A value needs one slot. An operator needs whatever its left side needed, or one more than its right side needed, whichever is larger, because the left-hand result is still sitting there while the right-hand side is worked out.
Which is why a+b+c needs two slots and a+(b+c) needs three. Same operators, same operands, one pair of brackets, and a machine that has to be one third bigger to evaluate it. The page works the number out from the shape before it runs, then runs it and checks, and says so if the two ever disagree.
What it cost
Every instruction in that little program costs the host machine a fetch, a decode and a jump before any arithmetic happens at all. That overhead is per instruction and it never goes away, which is why the standard description of the approach says plainly that it “leads to a slower execution speed”.
That was the deal, and it was a good one on a machine that would otherwise have had no Pascal at all.
What is real here, and what is not
This is not UCSD's p-machine
The real one has on the order of two hundred opcodes, with procedures and their stack frames, segments that are paged in from disk, sets, strings and byte arrays. This is expression evaluation, using p-code's own mnemonics for the four integer operations. It is in the style of the thing rather than being the thing.
Nothing here is benchmarked
The page says interpretation costs a fetch, a decode and a jump per instruction, which is structural and true of any interpreter of this shape. It does not tell you how much slower, because that depended on the host processor, on the interpreter, and on what the program spent its time doing, and no measurement is offered here.
The variables are a convenience
Letters here have fixed values and load straight onto the stack. On a real p-machine a local is reached through a stack frame with static and dynamic links, and getting at it is itself several instructions. Skipping that is what lets this page be about the stack rather than about scope.
The date is a range because the sources disagree about which moment counts
UCSD Pascal is dated to 1977, and the p-System as a self-hosting operating system is often placed in the early 1980s; IBM offered it for the PC in 1981. Rather than pick one and print it as the date, the era spans them.
A lineage often claimed, and not claimed here
The p-machine's instruction set is frequently said to be modelled on the Burroughs large systems, which were stack machines in hardware. It may well be. It is not in the reference this page leans on, and one source repeating an attractive story is not two, so the page does not assert it.
Sources
- SofTech Microsystems, UCSD p-System Internal Architecture Guide, 1981 — the manual for the machine that is not a machine, listing the p-code instruction set and its top-of-stack notation. It says of the thing this page is about: “The Stack is used for static variables, bookkeeping information about procedure and function calls, and evaluation of expressions.” This links the Internet Archive's scanned text rather than a PDF, because the PDF is an image with no text layer and a citation nobody can search is half a citation. It is OCR, so it is quoted exactly as the scan reads it.
- P-code machine, on the stack architecture and the tradeoff
- UCSD Pascal, and the p-System
- Mark Bessey, UCSD Pascal in depth: the p-machine
- Jefferson Computer Museum, the UCSD p-System