(use-modules (ice-9 runq))

One way to schedule parallel computations in a serial environment is
to explicitly divide each task up into small, finite execution time,
strips.  Then you interleave the execution of strips from various
tasks to achieve a kind of parallelism.  Runqs are a handy data
structure for this style of programming.

We use thunks (nullary procedures) and lists of thunks to represent
strips.  By convention, the return value of a strip-thunk must either
be another strip or the value #f.

A runq is a procedure that manages a queue of strips.  Called with no
arguments, it processes one strip from the queue.  Called with
arguments, the arguments form a control message for the queue.  The
first argument is a symbol which is the message selector.

A strip is processed this way: If the strip is a thunk, the thunk is
called -- if it returns a strip, that strip is added back to the
queue.  To process a strip which is a list of thunks, the CAR of that
list is called.  After a call to that CAR, there are 0, 1, or 2 strips
-- perhaps one returned by the thunk, and perhaps the CDR of the
original strip if that strip has 2+ elements.  The runq puts whichever
of these strips exist back on the queue.  (The exact order in which
strips are put back on the queue determines the scheduling behavior of
a particular queue -- it's a parameter.)

— Scheme Procedure: runq-control q msg [args...]

For runq q, process in the default way the control message msg (a symbol) and its args. These messages are recognized:

add!

enqueue!

Enqueue args as strips.

push!

Add args as strips to the front of the queue.

empty?

Return #t iff the runq is empty.

length

Return the number of strips in the runq.

kill!

Empty the runq.

Signal error for any other message, with key not-understood and two arguments msg and args.

— Scheme Procedure: make-void-runq

Return a runq that discards all messages except length, for which it returns 0.

— Scheme Procedure: make-fair-runq

Return a runq procedure. Called with no arguments, the procedure processes one strip from the queue. Called with arguments, it uses runq-control.

In a fair runq, if a strip returns a new strip X, that is added to the end of the queue, meaning it will be the last to execute of all the remaining strips.

— Scheme Procedure: make-exclusive-runq

Return a runq procedure. Called with no arguments, the procedure processes one strip from the queue. Called with arguments, it uses runq-control.

In an exclusive runq, if a strip W returns a new strip X, X is added to the front of the queue, meaning it will be the next to execute of all the remaining procedures.

An exception to this occurs if W was the car of a list of strips. In that case, after X is pushed onto the front of the queue, the cdr of the list of strips is pushed in front of that (if the cdr is not empty). This way, the rest of the thunks in the list that contained W have priority over X.

— Scheme Procedure: make-subordinate-runq-to superior basic-inferior

Return a runq proxy for the runq basic-inferior.

The proxy watches for operations on basic-inferior that cause a transition from a queue length of 0 to a non-zero length and vice versa. While basic-inferior is not empty, the proxy installs a task on the superior runq. Each strip of that task processes N strips from basic-inferior where N is the length of basic-inferior when the proxy strip is entered. [Countless scheduling variations are possible.]

— Scheme Procedure: strip-sequence [strips...]

Return a new strip which is the concatenation of strips.

— Scheme Procedure: fair-strip-subtask [initial-strips...]

Return a new strip which is the synchronous, fair, parallel execution of the initial-strips.