Recursive Macros in Racket

Consider the let* special form in Racket. The only difference compared to let is that later bindings can refer to earlier ones.

1
#lang racket
2

3
(let*
4
  ([x 3]
5
   [y (+ x 5)])
6
  (* x y))
7

8
;; => 24

If you think about it, you can rewrite this whole expression without the let*. Consider the nested lambdas:

1
#lang racket
2

3
((lambda (x) ((lambda (y) (* x y)) (+ x 5))) 3)
4

5
;; => 24

Racket provides compile time syntax-rewriting capabilities, so we can implement the let* special form using these capabiliites as follows.

1
#lang racket
2

3
(define-syntax my/let*
4
  (syntax-rules ()
5
    [(my/let* () body) body]
6
    [(my/let* ([var val] rest ...) body) ((lambda (var) (my/let* (rest ...) body)) val)]))

We define two pattern match arms. We can match an empty binding list and a body, in which case we just return the body, or we can match more bindings, in which case we return a lambda that takes the first binding’s name and invokes the lambda with the first binding’s value. The body of the lambda recurses with the tail of the list and the body, unchanged. The my/let* macro can be used similarly to the way let* is.

1
(my/let*
2
  ([x 3]
3
   [y (+ x 5)])
4
  (* x y))

The recursion isn’t special. Trace the execution. At first, there are two bindings, so we hit the second branch.

1
;; first (outer) call =>
2
[(([x 3] rest ...) (* x y)) ((lambda (x) (my/let* (rest ...) (* x y))) 3)]
3
;; second (inner) call =>
4
[(([y (+ x 5)] rest ...) (* x y)) ((lambda (y) (my/let* (rest ...) (* x y))) (+ x 5))]
5
;; third (base) call =>
6
[(() (* x y)) (* x y)]
7
;; second (inner) call =>
8
[(([y (+ x 5)] rest ...) (* x y)) ((lambda (y) (* x y)) (+ x 5))]
9
;; first (outer) call =>
10
[(([x 3] rest ...) (* x y)) ((lambda (x) ((lambda (y) (* x y)) (+ x 5))) 3)]

so the whole thing expands to ((lambda (x) ((lambda (y) (* x y)) (+ x 5))) 3).