5.4.22  Call/CC and Soft Thread Programming

The fundamental concurrent programming primitive in modern praxis is callcc, "call with current fate", which may be thought of as saving the current call stack.

(Mythryl actually uses a stackless implementation, so in a literal sense there is no call stack to save or restore. This makes the Mythryl callcc implementation perhaps a hundred times faster than the typical competing implementation; in Mythryl callcc takes essentially the same time as any other function call, and works much the same way.)

Mythryl’s version of this facility pairs it with throw, which may be thought of as resuming a saved call stack.

The callcc interface represents low-level functionality reaching deep into system internals; the application level interface to it is defined in src/lib/std/src/nj/fate.api and src/lib/std/src/nj/fate.pkg.

The core of the API is

    Fate(X);
    callcc:  (Fate(X) -> X) -> X;
    throw:    Fate(X) -> X -> Y;

where

• Fate(X) is the type of fates taking arguments of type X.
• callcc user_function passes the current fate k to userfunction. Later doing throw cc x effectively results in the original callcc user_function returning x.
• throw k x resumes fate k (obtained from callcc) with argument x.

The callcc facility is really only useful in applications large enough to need multiple logical threads of control; consequently, simple examples tend to look fairly silly. Here is a minimal example of using callcc and throw:

    #!/usr/bin/mythryl

    callcc = fate::callcc;
    throw  = fate::throw;

    fun test_callcc string
        =
        callcc( \\ current_fate =  throw  current_fate  string );

    printf "Test result is '%s'.\n"  (test_callcc "foo");

As you probably suspect, when run this yields:

    linux$ ./my-script
    Test result is 'foo'.

Here we first use callcc to get access to the current_fate and then immediately use throw to resume that fate.

In a more realistic example we would be doing something like maintaining a priority queue of fates, entering current_fate into that priority queue, extracting the next fate to run from that priority queue, and then using throw to transfer control to that next fate, thus effecting a "cooperative multitasking" style time-slice context switch; instead of test_callcc our function might be called something like yield.

A production example of such coding may be found in src/app/makelib/concurrency/makelib-thread-boss.pkg.

Serious concurrent programming requires an infrastructure of appropriate priority queues, locks, message channels and so forth. The de facto standard concurrent programming solution for the SML world is John H Reppy’s CML, documented in his book Concurrent Programming in ML. This package has been partially ported to Mythryl; the source code compiles and is in the tree rooted at src/lib/thread-kit. A suitable entrypoint for reading purposes is src/lib/src/lib/thread-kit/src/core-thread-kit/threadkit.api.

The thread-kit code is not currently operational or supported; the change of syntax from SML to Mythryl has introduced some superficial breakage which I have not yet had time to pin down and fix.