3 ms·
Compiling Pattern Matching
- pfdietz 3y agoSomething as simple as "is this string in this fixed set of strings" benefits from compile-time optimization of the matching algorithm. This is a place where Lisp's macros really shine, as they enable this kind of optimization to be performed at macro expansion time, without the need for preprocessing or matching algorithms built into the compiler itself.
- nsm 3y agoI'm not sure how efficiently it compiles, but Racket's match form is implemented using macros and is stunningly powerful! https://docs.racket-lang.org/reference/match.html https://docs.racket-lang.org/reference/match.html
- ReleaseCandidat 3y agoThe paper (IIRC) https://arxiv.org/abs/1106.2578 https://arxiv.org/abs/1106.2578 https://arxiv.org/pdf/1106.2578.pdf https://arxiv.org/pdf/1106.2578.pdf
- kazinator 3y agoI wrote a purely macro-based implementation of pattern matching for TXR Lisp. It's documented over three consecutive chapters: https://www.nongnu.org/txr/txr-manpage.html#N-5C9CED75 https://www.nongnu.org/txr/txr-manpage.html#N-5C9CED75 (Structural Pattern Matching) https://www.nongnu.org/txr/txr-manpage.html#N-B5350C53 https://www.nongnu.org/txr/txr-manpage.html#N-B5350C53 (Pattern-Matching Notation) https://www.nongnu.org/txr/txr-manpage.html#N-CD6130ED https://www.nongnu.org/txr/txr-manpage.html#N-CD6130ED (Pattern-Matching Macros) It's implemented in one file: https://www.kylheku.com/cgit/txr/tree/stdlib/match.tl https://www.kylheku.com/cgit/txr/tree/stdlib/match.tl Starting with the second definition of the function non-triv-pat-p (the real definition which replaces the temporary stub one), the module starts to eat its own dogfood by using its own pattern matching. That function, for instance, decides whether a pattern is "trivial" or not, using pattern matching itself on the pattern matching notation. The string quasiliteral pattern's expansion relies heavily on pattern matching, also.
- tmtvl 3y agoYep, trivia* for instance is very impressive in performance, especially considering you can switch optimizers. * <https://github.com/guicho271828/trivia https://github.com/guicho271828/trivia>
- pfdietz 3y agoI've used it. :) https://github.com/guicho271828/trivia/issues/108 https://github.com/guicho271828/trivia/issues/108
- agumonkey 3y agoIIRC luc maranget's paper was also a basis to clojure/script core.match ps: checked https://github.com/clojure/core.match/wiki/References https://github.com/clojure/core.match/wiki/References
- ReleaseCandidat 3y agoA (IMHO) good and easy to read introduction is Wadler's "EFFICIENT COMPILATION OF PATTERN-MATCHING", chapter 5 of "The Implementation of Functional Programming Languages" https://simon.peytonjones.org/assets/pdfs/slpj-book-1987-2up-searchable.pdf https://simon.peytonjones.org/assets/pdfs/slpj-book-1987-2up... - actually I can recommend the whole book as an instruction to (the interesting stuff of) writing a compiler for a functional language. It also contains an introduction to the lambda calculus.
- burakemir 3y agoIf you are interested, I wrote a thesis in 2007 on "object-oriented pattern matching" available at EPFL which "formalizes" pattern matching in Scala. It did not get into path-dependent types and does not have mechanized proofs, but has a discussion of optimizing translation to lower level code, exhaustiveness checks and user definable patterns (extractors). Like the author of the article, I found Maranget's matrix representation a great basis. This is because algebraic data types come in the form of "sum of products" (or enums with records) and once you have tested one level you want to expand the components of the tuple pattern (columns) and you deal with multiple cases (rows). I won't claim my thesis is the most readable. I think I would do the presentation very differently today, but going back one's theis topic seems to be one of these impossible things in life if you don't work in academia.
- JNRowe 3y agoLink: https://infoscience.epfl.ch/record/109881?ln=en https://infoscience.epfl.ch/record/109881?ln=en
- herodotus 3y agoFun to see. When I worked on the implementation of Rod Burstall’s HOPE language (https://dl.acm.org/doi/pdf/10.1145/800087.802799 https://dl.acm.org/doi/pdf/10.1145/800087.802799) in 1979 I “invented” pattern compilation and implemented it (in POP-2) for the HOPE interpreter. HOPE patterns were of course way simpler than Haskell patterns, so my algorithm was pretty straightforward. From the math point of view, any function or arity n that has a parameter whose possible actual values belong to a finite discrete set can be replaced by a family of functions of arity n-1.
- 082349872349872 3y agoSo, I know of both HOPE and Charity; has "faith" ever been a programming language?
- kevindamm 3y agoI don't think so, but a lot of promises...
- amboo7 3y agohttps://www.cs.tufts.edu/~nr/cs257/archive/norman-ramsey/match.pdf https://www.cs.tufts.edu/~nr/cs257/archive/norman-ramsey/mat... by the current Microsoft CTO
- contificate 3y agoThis is my blog, thanks for posting - never expected to see such engagement.
- autumn-antlers 3y agoThanks for writing! Love the composition of your site pages btw. I've got the same "|"-seperated nav bar on my WIP branch. Cleaner then my current branch, but I'm trying to compromise between sparse-ness and something with more "vibes". If only I was in the habit of actually writing anything-- congats!
- contificate 3y agoThank you very much! Your website's landing page is very clean.