Informatik, TU Wien

Incremental Computation with Adapton

A computation is incremental if repeating it with a changed input is faster than from-scratch recomputation.


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). While these systems are effective, their incremental features are implemented in an ad hoc manner, with complex and tedious IC-related code woven throughout the program. We believe that IC should instead be a programming languages feature, to make it easier to build, improve, and maintain systems that include IC. I will present Adapton, a novel, general-purpose IC system that provides language abstractions that are particularly useful for interactive incremental systems. Adapton can achieve orders of magnitude speedups over prior general-purpose IC systems. I will also describe Nominal Adapton, a recent extension that gives programmers more control over computation reuse, providing even greater speedups.


Jeffrey S. Foster is a Professor in the Department of Computer Science at the University of Maryland, College Park and in the University of Maryland Institute for Advanced Computer Studies. He is also Associate Chair for Graduate Education in the Department of Computer Science. Dr. Foster received his Ph.D. in Computer Science from the University of California, Berkeley, and he received M.Eng. and B.S. degrees from Cornell University, also in Computer Science. Dr. Foster's research focuses on developing programming languages and software engineering approaches to making software easier to write and more reliable, secure, and available. Some of his recent research efforts include improving security and privacy on Android mobile devices; developing automated techniques to check web application security; exploring the use of program synthesis to automatically construct program code from specifications; and creating new approaches to safely update software at run time.


This talk is organized by the Compilers and Languages Group at the Institute of Computer Languages.
Tea at the library of E185/1, Argentinierstr. 8, 4th floor (central) at 10:30.