Self-Adjusting Computation

Overview

Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data.   The basic abstractions and algorithms for self-adjusting computation were invented  jointly with Guy Blelloch and Robert Harper in my Ph.D. thesis work.  In subsequent work, we have extended the foundations to include imperative (effectful) computations and traceable data structures, and developed programming languages and systems to support  self-adjusting computation. We have also applied self-adjusting computation in a number of domains including algorithms, machine learning, and software systems.  In these applications, we have solved several important open problems (e.g., geometric problems involving changing and moving data sets, inference algorithms for learning from changing models). 

Perhaps the most important idea in self-adjusting computation is the treatment of computation as a "first-class" mathematical and computational object that can be remembered, re-used, and adapted to changes in its environment.  Another important idea is the use of type systems that can separate "changeable" computations from "stable" or "invariable" computations that do not and cannot change.  Another crucial idea is the realization of the first-class nature of computation in efficient algorithms that represent a computation in the form of a dynamic dependency graph.  Such a graph can be constructed and updated efficiently, via a change-propagation algorithm, in response to changes to the computation data.   The research stands on advances made in what in computer science is known an Theory A and Theory B, combining and fusing techniques from both areas.  A key technique that permeates much of this work is the use of language-based and algorithmic efficiency or cost models for predictable, analyzable efficiency.  We have demonstrated that carefully designed languages and compilers can realize in practice the efficiency predicted by such theoretical models.

Publications

Software

  • The tarball of the earlier implementations that match the interface and algorithms described in our TOPLAS-2006 paper.
  • CEAL extends the C language with support for self-adjusting computation.  Download CEAL.  
  • Delta ML extends the ML language with support for self-adjusting computation. Download DeltaML. 

People

Funding

  • This research is supported partially by grants from Intel Labs, Microsoft Research, and National Science Foundations.