Macros

LISP is a ball of mud.
                - Alan J. Perlis

What are macros?

The text of a computer program sits in a text file, frozen and lifeless. Then by some magical process, this inanimate text has life breathed into it!

This animation proceeds though a few stages.

• The text is read and converted from a sequence of characters into an internal representation. This process is typically called parsing. In the case of Scheme, this corresponds to converting the program's text into an s-expression data structure in RAM: a box-and-pointers representation. (It is here that '(a 'b ''c) is converted to (QUOTE A (QUOTE B) (QUOTE (QUOTE C))), and that all text following ; on a line is discarded.)

• The internal representation is then groveled over, and each occurrence of a macro is expanded. This process continues until there are no more macros left in the program.

• Now the program is ready for compilation and execution or direct interpretation, depending on the particular implementation technology being used. It is here that the program itself becomes alive, and is able to take input and produce output.

Implementing macros

(define (my-load filename)
  (eval-no-macros (macro-expand (read-sexpr-from-file filename))
		  '()))

(define (macro-expand expr)
  (if (not (pair? expr))
      expr
      (let ((keyword (car expr)))
        (cond ((equal? keyword 'QUOTE) expr)
	      ((equal? keyword 'LAMBDA)
	       (list 'LAMBDA
	             (cadr expr)
		     (macro-expand (caddr expr))))
	      (else
	       (let ((expander (get-macro-expander keyword)))
		 (if expander
		     (macro-expand (expander expr))
		     (map macro-expand expr))))))))

(define (eval-no-macros expr env)
  (cond ((symbol? expr) (lookup expr env))
        ((pair? expr)
         (cond ((equal? (car expr) 'QUOTE) (cadr expr))
               ((equal? (car expr) 'LAMBDA) (make-lambda expr env))
	       (else
	        (let ((lis (map (lambda (x) (eval-no-macros x env))
				expr)))
		  (my-apply (car lis) (cdr lis))))))
	(else expr)))

(define (my-load filename)
  (my-eval (read-sexpr-from-file filename) '()))

(define (my-eval expr env)
  (cond ((symbol? expr) (lookup expr env))
        ((pair? expr)
	 (let ((keyword (car expr)))
	   (cond ((equal? keyword 'QUOTE) (cadr expr))
		 ((equal? keyword 'LAMBDA) (make-lambda expr env))
		 (else
		  (let ((expander (get-macro-expander keyword)))
		    (if expander
			(my-eval (expander expr) env)
			(let ((lis (map (lambda (x) (eval-no-macros x env))
			                expr)))
			  (my-apply (car lis) (cdr lis)))))))))
	(else expr)))

Digression: what language are your macros written in?

We were above in the fortunate situation of implementing Scheme in Scheme. This meant that the language in which we wrote our macro expanders was itself Scheme. However, it is not always the case that the macro expanders are written in the target language. For instance, in C macros are defined in a very weak language called cpp.

#define DO0(i,n)        for ((i)=0; (i)<(n); (i)++)

main()
{
  int j;
  DO0(j,21) {
   printf("%d %d", j, j*j)
  }
}

In general, if you really need to use macros, and the native macro-expansion system of the language you are writing in is insufficient for your needs, you can use some other macro-expansion language. A particularly popular example of this is the m4 macro language, which is used as a preprocessing step by many language interpreters. There is no reason you can't use it with, eg, C++.

However, even the more powerful m4 is unable to implement the symbolic differentiation macro discussed below.

What macros are good for

In general, macros can be used for two things:

• extending the language with convenient new constructs, to make your program more readable or maintainable
• compensate for difficiencies in the implementation you are using

Macros to force inline code

(define (foo n)
  (if (= n 0)
      0
      (+ (sqr n) (foo (- n 1)))))

(define (sqr x)
  (* x x))

We can ``manually inline'' the code for sqr, leading to

(define (foo n)
  (if (= n 0)
      0
      (+ (* n n) (foo (- n 1)))))

If our implementation was good, it might automatically inline the sqr routine during compilation, or there would be some way to ask it to inline the call. But say our implementation was deficient in this regard. We could then resort to a macro:

(define sqr
  (macro expr
     `(let ((s ,(cadr expr)))
        (* s s))))

In general this should be a last resort, to be used only when all other measures have proven inadequate.

The SWITCH macro

(let ((key (foo x)))
  (cond ((or (equal? key 'one) (equal? key 'uno)) 1)
	((or (equal? key 'two) (equal? key 'dos)) 2)
	((or (equal? key 'three) (equal? key 'tres)) 3)
	((or (equal? key 'four) (equal? key 'quatro)) 4)))

(switch (foo x)
  ((one uno) 1)
  ((two dos) 2)
  ((three tres) 3)
  ((four quatro) 4))

(define (macro-expand-switch expr)
  `(let ((key ,(cadr expr)))
     (cond ,@(map (lambda (clause) (expand-switch-clause 'key clause))
		  (cddr expr)))))

(define (expand-switch-clause key-var clause)
  `((or ,@(map (lambda (k) `(equal? ,key-var ',k))
	       (car clause)))
    ,(cadr clause)))

;;; this plugs into the STk evaluator:
(define switch (macro expr (macro-expand-switch expr)))

A symbolic derivative macro

Instead we could define a macro, to take the symbolic derivative of an expression. So instead of writing

(let ((f complicated-expression-involving-x)
      (df derivative-of-complicated-expression-involving-x-wrt-x))
  ... code using f and df ...)

(with-derivative f df complicated-expression-involving-x x
  ... code using f and df ...)

(define (with-derivative-expander expr)
  (let ((f-var (cadr expr))
	(df-var (caddr expr))
	(complicated (cadddr expr))
	(x-var (caddddr expr))
	(body (cadddddr expr)))
    `(let ((,f-var ,complicated)
	   (,df-var ,(diff complicated x-var)))
       ,body)))

New Variable Names

If we wrote code like

(let ((key 154267))
  (switch lock-type
    ((yale padlock) (foo key))
    ((deadbolt chain) (bar key))
    ((five-button combination) (baz key))))

There are two ways to avoid this problem. One is to wrap code up in lambdas in a place outside the scope of the newly bound variable. The other is to use a variable name that no one else will ever use, thus avoiding any possibility of a collision. To do this, we can define a helper function that uses set! to make up a new symbol every time it's called, and then call it when we want to make up a new variable name.

(define gensym-counter 0)

(define (gensym)
  (set! gensym-counter (+ gensym-counter 1))
  (word 'gen_var_ gensym-counter))

STk> (gensym)
gen_var_1
STk> (gensym)
gen_var_2
STk> (gensym)
gen_var_3
STk> (list (gensym) (gensym))
(gen_var_4 gen_var_5)

(define (macro-expand-switch expr)
  (let ((key-var (gensym)))
    `(let ((,key-var ,(cadr expr)))
       (cond ,@(map (lambda (clause) (expand-switch-clause key-var clause))
		    (cddr expr))))))

Quasiquote

    `(let ((,f-var ,complicated)
	   (,df-var ,(diff complicated x-var)))
       ,body)))

    (list 'let
	  (list (list f-var complicated)
		(list df-var (diff complicated x-var)))
	  body)

Basically, quasiquote is just like regular quote, except that anything inside the quoted form preceded by a comma is evaluated, and anything preceded by a comma-at is evaluated and ``spliced in'', ie has its surrounding parenthesis removed.

Quasiquote is probably easier to figure out by example than by explanation. Here is a table of equivalent code on the left and the right.

with quasiquote	without quasiquote
`foo	'foo
`,foo	foo
`(a b c)	'(a b c)
`(a ,b c)	(list 'a b 'c)
`(a (aa ,b cc) c ,d)	(list 'a (list 'aa b 'cc) 'c d)
`(,@foo)	foo
`(a (aa ,@b cc) c ,d)	(list 'a (cons 'aa (append b '(cc))) 'c d)

For more practice, try some Backquote Exercises.