## 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.