Stack Machine Info for CPSC 328

Stack Machine Info

The first part of this page lists the instructions in the abstract stack machine language for the course CPSC 328, taught in Winter '95 by David Eck. An "X" refers to a 32-bit data value to be used by the instruction. The interpretation of X depends on the instruction. The instructions are divided into five categories: basic operations, control and subroutines, numeric operators, logical operators and input/output.

More information is available below on the structure of the stack machine, using the stack machine, and the assembly language for the stack machine.

Instructions for the Stack Machine

Basic stack and memory operations.

sm_Push X
Push X onto the top of the stack. X can be any data value. Its interpretation will depend on how it is used once it is on the stack.
sm_Dupp
Duplicate the value on the top of the stack. This has the same effect as popping a value and then pushing the same value twice.
sm_Drop
Pop the top value from the stack and discard it.
sm_Swap
Interchange the two top values on the stack.
sm_ReserveBlock X
Increment top-of-stack by X. X must be a non-negative integer. This has the same effect as pushing X indeterminate values onto the stack. You might use this to reserve space for the global variables in a program or for the local variables in a subroutine.
sm_FreeBlock X
Decrement top-of-stack by X. X must be a non-negative integer. This has the same effect as dropping X values from the stack. You might use this before exiting from a subroutine to free up the space used by its local variables.
sm_Fetch
Pops a value from the top of the stack. That number is interpreted as an address. The value stored at that address is then pushed onto the stack.
sm_Store
Pops a value from the stack. Then pops another value. The second value is interpreted as an address. The first value that was popped is stored at that address.
sm_CheckRange
Can be used to check that a number is within a specified range of values. Three values are popped from the stack in the order: end-of-range, start-of-range, value-to-check. These are all interpreted as integers. If the value-to-check falls within the range of values from start-of-range to end-of-range, inclusive, then the value-to-check is simply pushed back onto the stack. If not, then a fatal error is generated.
sm_FetchBlock X
The purpose of this instruction is to push a sequence of values, such as an entire array or record, onto the stack. X gives the number of values in the sequence to be fetched; it is interpreted as an integer. The starting address of the sequence of values is popped from the stack. Then each of the values in the sequence is pushed onto the stack.
sm_StoreBlock X
The purpose of this instruction is to store a sequence of values, such as an entire array or record, from the top of the stack into memory starting at some specified location. X gives the number of values in the sequence; it is interpreted as an integer. These values are taken from the top of the stack. The starting address should be on the stack beneath the X valuse that are to be stored. The values and the address are all removed from the stack.
sm_TraceStores X
This instruction is provided for your convenience in debugging. It turns a tracing feature on if X is any non-zero number and off if X is zero. Ordinarily this feature is off. When it is on, any time an sm_store is executed it will be reported.
Instructions for subroutines and control.

sm_SetBase X,
sm_RestoreBase, and
sm_Offset
These instructions are useful for accessing the information in the activation record of a subroutine. This data must be accessed as an offset from the beginning of the record. The stack machine remembers the beginning of the currently active record in a register called the base. The command sm_Offset adds this starting location to the number on the top of the stack. That number, presumably, is the relative address of some item in the activation record; adding the base to the number gives the absolute address, which could then be used in an sm_Store or sm_Fetch instruction. Sm_SetBase pushes the current value of the base onto the stack. It then sets the base to the current top-of-stack minus~X. Sm_RestoreBase pops a value from the stack and sets the base to that value. Sm_SetBase is part of the normal subroutine calling sequence. Sm_RestoreBase is used as part of returning from the subroutine.
sm_Jump X,
sm_JumpIfTrue X, and
sm_JumpIfFalse X
Instructions in a stack machine program are numbered 0, 1, 2, \dots. Sm_jump transfers control to instruction number X in the program. Sm_JumpIfTrue and sm_JumpIfFalse are conditional jump instructions. They pop a value from the stack. Sm_JumpIfTrue will transfer control if that value is non-zero. Sm_JumpIfFalse will transfer control if the popped value is zero.
sm_Subroutine X,
sm_Return
Sm_Subroutine is like sm_Jump. except that before control is transferred to instruction number X, a return address is pushed on the stack. Sm_Return pops a value from the stack. That value is interpreted as an instruction number. Control is transferred to that instruction.
sm_Halt
Halts execution of the program. You should be sure to put an sm_Halt instruction at the end of the program.
Numeric Operators.

