A computation is incremental if repeating it with a changed input is faster than from-scratch recomputation. Many software systems use incremental computation (IC) as a fundamental aspect of their design. Everyday examples include spreadsheets (incremental formula evaluation), development environments (incremental type checking, static analysis, translation, optimization) and database interaction (incremental view maintenance). If IC research succeeds, future "everyday" examples may include software testing (incremental re-testing when code changes) and scientific simulation (incremental re-simulation when parameters change).
In this talk, I will outline a vision for giving IC a special status in our programming languages, similar to the status that garbage collection (GC) receives today in nearly all "high-level" languages. Just as language support for GC has liberated programmers from the inherent complexity and tedium of manual memory management, I believe that IC offers a similar potential to elevate us and the systems we can express as programmers. I will outline Adapton, which provides language abstractions for IC that seem most promising today, showing how they unify and subsume prior approaches to IC proposed in both the distant and recent past. I will outline current challenges, and goals for future work.
Matthew Hammer is a postdoctoral researcher at the University of Maryland in College Park. He has a PhD from the University of Chicago and was a visiting student at the Max Planck Institute for Software Systems. His PhD project produced CEAL, a C-based language for incremental computation. He has a MS in CS from the Toyota Technological Institute at Chicago, and a BS in CS from the University of Wisconsin, Madison.
Matthew's current research in programming languages and language-based security consists of two on-going projects: Wysteria and Adapton. Wysteria expresses new multi-party computation protocols (built on existing cryptographic techniques) in the form of a high-level, functional programming language. Meanwhile, Adapton offers a new, unifying approach to expressing incremental computation.