BRICS · Contents · Lecturer · Programme · References

Incrementalization: a Powerful Approach to Efficiency Improvement

A BRICS Mini-Course
June 28 and 29, 1999

Lectures by
Y. Annie Liu,
Computer Science Department, Indiana University, Bloomington, Indiana 47405

Course Contents

Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each new output incrementally by making use of the previous output rather than from scratch. This course describes a general systematic approach to efficiency improvement based on incrementalization.

Given a program f and an operation oplus, incrementalization yields an incremental program that computes f(xoplus y) efficiently by using the result of f(x), the intermediate results computed in computing f(x), and auxiliary information about f(x) that can be inexpensively maintained. It unifies existing approaches to incremental computation and is generally applicable; it exploits many existing program analysis and transformation techniques and can be systematically applied.

Since every non-trivial computation proceeds by iteration or recursion, incrementalization may be used for achieving efficient computation in general, by computing loops and recursions incrementally using appropriate incremental programs. Incrementalizing aggregate array computations over loops yields new powerful optimizations that are fully automatable; incrementalizing recursive equations allows dynamic programming programs to be automatically derived. These optimizations yield drastic performance improvements.

This method had been applied to problems in interactive systems, optimizing compilers, transformational program development, etc. Examples include problems in list processing, graph algorithms, VLSI design, and image processing, which were previously solved in ad hoc and often error-prone ways. The design and implementation of a prototype system, CACHET, for deriving incremental programs is also described.

About the Lecturer

Annie Liu is an assistant professor in the Computer Science Department at Indiana University. Her primary research interests are programming languages, compilers, and software systems. She is particularly interested in general and systematic approaches to improving the efficiency of computations.

Liu received a PhD in computer science from Cornell University in 1996. Liu is a member of IFIP WG2.1. She has served on the program committees of several international conferences, and she co-chairs the ACM SIGPLAN 1999 Workshop on Languages, Compilers, and Tools for Embedded Systems.


Monday June 28, 1999, 14:15-16:00 in Auditorium D4

Incrementalization: a general systematic approach to efficiency improvement.

Tuesday June 29, 1999, 14:15-16:00 in Auditorium D4

Optimizing loops and recursions using incrementalization.


  1. Y. A. Liu, Efficient computation via incremental computation. Technical Report TR 512, Computer Science Department, Indiana University, Bloomington, Indiana, July 1998.
  2. Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. In Proceedings of the 8th European Symposium on Programming, volume of 1576 of Lecture Notes in Computer Science, pages 288-305, Amsterdam, The Netherlands, March 22-24, 1999. Springer-Verlag.
  3. Y. A. Liu and S. D. Stoller. Loop optimization for aggregate array computations. In Proceedings of the IEEE 1998 International Conference on Computer Languages, pages 262-271, Chicago, Illinois, May 14-16, 1998. IEEE Computer Society Press.
  4. Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Transactions on Programming Languages and Systems, 20(3):546-585, May 1998.