H. RECURSION AND THE PUSH-DOWN LIST

One of the most powerful resources of the LISP language is its 
ability to accept function definitions that make use of the very 
function that is being defined. This may come about either 
directly by using the name of the function, or indirectly through 
a chain of function definitions that eventually return to the 
original ones. A definition of this type is called recursive. 
Its power lies in its ability to define an algorithm in terms of 
itself.

A recursive definition always has the possibility of not 
terminating and of being infinitely regressive. Some recursive 
definitions may terminate when given certain inputs and not 
terminate for others. It is theoretically impossible to 
determine whether a definition will terminate in the general 
case; however, it is often possible to show that particular cases 
will or will not terminate.

LISP is designed in such a way that all functions for which the 
possibility of recursion can exist are in fact recursive. This 
requires that all temporary stored results related to the 
computation that is in progress be set aside when a piece of 
coding is to be used recursively, and that they be later 
restored. This is done automatically and need not be programmed 
explicitly.

All saving of temporary results in LISP is performed on a linear 
block of storage called the push-down list. Each set of stored 
data that is moved onto the push-down list is in a block labeled 
with its size and the name of the subroutine from which it came. 
Since it is in the nature of recursion that the first block to be 
saved is always the last block to be restored, it is possible to 
keep the push-down list compact.

The frontier of the push-down list can always be found by 
referring to the cell CPPI. The decrement of this cell contains 
the complementary address of the first available unused location 
on the push-down list. Index register 1 also contains this 
quantity, except during certain nonrecursive subroutines; in 
these last cases it must be restored upon leaving these routines.

There are two types of blocks to be found on the push-down list, 
those put there by SAVE, and those put there by *MOVE. SAVE 
blocks are moved from fixed locations in certain subroutines onto 
the push-down list, and then moved back to the place where they 
came from by UNSAVE. Each block contains parameters that tell 
UNSAVE how many words are to be moved, and where they are to be 
moved to.

Functions compiled by the LISP compiler do not make use of 
storage cells located near the actual programming. All data are 
stored directly on the push-down list and referenced by using 
index register 1. *MOVE is used to update CPPI and index 
register 1, to place the arguments on the push-down list, and to 
set up the parameters for the push-down block.

Because pointers to list structures are normally stored on the 
push-down list, the garbage collector must mark the currently 
active portion of the push-down list during a garbage collection. 
Sometimes quantities are placed on the push-down list which 
should not be marked. In this case, the sign bit must be 
negative. Cells on the active portion of the push-down list 
having a negative sign bit will not be marked.

When an error occurs, an examination of the push-down list is an 
excellent indication of what was occurring at the time of the 
error. Since each block on the push-down list has the name of 
the function to which it belongs, it is possible to form a list 
of these names. This is called the backtrace, and is normally 
printed out after error diagnostics.