Collapsing Futures: Easy to Use, Hard to Represent

posted by Craig Gidney on May 28, 2013

Type systems are useful things, but they can also over-constrain how you represent values. In this post I discuss a useful kind of type that’s difficult to represent in the type systems of most popular languages: types that “collapse” when you nest them inside of themselves.

Collapsing the Eventual Eventual Future

Suppose you have a Future: a representation of a value that may not be computed yet but will eventually be ready. Further suppose the eventual value of that future (call it $F_{outer}$ ) is itself a future (call it $F_{inner}$ ), and that the eventual value of $F_{inner}$ is the integer $1$ . Said another way, $F_{outer}$ is eventually eventually $1$ . Notice that “eventually” was repeated twice.

An interesting property of the word “eventually” is that repeating it twice doesn’t seem to change the literal meaning of sentences. Saying something will eventually eventually happen is the same as saying it will just eventually happen. Doubly-eventual is the same as singly-eventual. However, your typical implementation of a $Future(T)$ type will not have this “doubly is the same as singly” property. You’ll find that that $F_{outer}.Value \neq 1$ , even though $F_{outer}$ is eventually eventually $1$ , because $F_{outer}.Value$ is a $Future(int)$ instead of an $int$ .

Can we implement a variant of $Future(T)$ , a $Future^{*}(T)$ , that does respect that singly-eventual should be the same as doubly-eventual? This would be useful because it would mean we wouldn’t have to track the level of nesting in order to write correct code (which is particularly useful in dynamic languages and languages without generics, where the compiler won’t catch nesting-level mistakes).

Side note: If you think of $Future^{*}$ as a function that takes a type and returns a type, then calling $Future^{*}$ a collapsing type is equivalent to saying its function is idempotent.

If we try to implement $Future^{*}$ in C# or in Java, we’ll run into a bit of trouble when we try to specify the type of the value in a $Future^{*}(T)$ . It’s a $T$ , unless $T$ is a $Future^{*}(T_2)$ in which case it’s a $T_2$ , unless $T_2$ is… you get the idea. Their type systems can’t express these sorts of conditions, although more flexible type systems can (I think you can do it with templates in C++, for example), so we’re forced to give up on collapsing or give up on knowing the type of value coming out of a future.

In a dynamic language, or in a language without generics, this trade-off doesn’t exist. The language designers have made the choice for us: the type of value coming out of a future can’t be specified. This makes implementations in such languages feel much more natural.

Python Implementation

I implemented a collapsing future type in python, which you can play with on PythonFiddle. It works by checking the types of results at runtime, and flattening them when they’re also futures. Here is the type:

### An eventual value that automatically flattens doubly-eventual results
class Future:
    ### Inits a new not-yet-specified future value
    def __init__(self):
        self.__continuations = []
        
    ### Registers a continuation to run when the flattened future value is ready
    ### Returns the continuation's future result
    def continueWith(self, continuation):
        # remember continuation, if result not provided yet
        if self.__continuations != None:
            r = Future()
            self.__continuations.append((continuation, r))
            return r
        
        # automatic flattening
        if isinstance(self.__result, Future):
            return self.__result.continueWith(continuation)

        # run continuation inline when already finished        
        r = Future()
        v = continuation(self.__result)
        r.trySetResult(v)
        return r
    
    ### Sets this future's value, if it has not yet been set.
    ### Causes all registered continuations to be run or handed off.
    def trySetResult(self, result):
        # already set?
        cs = self.__continuations
        if cs == None: return False;
        
        # state transition
        self.__continuations = None
        self.__result = result
        
        # perform or hand-off registered continuations
        for e in cs:
            continuation, future = e
            r = self.continueWith(continuation);
            future.trySetResult(r)
        
        return True

If you read closely, you’ll notice that the above (not particularly efficient) implementation is itself (ab)using the fact that $Future^{*}$ is a collapsing type. For example, when a future’s result is being set to a a future, the results of continuations are set directly to the results of handed-off continuations despite them having a different level of nesting.

Here’s some sample code that uses the above future type, demonstrating that you don’t have to care about the level of nesting:

f1 = Future()
f2 = Future()
f3 = f1.continueWith(lambda v1: f2.continueWith(lambda v2: v1 + v2))

def out(x): print x
f1.continueWith(lambda x: out("f1's result = " + x))
f2.continueWith(lambda x: out("f2's result = " + x))
f3.continueWith(lambda x: out("f3's result = " + x))

f1.trySetResult(f2)
f2.trySetResult('Hello')

# outputs: 
# f2's result = Hello
# f3's result = HelloHello
# f1's result = Hello

In the above code, $f2$ has type $Future^{*}(String)$ because its result is set to a string. $f1$ has type $Future^{*}(Future^{*}(String))$ because its result is set to be $f2$ . $f3$ has type $Future^{*}(Future^{*}(Future^{*}(String)))$ , for reasons related to continueWith returning a $Future^{*}(T)$ when given a function that returns a $T$ .

Wait, why are we doing this complicated analysis? Because of the collapsing property, it’s dead obvious that they all have type $Future^{*}(String)$ . The fact that $f3$ ‘s result prints out as "HelloHello", instead of <__main__.Future instance at ...>, confirms it.

This is a level beyond having the compiler detect that you’ve made a nesting-level mistake. The mistake has been made fundamentally impossible, at least with respect to our future type on its own.

Mixing With Others

There are other types that can benefit from being made collapsible. For example, the “MayFail” and “MayBeCancelled” types I mentioned last week would work well as collapsing types, because you very rarely care “at what level” a failure or cancellation occurred. On the other hand, “List” would be a terrible collapsing type because you so often need to have a lists of lists. Another terrible candidate is “Maybe”, because you usually do care about “at what level” a value has been omitted.

One potential obstacle to having lots of collapsing types is mixing. A $Future^{*}(MayFail^{*}(Future^{*}(MayFail^{*}(T))))$ won’t automatically collapse into a $Future^{*}(MayFail^{*}(T))$ , and so mixing may re-introduce the need to care about nesting level. This is particularly bad in the case of futures because they often represent operations that might fail, and so mixing will be endemic. Maybe it would be possible to have some sort of cross-type collapsing that applies in appropriate places… I really just don’t know yet.

Summary

A collapsing type transparently flattens itself when nested inside of itself. A $Future^{*}(Future^{*}(String))$ will act exactly identical to a $Future^{*}(String)$ .

Collapsing types are easy to use, because they make nesting-level mistakes impossible. Collapsing types are hard to represent, because their type can’t be specified in the type systems of most popular languages.

—

Discuss on Reddit

—

Comments are closed.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.