Warm Fusion Transformation

Warm fusion is a program transformation technique for deforesting functional programs developed by John Launchbury and Tim Sheard. Warm fusion works by the cata/build fusion rule:

   cata(f1,...,fn)(build(g)) = g f1 ... fn

Here g is a function that produces a `virtual` data structure that is parameterized with data constructors. The build function instantiantiates such a virtual data structure with actual constructors. Since cata replaces constructors with functions, application of a cata to a build can as well be replaced with the instantation of the virtual data structure with those functions.

Application of warm fusion is trivial once functions use cata and build to deal with data structures; instead of explicitly recursive functions to destruct and construct such data structures. Since programming with these operators is rather involved, it is nicer to derive the build/cata forms of functions automatically. That is what the warm fusion transformation of Launchbury and Sheard is about.

The warm fusion algorithm has been implemented in StrategoLanguage by PatriciaJohann and EelcoVisser. The implementation is described in a journal article and a technical report (WarmFusionInStratego). The Stratego implementation of warm fusion is distributed in the HSX package.