Metaprogramming 101: A Gentle Introduction

Apparently many people accused my previous essay of being “too light on substance.” Clearly, none of you have read Rich Hickey’s Hammock Driven Development (which I recommended a long time ago). The world doesn’t lack code; it lacks ideas. You want substance. Fine, let’s serve up some substance. As it happens, a reader recently complained in the comments that my earlier essay “On Abstraction” didn’t satisfy his appetite: although he had learned Clojure, he could never get a clear grasp of how to use macros. He could follow the examples in books, but once he left the examples he stumbled at every step, and he always felt that his understanding of metaprogramming was somewhere between “beginner” and “not yet a beginner.” So this essay will do some real work: it attempts, in plain language, to provide a small introduction to metaprogramming / macros, mainly to clarify a few concepts and ideas. Words and code together—any empty bottles to sell? Examples will combine Clojure and Elixir; all code will be as short as possible and, unless otherwise noted, can be run directly in the REPL. It doesn’t matter if you don’t know Clojure / Elixir; grasping the concepts and ideas is far more important than being able to write the code.

The previous essay already gave an example of abstracting a problem into rules and then programming against those rules. Although that can be called metaprogramming in a broad sense, for the sake of a clear definition we should still look at how Wikipedia explains metaprogramming:

Metaprogramming is the writing of computer programs with the ability to treat programs as their data. It means that a program could be designed to read, generate, analyse or transform other programs, and even modify itself while running.

Strictly speaking, then, metaprogramming means treating code as data and then writing code that generates and transforms code, so that a program gains additional capabilities. How can code be treated as data? This brings us to the first important concept in metaprogramming: the Abstract Syntax Tree (AST, or syntax tree for short).

AST

We know that in almost any language, during “compilation” (interpreted languages also have a compilation phase at runtime), code produces a tree-shaped intermediate representation: the AST. The AST describes the execution order and execution logic of the subexpressions/statements within each expression/statement, so it can be conveniently translated into target code—machine code (or assembly) for C, bytecode for interpreted languages such as JavaScript, and JavaScript for ClojureScript. (Yes, the target code of an AST can be the source file of another language.)

Lisp (in what follows, Lisp means its dialect Clojure) is a language that directly exposes AST-like syntax to the programmer. As a result, its syntax can look very awkward:

> (* 5 (+ 1 2))
> (if (< n 10) "yes" "no")

But if you look at this code from the perspective of a syntax tree, it is not so hard to understand:

AST := (operator lhs rhs)

Here, lhs is the left subtree (expression), and rhs is the right subtree. By nesting lhs / rhs repeatedly, one can generate syntax trees for very complex expressions.

Elixir is not a Lisp-family language, and its syntax is completely different from Lisp, but from the very beginning of its design it also considered exposing the syntax tree to programmers:

iex(5)> quote do: 5 * (1 + 2)
{:*, [context: Elixir, import: Kernel],
 [5, {:+, [context: Elixir, import: Kernel], [1, 2]}]}

At first glance, this representation seems very different from Lisp’s (* 5 (+ 1 2)), but if we simplify it by removing the metadata ([context: Elixir, import: Kernel]), the two are completely equivalent apart from the symbols used:

{:* [5, {:+, [1 2]}]}
# rewrite {}, [] as ()
(:* (5, (:+ (1 2))))
# remove extra parentheses
(:* 5, (:+ 1 2))

Whether a language has sufficiently powerful metaprogramming capabilities depends on the degree to which it exposes its own syntax tree to programmers. Exposing the syntax tree to programmers means they can manipulate it like data and perform the transformations they want. From this perspective, metaprogramming power ranks as follows: Lisp >= Elixir >> Ruby > Python >> Java/C# >> C/C++.

quote / quasiquote / unquote

Once we understand the place of the AST in metaprogramming, we immediately need to know two things:

• How to obtain the syntax tree of a piece of program
• How to transform an existing syntax tree

