Path: csiph.com!eternal-september.org!feeder.eternal-september.org!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 16:45:10 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 55
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <19-02-009@comp.compilers>
References: <19-02-002@comp.compilers> <19-02-004@comp.compilers> <19-02-006@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="35929"; mail-complaints-to="abuse@iecc.com"
Keywords: design, practice
Posted-Date: 12 Feb 2019 11:47:46 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:2161

On 2019-02-11, Bart <bc@freeuk.com> wrote:
> On 08/02/2019 23:36, George Neuner wrote:
>> On Fri, 8 Feb 2019 12:20:18 +0000, "Costello, Roger L."
>> <costello@mitre.org> wrote:
>>
>>> What is it about ML that makes it such a good language for implementing
>>> compilers?
>>
>> Compiling involves a lot of pattern matching, and pattern matching is
>> a native feature of ML.
>
> You mean for tokenising and parsing? That would be a small part of
> compilation (the easy bit, in my view), although it seems to be a
> preoccupation of this group.

I think George is talking about structural pattern matching:
expressing the handling of cases of various shapes of data using
a notation which resembles those shapes.

Opportunities for pattern-matching occur pretty much in any compiler
pass: various tree-to-tree transformations use pattern matching.
Target code generation, peephole optimizations and such can use it.

E.g. 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
   ...)

Pattern matching can typically handle objects other than just lists.
Vectors, data structures, tuples, dictionaries ...

Some pattern matchers have support for arbitrary Boolean predicates,
like matching only when the third element of the list in foo.bar is an
even integer.