4 ms·
Simon Peyton Jones's "The implementation of functional programming languages" has a chapter on the "Efficient compilation of pattern matching" (chapter 5 by Phi
by i_don_t_know 7mo ago
Simon Peyton Jones's "The implementation of functional programming languages" has a chapter on the "Efficient compilation of pattern matching" (chapter 5 by Philip Wadler).
https://simon.peytonjones.org/assets/pdfs/slpj-book-1987-2up-searchable.pdf https://simon.peytonjones.org/assets/pdfs/slpj-book-1987-2up...
- rwmj 7mo agoAlso Xavier Leroy's ZINC paper (https://xavierleroy.org/bibrefs/Leroy-ZINC.html https://xavierleroy.org/bibrefs/Leroy-ZINC.html) although I believe that's no longer the implementation used by OCaml since it got replaced by an even more efficient one.
- dklsf 7mo agoProbably Compiling Pattern Matching to Good Decision Trees (by Luc Maranget) is the scheme used by OCaml (http://moscova.inria.fr/%7Emaranget/papers/ml05e-maranget.pdf http://moscova.inria.fr/%7Emaranget/papers/ml05e-maranget.pd...). It explains how to minimize the decisions trees you obtain from a match statement, so you gain a ton of efficiency over a naive implementation, especially for large, multi-column matches.