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.
A snapshot of interactive incrementalization applied to a sorting program (a middle point).
Snapshots of automated incrementalization applied to hardware design for non-restoring binary integer square root (a sequence of key points from beginning to end).
A snapshot of automatic loop optimization for aggregate array computations applied to an image processing algorithm (the end point).
A snapshot of efficient dead-code analysis on recursive data applied to a demo program (the end point).
After CACHET, we continued to develop new powerful optimizations, for implementing sets, rules, and objects, using incrementalization. These are implemented in Python.
