Compiling Pattern Matching to good Decision Trees
đź“ś Abstract
We address the issue of compiling ML pattern matching to 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 notion from lazy pattern matching that we rephrase in terms of decision tree semantics. Thereby, we simplify previous semantical frameworks and demonstrate a direct connection between necessity and decision tree runtime efficiency. We complete our study by experiments, showing that optimized compilation to decision trees is competitive. We also suggest some heuristics precisely.
✨ Summary
Summary
The paper studies compilation of ML pattern matching into decision trees. Its central observation is that the order in which subject-value subterms are tested strongly affects both generated-code size and runtime path length. The paper formalizes necessity for strict ML matching: a pattern-matrix column is needed for a clause when every decision tree produced by the compiler must test that column on every path reaching the clause. This characterization leads to three heuristics: needed columns (n), needed prefixes (p), and constructor prefixes (q). It also evaluates earlier heuristics based on first-row relevance, default size, branching factor, constructor arity, leaf edges, and decomposed-row counts.
The compilation scheme uses pattern matrices, constructor specialization, default decomposition, and a simple decision-tree language. Correctness is established for all choices of the column-selection heuristic. The paper argues that maximal sharing—representing decision trees as dags—is essential for controlling code size. Experiments over 54 OCaml pattern matches show that necessity-oriented heuristics, especially q, p, and n, generally reduce average path length; the combined heuristic pba is reported as the best overall combination in the tested data, while qba is recommended when usefulness analysis is to be avoided. The authors also report integration into the OCaml compiler and measurable runtime improvements for a PCF bytecode interpreter, although whole-program binary-size effects were usually small. (cs.tufts.edu)
Subsequent concrete uses include the LLVM backend’s pattern-matching implementation, whose documentation states that its decision-tree compiler is heavily based on Maranget’s algorithm and adapts the paper’s q, b, a, and L heuristics. (github.com) The paper is also cited in later research on generalized algebraic data types and pattern matching, including GADTs meet their match and The Algebra of Patterns. (people.cs.kuleuven.be) These references document continued use of its matrix-decomposition and decision-tree framework in compiler and programming-language research; they do not by themselves establish that every cited system adopted the complete algorithm.