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.