Mythryl is a fork of the SML/NJ codebase. SML was standardized in 1990 and is defined as a single-threaded language, but SML/NJ supports callcc and SML/NJ’s stackless implementation makes callcc about 100X faster than in typical stack-based languages; This makes SML/NJ an excellent foundation upon which to build a concurrent programming language.
Mythryl (and more broadly ML-family languages) are wonderful candidates for concurrent and parallel programming because the problems with concurrent and parallel programming all revolve around heap side effects, and ML code typically uses only about one percent as many side effects as equivalent code in mainstream imperative languages like C/C++/Java/etc. One hundred times fewer side effects translates directly to one hundred times fewer race condition bugs, clobbered-shared-variable bugs and so forth. The typesafety provided by ML-family languages is also very welcome in the context of concurrent and parallel programming, because they mean fewer runtime bugs, and runtime debugging is inherently more difficult in concurrent and parallel programs than in old-style single-threaded programs.
Starting in about 1990 John H Reppy developed a concurrent programming library for SML called CML ("Concurrent ML"), documented in his book of that title.
This library has been integrated into the Mythryl codebase and work is under way to make concurrent programming the norm in Mythryl. At present, however, concurrent programming in Mythryl is experimental and uses a separate set of libraries. (The Mythryl codebase pervasively assumes single-threaded operation; making it all threadsafe and concurrent-programming oriented will take a lot of detail work.)
The Mythryl port of CML is called "threadkit", and is not well documented because the code is still evolving steadily. For an informal overview of what is working so far, take a peek at
src/lib/src/lib/thread-kit/src/core-thread-kit/threadkit-unit-test.pkg
in the Mythryl sourcecode distribution.
As a quick sketch of the current threadkit facilities:
This pre-emptive thread switching is driven by a 50Hz (by default — configurable) SIGALRM from the host OS. This is not something one wants to have running by default when not being used, so before using threadkit facilities you must first explicitly start it up via
thread_scheduler_control::start_up_thread_scheduling ();
The above unit-test code has lots of examples of doing this.
make_thread (\\ () = whatever());
I usually write that as
make_thread {.
#
whatever ();
};
taking advantage of Mythryl ’thunk’ syntax to improve readability a bit. The ’whatever()’ stuff will usually in practice be
for (;;) {
do_one_mailop [
...
];
}
which is to say, an infinite loop reading and handling input from other threads. (More on "select" in a bit.)
The basic protocol is:
include package threadkit;
slot: Mailslot (Foo)
=
make_mailslot (); # Create a mailslot for
# passing values of type Foo.
give (slot, foo); # Send a type-Foo value via the slot.
foo = take slot; # Receive a type-Foo value via the slot.
Here the ’give’ and ’take’ operations will of course have to be performed in separate threads! If the above code is executed as written in a single thread, the ’give’ will block forever for lack of a synchronous ’take’.
The basic protocol is:
include package threadkit;
slot: Oneshot_Mailslot (Foo)
=
make_oneshot_mailslot (); # Create a oneshot for
# passing values of type Foo.
set (slot, foo); # Send a type-Foo value via the oneshot.
foo = get slot; # Receive a type-Foo value via the oneshot.
In general, one should never share REF cells or mutable vectors between concurrent threads; maildrops are in essence concurrency-safe replacements for REF cells.
The basic protocol is:
include package threadkit;
drop: Maildrop (Foo)
=
make_empty_maildrop (); # Create an empty maildrop holding
# values of type Foo.
fill (drop, foo); # Deposit a a type-Foo value in the maildrop.
foo = empty drop; # Get contents of maildrop, leaving it empty.
Attempts to read from an empty maildrop will block until it is filled.
Attempts to fill an already full maildrop will generate an error exception.
Void-valued maildrops are often used as PV-style locks to provide mutual exclusion in monitor-style code.
Additional maildrop operations include:
include package threadkit;
drop: Maildrop (Foo)
=
make_full_maildrop foo; # Create an already-full maildrop holding
# values of type Foo.
foo = peek drop; # Read contents of maildrop without altering maildrop.
foo = swap (drop, foo'); # Get contents of maildrop, replacing with foo'.
A typical use looks like:
do_one_mailop [
take' mailslot1
==>
(\\ foo = handle_slot1_read foo),
take' mailslot2
==>
(\\ foo = handle_slot2_read foo)
];
Here we are expecting to get input now and then on either mailslot1 or mailslot2, but don’t know which. This construct lets us block until either one is ready, rather than having to guess correctly which will be ready next, at the risk of deadlock if we guess wrong.
Note the use of take’ rather than take. The difference is that take performs the mail operation immediately, whereas take’ generates a deferred operation suitable for use by select.
In general all mail operations which can block have primed versions suitable for use in select, and select can handle both blocking reads and writes, plus timeouts besides. A fancier select statement than you are ever likely to write demonstrates this:
do_one_mailop [
take' mailslot1
==>
(\\ foo = handle_slot1_read foo),
give' (mailslot1 foo)
==>
(\\ () = handle_slot1_write ()),
pull' mailqueue1 # Mailqueues are covered below.
==>
(\\ foo = handle_mailqueue1_read foo),
timeout_in' (time::from_milliseconds 100) # Timeouts are pretty self-explanatory.
==> # They are -so- much more convenient
(\\ () = handle_100_ms_timeout ()) # than the vanilla-C equivalent! :-)
];
One particularly nice aspect of Reppy’s concurrent programming model, distinguishing it from many other such models, is that everything is first class. Mailslots, maildrops and mailqueues are all first-class values which may be freely constructed at runtime and passed around, stored in datastructures etc.
In particular, the select argument list is in fact a vanilla Mythryl list, which may be freely re/constructed dynamically at runtime, although in most cases it will be fixed at compiletime as in the above examples.
This first-classness provides tremendous reserve flexibility for interactive programming, in distinct contrast to concurrent programming paradigms in which (for example) select style statements are completely fixed at compiletime.
(Reppy’s model also provides for user definition of compound mailops which are likewise first-class; I’m not going to cover that in this brief tutorial.)
Mailslots, oneshot mailslots, maildrops and ’do_one_mailop’ statements suffice for maybe ninety percent of typical concurrent programming; the remaining mail mechanisms are used considerably less frequently:
Reading from an empty mailqueue blocks the thread until there is something to read.
Writing to a mailqueue never blocks, but the mailqueue contents can grow without bound, potentially filling all of memory, so they need to be used with considerable caution.
The main virtue of mailqueues is that they avoid the risk of deadlock due to a cycle of threads all blocking waiting for each other.
The deadlock-avoidance protocol that the eXene development crew has arrived at is to use mailqueues on all values containing user input. This breaks most potential deadlock cycles, and there is very little risk of user-generated values filling all of memory before threads get enough CPU bandwidth to handle them.
The basic mailqueue protocol is:
include package threadkit;
queue: Mailqueue (Foo)
=
make_mailqueue (); # Create an empty mailqueue holding
# values of type Foo.
push (queue, foo); # Deposit a a type-Foo value in the mailqueue.
foo = pull queue; # Get one type-Foo value from mailqueue.
This presents considerable risk that if any individual reader dies or blocks, its mailqueue may grow without bound, eventually filling memory, so mailcasters must be used with caution, but there are times when one-to-many communication is exactly the functionality needed.
The basic mailcaster protocol is:
include package threadkit;
mailcaster: Mailcaster (Foo)
=
make_mailcaster (); # Create an empty mailcaster for
# values of type Foo.
readqueue1 = make_readqueue mailcaster;
readqueue2 = make_readqueue mailcaster;
[...] # One readqueue per reading thread.
send (mailcaster, foo); # Done in sender thread.
foo = receive readqueue1; # Done in first reader thread.
foo = receive readqueue2; # Done in second reader thread.
By far the largest body of code written in CML is eXene, the X widgetset and and client library that John H Reppy wrote to exercise CML. The Mythryl port of eXene is called xkit and the code may be found in src/lib/x-kit/ in the Mythryl source distribution.
This code is an ambitious experiment in highly concurrent programming. Each widget uses at least one private thread to animate it, and often more. In retrospect some of the ideas tried out in this package worked very well and some worked not very well at all.
One of the biggest design problems turned out to be using primarily synchronous communication between widgets (i.e. mailslots) while also having widgets send to both parent and child widgets; this proved a fertile breeding ground for deadlock bugs. (If I were redesigning it today I would use mailqueues as the primary interthread communication mechanism.)
Since xkit needs a fairly complete rewrite to bring it up to production quality (and since Gtk is more apropos for most purposes) I have not yet written a tutorial set for it, but sample apps may be found in
src/lib/x-kit/tut/
and using the widget kit is not terribly difficult working from these examples plus an occasional peek at the widget library sourcecode and/or the original eXene documents.