pymdl

The pymdl book

22. Coroutines

Coroutines let a program suspend one computation and resume another, retaining the state needed to continue later. This chapter explains MDL's primitives for creating, resuming, and inspecting those computations. pymdl requires the optional greenlet package for switching between them (chapter 3).

A coroutine in MDL is implemented by an object of TYPE PROCESS. In this manual, this use of the word "process" is distinguished by a capitalization from its normal use of denoting an operating-system process (which various systems call a process, job, fork, task, etc.).

MDL's built-in coroutine primitives do not include a "time-sharing system". Only one PROCESS is ever running at a time, and control is passed back and forth between PROCESSes on a coroutine-like basis. The primitives are sufficient, however, to allow the writing of a "time-sharing system" in MDL, with the additional use of the MDL interrupt primitives. This has, in fact, been done.

20.1. PROCESS (the TYPE)

A PROCESS is an object which contains the "current state" of a computation. This includes the LVALs of ATOMs ("bindings"), "depth" of functional application, and "position" within the application of each applied function. Some of the things which are not part of any specific PROCESS are the GVALs of ATOMs, associations (ASOCs), and the contents of OBLISTs. GVALs (with OBLISTs) are a chief means of communication and sharing between PROCESSes (all PROCESSes can refer to the SUBR which is the GVAL of +, for instance). Note that an LVAL in one PROCESS cannot easily be directly referenced from another PROCESS.

A PROCESS PRINTs as #PROCESS p, where p is a FIX which uniquely identifies the PROCESS; p is the "PROCESS number" typed out by LISTEN. A PROCESS cannot be read in by READ.

The term "run a PROCESS" will be used below to mean "perform some computation, using the PROCESS to record the intermediate state of that computation".

N.B.: A PROCESS is a rather large object; creating one will often cause a garbage collection.

<TYPE <MAIN>>              ⇒ PROCESS
<MAIN>                     ⇒ #PROCESS 1

#PROCESS 1 is the number in every LISTENING-AT-LEVEL i PROCESS 1 banner of chapter 19, and now it has a referent.

pymdl's own. Coroutines are the feature most likely to be quietly dropped by a reimplementation, because the host language may not have them -- and pymdl's host does, which is why this chapter reproduces rather than approximates. What matters is the list above of what is and is not per-PROCESS: local values, the application stack and the position within it are switched; globals, associations and oblists are shared. Getting that division wrong would not fail loudly, it would make two PROCESSes quietly agree about something they should disagree about. Chapter 23's interrupt system is built on this chapter, and chapter 29's single-step debugger is section 20.7.6 in a wrapper.

20.2. STATE of a PROCESS

<STATE process>

returns an ATOM (in the ROOT OBLIST) which indicates the "state" of the PROCESS process. The ATOMs which STATE can return, and their meanings, are as follows:

  • RUNABLE (sic) -- process has never ever been run.
  • RUNNING -- process is currently running, that is, it did the application of STATE.
  • RESUMABLE -- process has been run, is not currently running, and can run again.
  • DEAD -- process has been run, but it can not run again; it has "terminated".

In addition, an interrupt (chapter 23) can be enabled to detect the time at which a PROCESS becomes "blocked" (waiting for terminal input) or "unblocked" (terminal input arrived). (The STATE BLOCKED has not been implemented.)

All four states, in order, in one life:

<STATE <ME>>               ⇒ RUNNING
<DEFINE ST (A) .A>         ⇒ ST
<SETG P <PROCESS ,ST>>     ⇒ #PROCESS 2
<STATE ,P>                 ⇒ RUNABLE
<RESUME 7 ,P>              ⇒ 7
<STATE ,P>                 ⇒ DEAD

RUNABLE is spelled with one N, as the manual's "(sic)" warns, and that is the ATOM you must compare against.

20.3. PROCESS (the SUBR)

<PROCESS starter:applicable>

creates and returns a new PROCESS but does not run it; the STATE of the returned PROCESS is RUNABLE (sic).

starter is something applicable to one argument, which must be evaluated. starter is used both in starting and "terminating" a PROCESS. In particular, if the starter of a PROCESS ever returns a value, that PROCESS becomes DEAD.

20.4. RESUME

The SUBR RESUME is used to cause a computation to start or to continue running in another PROCESS. An application of RESUME looks like this:

<RESUME retval:any process>

where retval is the "returned value" (see below) of the PROCESS that does the RESUME, and process is the PROCESS to be started or continued.

The process argument to RESUME is optional, by default the last PROCESS, if any, to RESUME the PROCESS in which this RESUME is applied. If and when the current PROCESS is later RESUMEd by another PROCESS, that RESUME's retval is returned as the value of this RESUME.

20.5. Switching PROCESSes

