A very important aspect of the Pop-11 "virtual machine" is the stack. This is a part of the computer's memory used as a communication area in connection with procedures which take "arguments" (inputs) and return results, and also in connection with assignment.
Consider a statement in which the value of an arithmetic expression is printed, for example:
2 + 2 =>
** 4
This statement is processed in two stages; firstly the arithmetic expression is evaluated and then secondly the result is printed. The result of evaluating the arithmetic expression is left on the stack, from where the print routine removes it.
As with a stack of plates, the last thing put on the stack is the first one you get off. Because the stack can accommodate more than one result, it is possible to write several expressions separated by commas, or semi-colons, each of which causes something to be put on the stack. For example:
2 + 3, 10 * 2, 5 - 3 =>
If this instructions is obeyed then three numbers are put on the stack with 5 at the bottom, then 20 and finally 2 on the top. The print arrow prints the ENTIRE stack, starting from the bottom, and empties it, thus:
** 5 20 2
Note that the top element of the stack is printed last.
The stack is in some ways like a datastructure, e.g. a variable-sized list or a vector, to which other Pop-11 objects can be added or removed at one end only, like a stack of dishes on to which new dishes can be added, one at a time, and from which the top item can be removed.
The stack is implemented differently from a Pop-11 datastructure, for efficiency. And it is not itself an object that can be put in a list, assigned to a variable, or given as input to a procedure. In fact there is no explicit way of referring to the stack. Rather it is implicitly referred to in very many Pop-11 instructions. It is not, what is sometimes referred to as a "first-class object".
A language that uses a stack in a similar way to Pop-11 is Forth. Some pocket calculators also use a stack in the same sort of way.
Procedures communicate via the stack
Pop-11 procedures take their parameters, if any from the top of the stack, and leave their results, if any, on the stack. Thus the procedure SIN removes the top item from the stack, computes its sine, and place this number on the stack. When you write:
sin(45) =>
** 0.707107
Then three things happen:
(1) 45 is put on the stack
(2) SIN is called (invoked, applied, run...). SIN removes the
top item (in this case, 45), computes its sine (in this case
0.7071), and puts this on the stack
(3) The print arrow, '=>' prints and empties the stack.
Had we wished to be obscure, we could have written, with exactly the same effect:
45;
sin();
=>
If there is nothing on the stack for a procedure like SIN then it complains and we get a MISHAP message.
Whatever is currently on the top of the stack is used by the procedure SIN. If this expression were executed with the stack empty, a MISHAP message would be printed indicating that the stack had underflowed, thus:
sin() =>
;;; MISHAP - STE: STACK EMPTY (missing argument? missing result?)
;;; DOING : sin compile compile
Provided the number of parameters (arguments) put on the stack when a procedure is called is the same number as taken by the procedure, any numbers previously on the stack are unaffected by the transaction.
Note the difference between writing
sin;
which loads the sin procedure itself onto the stack and
sin();
which actually causes the sin procedure to be executed. It may be useful to think of "()" as the "doit" brackets. If there's anything between the brackets, that says "doit to...", e.g. sin(45).
The stack and arithmetic expressions
The stack is used while evaluating arithmetic expressions so that a statement such as:
2 + 3 -> x;
actually takes place in four steps, thus:
(1) Put 2 on the stack
(2) Put 3 on the stack
(3) Do the addition, that is remove the top two items on the stack
(ie 2 and 3) and replace them by their sum (ie 5)
(4) Remove the top item from the stack (ie 5) and put it in
the variable X.
A more complicated example, such as:
2 + 3 * 4 - 5 =>
takes place in EIGHT steps, which are left as an exercise for the reader to describe, some of which are:
(4) Do a multiplication
(5) Do an addition
(7) Do a subtraction
(8) Print the contents of the stack
Implicit uses of the stack
The Pop-11 stack is implicitly referred to in the following contexts:
1. Any Pop-11 expression which denotes some object, is implicitly
an instruction to create or find the object and put it on the
stack. (For most types of object this really amounts to putting a
"pointer" to the object on the stack. The object itself remains
somewhere in memory. For integers and single precision decimals,
a copy of the internal representation is put on the stack.)
E.g.
"3 + 5" puts 8 on the stack
"hd(tl([the black cat]))" puts "black" on the stack
x,y,z; puts the values of x, y and z
on the stack, in that order.
2. When a procedure is invoked with some arguments, the arguments
are put on the stack and then the procedure is run. E.g.
3 + 4
Puts 3 on the stack, then 4, then runs +
hd(list)
Puts the value of list on the stack then runs hd
3. If a procedure invoked with arguments has some input variables,
then when the procedure is run, the appropriate number of items
is taken off the stack and assigned to the variables within the
procedure.
define perim(len, breadth) -> total;
The command to run perim, will cause the item on top of the stack
to be removed and assigned to to the input local variable
breadth, then the next item will be removed from the stack and
assigned to len, and then the instructions in the procedure
definition will be obeyed, using these variables.
4. If a procedure is defined to produce any results, then invoking
the procedure will implicitly cause the results to be put on
the stack when the procedure is finished. For example, if the
numbers 3 and 4 are on the stack, and the addition procedure +
runs, then the procedure, when it has finished, will replace the
top two items on the stack with the single result, the number 7.
So the instruction
3 + 4 =>
is equivalent to these four instructions
3;
4;
+;
=>
Another example is what happens when the perim procedure
finishes. Because it has an "output" local variable in the header
line, i.e. "total", then Pop-11 will ensure that just before the
procedure finishes the value of the variable will be put on the
stack.
Exercise: Explain why case 4 is just a special example of case 1.
5. When an assignment instruction is run, e.g.
x -> y
the left hand side, in accordance with point 1 above, causes
the value of the expression to be put on the top of the stack
(i.e. the value of the variable x is put on the stack), and then
the rest of the instruction ( "-> y") causes the item on the top
of the stack to be removed and stored as the value of the
variable y. (I.e. the value is stored in the area of memory
associated with the variable.)
NOTE: there is a potential point of confusion. When the left hand
side of such an expression puts the value of x on the stack it
does not remove the value from x. Thus x still has the same value
as before and it can be re-used. For example the instructions:
x; x; x;
cause the value of x to be put on the stack three times.
By contrast, when the top of the stack is assigned to a variable
it is removed from the top of the stack. Thus if there is only
one thing on the stack you can obey the instruction to move it
to y, thus
99; ;;; Put 99 on the stack
-> y; ;;; move top of stack to y
But attempting to do the same again
-> y; ;;; move top of stack to y
will cause an error message to be printed out if there was
originally only one thing on the stack.
;;; MISHAP - ste: STACK EMPTY (missing argument? missing result?)
Note: although you can assign the top of the stack to a variable, you cannot assign it to a constant object, such as the number 37, or a string, or a word. If you try any of these:
3 + 4 -> 7;
"cat" -> 'dog';
33 -> [a b c];
then you will get the following error message:
;;; MISHAP - iue: IMPERMISSIBLE UPDATE EXPRESSION (e.g. after -> or ->>)
33 -> 44;
Back to Introduction
Back to Chapter 1
Go to Chapter 3
Go to Conclusion
Go to References