Slivers: Computational Modularity via Synchronized Lazy Aggregates
Franklyn Turbak
MIT Doctoral Dissertation, Februrary, 1994
Abstract:
Slivers are a new approach to expressing computations as
combinations of mix-and-match operators on aggregate data. Unlike
other aggregate data models, slivers enable programmers to control
fine-grained operational aspects of modular programs. In particular,
slivers can guarantee that networks of operators exhibit the desirable
storage behavior and operation scheduling of intricate loops and
recursions. For example, slivers can preserve the space efficiency of
a complex tree algorithm when it is expressed as the superposition of
simpler tree walks.
The sliver technique is based on a dynamic model of lock step
processing that enables combinations of list and tree operators to
simulate the operational behavior of a single recursive procedure.
Operational control is achieved through synchronized lazy
aggregates, dynamically unfolding data structures that constrain how
the processing of separate operators is interwoven. The key to the
technique is the synchron, a novel first-class object that
allows a dynamically determined number of concurrently executing
operators to participate in a barrier synchronization. Slivers embody
a notion of computational shape that specifies how the
operational patterns of a process can be composed out of the patterns
of its components.
The utility of slivers is illustrated in the context of
SYNAPSE, a simple language for expressing linear and
tree-shaped computations. SYNAPSE is built on top of
OPERA, a new concurrent dialect of Scheme that incorporates
the concurrency, synchronization, and non-strictness required by the
lock step processing model. The semantics of OPERA are
explained in terms of EDGAR, a novel graph reduction model
based on explicit demand propagation.
Contents:
Below are links to individual chapters of the disseration.
For a more concise overview of key aspects of the thesis research, please
see the papers on synchronized lazy aggregates
and synchrons.
-
Table of Contents
-
Acknowledgments
- Chapter 1:
Overview
-- An overview of the dissertation.
- Chapter 2:
Slivers
-- A motivation for sliver decomposition in the context of two
monolithic programs: an employee database program and an alpha
renaming program.
- Chapter 3:
The Signal Processing Style of Programming
-- A detailed analysis of why existing SPS techniques fail to express
desirable operational characteristics of programs.
- Chapter 4:
Computational Shape
-- A presentation of a simple notion of computational shape. Shapes are
described in terms of the time-based ordering induced on the call and
return events in the execution of a recursive procedure.
- Chapter 5:
Synchronized Lazy Aggregates
-- An explanation of the lock step processing model underlying the sliver
technique. Synchronized lazy aggregates are introduced as a mechanism
for guaranteeing that networks of slivers simulate the behavior of a
corresponding monolithic procedure.
- Chapter 6:
SYNAPSE: Programming with Slivers and Slags
-- An illustration of the power of slivers and slags in the context of
SYNAPSE, a simple language for manipulating synchronized lists and
trees.
- Chapter 7:
OPERA: Controlling Operational Behavior
-- A presentation of OPERA, the concurrent dialect of Scheme in which
SYNAPSE is embedded. An informal description of OPERA's concurrency,
synchronization, and non-strictness features is followed by an explanation
of how SYNAPSE is implemented in OPERA.
- Chapter 8:
EDGAR: Explicit Demand Graph Reduction
-- An overview of EDGAR, an explicit demand graph reduction model that
provides an operational semantics for OPERA. OPERA's concurrency,
synchronization, and non-strictness mechanisms are formally described here.
- Chapter 9:
Experience
-- A discussion of the experimental aspects of the research, including
the implementation and testing of EDGAR, OPERA, and SYNAPSE. This chapter
also describes the DYNAMATOR, a graphical program animator that proved
invaluable in the development of the other systems.
- Chapter 10:
Conclusion
-- A summary of the research, including contributions and future work.
-
Bibliography
- Appendix A:
Glossary
-- The dissertation introduces a large number of new terms, and uses some
existing terms in a non-standard way. The glossary is provided to help the
reader adjust to the terminology.
Select here for the entire dissertation document.
(Warning: it is 454 pages long with lots of figures!).
Feedback:
Send all questions and comments about this work to
fturbak@wellesley.edu.