In Stack Machines, Expression Evaluation, and the Magic of Reverse Polish, I showed how expressions can be evaluated by rewriting them in reverse Polish and translating this into machine-code instructions for a stack machine. I demonstrated with a stack-machine interpreter that I'd written as part of a working model of a Pascal compiler. But as well as expressions, the compiler needs to compile assignments and jumps, so — in my progress towards explaining the compiler — I'm going to extend the machine code so it can handle these. I'll demonstrate by interpreting a program that calculates five factorial.
Any imperative language needs somewhere
to store variables. So my machine needs
memory, and instructions to load from and store into
it. I'll demonstrate some of these instructions
now with
a tiny machine-code program. As well
as the loadconst
and mult
instructions used in Stack
Machines, Expression Evaluation, and the Magic of Reverse
Polish,
it uses my memory-access
instructions load
and store
:
loadconst 6 store 1000 load 1000 loadconst 7 mult store 1002
I wrote the compiler and interpreter that I'm describing in this series for a friend who was doing an MSc in computing. To show him some of the complications of real hardware, I divided my memory into bytes as well as words. The memory contains two bytes per word, and is byte-addressable. So when used as an address, 51 (say) points at the next byte past 50, not at the next word. In these examples, by the way, I assume that the compiler has allocated variables to addresses from 1000 upwards.
In the first two instructions above,
loadconst 6
pushes 6
onto the stack. The store
instruction pops the stack and stores
the value
at locations 1000 and 1001. The least
significant
byte goes in location 1000; the most significant
in 1001. I note that
the values on the stack are words, not bytes;
I probably did this to make my interpreter
easier to explain.
The final four instructions demonstrate
storing the result of
evaluating an expression over another
value from memory. The load
instruction
gets the two bytes at 1000 and 1001, packs
them into a word, and pushes that
onto the stack. This value gets
multiplied by 7 in the same way
as I showed in Stack
Machines, Expression Evaluation, and the Magic of Reverse Polish.
And then
it gets stored at 1002 and 1003.
Now I'll show you the interpreter running this code. The stack is depicted as in Stack Machines, Expression Evaluation, and the Magic of Reverse Polish. The "store" is a mapping from memory address to byte content, depicted in a way close to the mathematical notation for mappings. "Store", by the way, is a standard term from programming-language theory. It is often contrasted with "environment", which (for variables) is a mapping from names to memory address. Here is the output:
Stack: [] Store: map{1000->255, 1001->255, 1002->255, 1003->255} About to do OP(loadconst, 6) Stack: [6] Store: map{1000->255, 1001->255, 1002->255, 1003->255} About to do OP(store, 1000) Stack: [] Store: map{1000->6, 1001->0, 1002->255, 1003->255} About to do OP(load, 1000) Stack: [6] Store: map{1000->6, 1001->0, 1002->255, 1003->255} About to do OP(loadconst, 7) Stack: [7, 6] Store: map{1000->6, 1001->0, 1002->255, 1003->255} About to do OP(mult) Stack: [42] Store: map{1000->6, 1001->0, 1002->255, 1003->255} About to do OP(store, 1002) Stack: [] Store: map{1000->6, 1001->0, 1002->42, 1003->0}
After this informal example, here's a specification of my machine. First, I must explain that I represent the machine state as a quintuple:
MACHINE( Stack, Store, PC, In, Out )where
Stack
is the evaluation stack, as already explained;
Store
is the mapping from address to value, as also
explained;
PC
is the program counter;
In
is the input stream, represented as a list of
values to input;
Out
is the output stream, represented as a list of the
values already output.
I'll demonstrate these state components, including how the input and output streams get consumed and built up, in the next example run. I should point out that, though real machines have program counters and memory, as well as evaluation stacks if they are stack machines, they do not store their input and output streams as lists. After all, all the input from the terminal, for example, is not likely to exist when the program starts running. The lists are an abstraction, somewhat removed from reality, but useful when describing machine semantics mathematically.
Now that I've described the machine state, I can specify the machine instructions in terms of how they affect it. I'll do so as an informal translation of the interpreter into English. The interpreter implements each instruction as a function that takes one state quintuple and returns another. Again, this is an abstraction, useful because it makes it easy to specify the semantics mathematically. These, then, are the instructions:
storebyte Loc
:
Pops the top element off the stack,
and stores it as a byte in location Loc.
store Loc
:
Pops the top element off the stack,
and stores its least significant byte
at location Loc
and its most significant
byte at Loc+1
.
loadconst Const
:
Pushes Const
onto the stack.
load Loc
:
Pushes a word onto the stack:
its least significant byte is the byte at
location Loc
; its most significant
byte is the byte at Loc+1
.
loadbyte Loc
:
Pushes the byte at location Loc
onto the stack.
goto Label
:
Sets the program counter to
Label
.
jump_if_false Label
:
Pops the top element off the stack.
If it is 0, sets the program counter to
Label
, otherwise carries
on to the next instruction.
read
:
Pops the first element off standard input,
and pushes it onto the stack.
write
:
Pops the top element off the stack,
and appends to standard output a list
of the characters that
depict it as an integer. So if the top
element were 123, the interpreter would
append "123"
to standard output.
writestring
:
A string is represented by N+1
elements
on the stack, where the top
element is its length N
,
and the the remaining N
elements
are its characters. This operation
pops these elements, and appends the
resulting string to standard output.
eq
:
Pops the top two elements off the stack,
and pushes 1 if they are equal, otherwise 0.
not
:
Pops the top element off the stack, and
pushes 1 if it is 0, otherwise 1.
add
:
Pops the top two elements off the stack,
and pushes their sum.
sub
:
Pops the top two elements off the stack,
and pushes their difference
NextToTop-Top
.
mult
:
Pops the top two elements off the stack,
and pushes their product.
div
:
Pops the top two elements off the stack,
and pushes the
quotient NextToTop/Top
,
truncated to the nearest integer.
logand
:
Pops the top two elements off the stack,
and pushes 0 if either are 0, otherwise 1.
logor
:
Pops the top two elements off the stack,
and pushes
0 if both are 0, otherwise 1.
I'll end with a program to calculate
five factorial. The program listing is next,
annotated with "//" comments indicating
what each section of code does. The program
loops, incrementing a loop counter in locations
1000 and 1001, and accumulating the factorial
in locations 1002 and 1003. In my comments,
I've named these v
and
w
. The program writes its
result as an integer with the write
instruction, and accompanies that output with
strings emitted by writestring
. These
strings, are, as explained in the instruction-set
spec, held on the stack as a
sequence of character codes, with the value on top
of the stack giving the string length.
loadconst 46 loadconst 111 loadconst 108 loadconst 108 loadconst 101 loadconst 72 loadconst 6 writestring // // write('Hello.'); loadconst 1 store 1000 // // v := 1; loadconst 1 store 1002 // // w := 1; 46: // LOOP: load 1000 loadconst 5 eq jump_if_false 64 goto 96 64: // // if v=5 then goto OUT; load 1000 loadconst 1 add store 1000 // // v := v + 1; load 1002 load 1000 mult store 1002 // // w := w * v; goto 46 // // goto LOOP; 96: // OUT: loadconst 32 loadconst 61 loadconst 32 loadconst 118 loadconst 4 writestring // // write('v = '); load 1000 write // // write(v); loadconst 32 loadconst 61 loadconst 32 loadconst 33 loadconst 118 loadconst 5 writestring // // write('v! = '); load 1002 write // // write(w);
Stack: [] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 0 In : [] Out : [] About to do OP(loadconst, 46) Stack: [46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 4 In : [] Out : [] About to do OP(loadconst, 111) Stack: [111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 8 In : [] Out : [] About to do OP(loadconst, 108) Stack: [108, 111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 12 In : [] Out : [] About to do OP(loadconst, 108) Stack: [108, 108, 111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 16 In : [] Out : [] About to do OP(loadconst, 101) Stack: [101, 108, 108, 111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 20 In : [] Out : [] About to do OP(loadconst, 72) Stack: [72, 101, 108, 108, 111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 24 In : [] Out : [] About to do OP(loadconst, 6) Stack: [6, 72, 101, 108, 108, 111, 46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 28 In : [] Out : [] About to do OP(writestring) Stack: [] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 30 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 34 In : [] Out : [Hello.] About to do OP(store, 1000) Stack: [] Store: map{1000->1, 1001->0, 1002->255, 1003->255} PC : 38 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1] Store: map{1000->1, 1001->0, 1002->255, 1003->255} PC : 42 In : [] Out : [Hello.] About to do OP(store, 1002) Stack: [] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 46 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [1] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 50 In : [] Out : [Hello.] About to do OP(loadconst, 5) Stack: [5, 1] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 54 In : [] Out : [Hello.] About to do OP(eq) Stack: [0] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 56 In : [] Out : [Hello.] About to do OP(jump_if_false, 64) Stack: [] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 64 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [1] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 68 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1, 1] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 72 In : [] Out : [Hello.] About to do OP(add) Stack: [2] Store: map{1000->1, 1001->0, 1002->1, 1003->0} PC : 74 In : [] Out : [Hello.] About to do OP(store, 1000) Stack: [] Store: map{1000->2, 1001->0, 1002->1, 1003->0} PC : 78 In : [] Out : [Hello.] About to do OP(load, 1002) Stack: [1] Store: map{1000->2, 1001->0, 1002->1, 1003->0} PC : 82 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [2, 1] Store: map{1000->2, 1001->0, 1002->1, 1003->0} PC : 86 In : [] Out : [Hello.] About to do OP(mult) Stack: [2] Store: map{1000->2, 1001->0, 1002->1, 1003->0} PC : 88 In : [] Out : [Hello.] About to do OP(store, 1002) Stack: [] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 92 In : [] Out : [Hello.] About to do OP(goto, 46) Stack: [] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 46 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [2] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 50 In : [] Out : [Hello.] About to do OP(loadconst, 5) Stack: [5, 2] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 54 In : [] Out : [Hello.] About to do OP(eq) Stack: [0] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 56 In : [] Out : [Hello.] About to do OP(jump_if_false, 64) Stack: [] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 64 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [2] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 68 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1, 2] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 72 In : [] Out : [Hello.] About to do OP(add) Stack: [3] Store: map{1000->2, 1001->0, 1002->2, 1003->0} PC : 74 In : [] Out : [Hello.] About to do OP(store, 1000) Stack: [] Store: map{1000->3, 1001->0, 1002->2, 1003->0} PC : 78 In : [] Out : [Hello.] About to do OP(load, 1002) Stack: [2] Store: map{1000->3, 1001->0, 1002->2, 1003->0} PC : 82 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [3, 2] Store: map{1000->3, 1001->0, 1002->2, 1003->0} PC : 86 In : [] Out : [Hello.] About to do OP(mult) Stack: [6] Store: map{1000->3, 1001->0, 1002->2, 1003->0} PC : 88 In : [] Out : [Hello.] About to do OP(store, 1002) Stack: [] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 92 In : [] Out : [Hello.] About to do OP(goto, 46) Stack: [] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 46 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [3] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 50 In : [] Out : [Hello.] About to do OP(loadconst, 5) Stack: [5, 3] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 54 In : [] Out : [Hello.] About to do OP(eq) Stack: [0] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 56 In : [] Out : [Hello.] About to do OP(jump_if_false, 64) Stack: [] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 64 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [3] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 68 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1, 3] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 72 In : [] Out : [Hello.] About to do OP(add) Stack: [4] Store: map{1000->3, 1001->0, 1002->6, 1003->0} PC : 74 In : [] Out : [Hello.] About to do OP(store, 1000) Stack: [] Store: map{1000->4, 1001->0, 1002->6, 1003->0} PC : 78 In : [] Out : [Hello.] About to do OP(load, 1002) Stack: [6] Store: map{1000->4, 1001->0, 1002->6, 1003->0} PC : 82 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [4, 6] Store: map{1000->4, 1001->0, 1002->6, 1003->0} PC : 86 In : [] Out : [Hello.] About to do OP(mult) Stack: [24] Store: map{1000->4, 1001->0, 1002->6, 1003->0} PC : 88 In : [] Out : [Hello.] About to do OP(store, 1002) Stack: [] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 92 In : [] Out : [Hello.] About to do OP(goto, 46) Stack: [] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 46 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [4] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 50 In : [] Out : [Hello.] About to do OP(loadconst, 5) Stack: [5, 4] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 54 In : [] Out : [Hello.] About to do OP(eq) Stack: [0] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 56 In : [] Out : [Hello.] About to do OP(jump_if_false, 64) Stack: [] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 64 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [4] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 68 In : [] Out : [Hello.] About to do OP(loadconst, 1) Stack: [1, 4] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 72 In : [] Out : [Hello.] About to do OP(add) Stack: [5] Store: map{1000->4, 1001->0, 1002->24, 1003->0} PC : 74 In : [] Out : [Hello.] About to do OP(store, 1000) Stack: [] Store: map{1000->5, 1001->0, 1002->24, 1003->0} PC : 78 In : [] Out : [Hello.] About to do OP(load, 1002) Stack: [24] Store: map{1000->5, 1001->0, 1002->24, 1003->0} PC : 82 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [5, 24] Store: map{1000->5, 1001->0, 1002->24, 1003->0} PC : 86 In : [] Out : [Hello.] About to do OP(mult) Stack: [120] Store: map{1000->5, 1001->0, 1002->24, 1003->0} PC : 88 In : [] Out : [Hello.] About to do OP(store, 1002) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 92 In : [] Out : [Hello.] About to do OP(goto, 46) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 46 In : [] Out : [Hello.] About to do OP(load, 1000) Stack: [5] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 50 In : [] Out : [Hello.] About to do OP(loadconst, 5) Stack: [5, 5] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 54 In : [] Out : [Hello.] About to do OP(eq) Stack: [1] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 56 In : [] Out : [Hello.] About to do OP(jump_if_false, 64) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 60 In : [] Out : [Hello.] About to do OP(goto, 96) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 96 In : [] Out : [Hello.] About to do OP(loadconst, 32) Stack: [32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 100 In : [] Out : [Hello.] About to do OP(loadconst, 61) Stack: [61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 104 In : [] Out : [Hello.] About to do OP(loadconst, 32) Stack: [32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 108 In : [] Out : [Hello.] About to do OP(loadconst, 118) Stack: [118, 32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 112 In : [] Out : [Hello.] About to do OP(loadconst, 4) Stack: [4, 118, 32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 116 In : [] Out : [Hello.] About to do OP(writestring) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 118 In : [] Out : [Hello., v = ] About to do OP(load, 1000) Stack: [5] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 122 In : [] Out : [Hello., v = ] About to do OP(write) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 124 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 32) Stack: [32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 128 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 61) Stack: [61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 132 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 32) Stack: [32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 136 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 33) Stack: [33, 32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 140 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 118) Stack: [118, 33, 32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 144 In : [] Out : [Hello., v = , 5] About to do OP(loadconst, 5) Stack: [5, 118, 33, 32, 61, 32] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 148 In : [] Out : [Hello., v = , 5] About to do OP(writestring) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 150 In : [] Out : [Hello., v = , 5, v! = ] About to do OP(load, 1002) Stack: [120] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 154 In : [] Out : [Hello., v = , 5, v! = ] About to do OP(write) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 156 In : [] Out : [Hello., v = , 5, v! = , 120]