The Book

B: The Stack Machine

Memory Architecture

Instructions

The Stack Machine uses JavaScript functions to simulate machine instructions. Beginning with Machine10 the machine classes generate and store the instructions in an array code[] which is considered immutable once filled.

To simplify visual inspection of code[], the instructions are implemented through methods of the machine classes. Methods for simple instructions such as Add directly use memory as an argument, i.e., they are instruction functions. Other methods such as Branch require a memory address, etc., as arguments and return the actual instruction functions. All of the instruction functions manipulate memory in some way.

There are two interpreters which call the instruction functions:

  • The stack machine uses one JavaScript array memory for frames and the value stack.

  • The garbage-collected stack machine uses memory for global information followed by the value stack, and individually allocated arrays for the frames. These arrays have a property .id with a unique value for tracing; .id is initialized from memory.id.

To enable single step execution the interpreters return memory with a property .continue indicating if the program is suspended (true) or has terminated (false).

Example 6/10: Arithmetic Expressions

memory use
0 ... values of global variables
size ... value stack

Six.Machine10

Add (memory)                           // stack: ... a b -> ... a+b
Divide (memory)                        // stack: ... a b -> ... a/b
Input (dflt)                             // stack: ... -> ... input
Load (addr)                       // stack: ... -> ... memory[addr]
Minus (memory)                            // stack: ... a -> ... -a
Multiply (memory)                      // stack: ... a b -> ... a*b
Pop (memory)                               // stack: ... val -> ...
Push (result)                           // stack: ... -> ... result
Puts (memory)                  // stack: ... val -> ... | puts(val)
Store (a)            // stack: ... val -> ... val  | memory[a]: val
Subtract (memory)                      // stack: ... a b -> ... a-b

Example 6/11: Control Structures

memory use
.pc register next address in code to execute
0 ... values of global variables
size ... value stack

Six.Machine11 extends Six.Machine10

Branch (a)                             // stack: ... -> ... | pc: a
Bzero (a)                  // stack: ... bool -> ... | pc: !bool? a
Eq (memory)                         // stack: ... a b -> ... a == b
Ge (memory)                         // stack: ... a b -> ... a >= b
Gt (memory)                          // stack: ... a b -> ... a > b
Le (memory)                         // stack: ... a b -> ... a <= b
Lt (memory)                          // stack: ... a b -> ... a < b
Ne (memory)                         // stack: ... a b -> ... a != b
Print (n)                                // stack: ... n*val -> ...

Example 7/04: Functions

memory use
.pc register next address in code to execute
0 ... values of global variables
frame
+0 result value of function call
+1 return address in code for function call
... stack

Seven.Machine04 extends Six.Machine11

// stack: ... -> ... old-pc | pc: addr
Call (addr)   
// stack: ... old-pc -> ,,, 0 old-pc
Entry (memory)   
// stack: ... old-pc -> ... | pc: old-pc
Return (memory)   
// stack: ... x old-pc result -> ... result old-pc result
ReturnValue (memory)

Example 7/06: Local Variables

memory use
.pc register next address in code to execute
.fp register base address of current frame in memory
0 ... values of global variables
frame
+0 ... argument values for the parameters
+parms return address in code for function call
+parms+1 dynamic link, i.e., address in memory of previous frame
+parms+2 result value of function call
+parms+3 ... values of local variables
... stack

Seven.Machine06 extends Seven.Machine04

// stack: ... arguments old-pc
//     -> ... arguments old-pc old-fp result locals
Entry (parms, size)
// stack: ... arguments old-pc old-fp result locals
//     -> ... result old-pc
Exit (parms)
// stack: ... -> ... frame[addr]
LoadFP (addr)
// stack: ... val -> ... val | frame[addr]: val
StoreFP (addr)

Example 7/13: Nested Functions

memory use
.pc register next address in code to execute
.fp register base address of current frame in memory
.dp register base address of current display in memory
0 ... values of global variables
frame
+0 ... values of parameter arguments
+parms return address in code for function call
+parms+1 address in memory of previous frame
+parms+2 address in memory of previous display
+parms+3 result value of function call — memory.dp points here
+parms+3+1 ... base addresses of visible frames
+parms+3+depth base address of this frame — at depth
+parms+4+depth ... values of local variables
... stack

