Metaprogramming Ale
When I first saw Lisp code, my immediate reaction was “Wow, that’s a lot of parentheses!” I then backed up from the computer, turned around, walked away, and didn’t look at it again for years. I had convinced myself that any language that doesn’t have rich grammatical productions and super clean syntax couldn’t possibly be of any value. But that’s because I was young and stupid.
I remained stupid until my mid 40s. And then something happened. Although I had been designing and developing languages for about a decade at that point, I had never studied language design at a theoretical level. So when I finally did, I was blown away. Lambda calculus, why had I never heard of it!? Prolog, it’s like magic! I’d been missing out!
And then came Lisp.
Yes, there are a lot of parens, but that is a small price to pay for a language that is capable of morphing itself into nearly anything you need it to be. And the way that Lisp does that is with a macro system that puts #define
to shame!
(define-macro)
The power of Lisp derives from its ability to manipulate symbols and the fact that it’s a homoiconic language. By homoiconic I mean that the way Lisp represents data and code is identical. The implications here are that Lisp is able to create and evaluate Lisp code just as easily as creating a list or vector. How many other languages do you know that can do that? Not many. Maybe none.
So are you ready to have your mind blown? Type this in the Ale REPL:
define-macro
It’s going to spit out something like this:
{:instance "0x5366d0" :type macro}
So define-macro
, the low-level way that we define macros in Ale, is itself a macro! That’s how meta Lisp is!. And what is a macro? It’s nothing more than a function that’s been singled out to play a special role during the compilation of Ale code.
A Question of When
You may have heard of the concept of Metaprogramming before. It basically boils down to “programs writing programs.” The form it takes varies wildly between languages. For example, Ruby has made a form of it commonplace by abusing method_missing
. This means that a runtime attempt to call a method that doesn’t exist can be intercepted, allowing a stand-in method to be invoked instead. A friend of mine even wrote a book about it. He’s coding in Java these days.
But there’s a huge difference between the way Ruby and Lisp do it, and it’s a difference of “when?” The way that a Lisp programs are processed follows a few potentially independent steps. And it’s important to understand those steps to get the most out of Lisp macros. At the highest level, Lisp breaks the processing of a program down to two steps:
Read and Eval
Imagine we’re going to execute a Lisp expression such as the following:
(when happy (println "hello"))
The first thing Lisp will do is hand the program’s source code into the read
function. This function is responsible for scanning a stream of tokens and converting them into raw data structures. In this case, it will recognize these eight distinct tokens:
( ;; list start token
when ;; unqualified symbol
happy ;; unqualified symbol
( ;; list start token
println ;; unqualified symbol
"hello" ;; a string
) ;; list end token
) ;; list end token
It then converts those tokens into the proper data structures. In this case, it would be creating a list that contains three elements: The when
symbol, the happy
symbol, and another list that contains the println
symbol and the string "hello"
. If you were going to cons
your way to this structure, it might look like this:
(cons (sym "when")
(cons (sym "happy")
(cons (cons (sym "println")
(cons "hello" '()))
'())))
Lisp then hands the materialized data structures over to the eval
function. Eval will then inspect the data structure to see if there’s anything it can do with it. In this case it sees that we have an unquoted list. That means it should attempt to interpret the list as a function call.
A function call in Lisp takes the form: (operator args*)
, where operator is an expression capable of evaluating to a function, and args is any number of evaluable expressions that will serve as the function’s arguments. The function will then be applied to those arguments.
So the first thing the Lisp interpreter has to do is figure out what when
’s deal is. If it sees that it’s a symbol and that symbol resolves to a registered function, then there’s not much more we need to do. We just grab the function, evaluate the arguments, apply the function to the arguments, and then return the result. But what if when
refers to a macro? Well then we have some work to do.
Macro Expansion
If when
refers to a macro then we don’t evaluate the arguments. Instead we apply the macro function directly to the arguments’ raw data structures. Then, whatever is returned by that call is re-evaluated until there is no macro expansion left to be performed.
And just so we understand, here is what the when
macro looks like in Ale:
(define-macro when
[(test) null]
[(test form) `(if ,test ,form null)]
[(test . forms) `(if ,test (begin ,@forms) null)])
This means that if you pass a single argument to it, it will simply replace that single argument with the empty list, because there’s nothing it needs to do based on the test
condition. If you pass two arguments, it will treat form
as a stand-alone expression to be performed if the test
condition is met. If you pass more than two arguments, it will wrap the forms
in a do
block to be performed if the test
condition is met.
In the case of our example, the when
macro will return the following:
(if happy (println "hello") '())
In this case, if
is a special form and println
resolves to a function, so there is no more macro processing that needs to be performed. It can simply evaluate the expression. If happy
resolves to a truthy value, the println
expression is performed. Otherwise the empty list is returned.
Read, Expand, Compile, Eval
Ale takes a slightly different route when running programs. Whereas interpreted Lisps will wrap the macro expansion step into the evaluation of an expression, Ale performs the macro expansion before a compilation step. So by the time we compute the result of an expression, the code has been completely expanded, digested, and converted into abstract machine instructions.