From: Francois-Rene Rideau
Subject: Pattern-matching with Lisp2 style
Date: 
Message-ID: <87ofgl7ymo.fsf@Samaris.tunes.org>
Dear Lispers,

since today is Saint Paternus, it's a good day to announce my pattern-matcher.
I'm developing an extensible pattern-matcher in CL, that has a Lisp2 style
that I find very natural [*]. You can find it at:
	http://tunes.org/cgi-bin/cvsweb/fare/fare/lisp/matcher.lisp
It depends on the utilities defined in
	http://tunes.org/cgi-bin/cvsweb/fare/fare/lisp/fare.lisp

Lisp2 style means that instead of writing
	(destructuring-bind (a b (c d ()) . e) foo (bar a b c d e))
You'd write
        (match1 (list* a b (list c d 'nil) e) foo (bar a b c d e))
This might look heavier, but then, the fact that the head of a pattern
is a designator for an arbitrary pattern instead of having patterns
always be lists except for possible "magic" values like &rest and
other keywords allows patterns to be clearer, and *extensible*.
Thus you can trust that any symbol in head position is a pattern name,
while any symbol in parameter position is a variable name, except if
it is a special symbol, or the head is a pattern macro, in which case
it controls the meaning of the parameters.

Predefined special symbols are T and NIL:
T matches anything, NIL matches nothing.
Predefine functional patterns are CONS, LIST, LIST*, VECTOR,
that match corresponding objects with a known arity.
Predefined macro patterns are QUOTE, VALUE, LIKE-WHEN, AND
that respectively match a literal constant, the value of an expression,
a pattern with a guard condition, or the conjunction of several patterns.

MATCH1 (to be renamed IFMATCH in further releases) tries to match
a pattern with an expression, and conditionally executes either
the success form in a properly extended lexical environment,
or the failure form in the original lexical environment, depending
on whether the match succeeded (with freshly bound variables) or not.
MATCH (that I won't rename to COND-MATCH) tries to match a given
expression with several patterns, and executes the body of the matching
clause if found.
EMATCH is like MATCH but raises an error instead of returning NIL
when no match is found.

With this paradigm, matching patterns are thus dual from normal forms.
I like to think of all forms as patterns, with some patterns being
in "deconstruction position" (left-hand side of a match clause),
and other patterns being in "construction position" (right-hand side
of a match clause).
Although the current implementation follows Erlang (or ML-like) semantics
for matching, this paradigm can generalize to non-deterministic settings,
where you'd obtain something much like Mercury, unifying functional
and logic programming -- however, I haven't even attempted to implement
non-determinism (maybe this could be done using Screamer).

Simple examples:
        (defun my-length (x)
          (ematch x
            ((cons t x) (1+ (my-length x)))
            ('nil 0))) ==> MY-LENGTH
        (my-length '(1 2 3)) ==> 3

Bugs and limitations of the current implementation:
* in some cases, the current code produces functional constants instead of
 source code for same effect, which has bad interactions with COMPILE-FILE
 on some systems (notably CMUCL).
* although the matching macros expand code following a sound
 matcher-passing-style, it does it in an unsound match-lexical environment,
 instead of using a monadic environment-passing-style that would create
 bindings as the match progresses (limitation visible by using incorrect
 LIKE-WHEN patterns).
* not much of any error detection is done, and when there is,
 error reporting is minimal.
* not any pattern optimization is done by the matching macros (however,
 since patterns are expanded into lisp code at macro-expansion time,
 the compiler might still do a few optimizations and produce reasonable code).

To Do list for next release:
* fix above bugs and limitations
* use extensibility to add support for matching structures and classes
* include a backquote implementation that interacts well with the matcher,
 producing the equivalent of LIST and LIST* whenever possible.

Footnotes:
[*] Actually, I had first thought about this pattern-matcher when I was more
of a Lisp1 fan, and the fact that Lisp2 was much more natural for the pattern
matcher finished to turn me into a Lisp2 fan.

Enjoy!

[ Fran�ois-Ren� �VB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[  TUNES project for a Free Reflective Computing System  | http://tunes.org  ]
Trying to make bits uncopyable is like trying to make water not wet. The
sooner people accept this, and build business models that take this into
account, the sooner people will start making money again. -- Bruce Schneier

From: Kent M Pitman
Subject: Re: Pattern-matching with Lisp2 style
Date: 
Message-ID: <sfwd6x0q4x6.fsf@shell01.TheWorld.com>
Francois-Rene Rideau <····@tunes.org> writes:

> Footnotes:
> [*] Actually, I had first thought about this pattern-matcher when I was more
> of a Lisp1 fan, and the fact that Lisp2 was much more natural for the pattern
> matcher finished to turn me into a Lisp2 fan.

Misc semi-related historical data fyi...

In Maclisp, there were two competing styles of extended LET.  The
installed one [eventually; Maclisp had a long life and didn't have LET
for a long time, but eventually acquired an autoloading LET] had a lot
of support because of its simpler syntax and a general sense of
inertia [people immediately used it when it was offered and a bunch of
code was built up that depended upon it].  It did:
 (let (((a b) '(c d))) 
   (list b a))
 => (D C)

Someone [my recollection is that it was Stallman, but I might be 
misremembering] championed the idea of:
 (let (((list a b) '(c d)))
   (list b a))
 => (D C)
The key reason for this being advocated as a good idea wasn't the Lisp1/Lisp2
thing [which was not a political issue at all at the time and so had not been
named; I created the Lisp1/Lisp2 naming during the ANSIC CL design process],
but was instead that it admitted hiding of representation.  Advocates of this
notation said the important thing was allowing macros, so that either
 (defmacro make-foo (x y) (list 'x x 'y y))
 (defmacro foo-x (foo) (get foo 'x))
 (defmacro foo-y (foo) (get foo 'y))
or
 (defmacro make-foo (x y) (cons x y))
 (defmacro foo-x (foo) (car foo))
 (defmacro foo-y (foo) (cdr foo))
would still transparently allow
 (let ((the-foo (make-foo 1 2)))
   (let (((make-foo a b) the-foo))
     (list a b)))
 => (1 2)
without the writer of the LET having to know a FOO's internal representation.
From: Skip Egdorf
Subject: Re: Pattern-matching with Lisp2 style
Date: 
Message-ID: <3CC30BDE.30109@cybermesa.com>
Kent M Pitman wrote:

>
>Misc semi-related historical data fyi...
>
>In Maclisp, there were two competing styles of extended LET. ...
>
It occurs to me that perhaps we should all lobby
the current US administration to loosen its stance on
human cloning for the special case of Kent.

If he gets hit by a beer truck while crossing the street,
about two thirds of the history of lisp will be lost
to mankind.

Skip Egdorf
······@cybermesa.com
From: Rahul Jain
Subject: Re: Pattern-matching with Lisp2 style
Date: 
Message-ID: <874ri4ptad.fsf@photino.sid.rice.edu>
Skip Egdorf <······@cybermesa.com> writes:

> It occurs to me that perhaps we should all lobby the current US
> administration to loosen its stance on human cloning for the special
> case of Kent.

> If he gets hit by a beer truck while crossing the street, about two
> thirds of the history of lisp will be lost to mankind.

It's a pity that genes don't carry memes. :)

-- 
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  ············@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.