Tim Teitelbaum Associate Professor tt@cs.cornell.edu http://www.cs.cornell.edu/faculty/home/tt/vita/vita.html PhD Carnegie-Mellon University, 1975 Incremental algorithms exploit the fact that the function being computed is evaluated repeatedly on inputs that differ only slightly from one another. By avoiding unnecessary duplication of common computations, incremental algorithms can have better performance than batch algorithms. Based on the observation that explicitly incremental algorithms are hard to write, we aim to provide incremental computation automatically from non-incremental algorithms.

Our past work has focused on the study of incremental evaluators for various non-incremental computational formalisms. The formalisms considered have included (first-order) attribute grammars, relational data-base queries, first-order functional programs, acyclic expression graphs, the lambda calculus, and higher-order attribute grammars. For each formalism and for various notions of change in input, we have devised incremental evaluators. Because, in each case, the incremental evaluator can be applied to any program written in the given non-incremental computational formalism, our results have been broadly applicable.

Currently, we are studying the formal derivation of incremental programs from non-incremental programs. Although, in principle, the methods to be devised might be used to derive incremental evaluators for general purpose computational formalisms, it is our intention that the methods be applied directly to arbitrary end-user programs. By shifting attention to the derivation of incremental algorithms, we aim to exploit partial evaluation, other static analysis techniques, and domain specific knowledge to provide a degree of incrementality not otherwise achievable by a generic incremental evaluator. A prototype system for transforming non-incremental programs into incremental programs is under development.

University Activities

On sabbatical 1997-1998

External Activities

Co-founder and Chairman: GrammaTech, Inc.

Professional Activities

• Reviewer: NRC Computer Science and Telecommunications Board

• Referee: ACM Trans. on Programming Languages and Systems (TOPLAS)