{Note this chapter must become better organized, and clearer.}

{Note Everything should be checked carefully to see if it is the same in Interlisp-D, which uses deep binding --- how does this change things in this chapter?}

{index *BEGIN* pushdown list}
{index *BEGIN* variable bindings}
{index *PRIMARY* variable bindings}

A number of schemes have been used in different implementations of LISP for storing the values of variables.  These include:


{Begin Numberedlist}

{Item Storing values on an association list{index association list} paired with the
variable names.}

{Item Storing values on the property list of the atom which is the name of
the variable.}

{Item Storing values in a special value cell{index *PRIMARY* value cell} associated with the atom name, putting old values on a pushdown list, and restoring these values when exiting from a function.}

{Item Storing values on a pushdown list.}

{End Numberedlist}


Interlisp-10 uses the third scheme, so called "shallow binding".{index *PRIMARY* shallow binding}  When a function is entered, the value of each variable bound by the function (function argument) is stored in a value cell associated with that variable name.  The value that was in the value cell is stored in a block of storage called the basic frame{index basic frame} for this function call.  In addition, on exit from the function each variable must be individually unbound; that is, the old value saved in the basic frame must be restored to the value cell.  Thus there is a higher cost for binding and unbinding a variable than in the fourth scheme, "deep binding".  However, to find the current value of any variable, it is only necessary to access the variable's value cell, thus making variable reference considerably cheaper under shallow binding than under deep binding, especially for free variables.
However, the shallow binding scheme used does require an additional overhead in switching contexts when doing "spaghetti stack" operations. 


Interlisp-D uses the forth scheme, "deep binding."{index *PRIMARY* deep binding}  Every time a function is entered, a basic frame containing the new variables is put on top of the stack.  Therefore, any variable reference requires searching the stack for the first instance of that variable, which makes free variable use somewhat more expensive than in a shallow binding scheme.  On the other hand, spaghetti stack operations are considerably faster.  Some other tricks involving copying freely-referenced variables to higher frames on the stack are also used to speed up the search.  {note true?  I think I heard this somewhere....  if it is true, do we want to document it?}


The basic frames are allocated on a stack or pushdown list; for most user purposes, these frames should be thought of as containing the variable names associated with the function call, and the {it current} values for that frame.
The descriptions of the stack functions in below are presented from this viewpoint.  Both interpreted and compiled functions store both the names and values of variables so that interpreted and compiled functions are compatible and can be freely intermixed, i.e., free variables can be used with no {lisp SPECVAR} declarations necessary.  However, it is possible to {it suppress} storing of names in compiled functions, either for efficiency or to avoid a clash, via a {lisp LOCALVAR} declaration (see {PageRef Tag LocalVars}).
The names are also very useful in debugging, for they make possible a complete symbolic backtrace in case of error.

In addition to the binding information, additional information is associated with each function call: access information indicating the path to search the basic frames for variable bindings, control information, and temporary results are also stored on the stack in a block called the frame extension.  The interpreter also stores information about partially evaluated expressions as described on {PageRef Tag InterpreterBlips}.



