 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/principles-of-programming-languages/2/d/solution

 Top articles  Latest articles New article in topic

Past exam of the computer science course of the University of Oxford / 2015 / Principles of programming languages / 2 / d / Solution by

Codex  0 2026-10-31

Keep a FIFO queue of runnable continuations in shared computer memory. Removing a continuation from its head transfers control with nil; suspending a runnable computation appends its continuation at the rear. A single scheduler group also needs a terminal continuation so that finishing the last computation cannot return through an obsolete invocation of fork.

The following is FunMem, including the shared initialization and helper definitions. run(main) starts a scheduler group; nested fork calls use that same group.

val ready = new(); ready := nil;
val stop = new();

rec append(xs,ys) =
  if xs = nil then ys else head(xs) : append(tail(xs),ys);

val enqueue(k) =
  ready := append(!ready,k:nil); nil;

val dispatch() =
  if !ready = nil then withc(!stop,nil)
  else let val k = head(!ready) in
    ready := tail(!ready); withc(k,nil);

val run(main) =
  callcc(lambda (done)
    stop := done; ready := nil;
    main(); dispatch());

val fork(f) =
  callcc(lambda (parent)
    enqueue(parent); f(); dispatch());

val yield() =
  callcc(lambda (current)
    enqueue(current); dispatch())

At fork, the parent is queued before f() starts. The child runs immediately. Its ordinary return value is ignored by sequencing into dispatch(). At yield, the current computation joins the rear, then the oldest runnable computation is removed from the front. If there was no other runnable computation, these operations select the just-captured continuation, so the caller resumes immediately with nil.

The invariant is that each suspended runnable computation has exactly one entry in ready, ordered by the time it most recently became suspended and runnable. A running computation is absent from that FIFO queue. Neither appending nor removing an entry suspends, so these operations are indivisible relative to this cooperative multitasking scheduler. Completing a child removes the child from consideration permanently; it is never enqueued by its completion wrapper.

For the paper's example, call the initial computation

P

and the forked computation

C

. The FIFO queue and writes evolve as follows:

Event	Running next	Ready queue	New list head	Fork starts child	$C$	$P$	—	Child writes and yields	$P$	$C$	$1$	Parent writes and yields	$C$	$P$	$3$	Child writes and finishes	$P$	empty	$2$	Parent writes and finishes	scheduler exits	empty	$4$

Figure 1.
FIFO continuation scheduling of the paper's two coroutines
. **Details**.

Thus the observable list, read after the scheduler group finishes, is

[4, 2, 3, 1], fork (f) and yield () resume their callers with nil .

(1)

The scheduler exit is used only when no runnable continuations remain. A main computation can place its desired final observable value in shared computer memory and read it after run returns. This wrapper also permits already-forked computations to finish if the initial computation finishes before them. Each run creates one active scheduler group; calls of run are not nested.

 Read the full article

 New to topics? Read the docs here!