An Operational Semantics for Parallel Call-by-Need

Jon Hall, Clem Baker-Finch, Phil Trinder and David King. Research Report 98/18, Faculty of Mathematics & Computing, The Open University.

Abstract

Parallel (lazy) functional programs must describe both computation and coordination, i.e., what to compute and how to arrange the computation in parallel. The formal manipulation of the behaviours of such programs requires a semantics which accurately captures lazy evaluation, and the dependence of execution on the availability of (physical) resources. In this paper we present a lockstep semantics as a first step towards this goal which, we hope, will allow us to reason about the coordination in a lazy setting.

A later version of this report was published as Towards an Operational Semantics for a Non-Strict Parallel Language.

BibTeX, PostScript, gzipped PostScript