Trailing-Edge - PDP-10 Archives - decuslib20-01 - decus/20-0004/12lisp.tty
There are no other files named 12lisp.tty in the archive.

                               SECTION 12

                        AND THE SPAGHETTI STACK

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

    1.   Storing values on an association list paired with  the variable

    2.   Storing values on  the property list of  the atom which  is the
         name of the variable.

    3.   Storing values in a special value cell associated with the atom
         name,  putting old  values on  a pushdown  list,  and restoring
         these values when exiting from a function.

    4.   Storing values on a pushdown list.

In INTERLISP, we currently use a variation on the fourth scheme, usually
used only  for transmitting values  of arguments to  compiled functions.
When a function is entered, the association of names with the  values of
variables (arguments) is accomplished  by putting both names  and values
in a block  of storage called the  basic frame for the  function.  These
basic frames  are allocated on  a stack or  pushdown list.  To  find the
value  of a  variable used  freely within  a function,  successive basic
frames are searched until a slot is found which contains the name of the
variable, and then the corresponding value is used.   Compiled functions
know about the relative position of variables within their  basic frame,
and  can  pick up  these  values immediately  without  search.  However,
compiled functions still 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  special
declarations necessary.   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: control information  indicating the
calling function, access information  indicating the path to  search the
basic frames, 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 below.

