Re: Best language for implementing compilers?

On 2019-02-12, Costello, Roger L. <costello@mitre.org> 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

Return to the comp.compilers page.
Search the comp.compilers archives again.