Custom Splicing Expander

From time to time you need a custom expander . Like when you need to perform some analysis or optimization on an already expanded code before you pass it on to the compiler. Read on to see a rather simple example of such expander.

Before diving into the actual algorithm, the first thing to implement was something that allows for recognizing whether given expression is an expression to be spliced or just an ordinary one. As the syntax-parse supports syntax classes, it was a natural choice to define one that would do exactly that:

(define-syntax-class bblock
  #:description "normal expression or begin block"
  #:attributes (exprs multi?)
  (pattern ((~literal begin) multi ...)
           #:attr exprs #'(multi ...)
           #:attr multi? #t)
  (pattern single
           #:attr exprs #'(single)
           #:attr multi? #f))

This syntax class provides two useful attributes. One attribute always gives a list of expressions this expression represents. For ordinary expressions it is a one-element list, however for the expressions to be spliced it is a multi-element list. It can be said, that the first attribute exprs provides a unifying interface for getting a list of expressions to be spliced in the surrounding context. With the special case of ordinary expressions having only one element in such list.

The second attribute of this class is the multi? flag. If true, it tells us that this expression was a begin block that is getting spliced. It might seem a bit redundant without further context, but let's assume, it will become useful (it will). Also notice that we are really implementing something that Racket expander already can do - but we need the expansion results sooner here!

Now we can design a procedure that performs a single step of the splicing algorithm:

(define (splice-bblocks-step stx)
  (syntax-parse stx
    ((b:bblock ...)
     #:with ((ex ...) ...) #'(b.exprs ...)
     (if (for/or ((m? (in-list (attribute b.multi?)))) m?)
         #'(ex ... ...)
         stx))))

It didn't take long and we can see why the multi? attribute is useful. This procedure first checks whether there is at least one expression that needs splicing. If so, it performs the splicing. But if that is not the case, the original syntax is returned unchanged. Again, it seems a bit redundant - if the splicing step is performed, the resulting syntax would be equivalent to the source one. Yes, but not equal in terms of eq? - and that will become useful later.

Now all we need to do is to repeat this step as many times as needed until no expansions happen. A helper function might help here:

(define ((fix f) start-val)
  (let ((next-val (f start-val)))
    (if (equal? next-val start-val)
        start-val
        ((fix f) next-val))))

If you recognized a kind of canonical higher-order procedure used for finding a fixed point of another procedure, you are right. It should also be obvious by now, why made sure that if no splicing is performed, the original syntax is returned. Meaning the algorithm can be finished really simply:

(define (splice-bblocks stx)
  ((fix splice-bblocks-step) stx))

That was easy, wasn't it? We use this in our little expander when we need to perform some transformations on all spliced expressions before we pass it on to the Racket compiler.

Hope you liked yet another venture down some syntax fun and see ya next time for more!