Re: pattern-matching: a new approach

Barry Jay wrote:

> Announcing the availability of a new report titled
>         The Constructor Calculus

Looks interesting.

But I think the following work is related
and hence should be taken into account.
I assume that these pointers might be interesting
for others too.

The basic idea of pattern matching for constructors
of different datatypes while dealing with suitable
defaults for all others is already present in [1].

A more sophisticated setup based on ideas of
term rewriting strategies is found in [2]. I 
basically use a type-dependent form of choice which 
can be used to combine functions (say, strategies)
of different types. In addition, a few one-step
traversal combinators are considered.

Strategic programming has also been transposed to
functional programming in several ways. [3] might be
particularly interesting because there is a yet another
form of fold which can be used instead of pattern
matching to fold over the immediate subterms of a
term. This fold should not be confused with a generalized
fold. There is again a type-dependent composition combinator
involved. Furthermore, Eelco Dolstra and Eelco Visser
have also designed a related construct (cf. RhoStratego).

I would be interested in more off-line discussion.


[1] @inproceedings{LVK00,
      author   = "R.~L{\"a}mmel and J.~Visser and J.~Kort",
      title    = "{Dealing with Large Bananas}",
      pages    = "46--59",
      crossref = "WGP00",

      editor = "J.~Jeuring",
      title = "{Proceedings of WGP'2000, Technical Report, Universiteit
      booktitle = "{Proceedings of WGP'2000, 
                    Technical Report, Universiteit Utrecht}",
      month = jul,
      year = 2000

[2] @techreport{Laemmel02-TGT,
      author = "Ralf L{\"a}mmel",
      title = "{Typed Generic Traversal With Term Rewriting Strategies}",
      institution = "arXiv",
      number = "cs.PL/0205018",
      year = 2002,
      month = may,
      note = {85 pages;
              To appear in the Journal of Logic and Algebraic Programming;
              First published as CWI Technical Report SEN-R0122 in August 2001}

[3] @inproceedings{Laemmel02-SPS,
       author = "Ralf L{\"a}mmel",
       title = "{The Sketch of a Polymorphic Symphony}",
       booktitle = {Proc.\ of International Workshop on Reduction Strategies
                        in Rewriting and Programming (WRS 2002)},  
       editor = {Bernhard Gramlich and Salvador Lucas},
       series = "ENTCS",
       year = 2002,
       month = jul,
       note = "20 pages; To appear"

Dr.-Ing. Ralf Laemmel
CWI & VU, Amsterdam, The Netherlands