20.5.1. Starting Up a New PROCESS

Let us say that we are running in some PROCESS, and that this original PROCESS is the GVAL of P0. Somewhere, we have evaluated

<SETG P1 <PROCESS ,STARTER>>

where ,STARTER is some appropriate function. Now, in ,P0 we evaluate

<RESUME .A ,P1>

and the following happens:

  1. In ,P0 the arguments of the RESUME are evaluated: that is, we get that LVAL of A which is current in ,P0 and the GVAL of P1.
  2. The STATE of ,P0 is changed to RESUMABLE and ,P0 is "frozen" right where it is, in the middle of the RESUME.
  3. The STATE of ,P1 is changed to RUNNING, and ,STARTER is applied to ,P0's LVAL of A in ,P1. ,P1 now continues on its way, evaluating the body of ,STARTER.

The .A in the RESUME could have been anything, of course. The important point is that, whatever it is, it is evaluated in ,P0.

What happens next depends, of course, on what ,STARTER does.

20.5.2. Top-level Return

Let us initially assume that ,STARTER does nothing relating to PROCESSes, but instead simply returns a value -- say starval. What happens when ,STARTER returns is this:

  1. The STATE of ,P1 is changed to DEAD. ,P1 can never again be RESUMEd.
  2. The last PROCESS to RESUME ,P1 is found, namely ,P0, and its STATE is changed to RUNNING.
  3. starval is returned in ,P0 as the value of the original RESUME, and ,P0 continues where it left off.

All in all, this simple case looks just like an elaborate version of applying ,STARTER to .A in ,P0. The ST example in section 20.2 above is exactly that, and its answer 7 is the elaborate version of <ST 7>.

20.5.3. Symmetric RESUMEing

Now suppose that while still in ,P1, the following is evaluated, either in ,STARTER or in something called by ,STARTER:

<RESUME .BAR ,P0>

This is what happens:

  1. The arguments of the RESUME are evaluated in ,P1.
  2. The STATE of ,P1 is changed to RESUMABLE, and ,P1 is "frozen" right in the middle of the RESUME.
  3. The STATE of ,P0 is changed to RUNNING, and ,P1's LVAL of BAR is returned as the value of ,P0's original RESUME. ,P0 then continues right where it left off.

This is the interesting case, because ,P0 can now do another RESUME of ,P1; this will "turn off" ,P0, pass a value to ,P1 and "turn on" ,P1. ,P1 can now again RESUME ,P0, which can RESUME ,P1 back again, etc. ad nauseam, with everything done in a perfectly symmetric manner. This can obviously also be done with three or more PROCESSes in the same manner.

Here it is, with the default second argument doing the work on the way back:

<DEFINE PONG (A) <REPEAT () <SET A <RESUME <* .A 2>>>>>    ⇒ PONG
<SETG P1 <PROCESS ,PONG>>  ⇒ #PROCESS 2
<RESUME 3 ,P1>             ⇒ 6
<RESUME 5 ,P1>             ⇒ 10
<RESUME 10 ,P1>            ⇒ 20
<==? <RESUMER ,P1> <MAIN>> ⇒ T

PONG never names a PROCESS at all: its bare <RESUME ...> goes back to whoever resumed it, which is the rule in 20.4.

Note how this differs from normal functional application: you cannot "return" from a function without destroying the state that function is in. The whole point of PROCESSes is that you can "return" (RESUME), remembering your state, and later continue where you left off.

PONG is that sentence made concrete -- the REPEAT is still in progress, in the middle of its SET, between each pair of lines above.

20.6. Example

<DEFINE SUM3 (A)
        #DECL ((A) <OR FIX FLOAT>)
        <REPEAT ((S .A))
                #DECL ((S) <OR FIX FLOAT>)
                <SET S <+ .S <RESUME "GOT 1">>>
                <SET S <+ .S <RESUME "GOT 2">>>
                <SET S <RESUME .S>>>>          ⇒ SUM3
<SETG SUMUP <PROCESS ,SUM3>>       ⇒ #PROCESS 2
<RESUME 5 ,SUMUP>          ⇒ "GOT 1"
<RESUME 1 ,SUMUP>          ⇒ "GOT 2"
<RESUME 2 ,SUMUP>          ⇒ 8

