Implementing Normal Order Evaluation with Common Lisp Macros

Section 1.1.5 of SICP introduces the concept of normal order evaluation. Lisp traditionally evaluates all the arguments before applying functions, but with normal order evaluation this is reversed. The functions are expanded out as far as possible before any of the arguments are evaluated. It’s the Evil Universe version of Lisp!!

Now, when I’m confronted with problems having to do with normal order evaluation… for some reason my mind switches off. All of my Lisp experience is with the standard applicative order evaluation… and that’s the way I think. I have a really hard time imagining how normal order evaluation would break things out differently.

(And that’s the thing about SICP. It’s written for guys that scored higher on the SAT than I did… guys that actually paid attention in math class and did their homework. And it’s a tough book even for them— and they have the benefit of peers and TA’s and professors. And just because you can skirt by problems like Exercise 1.5, it doesn’t mean you’re through. This stuff will come back to haunt you in 1.20 and probably even more!)

So there I am having a pity party for myself: I’m a dummy. I have intellectual limits and weaknesses. Google doesn’t return much useful stuff on this topic. I don’t have a com-sci degree. I missed my chance to go to MIT and be somebody…. And then the light bulb goes off: Common Lisp pretty much comes with a normal order evaluator built in. They’re called macros! I can use Common Lisp as a sort of substitute professor to help me practice with normal order evaluation– and Common Lisp will even help me by checking the expansions that I’ve done by hand!

So I rewrite the Scheme example from SICP into Common Lisp macros:

CL-USER> (defmacro square (x)
`(* ,x ,x))
SQUARE
CL-USER> (defmacro sum-of-squares (x y)
`(+ (square ,x) (square ,y)))
SUM-OF-SQUARES
CL-USER> (defmacro f (a)
`(sum-of-squares (+ ,a 1) (* ,a 2)))
F
CL-USER> (macroexpand ‘(f 5))
(+ (SQUARE (+ 5 1)) (SQUARE (* 5 2)))
T

Oops. We’re close here, but we’re still not getting the same expansion as the book. For some reason we’re not expanding out the SQUARE macro. It must be because the reader waits until we have a macro name an the far left side before it expands one.  Maybe we can make it work by using a series of macroexpand-1 commands:

CL-USER> (macroexpand-1 ‘(f 5))
(SUM-OF-SQUARES (+ 5 1) (* 5 2))
T
CL-USER> (macroexpand-1 ‘(SUM-OF-SQUARES (+ 5 1) (* 5 2)))
(+ (SQUARE (+ 5 1)) (SQUARE (* 5 2)))
T
CL-USER> (macroexpand-1 ‘(+ (SQUARE (+ 5 1)) (SQUARE (* 5 2))))
(+ (SQUARE (+ 5 1)) (SQUARE (* 5 2)))
NIL
CL-USER> (macroexpand-1 ‘(SQUARE (+ 5 1)))
(* (+ 5 1) (+ 5 1))
T

CL-USER> (macroexpand-1 ‘(SQUARE (* 5 2)))
(* (* 5 2) (* 5 2))
T

CL-USER> (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
136

Okay, we can force it work… and then cut and paste the results together to get the same expansion that the text comes up with. But I hate cutting and pasting in Emacs. Let’s rewrite the sum-of-squares macro so that it does all of that work for me:

CL-USER> (defmacro sum-of-squares (x y)
(list ‘+
(macroexpand-1 `(square ,x))
(macroexpand-1 `(square ,y))))
SUM-OF-SQUARES
CL-USER> (macroexpand ‘(f 5))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
T

There’s probably a more elegant way to pull that off, but we get the job done. So now we not only have a little practice with macros and normal order evaluation, but we have techniques at our disposal that allow us to switch back and forth from normal order to applicative order evaluation whenever we choose. In what other language can you do that?!

(To see these techniques applied to  SICP exercises 1.5 and 1.20, please see my study notes in this text file.)

Advertisements

2 Responses to “Implementing Normal Order Evaluation with Common Lisp Macros”

  1. Master Fundamental Hacking Principles with Scheme « Learning Lisp Says:

    […] course, you could always try working through the book by youself and post lame blog entries about how it’s so hard to get through it on your own… but come on… you’re […]

  2. Mastering Higher Order Programming Techniques with SICP Chapter 1 « Learning Lisp Says:

    […] Exercise 1.13 asked us to “use induction” to prove something. Plugging through exercise 1.20 was exceedingly painful back when I was working on my own. The march of technology added some […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: