Path: utzoo!utgpu!watmath!clyde!ima!compilers-sender From: chase@orc.olivetti.com (David Chase) Newsgroups: comp.compilers Subject: re: Pattern Languages Message-ID: <2877@ima.ima.isc.com> Date: 9 Nov 88 18:59:42 GMT Sender: compilers-sender@ima.ima.isc.com Reply-To: David Chase Lines: 40 Approved: compilers@ima.UUCP 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. David -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU Plausible paths are { decvax | harvard | yale | bbn}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request