Common patterns in nanopass

Usually, we have a pattern E have to find from a syntax tree, this is a trivial case in nanopass since it defaults on. For example, if we have a small language have symbols, integers, and addition.

(define-language INT
  (terminals
    (symbol (x))
    (integer (n)))
  (Expr (e)
        x
        n
        (+ e1 e2)))
;;; parser
(define-parser parse INT)

It would be very natural want to reduce any addition on two integers to an integer, like (+ 1 2) reduced to 3, so we write down

(define-pass r : INT (e) -> INT ()
  (T : Expr (e) -> Expr ()
     [(+ ,n1 ,n2) (+ n1 n2)]))
(define f (compose unparse-INT r parse))

In fact, the following code might surprise you

(f '(+ 1 2)) ; ~~> 3
(f '(+ e (+ 1 2))) ; ~~> (+ e 3)

However, if we write (f '(+ e (+ 1 (+ 2 3)))), it produces (+ e (+ 1 5)) which is not good enough. This is the second pattern, which needs a feature provided by nanopass called catamorphism. Thus, we have the following definition. It might have to merge after reduction, so integer? check will postpone to after catamorphism

(define-pass r : INT (e) -> INT ()
  (T : Expr (e) -> Expr ()
     [(+ ,[e0] ,[e1])
      (if (and (integer? e0)
               (integer? e1))
          (+ e0 e1)
          `(+ ,e0 ,e1))]))

The final pattern is exponential expansion, an instance is let* form in Scheme, so we write down the new definition of language

(define-language Scm
  (terminals
   (symbol (x)))
  (Expr (e)
        x
        (let ([x* e*] ...)
          e)
        (let* ([x* e*] ...)
          e)
        (e e* ...)))

The transformation is still straightforward, this time we have to check the result and expand it continually if the result is not stable yet.

(define-pass remove-let* : Scm (e) -> Scm ()
  (T : Expr (e) -> Expr ()
     [(let* ([,x* ,e*]) ,e)
      `(let ([,x* ,e*]) ,e)]
     [(let* ([,x* ,e*] ...)
        ,e)
      (define x (car x*))
      (define e (car e*))
      (define rx* (cdr x*))
      (define re* (cdr e*))
      `(let ([,x ,e]) (let* ([,rx* ,re*] ...) ,e))])
  (let loop ([e-old e])
    (define e-new (T e-old))
    (if (equal? e-new e-old)
        e-new
        (loop e-new))))

To ensure and skip the non-existent forms, we usually also write the following

(define-language Scm1
  (extends Scm)
  (Expr (e)
        (- (let* ([x* e*] ...) e))))
(define-pass remove-let*-final : Scm (e) -> Scm1 ())

Then when we compose them, we are pretty sure there has no let* form anymore in the new language Scm1 if no error occurs.

(define-parser parse Scm)
(define f (compose unparse-Scm1
                   remove-let*-final
                   remove-let*
                   parse))

Of course, since let* form is a linear expansion, we actually can simplify the code by only applying T immediately on generated let* form. But here the point is to explain the pattern, so I use a more general solution that can handle when the pattern occurs on the whole expression produced by pass. An example of this situation is generating the clausal forms for classical logic, you can try to check your understanding of exponential expansion.