ACM SIGPLAN Notices · 2007 · 13 citations · 12 references
ComputingComputer EngineeringComputer ScienceCompilersData StructuresProgramming LanguagesAbstract Syntax TreesCompiler ConstructionData-flow AnalysisFunctional ProgrammingIntermediate RepresentationType SystemsAbstract Syntax Tree Optimization
This paper presents an automatic deforestation system, stream fusion , based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and functions over nested lists, including list comprehensions. A distinguishing feature of the framework is its simplicity: by transforming list functions to expose their structure, intermediate values are eliminated by general purpose compiler optimisations. We have reimplemented the Haskell standard List library on top of our framework, providing stream fusion for Haskell lists. By allowing a wider range of functions to fuse, we see an increase in the number of occurrences of fusion in typical Haskell programs. We present benchmarks documenting time and space improvements.
12
The implementation of functional programming languages
Microprocessors and Microsystems · 1987 · 1.1K citations
Deforestation: transforming programs to eliminate trees
Philip Wadler · Theoretical Computer Science · 1990 · 707 citations
Andrew Gill, John Launchbury, Simon Jones · 1993 · 415 citations · Full text
Shortcut deforestation in calculational form
Akihiko Takano, Erik Meijer · 1995 · 165 citations
Natural Resources, Forestry, Environmental Impact Assessment +5