{Begin SubSec Generators and Coroutines}
{Title Generators and Coroutines}
{Text


{note we should ensure that this stuff still works in process world --Gadol}


{note 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.}

{index coroutines}
{index generators}

This section describes an application of the spaghetti stack facility to provide mechanisms for creating and using simple generators, generalized coroutines, and Conniver style possibility lists.


{Begin SubSec Generators}
{Title Generators}
{Text


{Tag Generators}

A {it generator}{index generators} 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 {lisp LISTGEN} is defined as:

{lispcode
(LISTGEN (L)
      (IF L THEN (PRODUCE (CAR L))
                 (LISTGEN (CDR L))))}


we can use the function {fn GENERATOR} (described below) to create a generator that uses {lisp LISTGEN} to produce the elements of a list one at
a time, e.g.,


{lispcode (SETQ GR (GENERATOR (LISTGEN '(A B C)))}


creates a generator, which can be called by


{lispcode (GENERATE GR)}


to produce as values on successive calls, {lisp A}, {lisp B}, {lisp C}.
When {fn GENERATE} (not {fn GENERATOR}) is called the first time, it simply starts evaluating {lisp (LISTGEN '(A B C))}.  {fn PRODUCE} gets called from {lisp LISTGEN}, and pops back up to {fn GENERATE} with the indicated value after saving the state.  When {fn GENERATE} gets called again, it continues from where the last {fn PRODUCE} left off.  This process continues until finally {lisp LISTGEN} completes and returns a value (it doesn't matter what it is).  {fn GENERATE} then returns {lisp GR} itself as its value, so that the program that called {fn GENERATE} can tell that it is finished, i.e., there are no more values to be generated.


{FnDef {FnName GENERATOR} {FnArgs FORM## COMVAR##}
{Type NLAMBDA}
{Text
An nlambda function that creates a generator which uses {arg FORM##}
to compute values.  {fn GENERATOR} returns a {it generator handle}{index generator handle} which is represented by a dotted pair of stack pointers.

{arg COMVAR##} is optional.  If its value ({fn EVAL} of) is a generator handle, the list structure and stack pointers will be reused.  Otherwise, a new generator handle will be constructed.

{fn GENERATOR} compiles open.
}}


{FnDef {FnName PRODUCE} {FnArgs VAL}
{Text
Used from within (below) a generator to return {arg VAL} as the value of the corresponding call to {fn GENERATE}.
}}


{FnDef {FnName GENERATE} {FnArgs HANDLE VAL}
{Text
Restarts the generator represented by {arg HANDLE}.  {arg VAL} is returned as the value of the {fn PRODUCE} which last suspended the operation of the generator.  When the generator runs out of values, {fn GENERATE} returns {arg HANDLE} itself.
}}


Examples:

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

{lispcode
[LEAVESG (L)
    (if (ATOM L)
     then (PRODUCE L)
     else (LEAVESG (CAR L))
          (if (CDR L)
            then (LEAVESG (CDR L)]}


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


{lispcode
(PLEAVESG1 (L)
   (PROG (X LHANDLE)
         (SETQ LHANDLE (GENERATOR (LEAVESG L)))
     LP  (SETQ X (GENERATE LHANDLE))
         (if (EQ X LHANDLE)
             then (RETURN NIL))
         (PRINT X)
         (GO LP)))}


Note that the loop terminates when the value of the generator is {fn EQ} to the dotted pair which is the value produced by the call to {fn GENERATOR}.
A CLISP iterative operator, {lisp OUTOF},{index *PRIMARY* OUTOF (I.S. Operator)} is provided which makes it much easier to write the loop in {lisp PLEAVESG1}.  {lisp OUTOF} (or {lisp 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.  Therefore, the following is equivalent to the above program {lisp PLEAVESG1}:


{lispcode
(PLEAVESG2 (L)
   (for X outof (LEAVESG L) do (PRINT x))}


Here is another example; the following form will print the first {lisp N} atoms.


{lispcode
(for X outof (MAPATOMS (FUNCTION PRODUCE))
   as I from 1 to N do (PRINT X))}


}{End SubSec Generators}





{Begin SubSec Coroutines}
{Title Coroutines}
{Text

{index *PRIMARY* coroutines}

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 {it 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.


{FnDef {FnName COROUTINE} {FnArgs CALLPTR## COROUTPTR## COROUTFORM## ENDFORM##}
{Type NLAMBDA}
{Text
This nlambda function is used to create a coroutine and initialize the linkage.
{arg CALLPTR##} and {arg COROUTPTR##} are the names of two variables, which will be set to appropriate stack pointers.  If the values of {arg CALLPTR##} or {arg COROUTPTR##} are already stack pointers, the stack pointers will be reused.  {arg COROUTFORM##} is the form which is evaluated to start the coroutine; {arg ENDFORM##} is a form to be evaluated if {arg COROUTFORM##} actually returns when it runs out of values.

{fn COROUTINE} compiles open.
}}



{FnDef {FnName RESUME} {FnArgs FROMPTR TOPTR VAL}
{Text
Used to  transfer control from one coroutine to another.  {arg FROMPTR} should be the stack pointer for the current coroutine, which will be smashed to preserve the current state.  {arg TOPTR} should be the stack pointer which has preserved the state of the coroutine to be transferred to, and {arg VAL} is the value that is to be returned to the latter coroutine as the value of the {fn RESUME} which suspended the operation of that coroutine.
}}



For example, the following is the way one might write the {lisp LEAVES}
program using the coroutine package:

{lispcode
(LEAVESC (L COROUTPTR CALLPTR)
   (if (ATOM L)
    then (RESUME COROUTPTR CALLPTR L)
    else (LEAVESC (CAR L) COROUTPTR CALLPTR)
         (if (CDR L) then (LEAVESC (CDR L) COROUTPTR CALLPTR))))}


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


{lispcode
(PLEAVESC (L)
  (bind PLHANDLE LHANDLE
   first (COROUTINE PLHANDLE LHANDLE
                    (LEAVESC L LHANDLE PLHANDLE)
                    (RETFROM 'PLEAVESC))
   do (PRINT (RESUME PLHANDLE LHANDLE))))}


By {fn RESUME}ing {lisp LEAVESC} repeatedly, this function will print all the
leaves of list {lisp L} and then return out of {lisp PLEAVESC} via
the {fn RETFROM}.  The {fn 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 {arg ENDFORM##}.


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


{lispcode
(EQLEAVES (L1 L2)
    (bind LHANDLE1 LHANDLE2 PE EL1 EL2
     first (COROUTINE PE LHANDLE1 (LEAVESC L1 LHANDLE1 PE) 'NO-MORE)
           (COROUTINE PE LHANDLE2 (LEAVESC L2 LHANDLE2 PE) 'NO-MORE)
     do (SETQ EL1 (RESUME PE LHANDLE1))
        (SETQ EL2 (RESUME PE LHANDLE2))
        (if (NEQ EL1 EL2)
         then (RETURN NIL))
     repeatuntil (EQ EL1 'NO-MORE)
     finally (RETURN T)))}


}{End SubSec Coroutines}





{Begin SubSec Possibilities Lists}
{Title Possibilities Lists}
{Text

{note These functions are based on the CONNIVER system possibilities list package.}


{index possibilities lists}

A possibilities list is the interface between a generator and a consumer.  The possibilities list is initialized by a call to {fn POSSIBILITIES}, and elements are obtained from it by using {fn 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.


{FnDef {FnName POSSIBILITIES} {FnArgs FORM##}
{Type NLAMBDA}
{Text
This nlambda function is used for the initial creation of a possibilities list.  {arg FORM##} will be evaluated to create the list.  It should use the functions {fn NOTE} and {fn 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.:

{lisp (SETQ PLIST (POSSIBILITIES (GENERFN V1 V2)))}.

{fn POSSIBILITIES} compiles open.
}}


{FnDef {FnName NOTE} {FnArgs VAL LSTFLG}
{Text
Used within a generator to put items on the possibilities list being generated.
If {arg LSTFLG} is equal to {lisp NIL}, {arg VAL} is treated as a single item.
If {arg LSTFLG} is non-{lisp NIL}, then the list {arg VAL} is {fn NCONC}ed on the end of the possibilities list.  Note that it is perfectly reasonable to
create a possibilities list using a second generator, and {fn NOTE} that list as possibilities for the current generator with {arg LSTFLG} equal to {lisp T}.
The lower generator will be resumed at the appropriate point.
}}


{FnDef {FnName AU-REVOIR} {FnArgs VAL##}
{Type NOSPREAD}
{Text
Puts {arg VAL##} on the possibilities list if it is given, and then suspends the generator and returns to the consumer in such a fashion that control will return to the generator at the {fn AU-REVOIR} if the consumer exhausts the possibilities list.

Note:  {lisp NIL} is not put on the possibilities list unless it is explicitly given as an argument to {fn AU-REVOIR}, i.e., {lisp (AU-REVOIR)} and {lisp (AU-REVOIR NIL)} are {it not} the same.  {fn AU-REVOIR} and {fn ADIEU} are lambda nospreads to enable them to distinguish these two cases.
}}


{FnDef {FnName ADIEU} {FnArgs VAL##}
{Type NOSPREAD}
{Text
Like {fn AU-REVOIR} except releases the generator instead of suspending it.
}}



{FnDef {FnName TRYNEXT} {FnArgs PLST## ENDFORM## VAL##}
{Type NLAMBDA}
{Text
This nlambda function allows a consumer to use a possibilities list.  It removes the first item from the possibilities list named by {arg PLST##} (i.e. {arg PLST##} must be an atom whose value is a possiblities list), and returns that item, provided it is not a generator handle.  If a generator handle is encountered, 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 {fn TRYNEXT} causes a generator to be awakened, {arg VAL##} is returned as the value of the {fn AU-REVOIR} which put that generator to sleep.  If {arg PLST##} is empty, it evaluates {arg ENDFORM##} in the caller's environment.

{fn TRYNEXT} compiles open.
}}


{FnDef {FnName CLEANPOSLST} {FnArgs PLST}
{Text
This function is provided to release any stack pointers which may be left in the {arg PLST} which was not used to exhaustion.
}}


For example, {lisp FIB} is a generator for fibonnaci numbers.  It starts out by {fn NOTE}ing its two arguments, then suspends itself.  Thereafter, on being re-awakened, it will {fn NOTE} two more terms in the series and suspends again.  {lisp PRINTFIB} uses {lisp FIB} to print the first {lisp N} fibonacci numbers.


{lispcode
[FIB (F1 F2)
  (do (NOTE F1)
      (NOTE F2)
      (SETQ F1 (IPLUS F1 F2))
      (SETQ F2 (IPLUS F1 F2))
      (AU-REVOIR)]}

Note that this {fn AU-REVOIR} just suspends the generator and adds nothing to the possibilities list except the generator.

{lispcode
[PRINTFIB (N)
     (PROG ((FL (POSSIBILITIES (FIB 0 1))))
           (RPTQ N (PRINT  (TRYNEXT FL)))
           (CLEANPOSLST FL)]}

Note that {lisp FIB} itself will never terminate.


}{End SubSec Possibilities Lists}


}{End SubSec Generators and Coroutines}