Re: Best language for implementing compilers?

From	Kaz Kylheku <157-073-9834@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: Best language for implementing compilers?
Date	2019-02-12 16:45 +0000
Organization	Aioe.org NNTP Server
Message-ID	<19-02-009@comp.compilers> (permalink)
References	<19-02-002@comp.compilers> <19-02-004@comp.compilers> <19-02-006@comp.compilers>

Show all headers | View raw

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.

Thread

Best language for implementing compilers? "Costello, Roger L." <costello@mitre.org> - 2019-02-08 12:20 +0000
  Re: Best language for implementing compilers? Nala Ginrut <nalaginrut@gmail.com> - 2019-02-09 00:27 +0800
  Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-02-08 18:36 -0500
    Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-02-11 12:59 +0000
      Re: Best language for implementing compilers? drb@ihatespam.msu.edu (Dennis Boone) - 2019-02-12 09:38 -0600
        Re: Best language for implementing compilers? drb@ihatespam.msu.edu (Dennis Boone) - 2019-02-19 11:22 -0500
          Re: Best language for implementing compilers? arnold@skeeve.com (Aharon Robbins) - 2019-02-20 11:48 +0000
      Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-02-12 16:45 +0000
      Re: Best language for implementing compilers? mertesthomas@gmail.com - 2019-03-09 01:47 -0500
        Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-09 10:14 +0100
          Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-09 22:47 -0500
          Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-03-10 05:40 +0000
        Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-09 12:34 +0000
        Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-09 22:57 -0500
          Re: Best language for implementing compilers? Kaz Kylheku <157-073-9834@kylheku.com> - 2019-03-10 05:48 +0000
      Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-10 04:13 -0700
        Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-10 15:33 +0000
          Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-11 10:49 -0700
            Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-12 06:54 +0100
              Re: Best language for implementing compilers? Bart <bc@freeuk.com> - 2019-03-13 01:50 +0000
        Re: Best language for implementing compilers? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-03-10 16:13 +0100
          Re: Best language for implementing compilers? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-03-11 10:06 -0700
        Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-10 18:23 -0400
        Re: Best language for implementing compilers? George Neuner <gneuner2@comcast.net> - 2019-03-10 18:58 -0400
  Re: Best language for implementing compilers? "Robin Vowels" <robin51@dodo.com.au> - 2019-02-09 19:58 +1100
  Best language for implementing compilers? David Lovemore <davidlovemore@gmail.com> - 2019-02-12 03:28 -0800
  Re: Best language for implementing compilers? mertesthomas@gmail.com - 2019-03-12 10:40 -0700

csiph-web