Self-Adjusting Machines

Matthew A. Hammer.
Ph.D. Dissertation, University of Chicago


In computer systems, the interaction of computations and data often causes incremental changes, not wholesale ones. Hence, there exists the possibility of improving the efficiency of a system by recording and reusing computations, rather than blindly remaking them anew. To this end, self-adjusting computation is a technique for systematically constructing computational structures that evolve efficiently and incrementally. Past work has explored several facets of this programming language-based approach, but no prior formulations have given a low-level account of self-adjusting computation. By low-level, we mean an account where machine resources are defined and managed explicitly, e.g., as in the C programming language.

We offer self-adjusting machines, a concept based on an operational interpretation of self-adjusting computation with explicit machine resources. By making their resources explicit, self-adjusting machines give an operational account of self-adjusting computation suitable for interoperation with low-level languages; via practical compilation and run- time techniques, these machines are programmable, sound and efficient.

Abstractly, we formally define self-adjusting machines that run an intermediate language; we prove that this abstract machine semantics is sound. Concretely, we give techniques based on this semantics that construct self-adjusting machines by compiling a C-like surface language into C target code that runs within an extensible, C-based run-time system. By creating new programming abstractions, library programmers can extend this C-based system with new self-adjusting behavior. We demonstrate that this extension framework is powerful by using it to express a variety of both new and old self-adjusting abstractions. We give an empirical evaluation showing that our approach is efficient and well-suited for programming space and time-efficient self-adjusting computations.

Bibtex Entry

 author = "Matthew Arthur Hammer",
 title = "Self-Adjusting Machines",
 school = "Computer Science Department, University of Chicago",
 year = 2012,
 month = december,

Dissertation and Slides