Slivers: Computational Modularity via Synchronized Lazy Aggregates

Franklyn Turbak

MIT Doctoral Dissertation, Februrary, 1994


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.


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. Select here for the entire dissertation document. (Warning: it is 454 pages long with lots of figures!).


Send all questions and comments about this work to