Macro Walking

Understanding Lisp-macros is hard, even harder is understanding how to effectively use them. Here I delve deeper into code walking through macros on my journey to really understand what makes Lisp macros, and by extension Lisp, unique.

One of the best information sources for advanced macros I have found is the book Let over Lambda, which I'm currently (slowly) making my way through. So far the major take-away from it is that macros are my tool for parsing lisp code [Section 5.4].

The code in this page is written in Guile, but most of it is applicable to any Lisp. Syntax-case appears to be non-standard.

Let Lazy & Symbol Macros

One really simple, but still powerful example of code walking through macros is let-lazy; a variant of let which creates lazy bindings, and only evaluates them on demand. [1].

Just to be clear, the expected behavior is the value of a binding is only evaluated if needed, and then only evaluated once. For example:

(let-lazy ((x (begin (display "Hello\n")
                     10)))
  (+ x x))
⊣ Hello
⇒ 20

(let-lazy ((x (begin (display "Hello\n") 10)))
  'x)
⇒ x

Also note that this isn't possible to achieve with functions in an eager language, since function parameters are evaluated before a function is called.

[1] This assumes that our Lisp already has `delay` and `force` forms. Otherwise they are not much more than wrapping a value in a function, and calling the function to get the value (caching it for future accesses along the way).

My first naïve solution used a simple macro, along with a manual tree-map.

;; apply proc to each node in tree, keeping structure.
;; optionally pass descend: #f to skip a branch.
(define* (tree-map proc tree #:key (descend (const #t)))
  (cond ((not (list? tree)) (proc tree))
        ((null? tree) '())
        ((list? (car tree))
        (cons (if (descend (car tree))
                (tree-map proc (car tree) #:descend descend)
                (car tree))
            (tree-map proc (cdr tree) #:descend descend)))
        (else (cons (proc (car tree))
                    (tree-map proc (cdr tree) #:descend descend)))))

(define (quote? form)
  (and (not (null? form))
       (eq? 'quote (car form))))

(define-macro (let-lazy bindings . body)
  (let ((keys (map car bindings)))
      `(let ,(map (lambda (b) `(,(car b) (delay ,@(cdr b))))
                  bindings)
      ,@(tree-map (lambda (t) (if (memv t keys) `(force ,t) t))
                  body #:descend (negate quote?)))))

It works decently, but quickly brakes down. For example, something as simple as a back-tick in the body breaks it.

(let-lazy ((x (begin  (display "Hello\n") 10))) `x)
⇒ (force x)

And as Let over Lambda mentions, there are many more special forms in a lisp than expected, and continues to issue the following Common Lisp example, where exactly one of the following blah should be expanded.

(let (blah (blah (blah blah)))
  blah)

;; Borrowed from Let over Lambda under fair use.

My updated solution instead uses my underlying Lisp interpreter to handle my variable substitution. In the bellow example I introduce my field mappings in a let-syntax towards the bottom, followed by me giving control back to scheme to figure the rest of the tree out.

(define-syntax let-lazy
  (syntax-rules ()

      ;; Match rule, and capture symbols
      [(_ ((field value) ...)
          body ...)

       ;; give symbols their delayed slots
       (let ((field (delay value)) ...)
          ;; introduce local syntax for replacing fields with
          ;; their forced counterparts
         (let-syntax ((field (identifier-syntax (force field))) ...)
           body ...))])).

The macro is also rewritten in scheme's hygienic macro system. Here it doesn't make a big difference, but identifier-syntax gets happier, and I sleep better knowing that symbols don't slip in our out of macro-expanded code.

Structures and Self Reference

Another more practical example (which actually was written earlier) was my attempt to create objects with an implicit reference to self, similar to C++ or Java. In this example my end goal was a way to generate static configuration files [2], so I could do away with updating slots.

[2] I later realized I just reinvented Puppet.

After expansion my forms look more or less like

(define struct-1
  `(a (b ,(lambda (self) (get-field self '(c)))))).

Of note is that the field /a/b wants the value /c, which is allowed since it doesn't get evaluated before I actually instantiate the object, and that my system allows for rudimentary inheritance.

Before expansion the same information is written:

(struct struct-1 ()
    (a (b ,(? c))))

Which is rather similar. But keep in mind that the (? c) can be deep within arbitrary other code.

The base macro struct is just basic setup, but is here for completeness sake,

;; Comments added for this article.

(define-syntax struct
  (lambda (stx)
    (syntax-case stx ()
      [(_ name (parent ...) (key value ...) ...)

       ;; allow the symbol `?' to be used within the
       ;; input. Required due to hygienic macros
       (with-syntax ((? (datum->syntax stx '?)))
         #'(define name
             ;; Call to inner
             (let ((new-data (inner ? (acc-name ,(symbol->string 'name))
                                    (key value ...) ...)))

               ;; Inheritance (mostly unimportant)
               (lambda (mergable)
                 (alist-merge mergable
                              (fold $ new-data
                                    (list parent ...)))))))])))

Inner is however where all the fun stuff happens! To get it out of the way: all rules takes ? due to above mentioned hygienic macros, the leaves of the tree are wrapped in functions to delay evaluation, and the first case below matches on unquote (,) in a stroke of ~~ingenuity~~ madness when I realized that I could hijack scheme's syntax for my own bidding.

(define-syntax inner
  (syntax-rules (unquote)
    ;; case 1
    [(_ ? (unquote value))
     (lambda (self)
       ;; actually give a value to `?'
       (let-syntax ((? (with-ellipsis
                        .. (syntax-rules ()
                             [(? path ..) (get-field self `(path ..))]))))
         ;; give scheme the job to find all intances of (? ...)
         value))]

    ;; case 2
    [(_ ? (key sub ...) ...)
     (sort* `((key ,(inner ? sub ...)) ...)
            symbol<=? #:get car) ]

    ;; case 3
    [(_ _ v v* ...)
     (lambda _ (values `v `v* ...))]))

Relevant to code walking and macros is case one. The self is captured, the ? is finally given a value through let-syntax, which uses our captured self in a simple call to get-field. The core is still the same as above; introduce a binding with let-syntax and let our scheme do the job of finding all appropriate instances of our symbol. Here we just have more fancy stuff around it.

The scripts in their entirety can be found on GitHub, even though it feels a bit to intimate to share them this way. Struct there is called account, due to the code's original use case.

References

Let over Lambda

Section 5.4, Code-Walking with Macrolet https://letoverlambda.com/index.cl/guest/chap5.html#sec_4
Section 7.7, Pandoric Macros (define-handy-method) https://letoverlambda.com/index.cl/guest/chap6.html#sec_7

Full Scripts

https://github.com/HugoNikanor/dotfiles/blob/5c74da19aa12171495cb8b857cb2cd6135ff4ea1/scripts/conf-base.scm

RSS-feed to see more like this.