Incremental computation aims to compute more efficiently on changed input
by reusing previously computed results.
We give a high-level overview of works on incremental computation,
and highlight the essence underlying all of them, which we call
incrementalization—the discrete counterpart of differentiation in calculus.
We review the gist of a systematic method for incrementalization,
and a systematic method centered around it, called
Iterate-Incrementalize-Implement,
for program design and optimization, as well as algorithm design and
optimization.
At a meta-level, with historical contexts and for future directions,
we stress the power of high-level data, control, and module abstractions
in developing new and better algorithms and programs as well as their precise
complexities.

Y. Annie Liu is Professor of Computer Science at Stony Brook University. Her primary research is in languages and algorithms, especially on systematic methods for design and optimization. The methods are centered around incrementalization—the discrete counterpart of differentiation in calculus. Besides research and service, she also enjoys teaching. She has taught in a wide range of Computer Science areas, and presented over 100 conference and invited talks worldwide. She received her BS from Peking University, MEng from Tsinghua University, and PhD from Cornell University, all in Computer Science.

Annie Liu’s Design and Analysis Research Laboratory has projects in modeling and specification, analysis and verification, design and optimization, code generation, and testing. These projects are for optimizing compilers, interactive environments, real-time and embedded systems, database systems, semantic Web, distributed systems, big data analysis, security, and more. Her awards include a State University of New York Chancellor’s Award for Excellence in Scholarship and Creative Activities.