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