Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <157-073-9834@kylheku.com> Newsgroups: comp.compilers Subject: Re: Best language for implementing compilers? Date: Tue, 12 Feb 2019 23:52:16 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 151 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <19-02-011@comp.compilers> References: <19-02-010@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="35040"; mail-complaints-to="abuse@iecc.com" Keywords: Lisp, history Posted-Date: 12 Feb 2019 19:00:16 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2163 On 2019-02-12, Costello, Roger L. wrote: > Kaz Kylheku wrote: > ------------------------------------------------- > Suppose we want to check whether we have an expression that is the binary > product of two binary sums, as in (* (+ a b) (+ c d)). > > Without pattern matching: > > (when (and (eq (car expr) '*) ;; starts with * > (consp (cdr expr)) ;; has an argument > (consp (cddr expr)) ;; has another argument > (null (cdddr expr)) ;; then the list ends > (consp (cadr expr)) ;; first arg is a compound > (eq (cadr expr) '+) ;; ... starting with a + > ... ;; etc > (do-whatever ...)) > > With very rudimentary pattern matching (simple destructuring): > > (destructuring-when (op1 (op2 a b) (op3 c d)) expr > (when (equal (list op1 op2 op3) '(* + +)) > (do-whatever ...))) > > With pattern matching: > > (when-match expr (* (+ ?a ?b) (+ ?c ?d)) > (do-whatever ...) ;; ?a ?b ... are in scope bound to subtrees > ...) > ------------------------------------------------- > Wow! > > That is a fantastic example. > > Are there programming languages that have the pattern matching capability > shown in Kaz's last example? Numerous libraries for Common Lisp, for instance, as well as Scheme (and Racket). Links to CL pattern matching libs: https://www.cliki.net/pattern%20matching Some of them are fairly advanced; they are N-th generation improvements over older work with better optimization. They are quite different from each other in their notations, and capabilities. For instance, some have unification. If we repeat a variable in the pattern match, the occurrences add a constraint that it has to match the same thing. Some have predicates like "optional", and "zero/one or more of". They can be divided into two main categories, syntactically: pattern matchers that express "match by code" and those that express "match by template". Match by code is something along these lines: (match-cases object (cons a b) (do-whatever a b) ;; matches (10 . 20), a = 10, b = 20 (list 1 2 a b) (do-whatever a b) ;; matches '(1 2 3 4); a = 3, ) Here, the patterns look like the *code* you write to construct the object, rather than the printed representation of the object (which I'm using in the comments). "Match by template" augments the printed representations of objects with the ability to insert variables. Some "match by code" systems exploit Lisp's backquote syntax to also provide "match by template" (for things that can be backquoted). To re-use the previous fantasy example: (match-cases object (list 1 2 a b) (do-whatever a b) ;; matches '(1 2 3 4); a = 3, `(1 2 ,a ,b) (do-whatever a b) ;; identical meaning ) It's still "match by code" since if we have a = 3 and b = 4, then the expression `(1 2 ,a ,b) constructs (1 2 3 4). But since we are using a backquote template, it's "match by template" also. > What programming language has the best pattern matching capability? Some purely functional languages have pattern matching that statically compiles to efficient code, particularly for cases that hinge on differences in type. Like if you have some type that is a union of other types: Foo := X a | Y b | Z c then you can do pattern matches on that to handle those cases, destructuring on the parameter. match obj in X a -> ... Y b -> ... Z c -> ... If obj is really a Foo, then these cases are exhaustive, and the compiler will check that. So proponents of these languages will point that and tout all the static typing, safety and efficiency. I'm from the Lisp camp myself, though; everything organic, wrapped in recycled parentheses. The grass is so vividly green on this side of the fence, that everything looks red when I look around. > Is the programming language with the best pattern matching capability the best > language for implementing compilers? I would hardly say that. For doing production compiler work, multi-paradigm is the way to go. Suppose that we somehow decide that the best pattern matching language is one that is purely functional. Inside a compiler, there are good opportunities for plain old imperative programming with mutable data. Lke, oh, backpatching labels when assembling instructions. Moreover, stateful OOP is also useful. Like for iterating over a graph (e.g. representing code blocks) to propagate data flow information. You don't want to be sitting there translating every useful algorithm into a purely functional form with tail calls instead of recursion, new data always constructed instead of mutation and so on. > /Roger > [Why do you think we're talking about ML? It has matching as a > primitive. I don't recall any lisp-ish languages with built in tree > matchers but it's easy enough to do that it's often an exercise in the > introductory programming class. -John] Funny story; some 16 years ago I made a C++ library of object providing Lisp data types (with serialization to S-exps and back, network socket communication and such. Eventually an eval was added and it became programmable). Anyway, this was used in an embedded mail transport project. I used it for storing persistent configurations, and some inter-process communication (back-end <--> UI). Another programmer was working on the IMAP4 interface of this thing and noticed, hey, Kaz's Lisp stuff looks exactly like Lisp syntax used in the IMAP4 protocol! So he just used it for parsing IMAP4, including the rudimentary pattern matching to classify IMAP4 responses. Boy, was I surprised. -- TXR Programming Lanuage: http://nongnu.org/txr Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1