[racket-dev] racket/match is broken

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Sat Oct 8 13:43:00 EDT 2011

On Sat, Oct 8, 2011 at 11:44 AM, Matthias Felleisen
<matthias at ccs.neu.edu> wrote:
> On Oct 8, 2011, at 12:42 PM, Robby Findler wrote:
>>> I doubt that this applies but I am willing to look at
>>> counter-examples.
>> One has been discussed in this thread. I think Sam promised to look
>> into seeing how well it applies to our implementation.
> Sorry, I skipped some messages.
>>>> I don't mind if the ordering of calling the predicates is fixed when
>>>> match cannot prove that the predicates are all safe to be reordered
>>>> (presumably by match keeping a list of known-to-be-safe predicates
>>>> somewhere and perhaps looking at the compile-time info to find struct
>>>> predicates).
>>>> (That would seem to be a straight-forward change, unless I'm missing something.)
>>> That would be fine too.
>> Good.
> Yes, because this is in practice left-to-right :-)

I think you are wrong with this opinion.

This expression:

(match x
  [`(lambda (,x) ,e) ...]
  [(? number?) ...]
  [`(,e1 ,e2) ...])

has, by my count, 7 opportunities to do things in different orders (6
cons cells can be matched car-position first or cdr-position first and
the order of which clause to try first can be moved around in at least
one way) and at least one of them seems profitable (merging the cons?
test from the first and second lines). I'd have to try some timings
and get more careful to say if that one is actually profitable or if
there are others but it is, in my mind, definitely at the "worth
trying" level, especially because there has been published work that
gets a 30% speedup on match-intensive things.

I think that the restriction I suggest above will rule out only (what
I would consider) strange match expressions, in practice. At least
based on my experience.

In my mind, a more difficult question is just how much speed we're getting.


Posted on the dev mailing list.