Re: Tree Pattern Matching

Maarten Boekhold <>
23 Sep 1997 23:32:55 -0400

          From comp.compilers

Related articles
Tree Pattern Matching (1997-09-15)
Re: Tree Pattern Matching (Maarten Boekhold) (1997-09-23)
Re: Tree Pattern Matching (PROULX, DANIEL) (1997-09-23)
Re: Tree Pattern Matching (Terence Parr) (1997-09-23)
Re: Tree Pattern Matching (John Lindsay) (1997-09-24)
Re: Tree Pattern Matching (Abhay Kanhere) (1997-09-28)
Re: Tree Pattern Matching (1997-10-14)
| List of all articles for this month |

From: Maarten Boekhold <>
Newsgroups: comp.compilers
Date: 23 Sep 1997 23:32:55 -0400
Organization: Delft University of Technology, Dept. of Electrical Engineering
Keywords: bibliography, summary
In-reply-to: <199709161738.NAA03535@viper.cs.Virginia.EDU>

Below I have included a collection of the responses I got thus far in my
search. Several ppl have asked me to summarize the information I got, so
here it goes.

On Tue, 16 Sep 1997, Norman Ramsey wrote:

> Check out Phil Wadler's chapter in Simon Peyton Jones's book on
> implementing functional languages.

From: Allyn Dimock <>

Two products that you might want to look into are
TWIG -- a top down rewriter. Haven't found it yet
BURG -- a bottom up rewriter.

From: Daniel Wang <danwang@CS.Princeton.EDU>
    author = "Mikael Pettersson",
    title = "A Term Pattern-Match Compiler Inspired by Finite
                                  Automata Theory",
    journal = "Lecture Notes in Computer Science",
    volume = "641",
    pages = "258--??",
    year = "1992",
    coden = "LNCSD9",
    ISSN = "0302-9743",
    bibdate = "Mon May 13 11:46:24 MDT 1996",
    acknowledgement = "Nelson H. F. Beebe, Center for Scientific Computing,
                                  Department of Mathematics, University of Utah, Salt
                                  Lake City, UT 84112, USA, Tel: +1 801 581 5254, FAX: +1
                                  801 581 4148, e-mail: \path||, URL:

Is a good place to start, as it relatively recent and has a good
biblography. I have a copy of an updated version of the article that's a
chapter in Pettersson's thesis.

This is avalible online in

Author = "Marianne Baudinet and David MacQueen",
Title = "Tree Pattern Matching for {ML}",
Note="Available from David MacQueen, AT\&T Bell Laboratories, 600 Mountain
Avenue, Murray, Hill, NJ 07974",
Year = 1986

There's also a chapter in
    author = "Simon L. {Peyton Jones}",
    title = "The Implementation of Functional Programming
    publisher = "Prentice-Hall",
    year = "1987",

Here's a slightly different take on tree pattern matching. It's the
foundation for systems like iburg.

    author = "Christoph M. Hoffman and Michael J. O'Donnell",
    title = "Pattern matching in trees",
    journal = "Journal of the ACM",
    volume = "29",
    number = "1",
    pages = "68--95",
    year = "1982",

From: Dick Wesseling <

Refers to BURG and IBURG and to the master thesis of Todd Proebsting
( There are also pointers
to BURG and IBURG there.

From: Nathaniel McIntosh <>

This paper might be a good place to start:

                author = "David R. Chase",
                title = "An improvement to bottom-up tree pattern matching",
                booktitle = "Conference, Record of the 14th Annual ACM Symposium
on Principles of Programming Languages"
                pages = "168--177",
                address = "Munich, West Germany",
                month = January,
                year = 1987}

It's a bit dense, but it's one of the most interesting theory papers.

Try also:

                Author = {C. Fraser and R. Henry and T. Proebsting},
                Title = {BURG -- Fast Optimal Instruction Selection and Tree
                Journal = SIGPLAN,
                Volume = 27,
                Number = 4,
                Pages = {68-76},
                Month = Apr,
                Year = 1992}

I also found a web-page with some references to papers presented at
the Compiler Construction conference 1992, so I'm gonna look into that too.
In fact, it appears someone from my group (H. Corporaal) also presented a
paper there, so he'll probably has all the others too. I'll ask him.

Maarten Boekhold

| Maarten Boekhold, Faculty of Electrical Engineering TU Delft, NL |
| Computer Architecture and Digital Technique section |
| |

Post a followup to this message

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