Assignment 5 (callcc)

Due Date: May 8, 2000 before class

Threads can be implemented elegantly in a language with first-class continuations, i.e., in a language that has a construct like callcc.

Here is the simplest interface for an implementation of threads:

signature THREADS = sig
    exception NoThreadsToRun
    val fork : (unit -> unit) -> unit
    val yield : unit -> unit
    val exit : unit -> 'a 
end

The fork procedure takes a function f as an argument and then evaluates the expression f() in a newly created thread. The new process is called the "child" process, whereas the process that called fork is the "parent" process. There is also a notion of a "main" thread, which is the one thread that was not created by a call to fork. The main thread is the only thread whose return value is significant; its result is the result of the entire program.

Concurrency amongst threads is obtained by having individual threads voluntarily suspend themselves, thereby giving other threads a chance to execute. In this sense, our threads are cooperative coroutines rather than parallel of pre-emptable (time-sliced) processes. A thread calls yield to place itself in a queue of "ready" processes and activate the next thread. The ready processes are typically executed in first-in-first-out order, although it is considered bad programming style to depend on that ordering.

The exit procedure terminates the current thread and activates the next thread. Unlike yield, a call to exit never returns. Instead it either transfers control directly to a waiting thread or raises the NoThreadsToRun exception if there are no other threads remaining in the queue. A child thread implicitly exits if the expression it is evaluating returns.

There are some subtleties involving what should happen when the main thread returns. Should it implicitly wait for all the other threads to also finish? From the point of view of the implementor, the simplest approach is to make all the other threads silently disappear when the main thread returns.

Your job is to implement the thread interface. To do this you need to write an ML structure that has at least the following things. (You may obviously add additional definitions.)

structure Threads : THREADS = struct

    structure K = SMLofNJ.Cont (* access to callcc *)
    structure Q = Queue        (* access to the SML/NJ Queue library *)

    exception NoThreadsToRun   (* as required by the interface *)

    (* You must provide an implementation of the next three functions *)
    fun exit () = ...

    fun fork f = ...

    fun yield () = ...
end 

The easiest way to get access to the SML/NJ Queue library is to use version of sml with the compilation manager (called sml-cm). To do that, put the thread code in a file called "threads.sml" and create a file called "sources.cm" that has the following:

Group is

/local/apps/sml/lib/smlnj-lib.cm 
threads.sml
(* other files that you might want to use *)

When you run sml-cm, you can just type CM.make(); this will read your sources.cm file, load and compile everything, keeping track of dependencies (much like the Unix "make" utility). To access the functions inside an ML structure like Threads, you just give the fully qualified name like "Threads.yield()".