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.
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.
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.
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.