Stacks

Last-in-first-out

You will sometimes come across the error message OUT OF STACK SPACE. A stack is an area of computer memory reserved for storing and retrieving data in a very special way. Under normal circumstances, a computer holds the data used by an application in a random access fashion. In other words, the data can be entered in and recovered from any one memory location just as easily as any other. In a stack, however, data is stored and retrieved strictly sequentially. This means that the first item stored goes in the first place in the stack, the second in the second place . . . and so on. That may seem straightforward enough, but, equally importantly, retrieval proceeds in exactly the reverse order. The last item placed in the stack is at any one time the only item which can be recovered. It is, therefore, not possible to get at the third item in a stack without recovering first any items which were stored there later. If there are five items on the stack, then item 5 must be retrieved, then item 4 and only then can item 3 be accessed. A stack implements a last-in-first-out (LIFO) storage technique.

It is obvious, now, why such a system is called a stack. If you imagine the data in stack memory as a vertical array, then it is handled just like a stack of plates. You can't put a plate in position 3 in a pile unless there is already a plate in position 2, and you can't pull plate 2 from the pile if there are plates stacked on top of it. OK, I know that you could if you were prepared to risk a collapse, but then analogies are not always perfect. This analogy has at least the advantage that it draws attention to the fact that there are usually very tight limits on the size of the stack, although, just to show how fickle we are, when the limit of the stack is reached it is common switch analogy and talk of stack overflow!

LOGO's use of the stack

As far as LOGO is concerned, the stack is the place where temporary information relevant to the running of a procedure is put on hold when that procedure calls another. When the call is returned, the appropriate information is retrieved from the stack. The display produced by duke.of.york 10 revealed clearly the operation of last-in-first-out storage technique. The variable values needed to continue duke.of.york 1 are put on the stack when duke.of.york 2 is called. When duke.of.york 2 calls duke.of.york 3 the appropriate variable values are again put on the stack on top of the preceding ones. . . As the recursion unwinds, the values needed by duke.of.york 3 are pulled off the stack (so that it can finish its work) and the values needed by duke.of.york 2 are thus made available for the moment when control is passed back to it . . . Everything works nicely until LOGO finds itself OUT OF STACK SPACE.

Ron Brasington
Department of Linguistic Science
The University of Reading
Reading
UK

E-mail: ron.brasington@rdg.ac.uk