2001 · 184 citations · 19 references
ComputingComputer ScienceCompilersProgramming LanguagesTheory Of ComputationAbstract Syntax TreesCompiler ConstructionData-flow AnalysisType SystemsBottom-up Rewrite SystemsCode Generation By Rewrite RulesRewrite SystemsRewriting Systems
We describe a facility for improving optimization of Haskell programs using rewrite rules. Library authors can use rules to express domain-specific optimizations that the compiler cannot discover for itself. The compiler can also generate rules internally to propagate information obtained from automated analyses. The rewrite mechanism is fully implemented in the released Glasgow Haskell Compiler. Our system is very simple, but can be effective in optimizing real programs. We describe two practical applications involving short-cut deforestation, for lists and for rose trees, and document substantial performance improvements on a range of programs. 1 Introduction Optimising compilers perform program transformations that improve the efficiency of the program. However, a compiler can only use relatively shallow reasoning to guarantee the correctness of its optimisations. In contrast, the programmer has much deeper information about the program and its intended behaviour. For example, a programmer may know that
19
Koen Claessen, John Hughes · ACM SIGPLAN Notices · 2011 · 1K citations
Why Functional Programming Matters
John Hughes · The Computer Journal · 1989 · 739 citations · Full text
Andrew Gill, John Launchbury, Simon Jones · 1993 · 415 citations · Full text
Building program optimizers with rewriting strategies
Eelco Visser, Zine-el-Abidine Benaissa, Andrew Tolmach · 1998 · 251 citations · Full text