re: Pattern Languages

David Chase <>
Wed, 09 Nov 88 10:59:42 -0800

          From comp.compilers

Related articles
re: Pattern Languages (David Chase) (1988-11-09)
| List of all articles for this month |

From: David Chase <>
Date: Wed, 09 Nov 88 10:59:42 -0800

It's hard to get a sense of what is really being asked, so
I'll provide multiple pointers to stuff that sounds like it might
answer questions.

One interesting paper (in a moderately interesting book) is
"Compiling Pattern Matching" by Lennart Augustsson in
Functional Programming Languages and Computer Architecture 1985
(Springer-Verlag LNCS #201). Some languages (ML and Miranda, I
believe) contain a selection by pattern match; Augustsson talks
about compiling that into something efficient. This paper also
contains pointers to other work (by Augustsson and by Cardelli,
I believe).

Michael O'Donnell had been beating on "Equational Programming"
for some time and wrote a book on the subject in 1985 (Equational Logic
as a Programming Language). His "interpreters" work by successively
pattern-matching and rewriting a "string". I have heard that the
performance of his system is really quite reasonable for certain
applications (I wouldn't use it for ray-tracing). That book also
contains a number of pointers to other work (Kron, Hoffmann and O'Donnell,
Huet and Levy, e.g.). The book is worth reading to get a sense of
what can be done (fairly well, as opposed to in theory) by a
rewriting system.

Gyula Mago at UNC-Chapel Hill has been working on an "FFP machine"
(it may have a new name by now) that was supposed to operate by
(massively parallelized) string rewriting.

You could always use operator-precedence parsing for expressions and
introduce new operators as you went. I played with this once in an
interpreter -- it works, but it has a real air of ad-hockery. I wouldn't
recommend this for anything real without thinking about it for a
while first.


Post a followup to this message

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