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
smime.p7s
Description: S/MIME cryptographic signature
____________________ Racket Users list: http://lists.racket-lang.org/users
