[ Jocelyn Ireson-Paine's Home Page | Publications | Dobbs Code Talk Index | Dobbs Blog Version ]

Demonstrating a Mini-Compiler with a Stack-Machine Program that Calculates Factorials

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.

Contents

A small example: loading from memory, evaluating an expression, and storing back into memory

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}

The machine state

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

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.

The machine code

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:

A bigger example: calculating five factorial

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.

The program

Here is the program. It is followed by output, which now shows the program counter, and the standard input and output, as well as the stack and the store:
  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);

The output

  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]