SUM3, used as the startup function of another PROCESS, gets RESUMEd with numbers. It returns the sum of the last three numbers it was given every third RESUME. (The manual's DECL for A reads (OR FIX FLOAT>, with a parenthesis where an angle bracket belongs; it is <OR FIX FLOAT>.)

Just as a note, by taking advantage of MDL's order of evaluation, SUM3 could have been written as:

<DEFINE SUM3 (A)
        <REPEAT ((S .A))
           #DECL ((A S) <OR FIX FLOAT>)
           <SET S <RESUME <+ .S <RESUME "GOT 1"> <RESUME "GOT 2">>>>>>

(The manual's #DECL there reads ((A S0 <OR FIX FLOAT>), with a stray 0 and an unclosed parenthesis.)

20.7. Other Coroutining Features

20.7.1. BREAK-SEQ

<BREAK-SEQ any process>

("break evaluation sequence") returns process, which must be RESUMABLE, after having modified it so that when it is next RESUMEd, it will first evaluate any and then do an absolutely normal RESUME; the value returned by any is thrown away, and the value given by the RESUME is used normally.

If a PROCESS is BREAK-SEQed more than once between RESUMEs, all of the anys BREAK-SEQed onto it will be remembered and evaluated when the RESUME is finally done. The anys will be evaluated in "last-in first-out" order. The FRAME generated by EVALing more than one any will have as its FUNCT the dummy ATOM BREAKER.

<SETG HIT <>>              ⇒ #FALSE ()
<DEFINE W (A) <RESUME 1> <RESUME 2>>   ⇒ W
<SETG P <PROCESS ,W>>      ⇒ #PROCESS 2
<RESUME 0 ,P>              ⇒ 1
<BREAK-SEQ '<SETG HIT T> ,P>   ⇒ #PROCESS 2
,HIT                       ⇒ #FALSE ()
<RESUME 0 ,P>              ⇒ 2
,HIT                       ⇒ T

Note the ' on the first argument, which the manual's notation does not emphasize: BREAK-SEQ is a SUBR, so it evaluates its arguments like any other, and the thing you want run later must reach it unevaluated. Without the quote it fires immediately and nothing is remembered. The two ,HIT lines are the whole point -- unchanged after the BREAK-SEQ, true after the next RESUME.

20.7.2. MAIN

When you initially start up MDL, the PROCESS in which you are running is slightly "special" in these two ways:

  1. Any attempt to cause it to become DEAD will be met with an error.
  2. <MAIN> always returns that PROCESS.

The PROCESS number of <MAIN> is always 1. The initial GVAL of THIS-PROCESS is what MAIN always returns, #PROCESS 1.

<MAIN>                     ⇒ #PROCESS 1
,THIS-PROCESS              ⇒ #PROCESS 1
<==? <MAIN> ,THIS-PROCESS> ⇒ T

20.7.3. ME

<ME>

returns the PROCESS in which it is evaluated. The LVAL of THIS-PROCESS in a RUNABLE (new) PROCESS is what ME always returns.

<==? <MAIN> <ME>>          ⇒ T

-- true at top level, and the first thing that stops being true inside another PROCESS.

20.7.4. RESUMER

<RESUMER process>

returns the PROCESS which last RESUMEd process. If no PROCESS has ever RESUMEd process, it returns #FALSE (). process is optional, <ME> by default. Note that <MAIN> does not ever have any resumer.

<RESUMER>                  ⇒ #FALSE ()

Example:

<PROG ((R <RESUMER>))           ;"not effective in <MAIN>"
   #DECL ((R) <OR PROCESS FALSE>)
   <AND .R
        <==? <STATE .R> RESUMABLE>
        <RESUME T .R>>>

20.7.5. SUICIDE

<SUICIDE retval process>

acts just like RESUME, but clobbers the PROCESS (which cannot be <MAIN>) in which it is evaluated to the STATE DEAD.

<DEFINE S (A) <SUICIDE 42>>    ⇒ S
<SETG P <PROCESS ,S>>      ⇒ #PROCESS 2
<RESUME 0 ,P>              ⇒ 42
<STATE ,P>                 ⇒ DEAD

20.7.6. 1STEP

<1STEP process>

returns process, after putting it into "single-step mode".

A PROCESS in single-step mode, whenever RESUMEd, runs only until an application of EVAL in it begins or finishes. At that point in time, the PROCESS that did the 1STEP is RESUMEd, with a retval which is a TUPLE. If an application of EVAL just began, the TUPLE contains the ATOM EVLIN and the arguments to EVAL. If an application of EVAL just finished, the TUPLE contains the ATOM EVLOUT and the result of the evaluation.

process will remain in single-step mode until FREE-RUN (below) is applied to it. Until then, it will stop before and after each EVAL in it. Exception: if it is RESUMEd from an EVLIN break with a retval of TYPE DISMISS (PRIMTYPE ATOM), it will leave single-step mode only until the current call to EVAL is about to return. Thus lower-level EVALs are skipped over without leaving the mode. The usefulness of this mode in debugging is obvious.

20.7.7. FREE-RUN

<FREE-RUN process>

takes its argument out of single-step mode. Only the PROCESS that put process into single-step mode can take it out of the mode; if another PROCESS tries, FREE-RUN returns a FALSE.

pymdl's own. "The usefulness of this mode in debugging is obvious" is the manual being coy about a whole program: 1STEP, EVLIN, EVLOUT and DISMISS are the entire mechanism of the one-step debugger in chapter 29, and that debugger is a PROCESS watching another PROCESS evaluate. Making it work here took six separate engine fixes, because single-stepping exercises the boundary between EVAL and the PROCESS switch on every single form. Chapter 29 has the debugger; this section is why it is possible at all.

20.8. Sneakiness with PROCESSes

FRAMEs, ENVIRONMENTs, TAGs, and ACTIVATIONs are specific to the PROCESS which created them, and each "knows its own father". Any SUBR which takes these objects as arguments can take one which was generated by any PROCESS, no matter where the SUBR is really applied. This provides a rather sneaky means of crossing between PROCESSes. The various cases are as follows:

GO, RETURN, AGAIN, and ERRET, given arguments which lie in another PROCESS, each effectively "restarts" the PROCESS of its argument and acts as if it were evaluated over there. If the PROCESS in which it was executed is later RESUMEd, it returns a value just like RESUME!

SET, UNASSIGN, BOUND?, ASSIGNED?, LVAL, VALUE, and LLOC, given optional ENVIRONMENT arguments which lie in another PROCESS, will gleefully change, or return, the local values of ATOMs in the other PROCESS. The optional argument can equally well be a PROCESS, FRAME, or ACTIVATION in another PROCESS; in those cases, each uses the ENVIRONMENT which is current in the place specified.

That is section 20.1's "cannot easily be directly referenced" turning out to have a door in it:

<DEFINE F (A) <PROG () <SET LOCAL 99> <RESUME <ME>>>>  ⇒ F
<SETG P <PROCESS ,F>>      ⇒ #PROCESS 2
<SET Q <RESUME 0 ,P>>      ⇒ #PROCESS 2
<LVAL LOCAL .Q>            ⇒ 99

LOCAL has no value at all in <MAIN>; 99 is read out of the other PROCESS, which is still frozen mid-RESUME with its PROG binding intact. The PROCESS itself served as the ENVIRONMENT argument, which is what section 20.9 permits.

FRAME, ARGS, and FUNCT will be glad to return the FRAMEs, argument TUPLEs, and applied Subroutine names of another PROCESS. If one is given a PROCESS (including <ME>) as an argument instead of a FRAME, it returns all or the appropriate part of the topmost FRAME on that PROCESS's control stack.

<DEFINE F (A) <RESUME <ME>>>   ⇒ F
<SETG P <PROCESS ,F>>      ⇒ #PROCESS 2
<RESUME 0 ,P>              ⇒ #PROCESS 2
<FUNCT <FRAME ,P>>         ⇒ RESUME

RESUME, because that is exactly where the other PROCESS is stopped.

If EVAL is applied in PROCESS P1 with an ENVIRONMENT argument from a PROCESS P2, it will do the evaluation in P1 but with P2's ENVIRONMENT (!). That is, the other PROCESS's LVALs, etc. will be used, but (1) any new FRAMEs needed in the course of the evaluation will be created in P1; and (2) P1 will be RUNNING -- not P2. Note the following: if the EVAL in P1 eventually causes a RESUME of P2, P2 could functionally return to below the point where the ENVIRONMENT used in P1 is defined; a RESUME of P1 at this point would cause an ERROR due to an invalid ENVIRONMENT. (Once again, LEGAL? can be used to forestall this.)

20.9. Final Notes

  1. A RESUMABLE PROCESS can be used in place of an ENVIRONMENT in any application. The "current" ENVIRONMENT of the PROCESS is effectively used.
  2. FRAMEs and ENVIRONMENTs can be CHTYPEd arbitrarily to one another, or an ACTIVATION can be CHTYPEd to either of them, and the result "works". Historically, these different TYPEs were first used with different SUBRs -- FRAME with ERRET, ENVIRONMENT with LVAL, ACTIVATION with RETURN -- hence the invention of different TYPEs with similar properties.
  3. Bugs in multi-PROCESS programs usually exhibit a degree of subtlety and nastiness otherwise unknown to the human mind. If when attempting to work with multiple processes you begin to feel that you are rapidly going insane, you are in good company.

pymdl's own. Note 2 is the most useful sentence in the chapter for anyone reading pymdl's source, because it explains why FRAME, ENVIRONMENT and ACTIVATION are three names for nearly one thing. They are three TYPEs over one representation, kept distinct because three different SUBRs wanted them, and CHTYPE between them is free. Chapters 12 and 19 each treat one face of it; this note is where the manual admits they are the same object.

Note 3 is also accurate, and is offered without further comment.