CACHET: prototype implementations of incrementalization and powerful optimization


CACHET was originally built as a prototype system for incrementalization: given (1) a program p that takes certain input and produces certain output and (2) an input change operation + that takes an old input x and a change parameter y and returns a new input, it derives an incremental program p' that computes p(x+y) efficiently by using p(x). It was first developed as a semi-automatic transformation system, but its transformations for incrementalization can be carried out in a systematic manner, where the appropriate transformation for each next step in incrementalization is automatically determined and uniquely indicated. Its interactive nature allowed us to experiment with many other possible program transformations, not just incrementalization, so that we could understand them and eventually use them for incrementalization.

CACHET continued built on the original interactive systemfor incrementalization to include automated incrementalization for recursive functions and recursive data structures, loop optimization of aggregate array computations, and efficient dead-code analysis (a.k.a. slicing) on recursive data. These allowed us to use CACHET for many more applications. All the interfaces, input and output syntax, semantic analysis, and most transformations are implemented using the Synthesizer Generator. Noncircular analyses are implemented using attribute equations, and powerful fixed-point analyses are implemented in STk, a Scheme-based scripting language. Parts of the automatic transformations for arithmetic and booleans operations use also Omega and MONA.

Besides research, CACHET has been used in teaching several graduate courses on program transformation and program anlaysis.

After CACHET, we continued to develop new powerful optimizations, for implementing sets, rules, and objects, using incrementalization. These are implemented in Python.


[project description] [selected publications with an overview] [software systems on Annie Liu's homepage]
Annie Liu