[fare@tunes.org: Pattern-matching with Lisp2 style]

[Francois-Rene Rideau]

--3MwIy2ne0vdjdPXF
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit

Dear Tunesers,

Ok, I'm not coding much, if at all. But sometimes, I do code nevertheless.
Here is a post I just sent to comp.lang.lisp, that describes my pitiful
attempts at expressing my ideas about the duality between "construction"
and "deconstruction"...

Yours freely,

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[  TUNES project for a Free Reflective Computing System  | http://tunes.org  ]
Classical liberalism is not an economic doctrine. It is a theory of Law.

--3MwIy2ne0vdjdPXF
Content-Type: message/rfc822
Content-Disposition: inline
Content-Transfer-Encoding: 8bit

Received: from fare by Samaris with local (Exim 3.35 #1)
	id 16x8h1-0004rF-00
	for fare@localhost; Mon, 15 Apr 2002 17:46:59 +0200
Newsgroups: comp.lang.lisp
Subject: Pattern-matching with Lisp2 style
From: Francois-Rene Rideau <fare@tunes.org>
Date: 15 Apr 2002 17:46:55 +0200
Message-ID: <87ofgl7ymo.fsf@Samaris.tunes.org>
Organization: TUNES Project
User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Common Lisp)
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Sender: Francois-Rene Rideau <fare@Samaris.tunes.org>
Bcc: 
X-Spam-Status: No, hits=1.8 required=5.0 tests=DEAR_SOMEBODY,MISSING_HEADERS version=2.11

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

--3MwIy2ne0vdjdPXF--