# 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**.