Seven.Machine13 extends Seven.Machine06

// stack: ... arguments old-pc
//     -> ... arguments old-pc old-fp old-dp result display locals
Entry (parms, depth, size)
// stack: ... arguments old-pc old-fp old-dp result display locals
//     -> ... result old-pc
Exit (memory)
// stack: ... -> ... frame[depth][addr]
LoadDP (addr, depth) 
// stack: ... val -> ... val | frame[depth][addr]: val
StoreDP (addr, depth)

Example 8/01: Global first-order Functions

Same memory layout as Local Variables above.

mix-in Eight.Machine01()

// stack: ... addr -> ... old-pc | pc: addr`
CallValue (memory)  
// stack: ... x-len n*val -> ... n*val x-len`
Rotate (n, len = 1)

Example 8/08: Functions as Argument Values

Same memory layout as Nested Functions above.

This machine requires two slots to represent a function value: display pointer followed by function start address. This does not affect the Call, CallValue, and Return instructions.

mix-in Eight.Machine08()

// stack: ... arguments dp old-pc  
//        -> ... arguments old-pc old-fp old-dp result display locals`
Entry (args, depth, vars)  
// stack: ... arguments old-pc old-fp old-dp result display locals
//        -> ... result old-pc`
Exit (args)  
// stack: ... -> ... dp`
PushDP (memory)

Example 8/14: Nested first-order Functions

This machine manages frames dynamically: frames are separate arrays subject to JavaScript's garbage collection.

This machine requires two slots to represent a function value: frame pointer followed by function start address. This does not affect the Call, CallValue, and Return instructions.

memory use
.pc register next address in code to execute
.fp register null or Array of current frame
0 ... values of global variables
... stack
frame use
0 return address in code for function call
1 null or Array of previous frame
1+1 ... arrays of visible frames
1+depth Array of this frame (at depth)
2+depth result value of function call
3+depth extra slot, exactly if result value is function value
... argument values
... frame size-1 local variable values

mix-in Eight.Machine14()

// stack: ... arguments fp old-pc  
//        -> ... | frame: old-pc old-fp display result arguments locals`
Entry (args, depth, result, vars)  
// stack: ... | frame: old-pc old-fp display result ...  
//        -> ... result old-pc | fp: old-fp | frame unchanged`
Exit (depth, result)  
// stack: ... -> ... frame[depth][addr]`
LoadGC (addr, depth)  
// stack: ... -> ... fp`
PushFP (memory)  
// stack: ... val -> ... val | frame[depth][addr]: val`
StoreGC (addr, depth)

Example 11/10: Compiling Arithmetic Expressions

This mix-in for code generation extends Six.Machine10 with a Power instruction to support exponentiation.

mix-in Eleven.Code_Number()

Power (memory)                        // stack: ... a b -> ... a**b

Example 11/11: Compiling a Little Language

This mix-in for code generation extends Six.Machine11 with a Bnzero instruction to optimize code generation for while loops. It requires Eleven.Symbols.

mix-in Eleven.Code_Stmts()

Bnzero (a)                  // stack: ... bool -> ... | pc: bool? a

Example 11/12: Compiling a Typed Little Language

These mix-ins for code generation extend Six.Machine11 with instructions to support code generation for Boolean and string values and conversions.

mix-in Eleven.Code_Bool()

IfTrue (a)             // stack: ... bool -> ... bool | pc: bool? a
IfFalse (a)           // stack: ... bool -> ... bool | pc: !bool? a
Not (memory)                              // stack: ... a -> ... !a

mix-in Eleven.Code_String()

Concat (memory)                        // stack: ... a b -> ... a+b
Len (memory)                        // stack: ... a -> ... a.length
InputString ('prompt', 'default')       // stack: ... -> ... string

mix-in Eleven.Code_Cast()

Cast ('to', 'from')                   // stack: ... a -> ... cast a