Let’s look at the former first. Here we encounter two important concepts: syntax quote / unquote. Syntax quote provides programmers with an AST, while unquote lets programmers obtain the value of a subexpression when accessing an AST. These two concepts are quite abstract and hard to understand. Before giving concrete examples, and to make your understanding even more difficult, let’s look again at how Wikipedia defines these concepts in Lisp:

First, quote:

Any expression can also be marked to prevent it from being evaluated (as is necessary for symbols and lists). This is the role of the quote special operator, or its abbreviation ’ (a single quotation mark).

Lisp’s quote is not syntax quote; its role is to not evaluate the expression and instead return the original expression directly. Let’s compare:

user=> (* 5 (+ 1 2))
15
user=> '(* 5 (+ 1 2))
(* 5 (+ 1 2))

Because it does not return an AST (though it is very close to one), Lisp’s quote is not the protagonist in metaprogramming. The real protagonists are quasiquote (what we call syntax quote) / unquote:

This (quasiquote) is almost the same as the plain quote, except it allows expressions to be evaluated and their values interpolated into a quoted list with the comma, unquote and comma-at ,@ splice operators. If the variable snue has the value (bar baz) then (foo ,snue) evaluates to (foo (bar baz)), while (foo ,@snue) evaluates to (foo bar baz). The backquote is most frequently used in defining macro expansions.

All right, it’s fine if you don’t understand; let’s keep comparing:

