{Begin SubSec Generators}
{Title Generators}
{Text

{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 *PRIMARY* Generators}
{Tag Generators}

A {it 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 {lisp LISTGEN} is defined by:

{lispcode
(DEFINEQ (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.  {index *PRIMARY* Generator handles}{fn GENERATOR} returns a {it 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 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
(DEFINEQ (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
(DEFINEQ (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
(DEFINEQ (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
(DEFINEQ (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
(DEFINEQ (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
(DEFINEQ (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 *PRIMARY* 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
(DEFINEQ (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
(DEFINEQ (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}