Sandro Stucki

Fold-Based Fusion as a Library: a Generative Programming Pearl

Manohar Jonnalagedda and Sandro Stucki. In Proceedings of the 6th ACM SIGPLAN Symposium on Scala (Scala '15), pp. 41–50, ACM, 2015.


Fusion is a program optimisation technique commonly implemented using special-purpose compiler support. In this paper, we present an alternative approach, implementing fold-based fusion as a standalone library. We use staging to compose operations on folds; the operations are partially evaluated away, yielding code that does not construct unnecessary intermediate data structures. The technique extends to partitioning and grouping of collections.