Macros are not covered in SICP. I didn’t know how to use macro in scheme until I read Peter Norvig’s JScheme code. Only then I started to understand why “symbol” and “quote” are important to scheme. Scheme macros is similar to C macro, both transform some pattern into another. Scheme macros are more powerful because expansion/transformation happens at run time, and input/output patterns are structured scheme data that represents scheme code.

how is macro used?

Let’s look at an example. We know that let-expression can be replaced by equivalent lambda expression application.

1
2
3
(let ((x 1)(y 2)) (+ x y))
; is the same as
((lambda (x y) (+ x y)) 1 2)

That transformation can be easily defined as a macro.

1
2
3
4
5
6
(define my-let 
(macro (bindings . body)
(append (list (append
(list 'lambda (map car bindings))
body))
(map cadr bindings))))

What the code does, is basically transform input like (my-let ((x 1)(y 2)) (+ x y))into ((lambda (x y) (+ x y)) 1 2). Macro is very similar to functions, except that it’s parameter is quoted code, and it returns quoted code as well. When scheme interpreter sees an macro application, it will

  1. expand macro by applying macro body with parameter bound to quoted parameter expressions (without evaluating them).
  2. evaluate result of macro expansion.

why is macro important to scheme?

One thing I like about macro is it makes scheme interpreter/compiler much easier to implement. To write a scheme interpreter, you only need to implement very few core features (begin, define, lambda/macro, function call, quote, if expression, built-in functions). The rest of the language like let, cond, and, or can all be implemented in macros. JScheme source code uses this approach, and its source code contains a file that defines all these language features with macros. These definitions are reusable when writing scheme interpreter/compiler in the future. It is amazing that that adding a language feature can make the language easier to implement.

What is quasiquotes, unquote and unquote-splicing?

Quasiquote is the same as quote except that you can “unquote” part of the expression.

1
2
3
4
5
6
7
(quote (1 (+ 2 3)))                
; usually written as '(1 (+ 2 3))
; =\> (1 (+ 2 3))

(quasiquote (1 (unquote (+ 2 3))))
; usually written as `(1 ,(+ 2 3))
; => (1 5)

Unquoted code is evaluated instead of being treated as data. The best way to explain unquote-splicing is by example.

1
2
3
4
5
6
7
(quasiquote (1 (unquote-splicing (append (list 2) (list 3))) 4 ))
; usually written as `(1 ,@(append (list 2) (list 3)) 4)
; =\> (1 2 3 4)

; Compare to unquote
`(1 ,(append (list 2) (list 3)) 4)
; =\> (1 (2 3) 4)

These are utilities that make macro much easier to write. “my-let” above can be written as

1
2
3
4
(define my-let 
(macro (bindings . body)
`((lambda ,(map car bindings) . ,body)
,@(map cadr bindings))))

It might be brain twisting when looking at these for the first time, but it will start to make more sense when started writing more macros. Surprisingly, quasiquote, unquote, unquote-splicing can be implemented with macros. Following implementation is written by Darius Bacon, and I copied it from JScheme code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(define quasiquote 
(macro (x)
(define (constant? exp)
(if (pair? exp) (eq? (car exp) 'quote) (not (symbol? exp))))
(define (combine-skeletons left right exp)
(cond
((and (constant? left) (constant? right))
(if (and (eqv? (eval left) (car exp))
(eqv? (eval right) (cdr exp)))
(list 'quote exp)
(list 'quote (cons (eval left) (eval right)))))
((null? right) (list 'list left))
((and (pair? right) (eq? (car right) 'list))
(cons 'list (cons left (cdr right))))
(else (list 'cons left right))))
(define (expand-quasiquote exp nesting)
(cond
((vector? exp)
(list 'apply 'vector (expand-quasiquote (vector->list exp) nesting)))
((not (pair? exp))
(if (constant? exp) exp (list 'quote exp)))
((and (eq? (car exp) 'unquote) (= (length exp) 2))
(if (= nesting 0)
(second exp)
(combine-skeletons ''unquote
(expand-quasiquote (cdr exp) (- nesting 1))
exp)))
((and (eq? (car exp) 'quasiquote) (= (length exp) 2))
(combine-skeletons ''quasiquote
(expand-quasiquote (cdr exp) (+ nesting 1))
exp))
((and (pair? (car exp))
(eq? (caar exp) 'unquote-splicing)
(= (length (car exp)) 2))
(if (= nesting 0)
(list 'append (second (first exp))
(expand-quasiquote (cdr exp) nesting))
(combine-skeletons (expand-quasiquote (car exp) (- nesting 1))
(expand-quasiquote (cdr exp) nesting)
exp)))
(else (combine-skeletons (expand-quasiquote (car exp) nesting)
(expand-quasiquote (cdr exp) nesting)
exp))))
(expand-quasiquote x 0)))

To be honest I still don’t full understand the code, but I did some tests and was convinced it works.

What is hygiene macro?

Macros are powerful, but there is an issue when used in practice. Consider following example

1
2
3
4
5
6
7
(define plus-one
(macro (x)
`(let ((one 1))
(\+ ,x one))))

(plus-one (begin (set! one 2) 1))
; (let ((one 1)) (+ (begin (set! one 2) 1) one))

User code might modify variables defined in macro body and cause unexpected behavior. Hygiene macro addresses this problem by replacing variables defined in macro body with unique identifiers dynamically so that user don’t have to worry about naming collision. R5RS scheme has syntax-rules syntax which supports hygiene macro and pattern matching features. There are many resources on web about syntax-rule like this, and I still don’t understand it’s pattern matching mechanism well. But surprisingly again, syntax-rules can be implemented with regular macro as well! I found this implementation in JScheme home page.

What else can macro do?

It is possible to extend scheme language feature with macro. One example is stream (infinite length list) processing. Scheme does not natively support stream processing, but it is easy to add steaming support using macro.

1
2
3
4
(define stream-cons (macro (a b) `(cons ,a (lambda () ,b))))
(define stream-car car)
(define stream-cdr (lambda (s) ((cdr s))))
(define stream-null? null?)

Here is a program that creates infinite stream of prime numbers using Sieve of Eratosthenes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (stream-map f s)
(if (stream-null? s)
'()
(stream-cons (f (stream-car s)) (stream-map f (stream-cdr s)))))

(define (stream-filter f s)
(cond
((stream-null? s) '())
((f (stream-car s)) (stream-cons (stream-car s) (stream-filter f (stream-cdr s))))
(else (stream-filter f (stream-cdr s)))))

(define ones (stream-cons 1 ones))

(define ints (stream-cons 1 (stream-map (lambda (x) (+ x 1)) ints)))

(define evens (stream-filter (lambda (x) (= 0 (modulo x 2))) ints))

(define (sieve s)
(let ((fst (stream-car s)))
(stream-cons fst
(sieve (stream-filter (lambda (x) (not (= 0 (modulo x fst)))) (stream-cdr s))))))

(define prime (sieve (stream-cdr ints)))

Macro is such a simple yet powerful feature that makes scheme a beautiful languages. I am still learning and being surprised by what macro can do.