macro-magic

7.9

macro-magic

Lîm Tsú-thuàn

This project presents how macro work, by using quoted-expression, we can avoid parser part. The idea of macro is simple: a function operating AST. By operating AST, we can create new syntax for certain usage. Here I present two steps method.

syntax
(parse exp)

In this step we have to distinguish macro and other form, then record macro form define-syntax-rule into environment.

(define (parse exp)
  (match exp
    [`(define-syntax-rule (,name ,pat* ...) ,body)
     (hash-set! macro-env name (macro pat* (unique-binding body)))]
    [else exp]))

You might think why we don’t just use one step, we can do that actually, but price is macro must be defined before usage like C does. Now, let’s take a look at the second step:

syntax
(expand exp)

This step traverses all AST to lookup pattern, if name matched then check pattern matched.

(define (expand exp)
  (match exp
    [`(,name-pat ,pat* ...)
     (let ([macro! (hash-ref macro-env name-pat #f)])
       (when macro!
         (unless (= (length (macro-pat* macro!)) (length pat*))
           (error 'macro "macro pattern mismatching: ~a <-> ~a" (macro-pat* macro!) pat*))
         (define subst (make-hash))
         (for ([name (macro-pat* macro!)]
               [new-name pat*])
           (hash-set! subst name new-name))
         (subst! subst (macro-body macro!))))]
    [else exp]))

1 hygienic macro

With these we already can create macro system that a little bit better than C, but that’s not enough, the problem shows below:

(define-syntax-rule (swap first second)
  (let ([tmp first])
    (set! first second)
    (set! second tmp)))

Without new let, (swap tmp other) produces:

(let ([tmp tmp])
(set! tmp other)
(set! other tmp))

Which definitely wrong, to fix this, we need to let variable produces by macro and provide by macro argument were different. For example:

(let ([tmp19231 tmp])
(set! tmp other)
(set! other tmp19231))

To archieve this, we need new helpers unique-binding and subst!.

syntax
(subst! subst exp)

Replace variables in exp by substitute map(subst)

(define (subst! subst exp)
  (match exp
    [`(,e* ...)
     (map (λ (e) (subst! subst e)) e*)]
    [e (let ([result? (hash-ref subst e #f)])
         (if result? result? e))]))

syntax
(unique-binding exp)

Unique all new bindings in exp

(define (unique-binding exp)
  (match exp
    [`(let ([,name* ,value*] ...) ,body* ...)
     (define subst (make-hash))
     `(let (,@(map (λ (name value)
                     (let ([new-name (gensym name)])
                       (hash-set! subst name new-name)
                       `(,new-name ,value))) name* value*))
        ,@(map (λ (body) (subst! subst body)) body*))]
    [else exp]))

Now, when we record macros in parse, we use unique-binding to update macro body:

(hash-set! macro-env name (macro pat* (unique-binding body)))

When we expand expression, subst! macro parameter with macro argument, because of previous unique-binding, name conflict was resolved.

2 macro without name

Another problem would show up, in Racket, we can see that some language variants even override application, how? The answer is quite simple, because Racket provides #%app in a more fundamental language, then there has no different between the macro at here.

3 final test

Now, let’s test it.

(parse '(define-syntax-rule (swap first second) (let ([tmp first])
                                                  (set! first second)
                                                  (set! second tmp))))
(let ([parsed (parse '(swap a b))])
  (expand parsed))