STACKM (= STACK Machine)

In this chaper we will introduce a simple model of a computer, the STACKM. In the next chapter we will show how a program that compiles abstract LANG1 programs into programs for STACKM can again be presented as a homomophism between appropriate algebras.

The Machine

The STACKM is a simple stack machine that can run programs written as strings over a set of instructions that manipulate the full state of the machine which consists of a memory Mem, a stack Stack, a register R and an instruction counter C. The following diagram gives a visualization of the machine:

The program, Prog, is a string of instructions (as described below).

The contents of the memory, Mem, can be viewed as a partial function from the set Id = {a, b, c, ...., z} of identifiers to the set Val = Z {true, false} of integers and booleans. Equivalently, we can view it as a (subarray of a) JavaScript array of the form [["a", v_a], ["v". v_b],..., ["z", v_z]], where for each iId, v_i.Val= Z {true, false}.

The contents of the stack, Stack, can be viewed as a string on the set Val, i.e. an element of Val*.

The contents of the register, R, is an element of the set Val.

The contents of the counter, C, is a positive integer indicating the number of the current instruction (its location in the string of instructions that constitute the program)

We may think the machine as operating be repeating the following steps

The contents of C are used to extract the current instruction and send it to the CPU (the Central Processing Unit)
The CPU examines the current instruction to determine the relevant data (from C, R Stack and Mem) and to determine the current operation
The CPU the accesses the relevant data and applies the current operation to this data
The results are then used to modify the contents of C, R, Stack and Mem.

Here is a listing of the instructions for StackM together with an informal description of the overall effect (described under the assumption that the stack contains an appropriate number of values of the appropriate type)

z, for zZ, (puts the integer z on the stack and increases the contents of C by 1)
b, for b{true, false}, (puts the boolean b on the Stack and increases the contents of C by 1)
get(i), for iId = {a,b,c,...,z} (puts the current value of the identifer i in Mem onto the stack and increases the contents of C by 1)
put(i), for iId = {a,b,c,...,z} (Removes the top element on Stack and puts that value into memory location i in Mem and increases the contents of C by 1)
frR (puts the contents of the register R onto Stack and increases the contents of C by 1)
toR (Removes the top element from Stack, puts that value into the register R and increases the contents of C by 1)
add (Removes the two top elements from Stack, adds them together, puts the result on Stack and increases the contents of C by 1)
mult (Removes the two top elements from Stack, multiplies them together, puts the result on Stack and increases the contents of C by 1)
nand (Removes the two top elements from Stack, nands them together, puts the result on the Stack and increases the contents of C by 1) -- note, nand(b,b') = not(b and b')
neg (removes the top element from Stack, negates it (integer negation), puts the result on Stack and increases the contents of C by 1)
leq (Removes the two top elements from the Stack, if the second element is greater than the first then "true" is put on the stack, otherwise false is put on Stack, then the contents of C is increased by 1)
branch(n), for nN⁺ = {1,2,3,....} (removes the top element on the Stack, then, if it is "true" the value of the contents of C changes to n, otherwise the contents of C are increased by 1)
If the above definitions do not make sense (e.g., if the stack has too few elements, the stack of elements of the wrong type, or if C is changed to a value greater than the length of the program) then the machine stops. There are two stopping modes:

Program Errors: For example, arrival at a state where the stack has too few elements or elements of the wrong type. These will probably result in a Java Script error which we can regard as a "crash" by STACKM. We will be able to show that the compiler does not produce programs that cause STACKM to "crash".

Program Termination: This will occur only if a state is reached in which the contents of C are greater than the length of the program. This will be the way in which compiled programs will halt. It will also be the basis of the LANG1Syn-algebra structure that we impose on the set of STACKM programs.

Here is a typical StackM program together with a corresponding flow diagram (written using assignment statements, etc.) Note that we have numbered the instructions to make it easier to interpret the program.

1      0
2      put(c)
3      get(a)
4      get(b)
5      leq
6      branch(18)
7      get(c)
8      1
9      add
10      put(c)
11    get(a)
12    get(b)
13    neg
14    add
15    put(a)
16    true
17    branch(3)

Assuming we start this program in a state in which C = 1 and in a memory state in which "a" has value n and "b" has value p with n,p

Z, then the result will be a state in which "a" has value n mod p, "b" has value p, and "c" has value n div p where div is integer division. That is, if n mod p = r, and n div p = d, then n = d*p + r.

An Implementation of StackM in JavaScript

In this implementation a program is written as a JavaScript array of StackM instructions written as JavaScript strings, e.g., we write ["get(a)", "get(b)", "mult", "put(c)" ] rather than

get(a)
get(b)
mult
put(c)

Memory states are also written as JavaScript arrays of identifier/value pairs with 0 as the default value. E.g., as in our treatment of LANG1 states, we write [["a", 7], ["b", 2]] to denote the state s:IdVal, such that s("a") = 7, s(b) = 2, and s( i ) = 0 for all other i

Id.

setSTM(prog, mem): Given JavaScript arrays for a program, prog, and a memory, mem, the application of setSTM will put StackM into an initial state with

C = 1
R = 0
S = []
Prog = prog
Mem = mem

stateSTM( ): Will display the current internal state of StackM. Note, the UA-Calculator contains a default state for StackM -- this program, stateSTM( ), can be used to display that state (providing that the default state has not been modified by applications of the programs setSTM, stepSTM, or runSTM).
stepSTM( ): Will do one full step in the operation of StackM starting from the current state -- it will return the resulting state.
runSTM(num): will do num full steps in the operation of StackM starting from the current state and, if the computation terminates, itl returns the resulting state. If the computation terminates in fewer than num steps then the result returned will be the terminal state.
applySTM(mem, num): Changes the memory of StackM to mem, then runs StackM for num steps starting from instruction 1 and, if the computation terminates, it returns the resulting contents of the memory.

Here are some example to try out.

Example 1: Here is a simple straight-line program that multiplies the values given for the identifiers "a" and "b" and assigns the result to "c". To "load the program" just click on the perform button. The program can be run in several different ways -- see directions below the calculator.

The program (once loaded -- see above) can be executed with four performances of stepSTM( ). Note, here is a relatively efficient way to do this

press "clear input" on the UA-calculator
copy, or write, stepSTM( ) onto the INPUT of the UA_calculator (n.b., you must click on the input panel before writing)
press "perform" on the UA_calculator
press "perform" on the UA_calculator
press "perform" on the UA_calculator
press "perform" on the UA_calculator

Remember that by clicking on the reset button you can reset the calculator to its original input.
After resetting the calculator try doing the computation using runSTM and applySTM.

press "perform" to load the program and memory
press "clear input" on the UA-calculator
copy, or write, runSTM( 4) onto the INPUT of the UA_calculator
press "perform" on the UA_calculator

end

Example 2: The program in this example is the one shown above for division. It divides the value of identifier "a" by the value of identifier "b" and assigns the integer part of the result to identifier "c" and the remainder to identifier "a". Executing the program with the given arguments (memory) takes 51 steps. Remember, you must load the program (by clicking on the perform button) before trying to run it. Then clear the input and enter runSTM(51). Or, you can enter, say, runSTM(10) and click "perform" six times.

WARNING: Your browser may "optimize" the HTML code used to produce the above example -- the example will then fail to work.
end

Now try writing and running your own programs!