### The IVar monad

#### by Edward Z. Yang

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.

Did you enjoy this post? Please subscribe to my feed!

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

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

“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).

Possibly a typo: Blocked v.s. Blocking

Thanks, fixed.

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.