Eric Holk

You wouldn't like me when I'm not coding.

A Look at Macros in Scheme

One of the features that sets Scheme apart as a programming language is its powerful macro system. In the same way that procedures allow you to reuse bits of code, macros allow you to reuse syntax. Macros and procedures can express many of the same things, but macros are particularly useful when you want to be careful about control flow and effects. Consider the following program.

1
(choose-arg 1 (factorial 5) (+ 1 2) (fibonacci 40))

Here, choose-arg takes a number and some arguments. The whole expression should evaluate to the argument selected by the number argument. The example above should return 3. As a procedure, choose-arg might be written as follows:

1
2
3
4
5
(define choose-arg
  (lambda (i . args)
    (if (zero? i)
        (car args)
        (apply choose-arg (- i 1) (cdr args)))))

Using this definition (and appropriate definitions for factorial and fibonacci), we see that our starting example returns 3 as expected. Unfortunately, it takes a lot longer than we’d like:

1
2
3
4
5
(time (choose-arg 1 ...))
    no collections
    11167 ms elapsed cpu time
    11168 ms elapsed real time
    144 bytes allocated

That’s over 11 seconds to decide the answer is 3. What’s going on?

This takes so long because Scheme is an eager language, meaning it must fully evaluate all procedure arguments before applying a procedure. My version of Fibonacci takes exponential time, so (fibonacci 40) is somewhat nontrivial. What we’d really like is to only evaluate the argument we actually selected with choose-arg.

One way to do this is by using thunks. We just wrap all of the arguments in lambdas with no arguments, and wrap an extra set of parentheses around the call to choose-arg to evaluate the thunk we selected:

1
((choose-arg 1 (lambda () (factorial 5)) (lambda () (+ 1 2)) (lambda () (fibonacci 40))))

This performs much better:

1
2
3
4
5
(time ((choose-arg 1 ...)))
    no collections
    0 ms elapsed cpu time
    0 ms elapsed real time
    192 bytes allocated

Unfortunately, the program is now much harder to read. What we’d really like is to write our original program, but have Scheme execute it as if we had written something like this:

1
2
3
4
5
6
(if (= 1 0)
    (factorial 5)
    (if (= 1 1)
        (+ 1 2)
        (if (= 1 2)
            (fibonacci 40))))

This is exactly what macros let us do. Macros let us define syntax transformers, which take one part of your program as input and rewrite it into a different program. As a macro, we could write choose-arg like this:

1
2
3
4
5
6
7
8
(define-syntax choose-arg
  (syntax-rules ()
    ((_ i e)
     (if (= i 0) e))
    ((_ i e e* ...)
     (if (= i 0)
         e
         (choose-arg (sub1 i) e* ...)))))

While a full explanation of syntax-rules will have to wait for another post, let’s take a minute to make sure we have some idea what’s going on. We define macros with syntax-rules by giving a set of input and output patterns. Program fragments that match an input pattern are replaced with the output pattern. Our choose-arg macro has two sets of patterns. The first one matches things like (choose-arg 5 (+ 1 2)) and replaces it with (if (= 5 0) (+ 1 2)). Notice that the i and e in the output pattern are replaced with the code fragment from the input pattern. The second pattern is similar, except that the e* ... portion can match any number of instances. The second one would take (choose-arg 1 'a 'b) and transform it into (if (= 1 0) 'a (choose-arg 1 'b)). Macros keep expanding, so the next time around, the application of choose-arg would match the first pattern.

This version has the performance we would like, while also letting us write the code as we would like. Still, performance is not the most compelling reason to use macros. For any given problem, some languages are better at expressing the solution than others. Rather than having to choose the best language among many imperfect choices, macros let the programmer write their code in a language they have created for the program at hand. Additionally, macros make things easier for the language implementor because they can focus on high quality implementations for a small set of core forms and express the other forms as macros that expand to these core forms. For example, just lambda and if is enough to implement many more forms like let, let*, or, and, cond, etc.

Comments