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.
- 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 Charis the first character you type after a specific time. Then
fmap toUpper fc :: Future Charis the capitalized version of the future character. Thus,
Futureis a functor. The resulting future is knowable when
- 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
y80becomes knowable. So
Futureis 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 Pricegives the price of milk on a given day (at some specified place), and
nextFreeze :: Day -> Future Dayis 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
Futureis thus a monad. (The
returnmethod of a monad is the same as the
puremethod 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
(>>=). 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 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.
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 instance is provided entirely by the standard instance for pairs:
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)
Time t must be a monoid, with
mempty being the earliest time and
max. We’ll define
Time with the help of the
We could require that the underlying time parameter type
Bounded, but I want to have as few restrictions as possible. For instance,
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.
With these two reusable building blocks, our
Time definition falls right out:
type Time t = Max (AddBounds t)
Monad instance, we just need an instance for pairs equivalent to the Monad Writer instance.
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
f a could result from
pure and so have time
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
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.