Pugh, William W.2007-04-232007-04-231988-08http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-936https://hdl.handle.net/1813/6776Incremental computation is generally thought of as the technique of efficiently updating the result of a computation when the input is changed. This idea is used in doing semantic checking in programming environments, document formatting in WYSIWYG editors and other applications. More generally, incremental computation is the technique of efficiently applying a function to a series of similar inputs. Much of the previous work on incremental computation has centered on incremental attribute grammar and incremental dependency graph evaluation schemes, but these techniques are only suitable for certain applications. This thesis examines an alternative method for providing incremental computation. Our results provide practical methods that can be used for applications such as theorem provers for which attribute grammars are unusable. Even for those problems for which attribute grammars are best suited, our methods perform almost as well as attribute grammars. We describe an incremental evaluator for functional programs that makes use of function caching. Function caching, or memoising, allows reuse of solutions to problems that were solved previously. We examine how function caching can be effectively used when solving problems that are similar to problems that were solved previously. In order for function caching to provide incremental evaluation, two similar problems must be solved by decomposing them into sub-problems in such a way that they share many common sub-problems. We formalize and quantify this idea with the notion of a stable decomposition, and we present data structures for representing sets and sequences that have stable decompositions. We solve several problems related to the efficient implementation of function caching. To perform function caching efficiently, one must be able to determine if two values are equal in constant time and perform updates applicatively. The data structures we present for sets and sequences support these features. This was previously an open problem for representations that also supported efficient updates. We also examine how to calculate hash keys and perform fast equality tests for S-expressions and how to determine what to purge from a function cache when it is full. We report benchmarks that show our function caching implementation produces significant speed-ups in complex programs such as incremental theorem provers.8406355 bytes2469686 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report