Zero Address
Front Panel is assembly language on real silicon, entered by hand. This is assembly language for a processor that mostly did not exist, which is how one file ran on a 6502, a Z-80 and a PDP-11 without being compiled again — until Western Digital spoiled the phrase by casting the thing in silicon.
New to computer arithmetic? Start here
Numbers in a fixed-size box
A number on paper can be as long as it needs to be. A number in a computer gets a fixed number of digits and no more, so there is always a largest one it can hold and always a smallest difference it can tell apart.
Almost everything surprising about computer arithmetic follows from that. What happens when you count past the largest value depends on which kind of number it is: a fixed-width integer wraps round to the smallest, and a floating-point number goes to infinity instead. A value too fine for the gap is not rejected, it is rounded to the nearest one that fits, and then the rounding is added to the next rounding. These are not faults in the machines here. They are the edges of the box, and the machines are what people built to live inside it.
The machine for this idea on its own is Two's Complement, if you would rather press it than read about it.
What a processor actually does
A processor fetches an instruction, works out what it says, does that one small thing, and moves to the next. Add these two numbers. Put this number there. If that number is zero, carry on somewhere else. That is the job, and it repeats a few billion times a second.
Everything that looks like cleverness is arrangement around that loop: keeping the next instruction ready before it is asked for, keeping recently used numbers close by, letting a slow part and a fast part work at once. The machines here are those arrangements, and most of them exist because one part of the machine is thousands of times slower than another.
The machine for this idea on its own is Stored Program, if you would rather press it than read about it.
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 that usually was not there
Except once. On 4 October 1978, inside the span this page is dated to, Western Digital issued a release headed PASCAL PROCESSOR IS CAST IN SILICON BY WESTERN DIGITAL
, and its vice president said of the p-machine: and we have implemented this idealized machine directly in a chip set using LSI technology
. He called it the first ‘sand-casting’ of something that previously had been available only as a software product
. This page used to say the processor was never built, and an outside audit was right that it was. The interesting thing is not that the claim was wrong; it is that an imaginary machine specified precisely enough to interpret is also specified precisely enough to fabricate.
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, well before Java 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 this emitter has no register-allocation problem. An expression has one tree; once it commits to left, then right, then the operator, that is the program. Other choices a compiler can make do not go away: evaluation order where the semantics permit it, folding, common subexpressions. the hardest one does. 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.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| across 10 expressions the depth worked out from the tree shape disagreed with the depth actually used 0 times | yes | each one is compiled and its stack run for real; the deepest needed 4 slots |
| its 4 arithmetic instructions carry 0 operand fields between them, where three-address form would need 12 | yes | there is only one possible answer to which two integers to add, so the instruction does not ask |
| compiling the same expression twice gives the same 9 instructions in the same order | yes | the operator needs both results already on the stack, so the sequence is forced rather than picked |
| "(((a)))" and "a" compile to the same instruction, because the parse tree is the only source of truth here | yes | three pairs of brackets in the text and none in the tree |
| every one of the 10 programs ends with exactly one value on the stack | yes | an expression is worth one number; anything left over would mean the emitter had lost track of what it pushed |
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
- Western Digital, Pascal Processor Is Cast In Silicon By Western Digital, news release, 4 October 1978 — the document that retired this page's old title. It announces a chip set that directly executes Pascal object programs and quotes its vice president saying the idealised p-machine was implemented directly in silicon.
- 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