A Scheme Syntax-Rules Primer « It Seemed Like A Good Idea, At The Time

Blog
About

A Scheme Syntax-Rules Primer

September 4, 2008 at 8:34 pm | In scheme, tutorial | 15 Comments
Tags: macros, scheme, tutorial

Scheme has a wonderfully powerful hygienic macro system. Unfortunately, explanations on how to use it are few and far between. R5RS is utterly incomprehensible to anyone who doesn’t already have a firm grounding in hygienic macro systems, and TYSiFD’s section on macros dates from a time before syntax-rules and hygiene.

So this here is my attempt to share what I’ve learned over the past few days with regards to syntax-rules macros. Bear in mind that at the time of writing this, I have known how to use syntax-rules since yesterday, but my knowledge seems to be complete enough to write a working module system, so here’s my attempt to pass on what I’ve learned.

First things first. You use define-syntax to create a top level binding, and let-syntax bears the same relationship to define-syntax as you’d expect.

;; define-syntax is used to create
;;  a top-level binding of a macro
(define-syntax macro
  <syntax transformer>)

That much is pretty clear from reading R5RS, now we need to figure out how to write the syntax transformer. There are a few ways to do this, but the best way for beginners is to use syntax-rules, which avoids inadvertent variable capture and other such nasties automatically, and uses a rather elegant pattern matching language.

We’ll start by trying to write a simple macro, while. This will just be a standard looping construct that keeps executing over and over until its condition becomes false. We want its usage to look something like this:

;; A simple while loop
(define x 0)
(while (< x 5)
  (set! x (+ x 1))
  (print x))

So first, we need the define-syntax form.

(define-syntax while
  <syntax transformer>)

Next, we need to write the syntax transformer itself. This is where syntax-rules comes into play. Syntax-rules uses pattern matching and text substitution to allow you to make some pretty advanced macros. It looks like:

(define-syntax while
  (syntax-rules (<keywords>)
    ((<pattern>) <template>)
    ...
    ((<pattern>) <template>)))

I will explain keywords later. For now, just leave that bit blank. What we’re interested in are those ((<pattern>) <template>) pairs. Each <pattern> is just that, a pattern of code that will be matched. In our case, we want to match the pattern:

(while condition body ...)

Where the ‘…’ signifies that body may contain one or more forms. Luckily for us, this is exactly the syntax that syntax-rules wants to see, so we can just plug it in, giving us:

(define-syntax while
  (syntax-rules ()
    ((while condition body ...) <template>)))

So far so good. Now we just have to fill in the other half, with a suitable <template>.

Before we can write the <template>, though, we have to decide what we want the code to end up looking like. Since this isn’t a guide to scheme code in general, I’ll just go ahead and say that we want the output to look like:

