ezyang’s blog

the arc of software bends towards understanding

The IVar monad

An IVar is an immutable variable; you write once, and read many times. In the Par monad framework, we use a prompt monad style construction in order to encode various operations on IVars, which deterministic parallel code in this framework might use. The question I'm interested in this post is an alternative encoding of this functionality, which supports nondeterministic concurrency and shows up in other contexts such as Python Twisted, node.js, any JavaScript UI library and LWT. Numerous bloggers have commented on this. But despite all of the monad mania surrounding what are essentially glorified callbacks, no one actually uses this monad when it comes to Haskell. Why not? For one reason, Haskell has cheap and cheerful preemptive green threads, so we can write our IO in synchronous style in lots of threads. But another reason, which I will be exploring in a later blog post, is that naively implementing bind in this model space leaks! (Most event libraries have worked around this bug in some way or another, which we will also be investigating.)

First things first, though. We start by implementing the IVar monad in Haskell. We build it incrementally, starting by demonstrating that IO (IORef a) is a monad. It's not particularly interesting: we could get all of it's features using IO. Our main interest in it is demonstrating the basic structure by which we will present a nondeterministic IVar monad.

import Data.IORef

newtype R a = R { runR :: IO (IORef a) }

instance Functor R where
  fmap f m = R $ do xref <- runR m
                    x <- readIORef xref
                    newIORef (f x)

instance Monad R where
  return x = R (newIORef x)
  m >>= f
    = R $ do xref <- runR m
             x <- readIORef xref
             runR (f x)

We never ever pass around values: rather, we put them inside IORef boxes. The bind operation involves reading out the content of a box, and then getting a new box out of the function we're binding to f. We always know what the contents of a box are: we never call writeIORef. Also notice that retrieving the reference is in IO, so arbitrary other side effects could occur while this is happening. When we have an actual IVar, those side effects could involve spinning off another thread of execution, which will eventually fill the IVar. Pay attention to these “boxes”: we’ll be interested in their usage properties for performance purposes.

In the case of an IVar, we now would like to have “empty” boxes, which may only get filled in at some later date. We might be tempted to implement this using IO (IORef (Maybe a)):

newtype S a = S { runS :: IO (IORef (Maybe a)) }

instance Monad S where
  return x = S (newIORef (Just x))
  m >>= f
    = S $ do xref <- runS m
             mx <- readIORef xref
             case mx of
               Just x -> runS (f x)
               Nothing -> ???

But we’re in a bit of a bind (ahem): we don’t actually know what value we need to pass to f if the box is still empty. What do we do?

The traditional solution is save f away for another time when the value truly does become available, at which point we invoke all of the blocking callbacks with the new value. Since our monad admits arbitrary side effects, these callbacks can still do useful work. (By the way, IORef (IVarContents a) is essentially what the Par monad uses to encode IVars.)

data IVarContents a =
    Empty
  | Blocking [a -> IO ()]
  | Full a

newtype T a = T { runT :: IO (IORef (IVarContents a)) }

Now we can implement that last case:

instance Monad T where
  return x = T (newIORef (Full x))
  m >>= f
    = T $ do xref <- runT m
             mx <- readIORef xref
             r <- newIORef Empty
             let callback x = runT (f x >>= fillIVar r) >> return ()
             case mx of
               Full x      -> callback x
               Empty       -> writeIORef xref (Blocking [callback])
               Blocking cs -> writeIORef xref (Blocking (callback:cs))
             return r

filIVar is some magical function which fills an empty IVar and reschedules anyone who was waiting for that value for execution. One possible (and a little silly) implementation, which assumes single-threading, could be:

fillIVar :: IORef (IVarContents a) -> a -> T ()
fillIVar ref x = T $ do
  r <- readIORef ref
  writeIORef ref (Full x)
  case r of
    Empty -> newIORef (Full ())
    Blocking cs -> mapM_ ($x) cs >> newIORef (Full ())
    Full _ -> error "fillIVar: Cannot write twice"

This is all fairly straightforward, and some variant of this has been reimplemented by basically any cooperative nonblocking async library. In my next post, I’d like to explicate some problems with this naive monadic encoding, as explained by the authors of LWT, and put a finger precisely what kind of variations of this pattern we actually see in the wild.

6 Responses to “The IVar monad”

  1. Sjoerd Visscher says:

    Is Empty an optimization? As it seems to be the same as Blocking [].

  2. Yep, looks like it. I think this avoids an extra indirection in the case of no waiters.

  3. gasche says:

    “Dataflow values”, that are assigned only once, possibly in a concurrent thread, and where all undefined access are blocked until a definition becomes available, are a cornerstone of the Mozart programming model, where this is elegantly combined with prolog-style unification: instead of assigning a fully-defined value, you unify with a possibly-partially-undefined value.

    Sébastien Doeraene, a student of Peter Van Roy, has recently written a Scala-to-Oz translator that allow Scala programs to transparently use dataflow variables, and therefore use the concurrency style promoted by Oz/Mozart. You may be interested in this work, which is discussed here:
    http://lambda-the-ultimate.org/node/4300

    I would be interested in seeing a monadification/reification of this programming style, and Haskell is probably the right language to think about this. It would be nice if this resulted in something as satisfying as the Monadic Constraint Programming framework, which imho is a credible alternative to the in-the-language constraint paradigms of Prolog (or Oz) (cf. also Escape from Zurg, an Exercise in Logic Programming).

  4. Paul Liu says:

    Possibly a typo: Blocked v.s. Blocking

  5. gasche: Logic programming is one of my big weaknesses, partially because it’s really hard to strap it onto a traditional functional programming language (you really need some deep language level support to do it in a nice way.) Still, a reified version might be interesting to look at.

Leave a Comment