An Optimised Flow for Futures: From Theory to Practice

A future is an entity representing the result of an ongoing computation. A synchronisation with a get operation blocks the caller until the computation is over, to return the corresponding value. When a computation in charge of fulfilling a future delegates part of its processing to another task, mainstream languages return nested futures, and several get operations are needed to retrieve the computed value (we call such futures control-flow futures). Several approaches were proposed to tackle this issues: the forward construct, that allows the programmer to make delegation explicit and avoid nested futures, and data-flow explicit futures which natively collapse nested futures into plain futures. This paper supports the claim that data-flow explicit futures form a powerful set of language primitives, on top of which other approaches can be built. We prove the equivalence, in the context of data-flow explicit futures, between the forward construct and classical return from functions. The proof relies on a branching bisimulation between a program using forward and its return counterpart. This result allows language designers to consider forward as an optimisation directive rather than as a language primitive. Following the principles of the Godot system, we provide a library implementation of control-flow futures, based on data-flow explicit futures implemented in the compiler. This small library supports the claim that the implementation of classical futures based on data-flow ones is easier than the opposite. Our benchmarks show the viability of the approach from a performance point of view.