Incremental computation is the technique of efficiently maintaining computed information about a changing object. This idea is used in doing semantic checking in programming environments, spreadsheets, document formatting in WYSIWYG editors and many other applications. Simply recomputing the information from scratch after each change is often too inefficient. Writing explicitly incremental algorithms that describe how to update the computed information in response to changes is difficult and error-prone. Incremental evaluators, given a computation to perform, automatically figure out how to correctly and efficiently update their output when their input changes. Past work in incremental evaluators has been targeted primarily at helping to automate the construction of programming environments that perform such activities as type checking and code generation. The techniques used are unsuitable for many of the problems associated with more advanced programming environments that use concepts such as inferential or transformational programming, program verification and other semantically-rich concepts. Previous work helped to lay the ground work for a new paradigm of incremental evaluation that shows promise of being widely useful for such problems. The goal of this project is to continue the development of that research and to incorporate those ideas into useful tools so that these ideas and tools can be used by the research community to assist in the development and exploration of advanced programming environments.
