[racket] Question

From: Rüdiger Asche (rac at ruediger-asche.de)
Date: Wed Sep 5 16:53:58 EDT 2012

ok, thanks, that explains a few things (thanks also to Carl for his similar response).

But nevertheless, what about macro expansion time? Seems like SOMEBODY needs to do the grunt work at some time, regardless of what phase the computation takes place at... I can see how the JIT compiler "caches" the preprocessed code so in my test suite, the expansion takes place just once, making the expansion time negligible over the course of the test run... but would that hold true in general?

Regardless, for the sake of the excercise, it's kind of enlightening that your solution actually reduces to the naive approach - when I was in school (before the last ice age if I recall correctly) , we'd probably be asked to come up with an elegant *algorithmic* solution (which means, for example, something like a tower of Hanoi type circular swap which naturally beats the naive approach in the general case) - if the choice now is between two approaches that actually do the same thing only on two different abstraction levels - does that imply that the student is already so familiar with the syntactic expansion mechanism that he or she "looks behind the macro" at first glance and is able to identify both as based on the same procedure and only takes the macro approach for better readability - or does it mean that match is being looked at as some kind of black box that has a semantic of its own (regardless of how it is being implemented under the hood)?

Sorry for side tracking, I just try to understand how an excercise like that is set up and what a "good" solution is expected to look like and why...

btw, if this response should look funny in the thread tree view it's because Matthias signed his message digitally, and my Outlook wouldn't allow me to respond all without signing my response (which somehow didn't work), so I had to revert to a response on an earlier mail of mine, sorry.
  ----- Original Message ----- 
  From: Matthias Felleisen 
  To: Rüdiger Asche 
  Cc: Ashley Fowler ; users at racket-lang.org 
  Sent: Wednesday, September 05, 2012 10:29 PM
  Subject: Re: [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) 
       (let ([fst (car ls)]))
         (if (null? (cdr ls))
             (let ([snd (cadr ls)])
               (if (null? (cddr ls))
                   (let ([trd (caddr ls)])
                      (if (null? (cdddr ls)) ;; <--- here 
                          (list trd snd fst) 

  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/16e38ce1/attachment-0001.html>

Posted on the users mailing list.