**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.

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

Annie Liu