; Thanks to Alex Shinn for pointing out a mistake
(let loop ()
  (if condition
      (begin
        body ...
        (loop))
      #f))

Got that? Okay, now we’ve just got to put this in our syntax-rules macro as a template. By another startling coincidence, this is exactly what the template code is expected to look like. We just plug in that code, and our final result is:

(define-syntax while
  (syntax-rules ()
    ((while condition body ...)
     (let loop ()
       (if condition
           (begin
             body ...
             (loop))
           #f)))))

Just plug that into your scheme interpreter, and our while loop from earlier should execute perfectly.

Now let’s try to write something a little more complicated. We want to write a for loop similar to the one that Python has. This should be a pretty easy task, since it’s basically just syntactic sugar for scheme’s map function.

Our goal is to be able to write a piece of code taking the form:

(for <element> in <list>
     <body ...>)

And have it expand to:

; Thanks to Alex Shinn for pointing out a mistake
(for-each (lambda (<element>)
       <body ...>) <list>)

Our first try would probably look something like this:

(define-syntax for
  (syntax-rules ()
    ((for element in list body ...)
     (map (lambda (element)
            body ...)
          list))))

This works, but there’s one issue with it. All of the following are valid and work exactly the same:

(for i in '(0 1 2 3 4) (print i))
(for i fnord '(0 1 2 3 4) (print i))
(for i some-other-keyword '(0 1 2 3 4) (print i))

This is not so much of a problem in the case of a for loop, but what if you wanted to add another rule later, so that

(for '(0 1 2 3 4) as i
     (print i))

will also work? The solution to this problem is in that <keywords> argument that we glossed over earlier. Change the keywords list to include ‘in’ (and, for good measure, ‘as’), and it will allow those symbols, and only those symbols, in places where they are mentioned. This change leaves us with:

(define-syntax for
  (syntax-rules (in as)
    ((for element in list body ...)
     (map (lambda (element)
            body ...)
          list))
    ((for list as element body ...)
     (map (lambda (element)
            body ...)
          list))

Or, for simplicity (thanks to Dan Prager for pointing this out)

(define-syntax for
  (syntax-rules (in as)
    ((for element in list body ...)
     (map (lambda (element)
            body ...)
          list))
    ((for list as element body ...)
     (for element in list body ...))))

And if we load this code into our scheme interpreter of choice, we should have two fully functional little bits of new syntax.

Hopefully this guide will help shed some light on the arcane subject that is the Scheme macro system, and hopefully I will never have to learn enough about syntax-case to write a tutorial on it.

15 Comments »

RSS feed for comments on this post. TrackBack URI

Thanks for the article. I learned Scheme from SICP, and never did figure out how syntax-rules was supposed to work. I’ve moved on to clojure now, but I’m glad someone wrote something useful on this topic.

Allen

Comment by Allen — September 11, 2008 #
Hi, nice post. A couple of minor issues:

Your WHILE syntax is different from the definition
usually added as an extension – it always evaluates
the body once, and checks the condition at the end
of the loop like a do-while statement. You probably
want to use

(let loop ()
(if condition
(begin
body …
(loop))
#f))

for the loop template.

The for loop should also use FOR=EACH, not MAP,
partly for efficiency (since it doesn’t accumulate
a list), but mostly because the order of evaluation
for MAP is unspecified, so your example could print
out the numbers 0..4 in any random order.

–
Alex

Comment by foof — September 11, 2008 #
Nice.

One of the promises of macros is to reduce the amount of redundant code, even beyond what can be achieved with higher-order functions.

So, is there a way to re-write the final ‘for-in/as’ example so that the expansion

(map (lambda (element)
body …)
list))

is written only once? Especially without putting it into a separate function, or is that the way to do it and we rely on a ’sufficiently smart compiler’ to inline?

Comment by Dan Prager — September 11, 2008 #
Excellent post! Keep ‘em coming. I’d be interested to know what you think of syntax-rules after doing a similar treatment of syntax-case.

Also, what scheme implementation are you using?

Comment by Dave — September 12, 2008 #
very handy

Comment by Phil Lehar — September 12, 2008 #
nice one, thanks for taking the time to shed some light on it all for newbies like me.

Comment by Raoul Duke — September 12, 2008 #
Dan:

I honestly didn’t think of trying to simplify my code any when I first wrote it, but it appears that changing the macro definition to

(define-syntax for
(syntax-rules (in as)
((for element in list body …)
(map (lambda (element)
body …)
list))
((for list as element body …)
(for element in list body …))))

Works properly. Thanks for pointing that out.

Comment by Will Donnelly — September 12, 2008 #
foof / Alex:

(It’s rather confusing when you have a different name at the top and bottom of the comment. Which one is correct?)

Thanks for pointing out my mistakes. I am not a very practiced Scheme programmer yet, and I hadn’t noticed the FOR-EACH function’s existence. I will be fixing those bits of the post shortly.

I am glad that at least I seem to have gotten the macro parts correct.

Comment by Will Donnelly — September 12, 2008 #
Thanks. That’s the clearest treatment of syntax-rules that I’ve come across.

Comment by Chui Tey — September 12, 2008 #
[...] to Will Donnely’s Primer on Syntax-Rules, I finally got a headstart with Scheme [...]

Pingback by Learning Scheme macros | Chui’s counterpoint — September 20, 2008 #
I just wanted to point out one thing, the macros with print function is not in R5RS and causes a error, but display is.

Nice primer though thanks for the info

Comment by Patrick — March 5, 2009 #
visit us!
newsbox.cc
newsbox.us
nbstatus.wordpress.com
NOW!

Comment by Biagiance — June 11, 2009 #
Hi Will,
Thank for your page, even with some minor flow, it was useful for me to understand macro expansion which was its target.
Something also very hard to understand is the call/cc, if you feel like to write a page on that field, that will be great.
best regards.

Comment by J.P. — June 12, 2009 #
Nice, dude, but “print” isn’t in the R5RS. You should change that to

(define x 0)
(while (< x 5)
(set! x (+ x 1))
(newline)
(write x))

Comment by jj — July 25, 2009 #
Hi! I was surfing and found your blog post… nice! I love your blog. Cheers! Sandra. R.

Comment by sandrar — September 10, 2009 #