[MLton-user] simple, portable, asynchronous programming in SML

[Vesa Karvonen]

[This is a reply to
   http://mlton.org/pipermail/mlton-user/2006-July/000856.html]

As those who subscribe to the mlton-commit list might have noticed, I've
been working on another implementation of Stephen's Event library:

  http://mlton.org/pipermail/mlton-user/2006-July/000856.html

You can find my implementation from mltonlib:

  http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/async/unstable/

Why another implementation?  First I want to have a maintained version of
the library, because I'm using it.  Second, I also wanted to understand
the technique better.  Third, I also wanted to see how a different
signature for the library would turn out to be.

I don't yet have a lot of experience writing code using the library, and
the application I'm writing using the library is very simple, but the
technique does seem to lead to fairly readable client code.  Indeed, what
made me consider adopting the technique was that the application basically
just waits for a few different kinds of events and responds to them.  I
first tried to write an ad hoc event handling loop, but I didn't like the
way it looked like (unmodular mess).  Using the library, the core of the
application, albeit quite simple, seems considerably more modular and
easier to understand.  I also plan to use the library in a couple of other
simple applications.

As was clear to me from the beginning, one difficulty with the approach is
dealing with resources that need to be explicitly closed or freed.  This
is a problem, because one can't use the usual "withX" technique for simple
scoped resource management:

  withX (fn x => ... use x ...)

Instead, clean up code needs to be carefully added to all the right
places:

  try (fn () => open X,
       fn x =>
          any [on (event that requires x,
                   fn ... => ...use x and only close it when done ...),
               on (another event,
                   fn ... => ... also need to close x, preferably
                                 immediately ...  )],
       fn e => ...)

I haven't yet given it much thought, but there may be ways to simplify the
resource management problem.  An obvious way would be to use finalizers,
but those are not appropriate for certain critical resources.  Another way
might be to allow one to attach an arbitrary clean up effect to an event
to be performed when the event isn't selected.

A couple of specific notes below.

Quoting Stephen Weeks <sweeks at sweeks.com>:

> [...]  It is up to clients of the event module to call "runHandlers"
> 
>   val runHandlers: unit -> unit
> 
> to run all scheduled handlers.  The expectation is not that user code
> is littered with calls to runHandlers.  Rather, the expectation is
> that the code that interfaces with the low-level asynchronous system
> stuff (select, GUI callbacks, etc.) calls runHandlers whenever system
> events enable new handlers.  At that point, a single call to
> runHandlers suffices to propagate all the effects of the low-level
> event throughout the SML world.

Indeed, that's how my application does it.  There is just a single simple
event loop that waits for OS events, translates the events to uses of the
library provided communication mechanisms (Ch, SkipCh, IVar, MVar, Mailbox,
...) and runs the handlers.

> The benefit of this approach to handlers is preservation of the
> non-preemptive programming model and the immensely easier reasoning
> about programs that goes along with it.  Code that installs handlers,
> i.e. calls "when", doesn't have to worry about the handlers running
> while it is running and interfering with its state.  Handlers
> themselves are assured to run to completion without interruption from
> other handlers.  There is no unexpected context switching due to
> preemption or due to blocking.  Code doesn't block -- it just installs
> handlers.

I agree, this seems like a useful property that simplifies reasoning about
programs.  I just printed out the article "Event-Based Programming without
Inversion of Control" by Haller and Odersky (mentioned at
http://lambda-the-ultimate.org/node/2081) and while I haven't yet had time
to read through it, I noticed that they seem to run handlers recursively,
which doesn't seem as nice (but I haven't yet read the entire article).

> In addition to channels, there are several event combinators for
> creating basic events and building more complicated events from
> simpler ones.
> 
>   val always: 'a -> 'a t
>   val never: unit -> 'a t
[...]

Do you actually have uses for those two?  It seems to me that without
operations other than choose for combining events, those don't seem to be
of much use.  Neither always nor never seems to make sense to use with
choose.  The never event would be redundant and, without a more precise
definition of the semantics of choose, always would be unpredictable.

On the issue of combining events, I wonder whether one could implement a
useful variation of Transactional Events

  http://ttic.uchicago.edu/~fluet/research/tx-events/

without threads.

> A mailbox is exactly like a channel except that "put" is buffered.
> [...] Mailboxes are easily implemented in terms of channels and "when".
> 
>   fun mailbox () =
>      let
>         val {get, put} = channel ()
>      in
>         {get = get,
>          put = fn a => when (put a, ignore)}
>      end

One issue I learned while reimplementing the library is that one has to be
careful that mailbox get events are processed in the same order that the
corresponding mailbox put effects.  (I haven't tested whether your
implementation preserves the order.)

> An mvar is a cell that is either empty or full, in which case it
> holds a single value.  It is like an "'a option ref". 
> 
>   val mvar: unit -> {get: 'a t, put: 'a -> unit}
> 
> "put" stores a value in the cell.  It is an error to call put if the
> cell is full.  "get" is enabled with value "a" when the cell is full,
> holding value "a".  Handling a "get" removes the value from the cell.

A useful variation of mvars (or channels) is a skip channel.  (IIRC, I
read about the idea from an article on Concurrent Haskell.)  A skip
channel is roughly like an mvar, but writing (putting) to skip channel
twice without an intervening read (gets) just discards the older value.
This is useful when an event source produces more events than the
corresponding handler can handle and it is safe to skip events.  (Indeed,
that is exactly how one of the events in my applications should behave.)

> [...] The code also includes a space-safe version of mutable queues,
> where enque is curried so that one can hold on to the back of the queue
> without holding on to the entire queue.

I'm not entirely sure whether the implication here is that the space-safe
queue contributes to the space-safety of the library implementation.  I've
examined the code fairly carefully and I'm not at all sure that the use of
space-safe queues would make a difference.  Could you elaborate on the
space-safety of your implementation?

> fun ivar () =
>   let
>      val getters = Handlers.make ()
>      val r = ref (NotEnabled (Handlers.add getters ()))
>      val get = T (fn () => !r)
>      fun put a =
>         case !r of
>            NotEnabled _ =>
>               (r := Enabled a;
>                Handlers.scheduleAll getters a)
>          | _ => die "ivar put"
>   in
>      {get = get, put = put}
>   end

Actually, while using my version of the library, I noticed that the above
implementation of ivar has a space-leak.  Suppose that

  when (choose [get from ivar, something else], ...)

is executed and that the "something else" event gets chosen.  This has the
side-effect of adding a handler to the getters queue of the ivar.  Now,
suppose that the same happens an arbitrary number of times.  The problem is
that the queued handlers aren't removed until something is put into the
ivar, which might not happen until after a very long time and an arbitrary
number of unchosen get events (this was the case I ran into) or possibly
never.

Other communication primitives have similar space-leaks.  In general,
queued, but unchosen/uncommitted, handlers must be removed eagerly
(enough) or they will cause space-leaks.

-Vesa Karvonen