[racket-dev] racket/match is broken

In Eli's example, only the second pattern could match

But if we wrote it this way:

 (define (list?? x) (printf "list-checking ~s\n" x) (list? x))
 (define (one?? x) (printf "one-checking ~s\n" x) (eq? 1 x))
 (match '(1 (2) 3)
         [(list (? one??) (list 2) 3) 1]
         [(list _ (? list??) _) 2]
         [(list (? one??) (list 20) 30) 3])

Are you saying that match is allowed to return 1 or 2 depending on
these reorderings and this is in some sense an "illegal" match
expression?

Jay

On Thu, Oct 6, 2011 at 4:03 PM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:
> In Le Fessant and Maranget, ICFP 2001, they have measurements that
> show a 30% speedup of whole (toy) programs, with a similar but smaller
> suite of optimizations.
>
> Given the extensibility of `match', the performance difference can be
> made arbitrarily large.  For example, Eli's example doesn't call the
> `one??' function, which could take arbitrarily long (imagine a
> database query).
>
> On Thu, Oct 6, 2011 at 5:56 PM, Robby Findler
> <robby at eecs.northwestern.edu> wrote:
>> Do we have performance measurements that show the importance of such
>> reorderings?
>>
>> Robby
>>
>> On Thursday, October 6, 2011, Neil Toronto <neil.toronto at gmail.com> wrote:
>>> On 10/06/2011 01:20 PM, Eli Barzilay wrote:
>>>>
>>>> Just now, Neil Toronto wrote:
>>>>>
>>>>> On 10/06/2011 12:28 PM, Prabhakar Ragde wrote:
>>>>>>
>>>>>> On 10/6/11 2:12 PM, Eli Barzilay wrote:
>>>>>>
>>>>>>> Sam is talking about building the ASTs *while* matching, which is
>>>>>>> what Jay was trying to do with uses of `app'. I think that a
>>>>>>> teaching context is in particular one where such a thing doesn't
>>>>>>> fit -- it obscures the distinction between the side the sexpr
>>>>>>> goes into, and the side where an AST comes out.
>>>>>>
>>>>>> Okay, I see the distinction, and I apologize for not having fully
>>>>>> understood Jay's example. I agree that this obscurity is
>>>>>> hazardous. I think, though, that I have always assumed
>>>>>> left-to-right matching, though I may never have constructed
>>>>>> anything that would break if it didn't happen. --PR
>>>>>
>>>>> I think most people expect branching constructs like 'match' to make
>>>>> in-order (left-to-right/depth-first), short-cutting decisions.
>>>>> Additionally, the cases themselves do this. So I think the fact that
>>>>> the patterns don't is very surprising.
>>>>
>>>> IIRC, the cases are also reordered to optimize tests -- and that's an
>>>> even more important optimization:
>>>>
>>>>   ->  (define (list?? x) (printf "list-checking ~s\n" x) (list? x))
>>>>   ->  (define (one?? x) (printf "one-checking ~s\n" x) (eq? 1 x))
>>>>   ->  (match '(1 (2) 3)
>>>>        [(list (? one??) 2 3) 1]
>>>>        [(list _ (? list??) _) 2]
>>>>        [(list (? one??) 20 30) 3])
>>>>   list-checking (2)
>>>>   2
>>>>
>>>> and after Jay broke it, you get
>>>>
>>>>   one-checking 1
>>>>   list-checking (2)
>>>>   2
>>>>
>>>> IMO it is perfectly fine to require that stuff used in `match'
>>>> patterns is side-effect-free, and therefore cachable and reorderable.
>>>
>>> Well I'll be darned.
>>>
>>> I suppose this shows just how deeply I hold assumptions about order and
>>> shortcutting.
>>>
>>> Neil T
>>>
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://lists.racket-lang.org/listinfo/dev
>>>
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/dev
>>
>
>
>
> --
> sam th
> samth at ccs.neu.edu
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/dev
>



-- 
Jay McCarthy <jay at cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93