Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Source code of Wright’s pattern matcher

52 views
Skip to first unread message

Ludovic Courtès

unread,
Apr 16, 2010, 6:35:36 PM4/16/10
to
Hello,

Andrew K. Wright’s pattern matcher [0] is fairly dense code that was
most likely generated from some source form.

Is that source form available somewhere? Is there a document describing
the pattern matcher implementation?

Thanks,
Ludo’.

[0] http://www.cs.indiana.edu/scheme-repository/code.match.html

Sam TH

unread,
Apr 17, 2010, 7:47:31 AM4/17/10
to
On Apr 16, 6:35 pm, l...@gnu.org (Ludovic Courtès) wrote:
> Hello,
>
> Andrew K. Wright’s pattern matcher [0] is fairly dense code that was
> most likely generated from some source form.
>
> Is that source form available somewhere?  Is there a document describing
> the pattern matcher implementation?

I believe that it's expanded from an earlier use of `match'. This is
a long and bad tradition in the implementation of Scheme pattern
matchers.

There's a unpublished manuscript by Wright on `match', but it doesn't
describe the implementation.

Personally, as the maintainer of code formerly descended from the
Wright matcher, I recommend a re-write rather than using the existing
code. It shortened the code and made it much easier for me to
maintain.

sam th

Tom Lord

unread,
Apr 17, 2010, 3:23:40 PM4/17/10
to
On Apr 17, 4:47 am, Sam TH <sam...@gmail.com> wrote:
>
> I believe that it's expanded from an earlier use of `match'.  This is
> a long and bad tradition in the implementation of Scheme pattern
> matchers.
>

I'm pretty sure that that's right but I'm not
so sure that that's, in and of itself, a bad
tradition. The bad tradition is in not maintaining
and distributing the bootstrap matcher.

I'd also suggest a rewrite. One way to do it is
to write by hand a minimal expander, sufficient
for writing match, and then write match itself in
that.

Eduardo Cavazos

unread,
Apr 17, 2010, 3:45:20 PM4/17/10
to
Hi Ludovic,

If you decide to go the rewrite route, consider Alex Shinn's
implementation:

http://synthcode.com/scheme/match.scm

"a fully portable hygienic pattern matcher backwards compatible with
Andrew Wright's MATCH sytax"

There's an R6RS port in Derick Eddington's Xitomatl libraries
'(xitomatl AS-match)'.

Ed

Ludovic Courtès

unread,
Apr 17, 2010, 4:58:34 PM4/17/10
to
Hi,

Thanks everyone for your answers.

Eduardo Cavazos <wayo.c...@gmail.com> writes:

> If you decide to go the rewrite route, consider Alex Shinn's
> implementation:
>
> http://synthcode.com/scheme/match.scm
>
> "a fully portable hygienic pattern matcher backwards compatible with
> Andrew Wright's MATCH sytax"

Looks like an interesting option.

However, it appears to lack support for ‘$’ patterns for record matching
(there are mentioned in one place but it seems that the actual
implementation is missing.) Does anyone have more info on this?

Thanks,
Ludo’.

marcomaggi

unread,
Apr 18, 2010, 7:17:10 AM4/18/10
to
On Apr 17, 10:58 pm, l...@gnu.org (Ludovic Courtès) wrote:
> Hi,
>
> Thanks everyone for your answers.
>
> Eduardo  Cavazos <wayo.cava...@gmail.com> writes:
>
> > If you decide to go the rewrite route, consider Alex Shinn's
> > implementation:
>
> >    http://synthcode.com/scheme/match.scm
>
> > "a fully portable hygienic pattern matcher backwards compatible with
> > Andrew Wright's MATCH sytax"
>
> Looks like an interesting option.
>
> However, it appears to lack support for ‘$’ patterns for record matching
> (there are mentioned in one place but it seems that the actual
> implementation is missing.)  Does anyone have more info on this?
>
> Thanks,
> Ludo’.

http://synthcode.com/scheme/match-cond-expand.scm

Ludovic Courtès

unread,
Apr 19, 2010, 8:36:24 AM4/19/10
to
Hi,

marcomaggi <mrc...@gmail.com> writes:

Thanks. This version does have record matching, but it’s older than the
one above, according to the revision history at the beginning of the
file. Hopefully back-portable though.

Ludo’.

Alex Shinn

unread,
Apr 22, 2010, 3:29:49 AM4/22/10
to
On Apr 19, 9:36 pm, l...@gnu.org (Ludovic Courtès) wrote:

>
> marcomaggi <mrc....@gmail.com> writes:
>
> >http://synthcode.com/scheme/match-cond-expand.scm
>
> Thanks.  This version does have record matching, but it’s older than the
> one above, according to the revision history at the beginning of the
> file.  Hopefully back-portable though.

You can't portably do record matching because there are
no portable records. SRFI-9 has portable records but
not the introspection needed for a matching library.

The record matching in that file is in a commented out
section towards the end showing how to do record
matching for Chicken Scheme. If your implementation
has the equivalent of (slot-ref <record> <index>) then
it's straightforward to port.

--
Alex

Ludovic Courtès

unread,
Apr 22, 2010, 5:02:50 AM4/22/10
to
Hi,

Alex Shinn <alex...@gmail.com> writes:

> On Apr 19, 9:36 pm, l...@gnu.org (Ludovic Courtès) wrote:
>>
>> marcomaggi <mrc....@gmail.com> writes:
>>
>> >http://synthcode.com/scheme/match-cond-expand.scm
>>
>> Thanks.  This version does have record matching, but it’s older than the
>> one above, according to the revision history at the beginning of the
>> file.  Hopefully back-portable though.
>
> You can't portably do record matching because there are
> no portable records. SRFI-9 has portable records but
> not the introspection needed for a matching library.

‘$’ patterns don’t need introspection: they just need to be able to
access fields by index as you noted below.

‘=’ patterns apparently don’t rely on introspection either IIUC.

> The record matching in that file is in a commented out
> section towards the end showing how to do record
> matching for Chicken Scheme. If your implementation
> has the equivalent of (slot-ref <record> <index>) then
> it's straightforward to port.

Thanks,
Ludo’.

0 new messages