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. 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 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 Can we implement a variant of Side note: If you think of If we try to implement 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. 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: If you read closely, you’ll notice that the above (not particularly efficient) implementation is itself (ab)using the fact that Here’s some sample code that uses the above future type, demonstrating that you don’t have to care about the level of nesting: In the above code, Wait, why are we doing this complicated analysis? Because of the collapsing property, it’s dead obvious that they all have type 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. 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 A collapsing type transparently flattens itself when nested inside of itself. A 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. — —
Collapsing Futures: Easy to Use, Hard to Represent
Collapsing the Eventual Eventual Future
) is itself a future (call it
), and that the eventual value of
is the integer
. Said another way,
is eventually eventually
. Notice that “eventually” was repeated twice.
type will not have this “doubly is the same as singly” property. You’ll find that that
, even though
is eventually eventually
, because
is a
instead of an
.
, a
, 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).
as a function that takes a type and returns a type, then calling
a collapsing type is equivalent to saying its function is idempotent.
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
. It’s a
, unless
is a
in which case it’s a
, unless
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.
Python Implementation
### 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
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.
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
has type
because its result is set to a string.
has type
because its result is set to be
.
has type
, for reasons related to continueWith returning a
when given a function that returns a
.
. The fact that
‘s result prints out as
"HelloHello"
, instead of <__main__.Future instance at ...>
, confirms it.Mixing With Others
won’t automatically collapse into a
, 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
will act exactly identical to a
.
Discuss on Reddit
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.
Archive