{Begin SubSec The Spaghetti Stack}
{Title The Spaghetti Stack}
{Text


{index *BEGIN* spaghetti stacks}


The Bobrow/Wegbreit paper, "A Model and Stack Implementation for Multiple Environments",{foot
{it Communications of the ACM,} Vol. 16, 10, October 1973.
}{comment endfootnote}
describes an access and control mechanism more general than the simple pushdown stack.  The access and control mechanism used by Interlisp is a slightly modified version of the one proposed by Bobrow and Wegbreit.  This mechanism is called the "spaghetti stack."


The spaghetti system presents the access and control stack as a data structure composed of "frames." The functions described below operate on this structure.   These primitives allow user functions to manipulate the stack in a machine independent way.  Backtracking, coroutines, and more sophisticated control schemes can be easily implemented with these primitives.


The evaluation of a function requires the allocation of storage to hold the values of its local variables during the computation.   In addition to variable bindings, an activation of a function requires a {term return link} (indicating where control is to go after the completion of the computation) and room for temporaries needed during the computation.  In the spaghetti system, one "stack" is used for storing all this information, but it is best to view this stack as a tree of linked objects called {term frame extension}s (or simply {index frames}{term frame}s).


A {index frame extension}frame extension is a variable sized block of storage containing a {index frame name}frame name, a pointer to some variable bindings (the {index BLINK}BLINK), and two pointers to other frame extensions (the {index ALINK}ALINK and {index CLINK}CLINK).  In addition to these components, a frame extension contains other information (such as temporaries and reference counts) that does not interest us here.


The block of storage holding the variable bindings is called a {index *PRIMARY* basic frame}basic frame.  A basic frame is essentially an array of pairs, each of which contains a variable name and its value.  The reason frame extensions point to basic frames (rather than just having them "built in") is so that two frame extensions can share a common basic frame.  This allows two processes to communicate via shared variable bindings.


The chain of frame extensions which can be reached via the successive ALINKs from a given frame is called the {index access chain}"access chain" of the frame.  The first frame in the access chain is the starting frame.  The chain through successive CLINKs is called the {index control chain}"control chain".


A {index frame extension}frame extension completely specifies the variable bindings and control information necessary for the evaluation of a function.  Whenever a function (or in fact, any form which generally binds local variables) is evaluated, it is associated with some frame extension.


In the beginning there is precisely one frame extension in existence.  This is the frame in which the top-level call to the interpreter is being run.  This frame is called the "top-level" frame.


Since precisely one function is being executed at any instant, exactly one frame is distinguished as having the "control bubble" in it.   This frame is called the {index active frame}active frame.  Initially, the top-level frame is the active frame.  If the computation in the active frame invokes another function, a new basic frame and frame extension are built.  The {index frame name}frame name of this basic frame will be the name of the function being called.  The ALINK, BLINK, and CLINK of the new frame all depend on precisely how the function is invoked.  The new function is then run in this new frame by passing control to that frame, i.e., it is made the active frame.


Once the active computation has been completed, control normally returns to the frame pointed to by the CLINK of the active frame.  That is, the frame in the CLINK becomes the active frame.


In most cases, the storage associated with the basic frame and frame extension just abandoned can be reclaimed.  However, it is possible to obtain a pointer to a frame extension and to "hold on" to this frame even after it has been exited.  This pointer can be used later to run another computation in that environment, or even "continue" the exited computation.


A separate data type, called a {index stack pointer}stack pointer, is used for this purpose.  A stack pointer is just a cell that literally points to a frame extension.  Stack pointers print as  {lisp #{arg ADR}/{arg FRAMENAME}}, e.g., {lisp #1,13636/COND}.  Stack pointers are returned by many of the stack manipulating functions described below.  Except for certain abbreviations (such as "the frame with such-and-such a name"), stack pointers are the only way the user can reference a frame extension.  As long as the user has a stack pointer which references a frame extension, that frame extension (and all those that can be reached from it) will not be garbage collected.



{Tag EQPStackPointers}

Note that two stack pointers referencing the same frame extension are {it not} necessarily {fn EQ}, i.e., {lisp (EQ (STKPOS 'FOO) (STKPOS 'FOO))}={lisp NIL}.  However, {fn EQP} can be used to test if two different stack pointers reference the same frame extension ({PageRef Fn EQP}).


It is possible to evaluate a form with respect to an access chain other than the current one by using a stack pointer to refer to the head of the access chain desired.  Note, however, that this can be very expensive when using a shallow binding scheme such as that in Interlisp-10.  When evaluating the form, since all references to variables under the shallow binding scheme go through the variable's value cell, the values in the value cells must be adjusted to reflect the values appropriate to the desired access chain.  This is done by changing all the bindings on the current access chain (all the name-value pairs) so that they contain the value current at the time of the call.  Then along the new access path, all bindings are made to contain the previous value of the variable, and the current value is placed in the value cell.   For that part of the access path which is shared by the old and new chain, no work has to be done.  The {index context switching}context switching time, i.e. the overhead in switching from the current, active, access chain to another one, is directly proportional to the size of the two branches that are not shared between the access contexts.  This cost should be remembered in using generators and coroutines ({PageRef Tag Generators}).


}{End SubSec The Spaghetti Stack}