
The Derivation of Compositional Programs
K. Mani Chandy and Carl Kesselman ?
California Institute of Technology
Pasadena, California 91125, USA
mani@vlsi.caltech.edu, carl@vlsi.caltech.edu
July 24, 1992
To appear in the Proceedings of the 1992 Joint International Conference and Symposium on Logic Programming, MIT Press.
Abstract
This paper proposes a parallel programming notation and a method
of reasoning about programs with the following characteristics:
1. Parallel Composition The notation provides different forms of interfaces
between processes; the more restrictive the interface, the simpler
the proofs of process composition. A flexible interface is that of cooperating
processes with a shared address space; proofs of programs that
use this interface are based on noninterference [OG76] and temporal
logic [Pnu81, CM88, Lam91]. We also propose more restrictive interfaces
and specifications that allow us to use the following specificationconjunction
rule: the strongest specification of a parallel composition
of processes is the conjunction of the strongest specifications of its
components. This rule is helpful in deriving parallel programs.
2. Determinism A process that does not use certain primitives of the
notation is guaranteed to be deterministic. Programmers who wish to
prove that their programs are deterministic are relieved of this proof
obligation if they restrict their programs to a certain subset of the
primitives.