Conal Elliott

A future value (or simply “future”) is a value that might not be knowable until a later time, such as “the value of the next key you press”, or “the value of LambdaPix stock at noon next Monday” (both from the time you first read this sentence), or “how many tries it will take me to blow out all the candles on my next birthday cake”. Unlike an imperative computation, each future has a unique value — although you probably cannot yet know what that value is. I’ve implemented this notion of futures as part of a library Reactive.

Edits:

• 2008-04-04: tweaked tag; removed first section heading.

You can force a future, which makes you wait (block) until its value is knowable. Meanwhile, what kinds of things can you do a future now?

• Apply a function to the not-yet-known value, resulting in another future. For instance, suppose fc :: Future Char is the first character you type after a specific time. Then fmap toUpper fc :: Future Char is the capitalized version of the future character. Thus, Future is a functor. The resulting future is knowable when fc is knowable.
• What about combining two or more future values? For instance, how many days between the first time after the start of 2008 that the temperature exceeds 80 degrees Fahrenheit at (a) my home and (b) your home. Each of those dates is a future value, and so is the difference between them. If those futures are m80, y80 :: Day, then the difference is diff80 = liftA2 (-) m80 y80. That difference is becomes knowable when the later of the m80 and y80 becomes knowable. So Future is an applicative functor (AF), and one can apply a future function to a future argument to get a future result (futRes = futFun <*> futArg). The other AF method is pure :: a -> Future a, which makes a future value that is always knowable to be a given value.
• Sometimes questions about the future are staged, such as “What will be the price of milk the day after it the temperature next drops below freezing” (plus specifics about where and starting when). Suppose priceOn :: Day -> Future Price gives the price of milk on a given day (at some specified place), and nextFreeze :: Day -> Future Day is the first date of a freeze (also at a specified place) after a given date. Then our query is expressed as nextFreeze today >>= priceOn, which has type Future Price. Future is thus a monad. (The return method of a monad is the same as the pure method of an AF.) From another perspective on monads, we can collapse a future future into a future, using join :: Future (Future a) -> Future a.

These three ways of manipulating futures are all focused on the value of futures. There is one more, very useful, combining operation that focuses on the timing of futures: given two futures, which one comes first. Although we can’t know the answer now, we can ask the question now and get a future. For example, what is the next character that either you or I will type? Call those characters mc, yc :: Future Char. The earlier of the two is mc `mappend` yc, which has type Future Char. Thus, Future ty is a monoid for every type ty. The other monoid method is mempty (the identity for mappend), which is the future that never happens.

Why aren’t futures just lazy values?

If futures were just lazy values, then we wouldn’t have to use pure, fmap, (<*>) (and liftA_n_), and (>>=). However, there isn’t enough semantic content in a plain-old-value to determine which of two values is earlier (mappend on futures).

A semantics for futures

To clarify my thinking about future values, I’d like to have a simple and precise denotational semantics and then an implementation that is faithful to the semantics. The module Data.SFuture provides such a semantics, although the implementation in Data.Future is not completely faithful.

The model

The semantic model is very simple: (the meaning of) a future value is just a time/value pair. The particular choice of “time” type is not important, as long as it is ordered.

newtype Future t a = Future (Time t, a)
  deriving (Functor, Applicative, Monad, Show)

Delightfully, almost all required functionality comes automatically from the derived class instances, thanks to the standard instances for pairs and the definition of Time, given below. Rather than require our time type to be bounded, we can easily add bounds to an arbitrary type. Rather than defining Time t now, let’s discover the definition while considering the required meanings of the class instances. The definition will use just a bit of wrapping around the type t, demonstrating a principle Conor McBride expressed as “types don’t just contain data, types explain data”.

Functor

The Functor instance is provided entirely by the standard instance for pairs:

instance Functor ((,) a) where fmap f (a,b) = (a, f b)

In particular, fmap f (Future (t,b)) == Future t (f b), as desired.

Applicative and Time

Look next at the Applicative instance for pairs:

instance Monoid a => Applicative ((,) a) where
  pure x = (mempty, x)
  (u, f) <*> (v, x) = (u `mappend` v, f x)

So Time t must be a monoid, with mempty being the earliest time and mappend being max. We’ll define Time with the help of the Max monoid:

newtype Max a = Max { getMax :: a }
  deriving (Eq, Ord, Read, Show, Bounded)

instance (Ord a, Bounded a) => Monoid (Max a) where
  mempty = Max minBound
  Max a `mappend` Max b = Max (a `max` b)

We could require that the underlying time parameter type t be Bounded, but I want to have as few restrictions as possible. For instance, Integer, Float, and Double are not Bounded, and neither are the types in the Time library. Fortunately, it’s easy to add bounds to any type, preserving the existing ordering.

data AddBounds a = MinBound | NoBound a | MaxBound
  deriving (Eq, Ord, Read, Show)

instance Bounded (AddBounds a) where
  minBound = MinBound
  maxBound = MaxBound

With these two reusable building blocks, our Time definition falls right out:

type Time t = Max (AddBounds t)

Monad

For our Monad instance, we just need an instance for pairs equivalent to the Monad Writer instance.

instance Monoid o => Monad ((,) o) where
  return = pure
  (o,a) >>= f = (o `mappend` o', a') where (o',a') = f a

Consequently (using join m = m >>= id), join ((o, (o',a))) == (o `mappend` o', a). Again, the standard instance implies exactly the desired meaning for futures. Future (t,a) >>= f is available exactly at the later of t and the availability of f a. We might have guessed instead that the time is simply the time of f a, e.g., assuming it to always be at least t. However, f a could result from pure and so have time minBound.

Monoid

The last piece of Future functionality is the Monoid instance, and I don’t know how to get that instance to define itself. I want mappend to yield the earlier of two futures, choosing the first argument when simultaneous. The never-occuring mempty has a time beyond all t values.

instance Ord t => Monoid (Future t a) where
  mempty  = Future (maxBound, error "it'll never happen, buddy")
  fut@(Future (t,_)) `mappend` fut'@(Future (t',_)) =
    if t <= t' then fut else fut'

Coming next

Tune in for the next post, which describes the current implementation of future values in Reactive. The implementation uses multi-threading and is not quite faithful to the semantics given here. I’m looking for a faithful implementation.

A following post will then describe the use of future values in an elegant new implementation of functional reactive programming.

A future value (or simply “future”) is a value that might not be knowable until a later time, such as “the value of the next key you press”, or “the...