Pattern Matching Papers

Pattern Matching Papers

[Nicolas Cannasse]

Hi list,

I'm interested in implementing pattern matching in a ML-like language, and I
need some resources on the following topics :
- pattern matching completeness check
- pattern matching compilation
Papers, tutorials and source code are welcome.

Thanks,
Nicolas Cannasse

Re: [Caml-list] Pattern Matching Papers

[David MENTRE]

"Nicolas Cannasse" <warplayer@free.fr> writes:

> Papers, tutorials and source code are welcome.

You should take a look at Luc Maranget papers:
  http://moscova.inria.fr/%7Emaranget/pub.html

Yours,
d.
-- 
pub  1024D/A3AD7A2A 2004-10-03 David MENTRE <dmentre@linux-france.org>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A

Re: [Caml-list] Pattern Matching Papers

[Luc Maranget]

> You should take a look at Luc Maranget papers:
>   http://moscova.inria.fr/%7Emaranget/pub.html
> 
> Yours,
> d.
> -- 
> pub  1024D/A3AD7A2A 2004-10-03 David MENTRE <dmentre@linux-france.org>
>  5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A


Thank you for citing my papers!

I'd like to cite some other papers.

* On Backtracking Automata:

- Lennart Augustsson's article includes compiler code.

@inproceedings{5303,
 author = {Lennart Augustsson},
 title = {Compiling pattern matching},
 booktitle = {Proc. of a conference on Functional programming languages and computer architecture},
 year = {1985},
 isbn = {3-387-15975-4},
 pages = {368--381},
 location = {Nancy, France},
 publisher = {Springer-Verlag New York, Inc.},
 address = {New York, NY, USA},
 }

- Phil Wadler's chapter in Simon Peyton Jones book 'Implementation of
  Functional  languages' also provides compiler code.

- Another implementation of the same algorithm is described in Xavier Leroy's
  'Zinc Report'.
<http://pauillac.inria.fr/~xleroy/publi/ZINC.ps.gz>

* On decision trees (or tree automata)

- M. Pettersson's article, a stimulating approach of this other compilation
  algorithm (LNCS 641).

 @inproceedings{727270,
 author = {Mikael Pettersson},
 title = {A Term Pattern-Match Compiler Inspired by Finite Automata Theory},
 booktitle = {CC '92: Proceedings of the 4th International Conference on Compiler Construction},
 year = {1992},
 isbn = {3-540-55984-1},
 pages = {258--270},
 publisher = {Springer-Verlag},
 address = {London, UK},
 }


-- Luc

Re: [Caml-list] Pattern Matching Papers

[Norman Ramsey]

 > Hi list,
 > 
 > I'm interested in implementing pattern matching in a ML-like language, and I
 > need some resources on the following topics :
 > - pattern matching completeness check
 > - pattern matching compilation
 > Papers, tutorials and source code are welcome.

In addition to other papers mentioned on this list, there are two
unpublished papers that may have some value:

   Baudinet, Marianne and David MacQueen. 1985 (December). Tree pattern
   matching for ML (extended abstract). Unpublished manuscript, AT&T Bell
   Laboratories.

   Scott, Kevin and Norman Ramsey. 2000 (May). When do match-compilation
   heuristics matter? Technical Report CS-2000-13, Department of Computer
   Science, University of Virginia.

My paper with Kevin Scott has some tutorial stuff in it.  If you like,
I can try to dig out source code, but it's in SML and may not be so useful.



Norman