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