Using rewriting to add domain-specific optimisations to a compiler.

Recently I've added to the Glasgow Haskell Compiler the ability for the programmer to specify algebraic laws as part of the source code of a library. These laws are oriented as rewrite rules, and are used by the compiler to "improve" the code generated for clients of the library. The hope is to be able to perform optimisations that are well beyond the reach of a vanilla compiler. The plan was to implement the simplest thing possible, and see if it proves useful, and if so which inadequacy is most inconvenient in practice.

I say "improve" in quotes because the programmer has the responsibility not only of making sure that the laws are true, but also that they are terminating, and that they improve efficiency. Strangely enough, these traditional concerns of the term-rewriting community don't seem to have been a big issue in practice. Much more important seems to be a raft of issues concerning inlining.

I'll describe what we've done, explain what lessons we learned, and hope to have an animated discussion about what could be done better.

LS Home page or Talks in 1999/2000