{Begin SubSec The Push-Down List and the Interpreter}
{Title The Push-Down List and the Interpreter}
{Text


{index *PRIMARY* pushdown list}



{Tag InterpreterBlips}

In addition to the names and values of arguments for functions, information regarding partially-evaluated expressions is kept on the push-down list.  For example, consider the following definition of the function {lisp FACT} (intentionally faulty):


{lispcode
(FACT
   [LAMBDA (N)
      (COND
         ((ZEROP N)
           L)
         (T (ITIMES N (FACT (SUB1 N])}


In evaluating the form {lisp (FACT 1)}, as soon as {lisp FACT} is entered, the interpreter begins evaluating the implicit {fn PROGN} following the {lisp LAMBDA}.  The first function entered in this process is {fn COND}.  {fn COND} begins to process its list of clauses.  After calling {fn ZEROP} and getting a {lisp NIL} value, {fn COND} proceeds to the next clause and evaluates {lisp T}.  Since {lisp T} is true, the evaluation of the implicit {fn PROGN} that is the consequent of the {lisp T} clause is begun.  This requires calling the function {fn ITIMES}.  However before {fn ITIMES} can be called, its arguments must be evaluated.  The first argument is evaluated by retrieving the current binding of {lisp N} from its value cell; the second involves a recursive call to {lisp FACT}, and another implicit {fn PROGN}, etc.


Note that at each stage of this process, some portion of an expression has been evaluated, and another is awaiting evaluation.  The output below (from Interlisp-10) illustrates this by showing the state of the push-down list at the point in the computation of {lisp (FACT 1)} when the unbound atom {lisp L} is reached.

{Note this example isn't very clear}
{lispcode
←FACT(1)
u.b.a. L {bracket in FACT} in ((ZEROP N) L)
(L broken)
:BTV!

   *TAIL* (L)

   *ARG1 (((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N)))))
COND

   *FORM* (COND ((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N)))))
   *TAIL* ((COND ((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N))))))

   N 0
FACT


   *FORM* (FACT (SUB1 N))
   *FN* ITIMES
   *TAIL* ((FACT (SUB1 N)))
   *ARGVAL* 1
   *FORM* (ITIMES N (FACT (SUB1 N)))
   *TAIL* ((ITIMES N (FACT (SUB1 N))))

   *ARG1 (((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N)))))
COND

   *FORM* (COND ((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N)))))
   *TAIL* ((COND ((ZEROP N) L) (T (ITIMES N (FACT (SUB1 N))))))

   N 1
FACT

**TOP**}



Internal calls to {fn EVAL}, e.g., from {fn COND} and the interpreter, are marked on the push-down list by a special mark or blip {index backtrace}which the backtrace prints as {lisp *FORM*}.  The genealogy of {lisp *FORM*}'s is thus a history of the computation.  Other temporary information stored on the stack by the interpreter includes the tail of a partially evaluated implicit {fn PROGN} (e.g., a cond clause or lambda expression) and the tail of a partially evaluated form (i.e., those arguments not yet evaluated), both indicated on the backtrace by {lisp *TAIL*}, the values of arguments that have already been evaluated, indicated by {lisp *ARGVAL*}, and the names of functions waiting to be called, indicated by {lisp *FN*}.  {lisp *ARG1}, {ellipsis}, {lisp *ARGn}{index *ARG1 (as a blip on the stack)} are used by the backtrace to indicate the (unnamed) arguments to {lisp SUBR}s.


Note that a function is not actually entered and does not appear on the stack, until its arguments have been evaluated (except for nlambda functions, of course).  Also note that the {lisp *ARG1}, {lisp *FORM*}, {lisp *TAIL*}, etc. "bindings" comprise the actual working storage.  In other words, in the above example, if a (lower) function changed the value of the {lisp *ARG1} binding, the {fn COND} would continue interpreting the new binding as a list of {fn COND} clauses.  Similarly, if the {lisp *ARGVAL*} binding were changed, the new value would be given to {fn ITIMES} as its first argument after its second argument had been evaluated, and {fn ITIMES} was actually called.




{index blip functions}
{index blips}


Note that {lisp *FORM*}, {lisp *TAIL*}, {lisp *ARGVAL*}, etc., do not actually appear as variables on the stack, i.e., evaluating {lisp *FORM*} or calling {fn STKSCAN} to search for it will not work.
However, the functions {fn BLIPVAL}, {fn SETBLIPVAL}, and {fn BLIPSCAN} described below are available for accessing these internal blips.  These functions currently know about four different types of blips:


{Begin Labeledlist blips}

{Indent 20percent}

{Label {lisp *FN*}{index *FN* (as a blip on the stack)}}
{Text the name of a function about to be called}

{Label {lisp *ARGVAL*}{index *ARGVAL* (as a blip on the stack)}}
{Text an argument for a function about to be called}

{Label {lisp *FORM*}{index *FORM* (as a blip on the stack)}}
{Text a form in the process of evaluation}

{Label {lisp *TAIL*}{index *TAIL* (as a blip on the stack)}}
{Text the tail of a {fn COND} clause, implicit {fn PROGN}, {fn PROG}, etc.}

{End Labeledlist blips}



{FnDef {FnName BLIPVAL} {FnArgs BLIPTYP IPOS FLG}
{Text
Returns the value of the specified blip of type {arg BLIPTYP}.  If
{arg FLG} is a number {lisp N}, finds the {lisp N}th blip of the desired type, searching the control chain beginning at the frame specified by the stack descriptor {arg IPOS}.  If {arg FLG} is {lisp NIL}, 1 is used.  If {arg FLG} is {lisp T}, returns the number of blips of the specified type at {arg IPOS}.
}}



{FnDef {FnName SETBLIPVAL} {FnArgs BLIPTYP IPOS N VAL}
{Text
Sets the value of the specified blip of type {arg BLIPTYP}.
Searches for the {arg N}th blip of the desired type, beginning
with the frame specified by the stack descriptor {arg IPOS}, and
following the control chain.
}}



{FnDef {FnName BLIPSCAN} {FnArgs BLIPTYP IPOS}
{Text
Returns a stack pointer to the frame in which a blip of type
{arg BLIPTYP} is located.  Search begins at the frame specified by
the stack descriptor {arg IPOS} and follows the control chain.
}}



}{End SubSec The Push-Down List and the Interpreter}