A previous post described future values (or simply “futures”), which are values depend on information from the future, e.g., from the real world. There I gave a simple denotational semantics for future values as time/value pairs. This post describes the multi-threaded implementation of futures in Reactive‘s
A simple representation
Futures are represented as actions that deliver a value. These actions are required to yield the same answer every time. Having a special representation for the future that never arrives (
mempty) will allow for some very important optimizations later.
data Future a = Future (IO a) | Never
A value can be “forced” from a future. If the value isn’t yet available, forcing will block.
force :: Future a -> IO a force (Future io) = io force Never = hang -- block forever
Threads and synchronization
The current implementation of futures uses Concurrent Haskell‘s
(fork a thread) and
MVars (synchronized communication variables).
Except for trivial futures (
mempty), the action in a future will simply be reading an MVar. Internal to the implementation:
newFuture :: IO (Future a, a -> IO ()) newFuture = do v <- newEmptyMVar return (Future (readMVar v), putMVar v)
The MVar is written to as the final step of a forked thread. Importantly, it is to be written only once. (It’s really an IVar.)
future :: IO a -> Future a future mka = unsafePerformIO $ do (fut,sink) <- newFuture forkIO $ mka >>= sink return fut
Note that the actual value is computed just once, and is accessed cheaply.
Functor, Applicative, and Monad
Monad instances are defined easily in terms of
future and the corresponding instances for
instance Functor Future where fmap f (Future get) = future (fmap f get) fmap _ Never = Never instance Applicative Future where pure a = Future (pure a) Future getf <*> Future getx = future (getf <*> getx) _ <*> _ = Never instance Monad Future where return = pure Future geta >>= h = future (geta >>= force . h) Never >>= _ = Never
Monoid — racing
The remaining class to implement is
mempty method is
mappend method is to select the earlier of two futures, which is implemented by having the two futures race to extrat a value:
instance Monoid (Future a) where mempty = Never mappend = race race :: Future a -> Future a -> Future a
Racing is easy in the case either is
Never `race` b = b a `race` Never = a
Otherwise, spin a thread for each future. The winner kills the loser.
a `race` b = unsafePerformIO $ do (c,sink) <- newFuture let run fut tid = forkIO $ do x <- force fut killThread tid sink x mdo ta <- run a tb tb <- run b ta return () return c
This last piece of the implementation can fall short of the semantics. For
a `mappend` b, we might get
b instead of
a even if they’re available simultaneously. It’s even possible to get the later of the two if they’re nearly simultaneous.
Edit (2008-02-02): although simultaneous physical events are extremely unlikely, futures are compositional, so it’s easy to construct two distinct but simultaneous futures in terms of on a common physical future.
What will it take to get deterministic semantics for
a `mappend` b? Here’s an idea: include an explicit time in a future. When one future happens with a time
t, query whether the other one occurs by the same time. What does it take to support this query operation?
A simpler implementation
In this implementation, futures (other than
Never) hold actions that typically read an MVar that is written only once. They could instead simply hold lazy values.
data Future a = Future a | Never
Forcing a future evaluates to weak head normal form (WHNF).
force :: Future a -> IO a force (Future a) = a `seq` return a force Never = hang
Making new future would work almost identically, just adding an
newFuture :: IO (Future a, a -> IO ()) newFuture = do v <- newEmptyMVar return (Future (unsafePerformIO $ readMVar v), putMVar v)
Monad instances simplify considerably, using function application directly, instead of the corresponding methods from the
Monad instances of
instance Functor Future where fmap f (Future a) = Future (f a) fmap _ Never = Never instance Applicative Future where pure a = Future a Future f <*> Future x = Future (f x) _ <*> _ = Never instance Monad Future where return = pure Future a >>= h = h a Never >>= _ = Never
Monoid instance is completely unchanged.
How does this implementation compare with the one above?
- It’s simpler, as stated.
- It’s a bit more efficient. Each MVar is only read once. Also, the
Monadinstances no longer create threads and MVars.
- The type statically enforces that forcing a future always gives the same result.
- Forcing a future reduces the value to WHNF and so is probably a little less lazy than the implementation above.
I’ve tried out this implementation and found that it intermittently crashes some examples that work fine in the
IO version. I have no idea why, and I’d be very interested in ideas about it or anything else in this post.