Simplifying The Simplifier

Stratego -- Strategies for Program Transformation
Alan van Dam. Simplifying the Simplifier. HsOpt: a modular, rewrite rule based simplifier for the Helium compiler, a non-strict functional compiler. Institute of Information and Computing Sciences, Utrecht University, The Netherlands Master's thesis INF/SCR-03-25, July 7, 2003. (pdf)


Modern compilers optimize code during the compilation process. The goal of the optimizations is to obtain a program that is semantically equivalent, executes faster and uses less memory. The Glasgow Haskell Compiler also uses a simplifier. This simplifier is not modular and difficult to extend. The HsOpt simplifier is a 'simplified' GHC simplifier. The HsOpt simplifier is modular and relatively easy to extend. HsOpt is based on the paradigm of correctness preserving rewrite rules. The transformations can be applied separately. HsOpt interacts with the Helium compiler, a compiler for a large subset of Haskell. Helium uses a naive pattern matcher compiler which results in straightforward intermediate Core code. HsOpt simplifies most of the straightforward code. The result is Core code that could have been produced by an intelligent pattern match compiler. The simplified programs execute 10-15% faster and uses 0-25% less memory.