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.
@phdthesis{Hammer2012,
author = "Matthew Arthur Hammer",
title = "Self-Adjusting Machines",
school = "Computer Science Department, University of Chicago",
year = 2012,
month = december,
}