widespread bug in match

Just a heads-up to anyone using the original
code to Andrew Wright's pattern matcher or
a derivative thereof, the following bug bit me
today:

------------
> (match '(a . b) ((x) 1) ((x ...) 2) (x 3))
2
------------

This is wrong because '(a . b) is an improper list and
shouldn't match (x ...), it should match the last clause
and return 3.

This bug is present in at least the default Chicken
match (not the matchable egg), and in Gauche and
Guile's match implementations.

<sales-pitch>
If you don't feel like digging through that crufty old
code to fix this, you can always use the match
implementation at http://synthcode.com/scheme/match.scm
which is actively maintained, has more features,
and is hygienic and portable out of the box.
</sales-pitch>

--
Alex

Hello,

Alex Shinn <alexshinn@gmail.com> writes:

> Just a heads-up to anyone using the original
> code to Andrew Wright's pattern matcher or
> a derivative thereof, the following bug bit me
> today:
>
> ------------
>> (match '(a . b) ((x) 1) ((x ...) 2) (x 3))
> 2
> ------------
>
> This is wrong because '(a . b) is an improper list and
> shouldn't match (x ...), it should match the last clause
> and return 3.
>
> This bug is present in at least the default Chicken
> match (not the matchable egg), and in Gauche and
> Guile's match implementations.

Nice catch. Did you (or anyone else) try to fix it (and eventually gave
up)?

Thanks,
Ludovic.

On Aug 14, 11:53*pm, l...@gnu.org (Ludovic Courtès) wrote:
>
> Alex Shinn <alexsh...@gmail.com> writes:
> > Just a heads-up to anyone using the original
> > code to Andrew Wright's pattern matcher or
> > a derivative thereof, the following bug bit me
> > today:
>
> > ------------
> >> (match '(a . b) ((x) 1) ((x ...) 2) (x 3))
> > 2
> > ------------
>
> Nice catch. *Did you (or anyone else) try to fix it (and eventually gave
> up)?

I haven't tried to fix it because I can just use my
own matcher.

If you want to look into the bug to fix it, it has to
do with the optimizer. It works without the first
clause, but the optimizer incorrectly unifies the
first and second clauses.

--
Alex

On Aug 14, 11:23*pm, Alex Shinn <alexsh...@gmail.com> wrote:
> On Aug 14, 11:53*pm, l...@gnu.org (Ludovic Courtès) wrote:
>
>
>
> > Alex Shinn <alexsh...@gmail.com> writes:
> > > Just a heads-up to anyone using the original
> > > code to Andrew Wright's pattern matcher or
> > > a derivative thereof, the following bug bit me
> > > today:
>
> > > ------------
> > >> (match '(a . b) ((x) 1) ((x ...) 2) (x 3))
> > > 2
> > > ------------
>
> > Nice catch. *Did you (or anyone else) try to fix it (and eventually gave
> > up)?
>
> I haven't tried to fix it because I can just use my
> own matcher.
>
> If you want to look into the bug to fix it, it has to
> do with the optimizer. *It works without the first
> clause, but the optimizer incorrectly unifies the
> first and second clauses.

In general, the implementation of match is likely to be pretty bug-
ridden, simply because it hasn't been maintained in many years, and
it's very complex code that unlikely to be bug-free. Plus it is based
fundamentally on unhygenic macros, so the optimizer is likely to be
defeated by code such as:

(let ([pair? number?])
(match 3 [(a . b) 1] [(? pair?) 2] [_ 3]))

which gives an error in Chicken, for example.

In PLT, we recently junked the old implementation and wrote a new one
from scratch, which is better-performing and about 1/5th the code.

sam th

Hi,

samth <samth0@gmail.com> writes:

> In PLT, we recently junked the old implementation and wrote a new one
> from scratch, which is better-performing and about 1/5th the code.

Is it API-compatible (modulo bugs)?

Thanks,
Ludovic.

On Aug 19, 10:30*am, l...@gnu.org (Ludovic Courtès) wrote:
> Hi,
>
> samth <sam...@gmail.com> writes:
> > In PLT, we recently junked the old implementation and wrote a new one
> > from scratch, which is better-performing and about 1/5th the code.
>
> Is it API-compatible (modulo bugs)?

There's one change to the API, which is that patterns with ... are
more likely to match than they were previously. For example, the
pattern (list x ... y) would never match any list in the previous
implementation, since all the list elements would be consumed by x,
leaving none for y. In the current implementation, ... behaves like *
in a regular expression - it matches as many as possible, so that the
rest of the pattern matches.

sam th

Hi,

samth <samth0@gmail.com> writes:

> There's one change to the API, which is that patterns with ... are
> more likely to match than they were previously. For example, the
> pattern (list x ... y) would never match any list in the previous
> implementation, since all the list elements would be consumed by x,
> leaving none for y. In the current implementation, ... behaves like *
> in a regular expression - it matches as many as possible, so that the
> rest of the pattern matches.

Interesting. It's not really an incompatibility since this pattern
would have been useless with Wright's `match'.

Where's the source? (I quickly browsed the PLT repository without
success.)

Thanks,
Ludovic.

On Aug 20, 11:19*am, l...@gnu.org (Ludovic Courtès) wrote:
> Hi,
>
> samth <sam...@gmail.com> writes:
> > There's one change to the API, which is that patterns with ... are
> > more likely to match than they were previously. *For example, the
> > pattern (list x ... y) would never match any list in the previous
> > implementation, since all the list elements would be consumed by x,
> > leaving none for y. *In the current implementation, ... behaves like *
> > in a regular expression - it matches as many as possible, so that the
> > rest of the pattern matches.
>
> Interesting. *It's not really an incompatibility since this pattern
> would have been useless with Wright's `match'.

It is an incompatibility in some cases. For example:

(match (list 1 2 3)
[(list x ... y) 1]
[_ 2])

will return 1 with the new implementation, and 2 with the old. But I
don't think there are any actual problems caused by this.

>
> Where's the source? *(I quickly browsed the PLT repository without
> success.)

http://svn.plt-scheme.org/plt/trunk/.../scheme/match/

sam th

On 8ÔÂ21ÈÕ, ÎçÇ°12:19, l...@gnu.org (Ludovic Court¨¨s) wrote:
>
> Interesting. It's not really an incompatibility since this pattern
> would have been useless with Wright's `match'.
>
> Where's the source? (I quickly browsed the PLT repository without
> success.)

Note that the PLT implementation has another API incompatibility
by not supporting the get!/set! patterns (though they never seemed
very useful to me, and smell of bad coding).

There's another pattern matcher by Dan Friedman and distributed
with Ikarus that's worth looking into, but it has a different API.

The most featureful matcher I'm aware of is at

https://code.launchpad.net/~derick-e...aries/xitomatl

Except for Wright's matcher, none of these unify tests shared
in common between match clauses. That's what Wright's optimizer does,
and is the cause of the bug. In practice you're not likely to see big
difference in performance, but there are border cases where the
difference
is substantial - O(1) vs. O(n). Ideally the compiler should be
performing
these optimizations, but I'm still working on that

The matcher I posted at synthcode.com is the only one that
will give you all the features and no bugs out of the box with no
effort.
The others will require porting work. It's also documented and
simple,
and smaller than any of the alternatives.

--
Alex

On Aug 20, 1:04 pm, Alex Shinn <alexsh...@gmail.com> wrote:
> On 8ÔÂ21ÈÕ, ÎçÇ°12:19, l...@gnu.org (Ludovic Court¨¨s) wrote:
>
>
>
> > Interesting. It's not really an incompatibility since this pattern
> > would have been useless with Wright's `match'.
>
> > Where's the source? (I quickly browsed the PLT repository without
> > success.)
>
> Note that the PLT implementation has another API incompatibility
> by not supporting the get!/set! patterns (though they never seemed
> very useful to me, and smell of bad coding).

Right, I took them out as well. To the best of my knowledge, they've
never been used.

> There's another pattern matcher by Dan Friedman and distributed
> with Ikarus that's worth looking into, but it has a different API.
>
> The most featureful matcher I'm aware of is at
>
> https://code.launchpad.net/~derick-e...aries/xitomatl

Interesting. This matcher has one feature that the PLT matcher
doesn't support right now, which is upper bounds on ... patterns. The
internals of the PLT matcher support this, but I'm not sure what the
right syntax would be.

However, your claim is incorrect, since the PLT matcher also supports
features that this matcher doesn't (like the ability to add new
extensions to the pattern language, and unordered list patterns).

>
> Except for Wright's matcher, none of these unify tests shared
> in common between match clauses. That's what Wright's optimizer does,
> and is the cause of the bug. In practice you're not likely to see big
> difference in performance, but there are border cases where the
> difference
> is substantial - O(1) vs. O(n). Ideally the compiler should be
> performing
> these optimizations, but I'm still working on that
>
> The matcher I posted at synthcode.com is the only one that
> will give you all the features and no bugs out of the box with no
> effort.

I think programmers should be wary of saying that their code has no
bugs. Unless you're offering rewards, Knuth-style.

sam th