9 Conclusion
This paper contribution is twofold. First, we propose
an improvement on the classical technique of compiling
pattern-matching expressions into backtracking automata, a technique
that has remained virtually the same for about 15 years. Our
improvements yield automata which run faster, thereby alleviating
the disadvantage of backtracking automata in practical cases. Moreover
the very structure of the produced automata is not altered and hence
the highly desirable property that output size is linear in the input
size is preserved. As a second contribution, we propose a technique
for efficiently compiling or-patterns with variables, still preserving
the linearity of output size. Using or-patterns in place of
“catch-all” wild-cards results in more robust programs, while using
one clause with a or-pattern in place of several clauses with
identical actions results in more compact, sometime clearer, programs.
ML programmers can now enjoy these benefits, without being afraid of
degraded runtime efficiency or code size explosion.
We would have wished to make a clear statement on
comparing bactracking automata and decision trees.
However, sophisticated compilation techniques exist that
minimize the drawbacks of both approaches.
Those are our techniques for backtracking automata, and
hash-consing and column optimizations for decision trees.
In the absence of a practical comparison of full-fleged algorithms,
choosing one technique or the other reflects one's commitment
to guaranteed code size or guaranteed runtime performance.