CACHET: An interactive, incremental-attribution-based program transformation system for deriving incremental programs

This paper describes the design and implementation of an interactive, incremental-attribution-based program transformation system, CACHET, that derives incremental programs from non-incremental programs written in a functional language. CACHET is designed as a programming environment and implemented using a language-based editor generator, the Synthesizer Generator, with extensions that support complex transformations. Transformations directly manipulate the program tree and take into consideration information obtained from program analyses. Program analyses are performed via attribute evaluation, which is done incrementally as transformations change the program tree. The overall approach also explores a general framework for describing dynamic program semantics using annotations, which allows interleaving transformations with external input, such as user input. Designing CACHET as a programming environment also facilitates the integration of program derivation and validation with interactive editing, compiling, debugging, and execution.