TEACH STACK updated A.Sloman March 1990 THE POP-11 USER STACK ===================== This file explains the use of the "open" stack in Pop-11. The stack is a part of the memory of the computer used by Pop-11 for giving arguments to procedures and for procedures to produce their results. This file assumes that you alread know how to define and call procedures (see TEACH * DEFINE) how to declare variables and access or update their values (see TEACH * VARS). It is also useful to be familiar with marked ranges and methods of compiling a marked range in the editor, as explained in TEACH * MARK and TEACH * LMR. CONTENTS - (Use g to access required sections) -- Procedures and the stack -- How to interpret a procedure header -- Understanding the body of the procedure -- Assigning the result of running sumsq to a variable -- Assignment and the stack -- Procedure calls and the stack -- Infix operations -- Analysing a complex expression in terms of the stack -- The stack and the print arrow -- Mishaps and the stack POP-11 uses a portion of its memory known as 'the user stack', abbreviated usually as 'the stack', for procedures to store information temporarily when communicating with other procedures. (Besides the user stack, there is also a stacksused by the procedure-calling mechanism, but most users don't need to know about that.) It is called a STACK, because, like a stack of plates, you can add things on the top, and you can take things off the top. The thing you take off will always be the LAST thing that was put on. So procedures communicate information with one another as follows. If procedure A wants to run procedure B giving it certain inputs (arguments), it puts the arguments on the stack and then just runs B, leaving it to B to take them off, as needed. If when B has finished it has any information for its caller, A, it should leave the information on the stack, and A can take it off as needed, e.g. by printing it, by assigning it to a variable declared in A, or by calling another procedure that will use the information left on the stack by B. -- Procedures and the stack ------------------------------------------- Suppose you have a procedure which takes two numbers and produces the sum of their squares as a result: define sumsq(x, y) -> r; x*x + y*y -> r; enddefine; Mark and load this, and test it as follows: sumsq(3, 4) => sumsq(12,5) => -- How to interpret a procedure header -------------------------------- The Pop-11 compiler interprets the TOP line of the procedure definition as saying a number of things: define sumsq(x,y) -> r; Means: 1. This is a definition of a procedure, whose name is "sumsq". 2. It has three local variables, called x, y and r. 3. When it runs, there should be AT LEAST two items on the user stack. (There might be more items on the stack, because other procedures have stored information which is to be used later.) 4. The top two items should be removed from the stack, the top one being assigned to y and the next one to x (i.e. the assignments are in reverse order for "input" variables) 5. When the procedure finishes, the value of the variable R, whatever it is, should be left on the stack. (N.B. the procedure heading does not state that anything will be assigned to R. That has to be done inside the procedure.) ALL OF THAT is implied in just the first line of the procedure definition. Look at the procedure heading again and see how it gives all that information. It may be useful to remember the following "symmetry" between the "input variables" x, and y, and the "output" variable r. The input variables are used without any assignment arrow, yet values are assigned to them from the stack when the procedure starts up. The output variable appears to be preceded by an assignment arrow, yet its value is copied to the stack when the procedure finishes: the reverse of an assignment. Thus, the procedure form: define sumsq(x,y) -> r; enddefine; can be thought of as roughly meaning To do sumsq; make x, y and r local variables for the procedure sumsq. -> y; -> x; r; x*x + y*y -> r; enddefine; I.e. the body is x*x + y*y -> r; This says how the values given to x and y are to be used to work out what number to assign to r, so that it can be produced as the result at the end. Notice that in this case there is a REAL assignment to "r", unlike the use of "-> r" in the header, which merely says that when the procedure is finished the value of r must be put on the stack. -- Assigning the result of running sumsq to a variable ---------------- Now suppose you ask sumsq to find the sum of the squares of 3 and 4, and assign the result to the variable "z"; vars z; sumsq(3,4) -> z; Notice how this has the same general FORMAT as the procedure heading in the definition define sumsq(x,y) -> r; I.e. the format of the procedure heading gives a "pattern" for the USE of the procedure. The instruction: sumsq(3,4) -> z; translates into the following: 1. push 3 onto the stack 2. push 4 onto the stack 3. call the procedure sumsq (If defined as above, sumsq will "pop" two things off the stack, and when it has finished will push one thing onto the stack) 4. remove the top item from the stack and store it in the variable "z", (i.e. in the memory location associated with the name "z".) If you then type z => That says, push the value of "z" onto the stack, then run the "print arrow" procedure. The print arrow is defined in terms of instructions to print out (on the terminal) two asterisks, and then all the items on the stack. Notice that putting something on the STACK is not the same as printing something on the terminal. The computer cannot read what is on your screen, but it can examine and do things with items on the stack. -- Assignment and the stack ----------------------------------------- As implied above, whenever you use the assignment arrow "->" (except in a procedure heading) this is an instruction to move the top of the stack to somewhere else, usually to a variable. This is often described as "popping" something off the stack. E.g. -> item; means "pop" the top of the stack into the variable "item". The thing that was previously the second item on the stack will then become the new top of the stack. The assignment arrow "->" should not be confused with the print arrow "=>" which also uses things on the stack, but simply prints them on the screen. -- Procedure calls and the stack ----------------------------------------- In general, if you call a procedure, by typing its name, followed by various expressions between 'doit' parentheses, then this means: push the values of all the expressions (i.e. the things denoted by the expressions) onto the stack, then run the procedure. E.g. silly(x, sumsq(3,4), 99) Means: 1. push onto the stack all of the following the value of "x", the result of sumsq(3,4), 99 2. then run the procedure called SILLY Getting the result of SUMSQ(3,4) itself can be expanded in similar fashion, so the whole expression silly(x, sumsq(3,4), 99) translates to 1. push the value of x onto the stack 2. push 3 onto the stack 3. push 4 onto the stack 4. call the procedure called "sumsq" (It will take off two things and push its result onto the stack) 5. push 99 onto the stack 6. call the procedure called "silly" -- Infix operations ------------------------------------------------- Some procedures have names which are defined as 'infix operations': examples are + * =. So x * y means: push x onto the stack, push y onto the stack, run the multiplication procedure: * x + y = z means: 1. push the result of x + y onto the stack (by pushing, x, then y, then calling "+") 2. push the value of "z" onto the stack 3. call the procedure = (which takes two things off the stack, compares them, then puts back TRUE or FALSE as its result.) -- Analysing a complex expression in terms of the stack --------------- We can understand the middle line of the definition of sumsq in terms of the stack: x * x + y * y -> result; We assume as before that the addition procedure "+", and the multiplication procedure "*" both take two things off the stack and put back one thing. So the expression on the left x * x + y * y can be understood as push x onto the stack push x onto the stack run the procedure * (this takes two things off, and puts one back) push y onto the stack push y onto the stack (now there are three things onto the stack) run the procedure * (this takes two things off, and puts one back, leaving two things altogether) run the procedure + (this takes two things off and puts one back, leaving one thing on the stack) After that there is one thing on the stack. The second part of the line -> result; says: remove the top thing on the stack and assign it to the variable "result". I.e. store it in the portion of memory associated with the name "result". The order in which things are put on the stack and procedures executed depends on the conventions about the 'precedence' of + and *, i.e. when it's ambiguous do the multiplication first. The order can be altered by means of parentheses. For example: (x * x + y) * y translates to: push x onto the stack push x onto the stack run the procedure * (multiply) push y onto the stack (so far, exactly as before) run the procedure + (instead of doing the second * ) push y onto the stack run the procedure * In order to test your understanding, you should work out what each of the following means, and check your understanding by marking each line and executing it: 3 * 3 + 4 * 4 => (3 * 3 + 4) * 4 => 3 * (3 + 4 * 4) => (3 * 3) + 4 * 4 => 3 * (3 + 4) * 4 => 3 * 3 + 4 * 4 => (3 * 3) + (4 * 4) => (3 * 3 + 4 * 4) => Note: in some cases the parentheses don't make any difference because adding them does not alter the "conventional" grouping. -- The stack and the print arrow ----------------------------------------- See TEACH * PRINTARROW for information on the use of "=>" to print out things on the stack. -- Mishaps and the stack ----------------------------------------------- There is a very common mishap message associated with the stack MISHAP - STACK EMPTY (missing argument? missing result?) This happens when a procedure, or the assignment arrow, is trying to take something off the stack when there is nothing left on the stack. Try to mark and load the following: vars x; -> x; Because "-> x" tries to take something off the stack when there's nothing there, you'll get the "STACK EMPTY" error message. The reason why the error message includes "(missing argument? missing result?)" is that these are two frequent causes of STACK EMPTY errors (sometimes called "stack underflow" errors, as constrasted with "stack overflow" errors.) We can illustrate this with the procedure sumsq, defined above (look back at the definition if you don't remember it). Suppose you give the following Pop-11 command (try it and look carefully at the error message, then read on): sumsq(3) -> z; This would push 3 onto the stack, then run sumsq. sumsq would take the top of the stack (3) and assign it to y. It would then try to assign the top of the stack to x and find nothing left. You'd then get a stack error, with a message as above, except that the DOING line in the error message would be something like ;;; DOING : sumsq compile ... I.e. it shows you that it is doing sumsq at the time the error occurs. Looking at the DOING line is often essential for finding out the source of your errors. "sumsq(3)" was an example of a missing argument. You can also have a procedure which fails to produce a result. E.g. suppose the definition had been: define newsumsq(x,y); x * x + y * y -> x; enddefine; This is a bit subtle. If you type sumsq(3,4), x and y get the values 3 and 4 respectively (via the stack). Then the result of the expression x * x + y * y is assigned to x (which is local to sumsq so x will not have that value when sumsq is finished). At this stage, nothing is left on the stack. Moreover, the heading of the definition does not specify that x is an 'output local' variable for sumsq, so the value of x is not left on the stack. Nor is anything else left on the stack. Compile the above procedur definition, then run the following and look carefully at the error message, including the DOING line: vars z; newsumsq(3, 4) -> z; When this is obeyed, newsumsq runs, using up the 3 and the 4, then finishes with nothing on the stack. But the assignment arrow '->' tries to take something off the stack to give to "z", and at this point finds the stack empty, producing another mishap message. This time the problem is the missing RESULT from newsumsq, so that there is nothing to assign to z. This time the DOING line of the mishap message will not mention newsumsq. This is because newsumsq has finished running when the error occurs. I.e. it is no longer active when the error is detected. This can sometimes make it difficult to track down errors due to procedures failing to return a result. Usually you can get clues by looking at which procedures WERE active at the time, or by tracing procedures (as explained in TEACH * TRACE.) If you type newsumsq(3) -> z; You'll get the same mishap message, but this time the mishap is INSIDE sumsq, trying to take two things off the stack, for X and Y. You are advised to try all those examples, looking carefully at the error messages. For more on the stack see TEACH * DEFINE. Advanced programmers will find more information on procedures which manipulate the stack in HELP * STACK and some more technical information in REF * STACK and REF * VMCODE. There is more material explaining the Pop-11 stack in the following books: J. Laventhol Programming in POP-11 Blackwell Scientific Publications Ltd., 1987 R. Barrett, A Ramsay, A Sloman POP-11: a Practical Language for Artificial Intelligence Ellis Horwood and John Wiley,1985 See HELP * POPREFS for additional literature. --- C.all/teach/stack -------------------------------------------------- --- Copyright University of Sussex 1990. All rights reserved. ----------