[racket] Question

On Sep 5, 2012, at 4:15 PM, Rüdiger Asche wrote:

>  the pattern matching and substitution process is expectedly rather sophisticated (and thus more resource consuming)?

Nope, it all happens at compile time. The object code is probably close to this 

 (if (null? ls) 
     (void)
     (let ([fst (car ls)]))
       (if (null? (cdr ls))
           (void) 
           (let ([snd (cadr ls)])
             (if (null? (cddr ls))
                 (void) 
                 (let ([trd (caddr ls)])
                    (if (null? (cdddr ls)) ;; <--- here 
                        (list trd snd fst) 
                        (void))))))))

Now you would think that 

 (list (caddr ls) (cadr ls) (car ls))

is much faster because it avoids all the null? checks. BUT, you need to keep in mind that Racket's car must perform the null? checks anyway because it cannot just assume that ls consists of three items. 

Conjecture: the jit compiler actually knows that the two checks happen and eliminates one of them. I do not know for sure that this is true but I know that some compilers have done this in the past. 

Meaning? For this simple pattern matching problem, the code produced via (the) match (macro) and the plain function definition _performs_ at about the same level, possibly with one extra null? check -- labeled "<-- here" because this one is not needed for the naive version, which does not check whether there is a fourth item on the list. The match version enforces this constraint however. 

;; --- 

At this point you may realize that the two functions aren't trivially equivalent. It is not true that 

 for all x in Racket values, 
   (equal? (switch-one-and-three1 x) (switch-one-and-three4 x))

What you would have to prove is 
 
  for all x in Racket values, 
   (implies (and (list? x) (= (length x) 3)) 
                (equal? (switch-one-and-three1 x) (switch-one-and-three4 x))

Exercise: Try to prove the above in Dracula. -- Matthias






 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120905/7fec019f/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4373 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20120905/7fec019f/attachment.p7s>