{Begin SubSec The Stack and the Interpreter}
{Title The Stack and the Interpreter}
{Text


{index *PRIMARY* Stack and the interpreter}
{index *PRIMARY* Interpreter and the stack}

{index *PRIMARY* Blips on the stack}

{index *PRIMARY* Interpretor blips on the stack}

{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 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*}.  {indexX {Name ARG} {Type Stack blip} {Text {lisp *ARG{arg N}}}}{indexX {Name *ARG} {Type Stack blip} {Text {lisp *ARG{arg N}}}}{lisp *ARG1}, {ellipsis}, {lisp *ARGn} 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.





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}

{Label {indexX {Name FN} {Type stack blip} {Text {lisp *FN*}}}{index *PRIMARY* *FN* (stack blip)}{lisp *FN*}}
{Text The name of a function about to be called.}

{Label {indexX {Name ARGVAL} {Type stack blip} {Text {lisp *ARGVAL*}}}{index *PRIMARY* *ARGVAL* (stack blip)}{lisp *ARGVAL*}}
{Text An argument for a function about to be called.}

{Label {indexX {Name FORM} {Type stack blip} {Text {lisp *FORM*}}}{index *PRIMARY* *FORM* (stack blip)}{lisp *FORM*}}
{Text A form in the process of evaluation.}

{Label{indexX {Name TAIL} {Type stack blip} {Text {lisp *TAIL*}}}{index *PRIMARY* *TAIL* (stack blip)}{lisp *TAIL*}}
{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 Stack and the Interpreter}