Warm Fusion Deriving Build Catas From Recursive Definitions

Program-Transformation.Org: The Program Transformation Wiki
JohnLaunchbury? and TimSheard. Warm Fusion: Deriving Build-Catas from Recursive Definitions. Conference Record 7th ACM SIGPLAN/SIGARCH Int.Conf. on Functional Programming Languages and Computer Architecture, (FPCA'95), La Jolla, San Diego, CA, USA, 25--28 June 1995, ACM Press, New York, 314--323", 1995.


Program fusion is the process whereby separate pieces of code are fused into a single piece, typically transforming a multi-pass algorithm into a single pass. Recent work has made it clear that the process is especially successful if the loops or recursions are expressed using catamorphisms (e.g.foldr) and constructor-abstraction (e.g. build). In this paper we show how to transform recursive programs into this form automatically, thus enabling the fusion transformation to be applied more easily than before.

The algorithm in this paper has been implemented in a couple of systems including HSX (WarmFusionInStratego).

CategoryPaper | -- EelcoVisser - 14 May 2001