<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content="text/html; charset=iso-8859-1" http-equiv=Content-Type><BASE href="x-msg://1444/"> <META name=GENERATOR content="MSHTML 8.00.6001.18928"> <STYLE></STYLE> </HEAD> <BODY style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space" bgColor=#ffffff> <DIV> <DIV> <DIV><FONT size=2 face=Arial>ok, thanks, that explains a few things (thanks also to Carl for his similar response).</FONT></DIV> <DIV><FONT size=2 face=Arial></FONT> </DIV> <DIV><FONT size=2 face=Arial>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?</FONT></DIV> <DIV><FONT size=2 face=Arial></FONT> </DIV> <DIV><FONT size=2 face=Arial>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)</FONT> <FONT size=2 face=Arial>, 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)?</FONT></DIV> <DIV><FONT size=2 face=Arial></FONT> </DIV> <DIV><FONT size=2 face=Arial>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...</FONT></DIV> <DIV><FONT size=2 face=Arial></FONT> </DIV> <DIV><FONT size=2 face=Arial>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.</FONT></DIV></DIV> <BLOCKQUOTE style="BORDER-LEFT: #000000 2px solid; PADDING-LEFT: 5px; PADDING-RIGHT: 0px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px"> <DIV style="FONT: 10pt arial">----- Original Message ----- </DIV> <DIV style="FONT: 10pt arial; BACKGROUND: #e4e4e4; font-color: black"><B>From:</B> <A title=matthias@ccs.neu.edu href="mailto:matthias@ccs.neu.edu">Matthias Felleisen</A> </DIV> <DIV style="FONT: 10pt arial"><B>To:</B> <A title=rac@ruediger-asche.de href="mailto:rac@ruediger-asche.de">Rüdiger Asche</A> </DIV> <DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=afowler2@broncos.uncfsu.edu href="mailto:afowler2@broncos.uncfsu.edu">Ashley Fowler</A> ; <A title=users@racket-lang.org href="mailto:users@racket-lang.org">users@racket-lang.org</A> </DIV> <DIV style="FONT: 10pt arial"><B>Sent:</B> Wednesday, September 05, 2012 10:29 PM</DIV> <DIV style="FONT: 10pt arial"><B>Subject:</B> Re: [racket] Question</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV><BR> <DIV> <DIV>On Sep 5, 2012, at 4:15 PM, Rüdiger Asche wrote:</DIV><BR class=Apple-interchange-newline> <BLOCKQUOTE type="cite"><SPAN style="WIDOWS: 2; TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium 'Lucida Grande'; WHITE-SPACE: normal; ORPHANS: 2; LETTER-SPACING: normal; WORD-SPACING: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none" class=Apple-style-span><SPAN style="FONT-FAMILY: Arial; FONT-SIZE: small" class=Apple-style-span><SPAN class=Apple-converted-space> </SPAN>the pattern matching and substitution process is expectedly rather sophisticated (and thus more resource consuming)?</SPAN></SPAN></BLOCKQUOTE></DIV><BR> <DIV>Nope, it all happens at compile time. The object code is probably close to this </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV> (if (null? ls) </DIV> <DIV>     (void)</DIV> <DIV>     (let ([fst (car ls)]))</DIV> <DIV>       (if (null? (cdr ls))</DIV> <DIV>           (void) </DIV> <DIV>           (let ([snd (cadr ls)])</DIV> <DIV>             (if (null? (cddr ls))</DIV> <DIV>                 (void) </DIV> <DIV>                 (let ([trd (caddr ls)])</DIV> <DIV>                    (if (null? (cdddr ls)) ;; <--- here </DIV> <DIV>                        (list trd snd fst) </DIV> <DIV>                        (void))))))))</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>Now you would think that </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV> (list (caddr ls) (cadr ls) (car ls))</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>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. </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>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. </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>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. </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>;; --- </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>At this point you may realize that the two functions aren't trivially equivalent. It is not true that </DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV> for all x in Racket values, </DIV> <DIV>   (equal? (switch-one-and-three1 x) (switch-one-and-three4 x))</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>What you would have to prove is </DIV> <DIV><FONT size=2 face=Arial></FONT> </DIV> <DIV>  for all x in Racket values, </DIV> <DIV>   (implies (and (list? x) (= (length x) 3)) </DIV> <DIV>                (equal? (switch-one-and-three1 x) (switch-one-and-three4 x))</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV>Exercise: Try to prove the above in Dracula. -- Matthias</DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV> <DIV><SPAN style="FONT-FAMILY: Arial; FONT-SIZE: small" class=Apple-style-span><BR></SPAN></DIV> <DIV><FONT class=Apple-style-span size=2 face=Arial><BR></FONT></DIV> <DIV><FONT class=Apple-style-span size=2 face=Arial><BR></FONT></DIV> <DIV><FONT size=2 face=Arial></FONT><BR></DIV><SPAN style="FONT-FAMILY: Arial; FONT-SIZE: small" class=Apple-style-span> </SPAN></BLOCKQUOTE></DIV></BODY></HTML>