Skip to topic | Skip to bottom


EelcoVisser.SimplifyingTheSimplifierr1.3 - 28 Apr 2005 - 22:53 -

Start of topic | Skip to actions

Not Found

The requested URL /twiki/bin/view/Stratego/SimplifyingTheSimplifier was not found on this server.

Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument? to handle the request.

Project Description

The simplifier of the GHC performs optimizations by applying a number of small transformation rules iteratively to the abstract syntax tree of a program. The simplifier is implemented as one big Haskell module. The implementation is not modular and is difficult to change. Small changes lead to a big difference in optimization behaviour. It is not possible to make different versions of the simplifier re-using the same basic code. In addition, GHC has introduced user-definable optimization rules that can be specified by the user as pragmas in the program. The design of the simplifier, however, suggests a modular set-up that is based on a number of separate transformation rules that are combined into one transformation. (source: Simon Peyton Jones)

This suggests that the Stratego approach of defining transformations as a set of transformation rules combined with a strategy that applies these rules would be advantageous to the implementation of the simplifier. The goal of this project is to develop a modular implementation of the GHC simplifier in Stratego. The goal is not to just replicate the GHC simplifier, but to explore the possibilities of Stratego in implementing it, possibly leading to a family of simplifiers. The result should be evaluated against the following questions:

  • Correctness
    • Is it possible to replicate the behaviour of the simplier?

  • Is the result a readable specification of simplification?

  • Modularity: Is it possible to
    • Create different configurations or strategies based on the same set of rules
    • Vary the rules used?
    • Vary the command-line options (e.g., inlining heuristics) to simplifier?
    • Add user-defined optimization rules

  • Performance
    • What is complexity of the simplifier?
    • Does it scale up?


Implementation of optimization in the Glasgow Haskell Compiler

  • Implementation of the simplifier: see the GHC source distribution

Helium compiler

  • Ask Arjan van IJzendoorn


  • General Stratego knowledge. See Stratego:StrategoPublications

Implementation of optimizers in Stratego

ATerm Exchange Format

  • Efficient Annotated Terms. M.G.J. van den Brand, H.A. de Jong, P. Klint, and P.A. Olivier. Software - Practice & Experience, 30:259-291, 2000.


Set up Infrastructure

  • Use the front-end of Arjan van IJzendoorn's Helium compiler
  • Use Daan Leijen's back-end (compiler to byte-code)
  • Make a translation from Core language to ATerm Format
    • Write after front-end
    • Read before back-end

Set up Benchmarks

  • Collect set of programs to optimize
  • Automate the running and measuring of performance figures
  • Also measure compile time

Implement Simplifier

  • Study the implementation of the simplifier in Haskell
  • Implement the rules as separate rewrite rules
  • Define strategies to apply the rules
  • Experiment with different configurations of the simplifier
    • Measure performance of compiled programs and compiler
  • Add additional optimizations


  • Discuss related work
  • Describe the design and implementation of the simplifier
  • Evaluate advantages and disadvantages of using Stratego

-- EelcoVisser - 27 Nov 2001

Edit | Attach | Printable | Raw | More topic actions
Revisions: | r1.3 | > | r1.2 | > | r1.1 | Page history | Backlinks
You are here: EelcoVisser > SimplifyingTheSimplifier

to top

Copyright © 2003-2018, Software Engineering Research Group, Delft University of Technology, The Netherlands