Towards an Operational Semantics for a Non-Strict Parallel Language
Jon Hall, Clem Baker-Finch, Phil Trinder and David
King. In International Workshop on the Implementation of
Functional Languages, London, 1998, LNCS vol. 1595, pages 55-72.
Abstract
Parallel programs must describe both computation and coordination,
i.e. what to compute and how to organise the
computation. In functional languages equational reasoning is often
used to reason about computation. In contrast there have been many
different coordination constructs for functional languages, and far
less work on reasoning about coordination.
We present an initial semantics for GpH, a small extension of the
Haskell language, that allows us to reason about coordination. In
particular we can reason about work, average parallelism and
runtime. The semantics captures the notions of limited
(physical) resources, the preservation of sharing, and speculative
evaluation. We show a consistency result with Launchbury's well-known
lazy semantics.
BibTeX, PostScript, gzipped PostScript