user=> (* 5 (+ 1 2))
15
user=> '(* 5 (+ 1 2))
(* 5 (+ 1 2))
user=> `(* 5 (+ 1 2))
(clojure.core/* 5 (clojure.core/+ 1 2)) ;; note how it differs from quote
user=> `(* 5 ~(+ 1 2)) ;; ~ means unquote; Clojure's notation differs slightly from Common Lisp
(clojure.core/* 5 3)  ;; ~ causes this expression (+ 1 2) to be evaluated

To make it easier to understand what ~ actually is, let’s quote it and see what manner of creature it is:

user=> (def a (list 1 2))
#'user/a
user=> '(a, ~a, ~@a)  ;; quote
(a (clojure.core/unquote a) (clojure.core/unquote-splicing a))
user=> `(a, ~a, ~@a)  ;; quasiquote
(user/a (1 2) 1 2)

That makes it quite clear.

Elixir, by contrast, has no concept of quote as in Lisp (because it doesn’t need one); it has only syntax quote / unquote, with the syntax quote do ... end and unquote(expression). Let’s look again at the earlier example:

iex(5)> quote do: 5 * (1 + 2)
{:*, [context: Elixir, import: Kernel],
 [5, {:+, [context: Elixir, import: Kernel], [1, 2]}]}
iex(6)> quote do: 5 * unquote(1 + 2)
{:*, [context: Elixir, import: Kernel], [5, 3]}

Only after understanding syntax quote / unquote can we move on to the concept of macros—that is, the second thing: how to transform an existing syntax tree.

macro

(Note: since most readers have no background in Lisp, the following examples are all expressed in Elixir. Anyone who knows Python / Ruby should basically be able to follow Elixir.)

Many people’s vision goes dark when they see macros, and they always feel that macros represent some mysterious power. When we encounter something we cannot understand, we tend to mystify it and then worship it—such has been human habit since ancient times. In many books that discuss macros, the explanation is vague and unclear; even Wikipedia rambles on for a whole paragraph without explaining what macros really mean:

A macro in Lisp superficially resembles a function in usage. However, rather than representing an expression which is evaluated, it represents a transformation of the program source code. The macro gets the source it surrounds as arguments, binds them to its parameters and computes a new source form. This new form can also use a macro. The macro expansion is repeated until the new source form does not use a macro. The final computed form is the source code executed at runtime.

Actually, we can think of a macro as a special function that accepts a syntax tree (or several) as its arguments and returns a syntax tree. That’s it. This is also why a macro’s return value can only be syntax-quoted code. Remember this well; many beginners make a great many mistakes here.

Let’s examine macros carefully from their inputs and outputs. Studying inputs and outputs is also the first step toward understanding any system.

Below is the simplest possible example in Elixir (don’t worry about the syntax for now). It defines unless, which should be familiar to anyone who has used Ruby. This example implements the functionality of unless, but its main purpose is to print the macro’s input and output:

# Since Elixir macros can only be defined in a module, this code must be written in a file
defmodule ControlFlow do
  defmacro unless(expression, do: block) do
    IO.puts("#{inspect expression}, #{inspect block}")
    result = quote do
      if !unquote(expression), do: unquote(block)
    end
    IO.puts("#{inspect result}")
    result
  end
end

iex(1)> require ControlFlow
nil
iex(2)> ControlFlow.unless 1 == 2, do: 3 + 4
{:==, [1, 2]}, {:+, [3, 4]}
{:if, [{:!, [{:==, [1, 2]}]}, [do: {:+, [3, 4]}]]}
7

(Note: for clarity, I have removed the AST metadata from the return values above.)

From this we can clearly see that the macro’s inputs are two ASTs: the AST for 1 == 2 and the AST for 3 + 4. In this code, we transform unless into if !, so the returned result is an AST related to an if statement.

Note that when we want to obtain the value of the original expression, we need to use unquote to get the expression’s value rather than its AST. Using unquote in the right places is a basic skill in writing macros.

When using macros for metaprogramming, one of the most common pitfalls is repeated evaluation of expressions. Let’s look at a function:

iex(1)> f = fn(a,b) ->
...(1)>   IO.puts("#{inspect a}, #{inspect b}")
...(1)> end
#Function<12.54118792/2 in :erl_eval.expr/5>
iex(2)> f.(1, 2+3)
1, 5
:ok

In this function, we can use and manipulate the variable b as much as we like, because the value of b has already been computed when it is passed into the function. Using b multiple times has no negative effect. But in a macro, using unquote on an expression multiple times causes it to be evaluated multiple times. Let’s modify the earlier unless example slightly by adding a print statement:

defmodule ControlFlow do
  defmacro unless(expression, do: block) do
    IO.puts("#{inspect expression}, #{inspect block}")
    result = quote do
      IO.inspect unquote(expression)  # newly added print
      if !unquote(expression), do: unquote(block)
    end
    IO.puts("#{inspect result}")
    result
  end
end

To make the result clearer, let’s write a compare function and then use unless:

iex(3)> compare = fn(a, b) ->
...(3)>   IO.puts "function get called"
...(3)>   a == b
...(3)> end
#Function<12.54118792/2 in :erl_eval.expr/5>
iex(4)> ControlFlow.unless compare.(1, 2), do: 3+4
{{:., [line: 4], [{:compare, [line: 4], nil}]}, [line: 4], [1, 2]}, {:+, [line: 4], [3, 4]}
{:__block__, [], [{{:., [], [{:__aliases__, [alias: false], [:IO]}, :inspect]}, [], [{{:., [line: 4], [{:compare, [line: 4], nil}]}, [line: 4], [1, 2]}]}, {:if, [context: ControlFlow, import: Kernel], [{:!, [context: ControlFlow, import: Kernel], [{{:., [line: 4], [{:compare, [line: 4], nil}]}, [line: 4], [1, 2]}]}, [do: {:+, [line: 4], [3, 4]}]]}]}
function get called   # first call
false
function get called   # second call
7

We can see that the function was executed twice. This kind of inadvertent repeated evaluation of expressions inside macros is a common mistake when writing macros, because we have not correctly completed the paradigm shift from function to macro.

In Elixir, unquote() must be called explicitly, so it is relatively easy to notice, and Elixir also provides bind_quoted to avoid this problem. In Lisp, unquote is a simple symbol (Clojure uses ~ for unquote, for example), so it is very easy to misuse. Lisp does not provide anything like bind_quoted, but we can use let-binding to bind an unquoted AST and reuse it.

I accidentally wrote such a long piece, but as an introduction to the concepts of metaprogramming, it should be enough. By now we should understand the basic concepts and roles of ASTs, syntax quote / unquote, and macros.