The Semantics of Futures

Abstract

The future annotation introduced by MultiLisp provides a simple method for taming the implicit parallelism of functional programs. Prior research on futures has concentrated on implementation and design issues, and has largely ignored the development of a semantic characterization of futures. This paper presents four operational semantics for an idealized functional language with futures with varying degrees of intensionality. The first semantics defines future to be a semantically-transparent annotation. The second semantics interprets a future expression as a potentially parallel task. The third semantics explicates the coordination of parallel tasks and the need for touch operations on placeholder-strict arguments to certain primitive operations by introducing placeholder objects. The fourth and last semantics is a low-level refinement of the third semantics, which explicates just enough information to permit the smooth derivation of program analyses. The paper includes proofs showing the equivalence of these semantics.