sm_IntPlus,
sm_IntSubtract,
sm_IntTimes,
sm_IntDiv, and
sm_IntMod
These instructions pop two values from the stack. The values are interpreted as integers. The operation is performed and the integer result is pushed back onto the stack.
sm_IntDivide
Pops two values from the stack. The values are interpreted as integers. A division is performed, giving a floating point result that is pushed back onto the stack.
sm_IntUnaryMinus, and
sm_IntAbs
A single value is popped from the stack. It is interpreted as an integer. The operation is performed and the integer result is pushed back onto the stack.
sm_FloatPlus,
sm_FloatSubtract,
sm_FloatTimes, and
sm_FloatDivide
Two values are popped from the stack. They are interpreted as floating point numbers. The operation is performed and the floating point result is pushed back onto the stack.
sm_FloatUnaryMinus,
sm_FloatAbs,
sm_Sin,
sm_Cos,
sm_Arctan,
sm_Sqrt,
sm_Ln, and
sm_Exp
A single value is popped from the stack. It is interpreted as a floating point number. The operation is perfromed and the floating point result is pushed back onto the stack.
sm_Trunc, and
sm_Round
A single value is popped from the stack. It is interpreted as a floating point number. The operation is performed, giving an integer result. That integer is pushed back onto the stack.
sm_Random
Nothing is popped from the stack. A random integer in the range from $-2^{15}$ to $2^{15}-1$ is pushed onto the stack.
sm_IntToFloat
A number is popped from the stack. It is interpreted as an integer. That integer is converted to a floating point number, which is pushed back onto the stack.
sm_FirstOpIntToFloat
Similar to sm_IntToFloat, except that the number on the top of the stack is not affected. Instead, the value one down from the top is converted from integer to floating point.
Logical Operators.

sm_And,
sm_Or, and
sm_Not
These operators pop values from the stack that are interpreted as logical values. The number zero represents false. Any other value represents true, but when a logical value is computed, the number one is used to represent true. Sm_and and sm_or pop two values from the stack; sm_Not pops a single value. The result is computed and pushed back onto the stack.
sm_IntEQ,
sm_IntNE,
sm_IntGT,
sm_IntLT,
sm_IntGE, and
sm_IntLE
Two values are popped from the stack. They are interpreted as integers. The comparison is performed and the result---0 to represent false or 1 to represent true---is pushed back onto the stack.
sm_FloatEQ,
sm_FloatNE,
sm_FloatGT,
sm_FloatLT,
sm_FloatGE, and
sm_FloatLE
Two values are popped from the stack. They are interpreted as floating point numbers. The comparison is performed and the result---0 to represent false or 1 to represent true---is pushed back onto the stack.
Input/Output operators.

sm_WriteInt
Two numbers are popped from the stack. The first number popped is interpreted as a field width. The second is interpreted as an integer. That integer is written to the I/O window, using the specified field width, as in write(n: w).
sm_WriteFloat
Two numbers are popped from the stack. The first number popped is interpreted as a field width. The second is interpreted as a floating point number. That number is written to the I/O window, using the specified field width, as in write(X: w).
sm_WriteDecimal
Three numbers are popped from the stack. The first is interpreted as the number of decimal places desired in the output. The second is interpreted as a field width. The third is interpreted as a floating point number. That number is written to the I/O window, using the specified field width, as in write(X: w: d).
sm_WriteString
A value is popped from the stack. It is interpreted as a string descriptor. The string is specifies is written to the I/O window.
sm_WriteChar
A value is popped from the stack. It is interpreted as (the ASCII code of) a character. That character is written to the I/O window.
sm_WriteBoolean
A value is popped from the stack. It is interpreted as a logical value (0 representing false and anything else representing true). The appropriate Boolean constant TRUE or FALSE is written to the I/O window.
sm_WriteNewLine
Nothing is popped from the stack. An end-of-line is written to the I/O window.
sm_Readln
Has the same effect as a ``readln'' command in Pascal. That is, reads up to and including the next end-of-line encountered in input.
sm_FillBuffer,
sm_FlushBuffer
You probably won't need these, since they don't correspond directly to things in Pascal. sm_FillBuffer waits for the user to type in a line an puts it into the internal input buffer. Sm_FlushBuffer empties that buffer. Nothing is popped from the stack.
sm_Eoln
Pushs a logical value, 0 or 1, onto the stack indicating whether and end-of-line is the next character waiting to be read in the input buffer.
sm_ReadInt
Tries to read an integer from input and pushes the number read onto the stack. May cause a run-time error.
sm_ReadFloat
Tries to read a floating point number from input and pushes the number read onto the stack. May cause a run-time error.
sm_ReadChar
Reads a character from input and pushes it---that is, its ASCII code---onto the stack.
sm_LookChar
Looks at the next character to be read from input and pushes it onto the stack, without removing it from the input buffer.

Structure of the Stack Machine

The "stack machine" that you will be using in this course has two major components, the Main Memory and the I/O Window. It also has a few other pieces: a Top-of-stack Register, a Base Register, and an I/O Buffer, and a String Storage Area. The I/O Buffer and I/O Window are used by the stack machine's input/output operators, and you don't really need to know anything more about them.

The stack machine also has a program, which you can think of as being stored in a separate set of memory locations if you like. The instructions in the program are numbered 0, 1, 2, 3, and so forth. Instruction numbers are used in jump and subroutine instructions.

