Optimizing Pattern Matching by Program Transformation
Émilie Balland, Pierre‐Etienne Moreau · 2006
The compilation of pattern matching constructs is crucial to the efficient implementation of functional languages like ML, Caml, or Haskell as well as rewrite rule based languages such as ASF+SDF, ELAN, Maude, or Stratego for example. Until now, the classical approach was to compute an (optimized) automaton before generating, in a straight-forward way, the corresponding implementation code. Optimizations such as tests-sharing are encoded in the construction of the automaton. While efficient, this leads to algorithms which are often complex and difficult to extend and to maintain. In this paper we present a new compilation and optimization method based on program transformation. The principle is to separate the compilation of pattern matching from the optimization, in order to improve modularity and make extensions simpler. In a first step, the patterns are compiled using a simple, but safe algorithm. Then, optimizations are directly performed on the generated code, using transformation rules. Separating optimization from compilation eases the compilation of extensions, such as new equational theories, or the addition of or-patterns for example. Another contribution of this paper is to define a set of rules which defines the optimization, to show their correction as well as their effectiveness on real programs. The presented approach has been implemented and applied to Tom, a language extension which adds pattern-matching facilities to C and Java.