12.1 The Push-Down List and the Interpreter

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 fact (intentionally faulty):

      ((ZEROP N)
      (T (ITIMES N (FACT (SUB1 N])

In  evaluating  the form  (FACT 1),  as  soon as  fact  is  entered, the
interpreter begins  evaluating the implicit  progn following  the LAMBDA
(see Section 4).   The first function entered  in this process  is cond.
cond begins  to process its  list of clauses.   After calling  zerop and
getting a NIL value, cond  proceeds to the next clause and  evaluates T.
Since  T is  true, the  evaluation  of the  implicit progn  that  is the
consequent of  the T  clause is  begun (see  Section 4).   This requires
calling the function itimes.   However before itimes can be  called, its
arguments  must  be  evaluated.   The  first  argument  is  evaluated by
searching the  stack for the  last binding of  N; the second  involves a
recursive call to fact, and another implicit 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 illustrates this by showing the state of the push-down list at the
point in the computation of (FACT 1) when the unbound atom L is reached.


u.b.a. L {in FACT} in ((ZEROP N) L)

   *TAIL* (L)

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

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

   N 0

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

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

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

   N 1


Internal calls to eval, e.g., from cond and the interpreter,  are marked
on the  push-down list  by a special  mark or  blip which  the backtrace
prints as *FORM*.   The genealogy of *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 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 *TAIL*, the values  of arguments that  have already
been  evaluated,  indicated  by *ARGVAL*,  and  the  names  of functions
waiting to be called, indicated  by *FN*.  *ARG1, ... *ARGn are  used by
the backtrace to indicate the (unnamed) arguments to subrs.

    Note that *FORM*, *TAIL*, *ARGVAL*, etc., do not actually  appear on
    the backtrace, i.e., evaluating *FORM* or calling stkscan  to search
    for it  will not work.  However, the functions  blipval, setblipval,
    and  blipscan  described  below are  available  for  accessing these
    internal blips.


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

Blip Functions

The temporaries  of the interpreter,  or blips, can  be accessed  by the
following  three functions,  which currently  know about  four different
types of blips:

    *FN*      the name of a function about to be called
    *ARGVAL*  an argument for a function about to be called
    *FORM*    a form in the process of evaluation
    *TAIL*    the tail of a cond clause, implicit progn, prog, etc.

                        Returns the value of the specified blip  of type
                        bliptyp.  If flg is a number, finds the nth blip
                        of the desired type, searching the control chain
                        beginning at  the frame  specified by  the stack
                        descriptor ipos.  If flg is NIL, 1 is  used.  If
                        flg is  T, returns  the number  of blips  of the
                        specified type at ipos.

                        Sets  the value  of the  specified blip  of type
                        bliptyp.   Searches  for  the  nth  blip  of the
                        desired type, beginning with the frame specified
                        by the stack descriptor ipos, and  following the
                        control chain.

blipscan[bliptyp;ipos]  Returns a stack pointer to the frame in  which a
                        blip of type bliptyp is located.   Search begins
                        at the frame  specified by the  stack descriptor
                        ipos and follows the control chain.

12.2 The Pushdown List and Compiled Functions

Calls to compiled functions, and the bindings of their  arguments, i.e.,

    except for  functions which  do not  have their  arguments evaluated
    (although they themselves may call eval, e.g., cond).


names  and  values, are  handled  in  the same  way  as  for interpreted
functions  (hence  the compatibility  between  interpreted  and compiled
functions).   However,  compiled  functions treat  free  variables  in a
special way  that interpreted functions  do not.   Interpreted functions
"look up" free variables when the variable is encountered, and  may look
up the same  variable many times.   However, compiled functions  look up
each free variable only once.  Whenever a compiled function  is entered,
the stack is scanned and the most recent binding for each  free variable
used in the function is found (or if there is no binding, the value cell
is obtained) and  stored on the  stack (and marked  in a special  way to
distinguish this 'binding' from ordinary bindings).  Thus, following the
bindings  of  their arguments,  compiled  functions store  on  the stack
pointers to the bindings for each free variable used in the function.

12.3 The Spaghetti Stack

The  Bobrow/Wegbreit  paper,  "A  Model  and  Stack  Implementation  for
Multiple Environments" [Bob3], 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

Overview of Spaghetti Stack

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 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 frame extensions (or simply frames).

A frame  extension is  a variable  sized block  of storage  containing a
frame name,  a pointer to  some variable bindings  (the blink),  and two
pointers to other frame  extensions (the alink and 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 basic

    A list of all free variables is generated at compile time, and is in
    fact obtainable from the compiled definition. See Section 18.


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 access chain of the  frame.  The
first  frame in  the  access chain  is  the starting  frame.   The chain
through successive clinks is called the control chain.

A 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 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 frame
name of this basic frame will be the name of the function  being called.
The b-, a-, and clinks 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.

If  the  active computation  needs  the  value of  some  variable  it is
obtained by searching the access chain of the active frame.   Each blink
along the access chain is  scanned for the variable name.  If  a binding
is found, the associated value is used.  If none is found, the top-level
value is used.

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

A separate data type, called a 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 #adr/framename,  e.g., #117753/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) may  not (will not)  be garbage


Note that two  stack pointers referencing  the same frame  extension are
not  necessarily  eq,  i.e.,  (EQ  (STKPOS  'FOO)   (STKPOS  'FOO))=NIL.
However,  eqp  can be  used  to  test if  two  different  stack pointers
reference the same frame extension.

12.4 Stack Functions

In the descriptions  of the stack functions  below, when we refer  to an
argument  as a  stack descriptor,  we  mean that  it is  either  a stack
pointer or one of the following abbreviations:

    1.  NIL  means the  active frame; that  is, the  frame of  the stack
function itself.

    2.  T means the top-level frame.

    3.  Any other literal atom is equivalent to (STKPOS ATOM -1).

    4.  A number is equivalent to (STKNTH number).

In the stack functions described below, the following errors can occur.

ILLEGAL STACK ARG       Occurs when a  stack descriptor is  expected and
                        the  supplied  argument is  either  not  a legal
                        stack  descriptor  (i.e., not  a  stack pointer,
                        litatom, or number),  or is a litatom  or number
                        for which there is no corresponding  stack frame
                        (e.g., (STKNTH -1 (QUOTE FOO)) where there is no
                        frame named FOO  in the active control  chain or
                        (STKNTH -10 (QUOTE EVALQT)).

HAS BEEN RELEASED       Occurs  whenever  a  released  stack  pointer is
                        supplied as a stack descriptor argument  for any
                        purpose other than as a stack pointer to re-use.


                        Search for  the nth  frame with  name framename.
                        The search begins with (and includes)  the frame
                        specified by the stack descriptor  ipos (initial
                        position).   The   search  proceeds   along  the
                        control  chain from  ipos if  n is  negative, or
                        along the access chain  if n is positive.   If n
                        is NIL, -1 is used.  Returns a stack  pointer to
                        the  frame  if such  a  frame  exists, otherwise
                        returns NIL.  If opos is supplied and is a stack
                        pointer, it is reused.   If opos is not  a stack
                        pointer  it  is  ignored.   (Note  that  (STKPOS
                        (QUOTE STKPOS))  causes an error,  ILLEGAL STACK
                        ARG;  it is  not permissible  to create  a stack
                        pointer to the active frame.)


stknth[n;ipos;opos]      Returns a stack  pointer to the nth  frame back
                        from the frame specified by the stack descriptor
                        ipos.  If n is negative, the control  chain from
                        ipos is followed.   If n is positive  the access
                        chain  is followed.   If n  equals 0,  returns a
                        stack pointer to ipos, i.e., this provides a way
                        to copy a  stack pointer.  Returns NIL  if there
                        are  fewer  than  n  frames  in  the appropriate
                        chain.   If  opos  is supplied  and  is  a stack
                        pointer, it is reused.   If opos is not  a stack
                        pointer it  is ignored.   (Note that  (STKNTH 0)
                        causes an  error, ILLEGAL STACK  ARG; it  is not
                        possible to create a stack pointer to the active

stkname[pos]             Returns the  frame name of the  frame specified
                        by the stack descriptor pos.

stknthname[n;ipos]       Returns  the frame name  of the nth  frame back
                        from  ipos.   Equivalent to  (STKNAME  (STKNTH n
                        ipos)) but avoids creation of a stack pointer.

In summary,  stkpos converts  function names  to stack  pointers, stknth
converts numbers to stack  pointers, stkname converts stack  pointers to
function names, and stknthname converts numbers to function names.

The following  functions are used  for accessing and  changing bindings.
Some  of functions  take an  argument, n,  which specifies  a particular
binding in the basic frame.  If n is a literal atom, it is assumed to be
the name of a variable bound in  the basic frame.  If n is a  number, it
is assumed to reference the  nth binding in the basic frame.   The first
binding is  1.  If the  basic frame contains  no binding with  the given
name or if the number is  too large or too small, the error  ILLEGAL ARG

stkscan[var;ipos;opos]   Searches beginning at ipos for a frame in which
                        a  variable  named  var  is  bound.   The search
                        follows  the  access  chain.   Returns  a  stack
                        pointer to the frame if found, otherwise returns
                        NIL.  If opos is  a stack pointer it  is reused,
                        otherwise it is ignored.

framescan[atom;pos]      Returns the relative position of the binding of
                        atom in the basic frame of pos.

stkarg[n;pos]            Returns the value of the binding specified by n
                        in the basic frame of the frame specified by the
                        stack descriptor pos.   n can be a  literal atom
                        or number.


stkargname[n;pos]        Returns the name of the binding specified by n,
                        in the basic frame of the frame specified by the
                        stack descriptor pos.   n can be a  literal atom
                        or number.

setstkarg[n;pos;value]   Sets the value of the binding specified by n in
                         the basic frame  of the frame specified  by the
                         stack descriptor pos.  n can be a  literal atom
                         or a number.  Returns value.

setstkargname[n;pos;name]Sets the name of the binding specified by  n in
                         the basic frame  of the frame specified  by the
                         stack descriptor pos.  n can be a  literal atom
                         or a number.  Returns name.

stknargs[pos]            Returns  the number of  arguments bound  in the
                        basic frame of the frame specified by  the stack
                        descriptor pos.

As an example of the use of stknargs and stkargname:

variables[pos]          returns list of variables bound at pos.

can be defined by:

    (PROG (N L)
          (SETQ N (STKNARGS POS))
      LP  (COND
            ((ZEROP N)
              (RETURN L)))
          (SETQ N (SUB1 N))
          (GO LP])

The dual of variables is also available:

stkargs[pos]            Returns  list of  values of  variables  bound at

The  following  functions  are  used  to  evaluate  an  expression  in a
different environment, and/or to alter the flow of control.

                        evaluates form  in the environment  specified by
                        apos and cpos.  That  is, a new active  frame is
                        created with  the frame  specified by  the stack
                        descriptor  apos  as its  alink,  and  the frame


                        specified by  the stack  descriptor cpos  as its
                        clink.  Then form is evaluated.  If aflg  is not
                        NIL, and apos is a stack pointer, then apos will
                        be released.  Similarly, if cflg is not NIL, and
                        cpos  is  a  stack pointer,  then  cpos  will be

                        applys fn to  args in the  environment specified
                        by apos and cpos.   aflg and cflg have  the same
                        interpretation as with enveval.

stkeval[pos;form;flg]   Evaluates form in the access environment  of the
                        frame specified by the stack descriptor pos.  If
                        flg  is  not NIL  and  pos is  a  stack pointer,
                        releases  pos.   The  definition  of  stkeval is
                        (ENVEVAL FORM POS NIL FLG).

                        Similar to stkeval but applies fn to args.

reteval[pos;form;flg]   Evaluates form in the access environment  of the
                        frame specified by the stack descriptor pos, and
                        then returns from  pos with that value.   If flg
                        is not NIL and pos is a stack pointer,  then pos
                        is  released.   The  definition  of  reteval  is
                        equivalent     to    (ENVEVAL FORM POS (STKNTH -
                        1 POS) FLG T),  except  that  reteval  does  not
                        create a stack pointer.

                        Similar to reteval except applies fn to args.

retfrom[pos;val;flg]     Return  from the frame  specified by  the stack
                        descriptor pos, with  the value val.  If  flg is
                        not NIL, and pos is a stack pointer, then pos is
                        released.  An attempt  to retfrom the  top level
                        (e.g.,  (RETFROM  T)) causes  an  error, ILLEGAL
                        STACK ARG.  Retfrom  can be written in  terms of
                        enveval as follows:

                    ((STKNTH -1 POS (COND (FLG POS))))
                    (T (ERRORX (LIST 19 POS)))
                  NIL T)))

retto[pos;val;flg]      like retfrom, except returns to  frame specified
                        by pos.


evalv[x;pos]            Evaluates x, where x is assumed to be a litatom,
                        in the access environment specifed by  the stack
                        descriptor pos.  While evalv could be defined as
                        (ENVEVAL X POS) it  is in fact  a subr  which is
                        somewhat faster.

function[fn;env]        If env is  NIL, function is equivalent  to quote
                        when  interpreted and  is also  a signal  to the
                        compiler that fn should be compiled.  If  env is
                        a stack pointer,  then the value of  function is
                        the expression  (FUNARG fn env).  When  a funarg
                        expression is apply'd or is car of a  form being
                        eval'd,  the apply  or eval  takes place  in the
                        access  environment   specified  by   env.   For
                        example,  if FOO  is a  funarg  expression, then
                        (APPLY    FOO    FIE)    is     equivalent    to
                        (ENVAPPLY (CADR FOO) FIE (CADDR FOO)).   Env can
                        also be a list of variable names.  In this case,
                        a new  frame is created  with the values  of the
                        specified  variables  in the  basic  frame.  The
                        variables  are  evaluated in  the  active access
                        environment (the environment of  function).  The
                        alink  of the  new  frame is  the  active access
                        environment, and  clink is  the top  level.  The
                        value of function is (FUNARG fn pos),  where pos
                        is a stack pointer to the new frame.

The  following  functions and  variables  are used  to  manipulate stack

stackp[x]               Returns  x if  x is  a stack  pointer, otherwise
                        returns NIL.

relstk[pos]              Release the stack pointer pos.  If pos is not a
                        stack pointer, does nothing.  The value is pos.

clearstk[flg]             If  flg  is  NIL,  releases  all  active stack
                        pointers, and returns NIL.  If flg is T, returns
                        a  list  of all  the  active  (unreleased) stack

    Note that the effect of  funarg in the spaghetti system  is somewhat
    different from what it  was previously in non-spaghetti  system. Now
    when  the  funarg  is  apply'd  or  eval'd  we  see  in  the  access
    environment  first the  variables given  in the  list, and  then the
    access environment at the time the funarg was created.   Formerly we
    saw the  variables in the  list (the "own"  variables) and  then the
    access environment at the time the funarg was used.


clearstklst               Is  a  (global)  variable  used  by  top-level
                        evalqt.  Every time evalqt is  re-entered (e.g.,
                        following errors, or control-D),  clearstklst is
                        checked.  If  its value is  T, all  active stack
                        pointers  are released  using clearstk.   If its
                        value is a list, then all stack pointers on that
                        list are released.  If its value is NIL, nothing
                        is released.  clearstklst is initially T.

noclearstklst           is a global  variable used by  top-level evalqt.
                        If clearstklst is T (see above) all active stack
                        pointers  except  those  on   noclearstklst  are
                        released.  noclearstklst is initially NIL.

Thus if  one wishes  to use multiple  environments that  survive through
control-D, either clearstklst  should be set to  T, or else  those stack
pointers to be retained should be explicitly added to noclearstklst.

copystk[pos1;pos2]      Copies the  stack, including basic  frames, from
                        the frame specified by the stack descriptor pos1
                        to the frame  specified by the  stack descriptor
                        pos2.  That is, copies the frame  extensions and
                        basic frames  in the access  chain from  pos2 to
                        pos1 (inclusive).   Pos1 must  be in  the access
                        chain of pos2, i.e., "above" pos2.   Returns the
                        new pos2.  This provides a way to save an entire
                        environment including variable bindings.

                        Performs  a  backtrace  beginning  at  the frame
                        specified  by  the  stack  descriptor  ipos, and
                        ending  with the  frame specified  by  the stack
                        descriptor epos.  flags is a number in which the
                        options of the backtrace are encoded.  If  a bit
                        is   set,  the   corresponding   information  is
                        included in the backtrace.

    bit 0 - print arguments of non-subrs
    bit 1 - print temporaries of the interpreter
    bit 2 - print subr arguments and all temporaries
    bit 3 - omit printing of UNTRACE: and function names
    bit 4 - follow access chain instead of control chain.

For example:  if flags=7, everything  is printed; if  flags=21Q, follows
the access chain, prints arguments.


mapdl[mapdlfn;mapdlpos] starts  at  mapdlpos  and  applies   mapdlfn,  a
                        function of two arguments, to the  function name
                        at  each frame,  and the  frame  (stack pointer)
                        itself, until the  top of the stack  is reached.
                        Value is NIL.

For  example,  mapdl[(LAMBDA (X) (AND (EXPRP X) (PRINT X)))]  will print
all exprs on the push-down list.

print all functions of more than two arguments.

                        similar to  mapdl, except searches  the pushdown
                        list starting at position srchpos until it finds
                        a  frame for  which  srchfn, a  function  of two
                        arguments, applied to  the name of  the function
                        and  the  frame  itself is  not  NIL.   Value is
                        (name . frame)  if   such  a  frame   is  found,
                        otherwise NIL.

12.5 Releasing and Reusing Stack Pointers

The creation of a single stack pointer can result in the retention  of a
large amount of stack space.  Furthermore, this space will not  be freed
until  the next  garbage collection,  even if  the stack  pointer  is no
longer being used,  unless the stack  pointer is explicitly  released or
reused.  If there  is sufficient amount of  stack space tied up  in this
fashion, a STACK OVERFLOW condition  can occur, even in the  simplest of
computations.  For  this reason,  the user  should consider  releasing a
stack pointer when the environment referenced by the stack pointer is no
longer needed.

The effects of releasing a stack pointer are:

     1.  The link between the stack  pointer and the stack is  broken by
         setting  the contents  of the  stack pointer  to  the "released
         mark" (currently unboxed  0).  A released stack  pointer prints
         as #adr/#0.

     2.  If this  stack pointer  was the last  remaining reference  to a
         frame extension; that is, if no other stack  pointer references
         the frame extension and  the extension is not contained  in the
         active  control  or access  chain,  then the  extension  may be
         reclaimed, and is  reclaimed immediately.  The  process repeats
         for the access and control chains of the reclaimed extension so
         that all stack space that was reachable only from  the released
         stack pointer is reclaimed.

A stack pointer may be released using the function relstk, but there are
some  cases for  which  relstk is  not  sufficient.  For  example,  if a
function contains a call to retfrom in which a stack pointer was used to
specify where to return to,  it would not be possible  to simultaneously
release  the  stack  pointer.   (A  relstk  appearing  in  the  function
following the call to retfrom would not be executed!) To  permit release
of  a  stack  pointer  in  this  situation,  the  stack  functions  that


relinquish control have optional flag arguments to denote whether or not
a stack pointer is to be released.  Note that in this case releasing the
stack pointer will not cause the stack space to be reclaimed immediately
because the frame referenced by the stack pointer will have  become part
of the active environment.

Reusing Stack Pointers

Another way of  avoiding creating new stack  pointers is to  reuse stack
pointers that  are no  longer needed.  The  stack functions  that create
stack pointers (stkpos, stknth,  and stkscan) have an  optional argument
which is a stack pointer to reuse.  When a stack pointer is  reused, two
things happen.  First the  stack pointer is released (see  above).  Then
the  pointer  to the  new  frame  extension is  deposited  in  the stack
pointer.  The old stack pointer (with its new contents) is the  value of
the function.  Note that the reused stack pointer will be  released even
if the function does not find the specified frame.

Note that even if stack pointers are explicitly being released, creation
of many stack pointers can  cause a garbage collection of  stack pointer
space, GC: 5.   Thus, if the  user's application requires  creating many
stack pointers,  he definitely  should take  advantage of  reusing stack

12.6 Spaghetti and the Block Compiler

In order that the stack  discipline be consistent, it is  necessary that
all bindings that are either  used freely or are used  for communication
between processes, be contained  in some basic frame.  Basic  frames are
never copied, except explicitly and presumably intentionally by copystk.
If we have a stack structure such as:

                 |             |

where frame extensions  B1 and B2  share the basic  frame B, then  if B1
changes the value of  one of its variables  (in basic frame B),  the new
value  will  be  seen by  B2.   If  a binding  were  stored  in  a frame
extension, which is copied, then the two processes, B1 and B2 would each
have  their own  copies  of the  binding.  The  block  compiler produces
speedy  code  by avoiding  function  calls (and  hence  the  creation of
frames).  Bindings of  variables (including specvars) in  block compiled
code are  contained in  the frame extension.   Therefore one  should not
block compile any function that binds a "state variable" of  some multi-
process  computation.   We hope  to  restructure the  block  compiler to
eliminate  this problem  - but  for  the moment  it is  a  problem.  For
example, if we have the following two functions:



        (SETQ Y 3)
        (SETQ Y 4)

If FOO is interpreted or compiled individually (not block compiled) then
the value  of the  enveval is  4.  However, if  FOO is  a function  in a
compiled block and Y is a specvar, then the value of the enveval will be
3 because the  active frame for the  block containing FOO and  the frame
retained by mark have their own private copies of the binding of Y.

12.7 Coroutines and Generators

This section describes an application of the spaghetti stack facility to
provide mechanisms  for creating and  using simple generators  (with and
without CLISP, Section  23), generalized coroutines, and  Conniver style
possibility lists.

A  generator is  like a  subroutine except  that it  retains information
about previous times it has been called.  Some of this state may be data
(for example, the seed in a random number generator), and some may be in
program state (as in a recursive generator which finds all the  atoms in
a list structure).  For example, if listgen is defined using defineq as:

    (LISTGEN (L)
       (IF L THEN (PRODUCE L:1) (LISTGEN L::1)))

we  can  use  the  function  generator  (described  below)  to  create a
generator that uses listgen to produce  the elements of a list one  at a
time, e.g.,


creates a generator, which can be called by


to produce as values on  successive calls, A, B, C.  When  generate (not
generator)  is  called  the  first  time,  it  simply  starts evaluating
(LISTGEN '(A B C)).  produce gets called from listgen, and pops  back up
to  generate with  the  indicated value  after saving  the  state.  When
generate gets  called again,  it continues from  where the  last produce
left off.   This process continues  until finally listgen  completes and

    Designed  and  implemented  by   D.G.  Bobrow,  who  also   did  the
    documentation.   Early  versions of  the  Conniver possibilites-list
    package  were  written by  Henry  Thompson. Daryle  Lewis  found and
    corrected a number  of bugs, and wrote  the compiler macros  that go
    with the package.


returns a value (it doesn't  matter what it is).  generate  then returns
gr itself  as its value,  so that the  program that called  generate can
tell  that  it  is  finished,  i.e., there  are  no  more  values  to be

                        is an nlambda function that creates  a generator
                        which uses form## to compute values.   The value
                        of  generator  is a  generator  handle  which is
                        represented by a dotted pair of stack pointers.

                        comvar## is optional.  If its value (eval of) is
                        a generator handle, the list structure and stack
                        pointers  will  be  reused.   Otherwise,  a  new
                        generator handle will be constructed.

                        generator compiles open.

produce[val]            is  used from  within  (below) a  generator   to
                        return  val as  the value  of  the corresponding
                        call to generate.

generate[handle;val]    restarts  the generator  represented  by handle.
                        val will be returned as the value of the produce
                        which  last  suspended  the  operation   of  the
                        generator.   When  the  generator  runs  out  of
                        values, generate returns handle itself.


The following function will go down recursively through a list structure
and produce the atoms in the list structure one at a time.

    [LEAVESG (L)
        (if (ATOM L)
            then (PRODUCE L)
          else (LEAVESG L:1)
               (if L::1
                   then (LEAVESG L::1]

The following  function prints each  of these atoms  as it  appears.  It
illustrates how a loop can be set up to use a generator.

    (PLEAVESG1 (L)
       (PROG (X LHANDLE)
             (if X=LHANDLE
                 then (RETURN NIL))
             (PRINT X)
             (GO LP)))

Note that the loop terminates when  the value of the generator is  eq to
the dotted pair which is the value produced by the call to generator.  A


CLISP iterative operator, OUTOF, is provided which makes it  much easier
to write  the loop in  PLEAVESG1.  OUTOF (or  outof) can precede  a form
which is to  be used as a  generator.  On each iteration,  the iteration
variable will be set to successive values returned by the generator; the
loop will be terminated automatically when the generator runs out.  Thus
we can write

    (PLEAVESG2 (L)
       (for X outof (LEAVESG L) do (PRINT x))

as equivalent to the above program PLEAVESG1.

Here is another example:

     as I from 1 to N do (PRINT X))

will print the first n atoms.


This  package provides  facilities  for the  creation and  use  of fully
general coroutine structures.  It  uses a stack pointer to  preserve the
state of a coroutine, and allows arbitrary switching between n different
coroutines rather  than just  a call  to a  generator and  return.  This
package is slightly more efficient than the generator  package described
above, and allows more flexibility on specification of what to do when a
coroutine terminates.

                        This nlambda is  used to create a  coroutine and
                        initialize    the   linkage.     callptr##   and
                        coroutptr##  are  the  names  of  two variables,
                        which will be set to appropriate stack pointers.
                        If the  values of  callptr## or  coroutptr## are
                        already stack pointers, the stack  pointers will
                        be reused.   coroutform## is  the form  which is
                        evaluated to start the coroutine; endform## is a
                        form  to be  evaluated if  coroutform## actually
                        returns when it  runs out of  values.  coroutine
                        compiles open.

                        is used to  transfer control from  one coroutine
                        to another.  fromptr should be the stack pointer
                        for the current coroutine, which will be smashed
                        to preserve the current state.  toptr  should be
                        the stack pointer which has preserved  the state
                        of the coroutine  to be transferred to,  and val
                        is  the  value that  is  to be  returned  to the
                        latter  coroutine  as the  value  of  the resume
                        which suspended the operation of that coroutine.



The following is  the way one might  write the LEAVES program  using the
coroutine package:

              (if L::1 then (LEAVESC L::1 COROUTPTR CALLPTR))))

A function PLEAVESC which uses LEAVESC can be defined as follows:

                                         (LEAVESC L LHANDLE PLHANDLE)
                                         (RETFROM 'PLEAVESC))

By RESUMEing leavesc repeatedly, this function will print all the leaves
of list L and then return out of pleavesc via the retfrom.   The retfrom
is necessary to break out of the non-terminating do-loop.  This was done
to  illustrate the  additional flexibility  allowed through  the  use of

We use  two coroutines  working on  two trees  in the  example eqleaves,
defined below.  eqleaves  tests to see whether  two trees have  the same
leaf set in the same order, e.g., EQLEAVES((A B C)(A B (C))) is true.

       do (EL1_(RESUME PE LHANDLE1))
          (EL2_(RESUME PE LHANDLE2))
          (if EL1~=EL2
              then (RETURN NIL))
       repeatuntil EL1='NO-MORE finally (RETURN T)))

Possibilities Lists

A  possibilities  list  is  the  interface  between  a  generator  and a
consumer.   The  possibilities  list   is  initialized  by  a   call  to
possibilities, and elements are  obtained from it by using  trynext.  By
using  the  spaghetti  stack  to  maintain  separate  environments, this
package allows a regime  in which a generator can  put a few items  in a
possibilities list, suspend itself until they have been consumed, and be
subsequently aroused and generate some more.

    These functions are based on the CONNIVER system  possibilities list


possibilities[form##]   This nlambda is used for the initial creation of
                        a possibilities list.  form## will  be evaluated
                        to create the list.  It should use the functions
                        note and  au-revoir described below  to generate
                        possibilities.   Normally,  one  would  set some
                        variable  to  the  possibilities  list  which is
                        returned, so it can be used later, e.g.,:

                        (SETQ PLIST (POSSIBILITIES (GENERFN V1 V2))).

                        possibilities compiles open.

note[val;lstflg]        is used within a  generator to put items  on the
                        possibilities list  being generated.   If lstflg
                        is  equal to  NIL, val  is treated  as  a single
                        item.  If lstflg  is non-NIL, then the  list val
                        is nconced on the end of the possibilities list.
                        Note that it is perfectly reasonable to create a
                        possibilities list using a second generator, and
                        note that list as possibilities for  the current
                        generator  with lstflg  equal to  T.   The lower
                        generator  will  be resumed  at  the appropriate

au-revoir[val##]        puts an item on the possibilities list if one is
                        given. If no argument is given to au-revoir then
                        the generator is just suspended;  NIL is not put
                        on   the   possibilities  list   unless   it  is
                        explicitly given as an argument to au-revoir.  A
                        call  to  au-revoir suspends  the  generator and
                        returns to the  consumer in such a  fashion that
                        control will return to the generator at  the au-
                        revoir    if   the    consumer    exhausts   the
                        possibilities list.

adieu[]                 returns to the  consumer the items  currently on
                        the   possibilities  list.    It   releases  the
                        generator so that it can no longer be resumed.

                        This  nlambda  allows   a  consumer  to   use  a
                        possibilities list.   It removes the  first item
                        from the possibilities list plst##,  and returns
                        that  item,  provided  it  is  not  a  generator
                        handle.  If  a generator handle  is encountered,

    au-revoir is a lambda spread so  that the case where no value  is to
    be returned can be distinguished from the case where a NIL  value is


                        the generator is reawakened.  When it  returns a
                        possibilities list,  this list  is added  to the
                        front  of  the  current list.   When  a  call to
                        trynext causes a generator to be awakened, val##
                        is returned as the value of the  au-revoir which
                        put  that  generator  to  sleep.   If  plst## is
                        empty,  it evaluates  endform## in  the caller's

                        trynext compiles open.

cleanposlst[plst]       This function is  provided to release  any stack
                        pointers which may be left in the plst which was
                        not used to exhaustion.


(1) fib is a generator for fibonnaci numbers.  It starts out  by noteing
    its two arguments, then  suspends itself.  Thereafter, on  being re-
    awakened, it  will note two  more terms in  the series  and suspends
    again.  printfib uses fib to print the first N fibonacci numbers.

    [FIB (F1 F2)
      (do (NOTE F1)
          (NOTE F2)

         (PROG ((FL (GENERATOR (FIB 0 1))))
               (RPTQ N (PRINT  (TRYNEXT FL)))
               (CLEANPOSLST FL) ]

    Note that fib itself will never terminate.

(2) nodes is somewhat subtler.  It can be used to generate the  nodes of
    a tree in prefix, postfix, or infix order depending on the  value of
    type.  It takes as its first argument L a structure which  has three
    fields;  a head,  left-daughter and  right-daughter.   Suppose these
    fields are accessed by the functions HD, LD and RD respectively, and
    R is the following tree:

    Note that this just suspends  the generator and adds nothing  to the
    possibilities list except the generator.


    (N1 _ '(+ N2 N3))                           +
    (N2 _ '(X))                               / \
    (N3 _ '(  ** N4 N5))                    x     **
    (N4 _ '(Y))                                   / \
    (N5 _ '(3))                                  y    3

    Each subnode is generated  by using a possibilities list,  and these
    are oredered  on the basis  of type.  Notice  that since  nodes ends
    with an adieu, it does not persist.  printnodes uses nodes  to print
    the nodes of a tree in any of the three orders.

  (PROG [(VAL (HD L))
         (LD L)
         [LGEN (if (LD L)
                   then (POSSIBILITIES (NODE (LDL)
         [RGEN (if (RD L)
                   then POSSIBILITIES (NODES (RD L)
                      (PREFIX <! VAL LGEN RGEN>)
                      (INFIX  <! LGEN VAL RGEN>)
                      (POSTFIX <! LGEN RGEN VAL>)

    (foreach E from (NODES X TYPE) do (PRIN1 E) finally (TERPRI)]

    When printnodes is run, it produces the following.