The Semantics of Future and an Application

Abstract

The future annotation of MultiLisp provides a simple method for taming the implicit parallelism of functional programs. Prior research on future has concentrated on implementation and design issues, and has largely ignored the development of a semantic characterization of future . This paper considers an idealized functional language with futures and presents a series of operational semantics with increasing 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 by introducing placeholder objects and touch operations. We use the last semantics to derive a program analysis algorithm and an optimization algorithm that removes provably redundant touch operations. Experiments with the Gambit compiler indicate that this optimization significantly reduces the overhead imposed by touch operations.