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.

Revision: r1.2 - 03 Jan 2002 - 10:20 - EelcoVisser

Copyright © 1999-2020 by the contributing authors.
All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback