Overview

Self-adjusting computation refers to a model of computing where computations can automatically respond to changes to their data.   The basic abstractions and algorithms for self-adjusting computation were invented during my Ph.D. jointly with Guy Blelloch and Robert Harper.  In subsequent work, we have extended these techniques to imperative (effectful) computations and traceable data structures, developed programming languages and systems support  self-adjusting computation. We have  also applied self-adjusting computation to a number of domains including algorithms, machine learning, and systems (cloud computing), where we have also solved some important open problems and built some sizable software artifacts.  The key ideas behind self-adjusting computation include the use  traces represented as higher-order dynamic dependence graphs and reuse of partial computations.  Stability analysis helps determine the complexity of self-adjusting programs.  Compilers realize predicted efficiency by generating executables from high-level source programs written in C or ML-like languages.  Our compilers make innovative use of static analysis, types, and optimizations to ensure asymptotic and practical efficiency.