The String Storage Area is just an array of characters, The characters are numbered 0, 1, 2, 3 and so forth. Strings are not themselves stored in Main Memory. Instead, the characters in the string are placed in the String Storage Area. The string is then referred to by a "string descriptor", which is a record consisting of two 16-bit integers. The first integer gives the starting position of the string in the String Storage Area. The second integer gives the number of characters in the string. Fortunately, you probably won't have to deal with string descriptors directly because strings are handled in a reasonably straightforward way by the assembly language of the stack machine.

The Main Memory of the stack machine is organized as a sequence of locations numbered 0, 1, 2, 3, etc. There is no fixed limit on the number of locations you can use. Each location holds a 32-bit value. The same value can be interpreted, depending on the instruction that references it, as either

an integer,
a floating-point number,
a string descriptor,
the address of a location in memory, or
the instruction number of an instruction in the program.

As far as the stack machine is concerned, any value in memory is just a string of 32 bits. It is up to you to see that values are interpreted correctly by your program. Fortunatly, a lot of difficulty is avoided by the way the five types of values are handled by the assembly language of the stack machine.

The Top-of-Stack Register is just an integer indicating the current top of stack. It is incremented by 1 by an sm_Push instruction, for example. It actually indicates the next available (currently unused) memory location.

The Base Register is probably the hardest part of the stack machine to understand. You will use it only to access the local variables and parameters of procedures and functions. It holds an integer that represents the start of the activation record of the currently active procedure or function. The hard part is maintaining the correct value in this register at all times. This is done with the sm_SetBase and sm_RestoreBase commands, which you can read about above.

Using the Stack Machine

When you translate a Pascal program into a stack machine program, there are certain conventions you should follow. This is not the only way to use the stack machine, but it is probably the only reasonable way to use it to run Pascal programs. I would suggest, to start, thay you organize the memory as follows:

First in memory, starting at location zero, come the global variables. Your compiled program should start execution with an sm_ReserveBlock to reserve these memory locations for this use.

Following the global variables comes the "stack" itself. This stack is used to hold the activation records of any active procedures or functions. When a procedure or function is called, an activation record is created for it. The activation record holds its local variables and parameters. When the procedure or function ends, its activation record is removed from the stack.

The stack is also used as workspace for evaluation of expressions. The space at the top of the stack, on top of any current activation records, is used for this purpose.

Assembly Language for the Stack Machine

Your compiler will output a program written in a simple "assembly language" for the abstract stack machine. It's really stretching things to call it an assembly language, since it is only a small step away from machine language. However, it does allow you to use symbolic lables instead of numbers in jump instructions. And it does let you write numbers and strings in reasonable formats. Here is a short sample program:

   L1  sm_push  :Enter a number (Enter 0 to end): 
       sm_WriteString
       sm_ReadInt
       sm_dupp
       sm_JumpIfTrue  L2
       sm_halt
   L2  sm_push  :Enter another number: 
       sm_WriteString
       sm_ReadInt
       sm_IntTimes
       sm_Push  :The product is 
       sm_WriteString
       sm_push  1
       sm_WriteInt
       sm_WriteNewLine
       sm_Jump  L1

Each line of the program contains an instruction. Some instructions have operands, such as the "L2" in the fifth line or the string "Enter a number (Enter 0 to end):" in the second line. Some instructions are preceded by labels, such as L1 and L2 in this sample program.

It is also legal to have several labels on one line, or to have a label on a line by itself (in which case, it refers to the next instruction that is encountered). The only labels you can use are L1, L2, L3, ..., L999. Labels can be used as operands in the instructions sm_Jump, sm_JumpIfTrue, sm_JumpIfFalse and sm_Subroutine.

There is no provision for using symbolic names for memory locations. You will have to work with actual integers.

In the machine language of the stack machine, an operand is just a string of 32 bits. An operand in assembly language is really just a way of specifying a 32-bit value:

An operand that begins with a digit or a minus sign is assumed to be an integer.
An operand that begins with an "L" is treated as a label; it is translated into an integer representing an appropriate instruction number.
An operand that begins with an "F" is assumed to be a floating point number. The F is skipped, and then a floating point number is read and translated into a 32-bit real value.
An operand that begins with a ":" is assumed to be a string. The ":" is skipped, and then a string is read. The string consists of all characters up to the next end-of-line. The characters are stored in the String Storage Area and a 32-bit string descriptor is used as the operand.
Finally, an operand that begins with a "$" is assumed to be a hexadecimal number. The "$" is skipped and a hexadecimal integer is read. (You will probably not have any need for this.)

Thus, in the first instruction of the sample program, it is really a string descriptor that is pushed onto the stack. That string descriptor is then popped from the stack and used by the sm_WriteString instruction.

Note that there is nothing to stop you from using an inappropriate operand. For example, if you push two integers onto the stack and then use a floating point operator such as sm_FloatPlus on them, you will get a completely meaningless answer.