Compiling pattern matching to good decision trees

ABSTRACT

We address the issue of compiling ML pattern matching to compact and efficient decisions trees. Traditionally, compilation to decision trees is optimized by (1) implementing decision trees as dags with maximal sharing; (2) guiding a simple compiler with heuristics. We first design new heuristics that are inspired by necessity, a concept from lazy pattern matching that we rephrase in terms of decision tree semantics. Thereby, we simplify previous semantic frameworks and demonstrate a straightforward connection between necessity and decision tree runtime efficiency. We complete our study by experiments, showing that optimizing compilation to decision trees is competitive with the optimizing match compiler of Le Fessant and Maranget (2001).

REFERENCES

• 1: Lennart Augustsson, Compiling pattern matching, Proc. of a conference on Functional programming languages and computer architecture, p.368-381, January 1985, Nancy, France
• 2: Marianne Baudinet and David B. MacQueen. Tree pattern matching for ML. http://www.smlnj.org/compiler-notes/85-note-baudinet.ps, 1985.
• 3: Coq. The Coq proof assistant (v. 8.1). By the Coq team, http://coq.inria.fr/, 2007.
• 4: Jean-Christophe Filliâtre. The Why verification tool (v. 2.13). http://why.lri.fr/, 2008.
• 5: Jean-Christophe Filliâtre , Sylvain Conchon, Type-safe modular hash-consing, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159876.1159880]
• 6: Gérard Huet and Jean-Jacques Lévy. Call by need computations in non-ambiguous linear term rewriting systems. In Jean-Louis Lassez and Gordon D. Plotkin, editors, Computational Logic, Essays in Honor of Alan Robinson. The MIT Press, 1991.
• 7: Alain Laville, Implementation of Lazy Pattern Matching Algorithms, Proceedings of the 2nd European Symposium on Programming, p.298-316, March 21-24, 1988
• 8: Fabrice Le Fessant , Luc Maranget, Optimizing pattern matching, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 9: Xavier Leroy, Damien Doligez, Jacques Garrigue, Jérôme Vouillon, and Didier Rémy. The Objective Caml language (v. 3.10). http://caml.inria.fr, 2007.
• 10: Luc Maranget. Warnings for pattern matching. Journal of Functional Programming, 17: 387--422, May 2007.
• 11: Luc Maranget, Compiling lazy pattern matching, Proceedings of the 1992 ACM conference on LISP and functional programming, p.21-31, June 22-24, 1992, San Francisco, California, United States
• 12: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 13: George Necula, Scott McPeak, Westley Weimer, Ben Liblit, Matt Harren, Ramond To, and Aman Bhargava. Cil - infrastructure for C program analysis and transformation (v. 1.3.6). http://manju.cs.berkeley.edu/cil/, 2007.
• 14: Nadia Nedjah , Luiza de Macedo Mourelle, Optimal Adaptive Pattern Matching, Proceedings of the 15th international conference on Industrial and engineering applications of artificial intelligence and expert systems: developments in applied artificial intelligence, p.768-779, June 17-20, 2002
• 15: Scott Owens. A sound semantics for OCaml-Light. In European Symphosium On Programming, 2008. LNCS 4960.
• 16: Mikael Pettersson, A Term Pattern-Match Compiler Inspired by Finite Automata Theory, Proceedings of the 4th International Conference on Compiler Construction, p.258-270, October 05-07, 1992
• 17: Gordon D. Plotkin. LCF considered as a programming language. Theoretical Computer Science, 5: 225--255, December 1977.
• 18: Laurence Puel , Ascander Suarez, Compiling pattern matching by term decomposition, Proceedings of the 1990 ACM conference on LISP and functional programming, p.273-281, June 27-29, 1990, Nice, France [doi>10.1145/91556.91670]
• 19: Kevin Scott , Norman Ramsey, When Do Match-compilation Heuristics Matter?, University of Virginia, Charlottesville, VA, 2000
• 20: R. C. Sekar , R. Ramesh , I. V. Ramakrishnan, Adaptive Pattern Matching, SIAM Journal on Computing, v.24 n.6, p.1207-1234, Dec. 1995 [doi>10.1137/S0097539793246252]
• 21: Peter Sestoft. ML pattern matching compilation and partial evaluation. In Dagstuhl Seminar on Partial Evaluation. Springer-Verlag, 1996. LNCS 1110.
• 22: Don Syme , Gregory Neverov , James Margetson, Extensible pattern matching via a lightweight language extension, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 23: Terese. Term Rewriting Systems. Cambridge University Press, 2003. Terese is Marc Bezem, Jan Willem Klop and Roel de Vrier.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns

General Terms:
Design, Performance

Keywords:
decision trees, heuristics, match compilers