Content area
Conventional approaches to parallel and distributed programming are complicated by nondeterminism. In order to understand their program, a programmer must understand its behavior under every possible interleaving chosen by the scheduler or every possible reordering of messages imposed by the network. Past efforts to address this problem have shown that by modeling shared state as an element of a semilattice and restricting stateful operations so that this structure is respected, it is possible to build languages admitting only well-behaved parallel computations. Exploiting the observation that the lattice-theoretic underpinnings of these systems fit naturally into a programming model based on domain theory, this dissertation integrates these ideas into λ∨, a nearly-pure functional programming language for deterministic parallelism. The language's distinctive feature is a parallel composition construct called the join operator. It retains the good behavior of prior systems while also witnessing a language-design that is both general-purpose and declarative.
The notion of parallel composition studied here is useful for more than just parallelism: another line of work on compositional programming has shown it to be useful in making programs more modular and extensible. The common thread behind its several uses is that a principled notion of parallel composition facilitates the separation of concerns: systems may be built as combinations of independent components. To keep such systems unambiguous and free of runtime errors, this work also introduces a type system that prevents compositions of components with conflicting behavior. My thesis is that languages featuring semilattice-structured data and the join operator provide a well-behaved foundation for compositionally designing parallel and extensible systems.