Previous Up Next

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.


Previous Up Next