Quote-unquote "macros"

You’ve probably seen this Python 101 thing before:

@memoized
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Leaving aside the absurdity of computing Fibonacci numbers recursively, it’s a common first introduction to Python decorators and higher-order functions. fib is just a function, and memoized takes that function and returns a new function (or something with a __call__ method) that, you know, memoizes the result.

Python’s decorators give us a nice notation for writing this, but we could write the same thing in any dynamic language with first-class functions. Like JavaScript:

const memoized = (f) => {
  const results = new Map();
  return (x) => {
    if (results.has(x)) {
      return results.get(x);
    } else {
      const result = f(x);
      results.set(x, result);
      return result;
    }
  }
}

let fib = (n) => {
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

fib = memoized(fib);

And we’ll just gloss over, like, value equality and variadic functions and the memory leak this will cause.

Is this useful? Probably not, but that’s not the point. The point is that it’s a simple concrete example of an abstract idea – higher-order functions, or decorators, or basic metaprogramming. It’s pedantically useful, even if it’s not practically useful.

So now let’s talk about macros.

We could use macros to implement something like Python’s decorators – a better notation for doing something that we can already do without them. And this is great! Within limits, this is great. But that’s not what this blog post is about.

Instead, I want to talk about something that you can’t really do without macros. A new expressive power that macros enable, something more than just notational freedom.

So bear with me for a moment, because I know this is a little silly. But let’s consider the following alternative memoization scheme:

(defn dumb-example [x]
  (while (some-complicated-stuff-happens)
    (pretend-like-this-function-is-big))

  (def result (memoize (do-something-very-expensive x)))

  (do-more-interesting-work))

Instead of memoizing a function to return a new memoized function, I want to memoize an expression. The memoized examples we saw earlier took place on the callee side – the function declaration – but here I want the memoization to happen on the caller side – at the function invocation.

I want it to be the case that this function only actually calls do-something-very-expensive once per unique value of x, even across separate invocations of dumb-example. And if you can stop wondering why you’d want to do this, think for a moment about how you would do this. How could you even write this in JavaScript?

We’ll simplify it a little: instead of worrying about arbitrary expressions, let’s assume that this is always a function call with a single argument, like we did before:

const dumbExample = (x) => {
    while (someComplicatedStuffHappens()) {
        pretendLikeThisFunctionIsBig();
    }

    const result = memoize(doSomethingVeryExpensive, x);

    doMoreInterestingWork();
}

How do you implement memoize?

I think that you basically can’t, in JavaScript. Or, more accurately: I can’t think of a way to do it.¹

You can easily implement something very similar:

const resultMap = new Map();
const dumbExample = (x) => {
    while (someComplicatedStuffHappens()) {
        pretendLikeThisFunctionIsBig();
    }

    const result = memoize(resultMap, doSomethingVeryExpensive, x);

    doMoreInterestingWork();
}

If you can manually find a place to hoist the memoization dictionary. And, you know, in practice this would be completely fine. But it wouldn’t teach us anything new.

The problem is that we need some place to store the results that’s somehow tied to this callsite. Not the function, not the program containing the function, but this particular invocation of memoize.

And macros let us do exactly that: a macro will let us allocate, at compile time, a dictionary of results which we can then reference at runtime.

Which would have been a very surprising statement to me, a few years ago. Before I started writing Janet, I thought that macros were syntactic transformations. And in some languages – Rust or OCaml, say – that’s exactly what they are. Syntactic transformations, AST twisters, token shufflers. Still very useful! But you can’t write a purely syntactic macro that admits per-callsite memoization.²

But in Janet, and some other lisp-family languages, macros are so much more than syntactic transformations. They’re ways to execute code – any code – and dynamically generate new functions – any functions – which will become our eventual program. Let’s take a look:

(defmacro memoize [[f & args]]
  (def results @{})
  ~(let [f ,f
         args [,;args]
         memoization-key [f args]]
    (if (has-key? ,results memoization-key)
      (in ,results memoization-key)
      (let [result (f ;args)]
        (put ,results memoization-key result)
        result))))

(memoize (+ 1 2))

Set aside the horrific hygiene crimes in this macro definition, and just think about results. We allocated that at compile time, during macro expansion. Just one table! And then we unquoted multiple references to it into our macro expansion.

And this absolutely does not work.

It doesn’t work because unquote puts this table into the abstract syntax tree of our function, and tables, when they’re interpreted as abstract syntax trees and evaluated by Janet, create new tables. The empty table @{} is just how Janet represents the abstract syntax tree for an empty table literal.

So if we look at the macro expansion for our call:

(let [f +
      args [1 2]
      memoization-key [f args]]
  (if (has-key? @{} memoization-key)
    (in @{} memoization-key)
    (let [result (f (splice args))]
      (put @{} memoization-key result)
      result)))

We’re allocating a brand new table every time we reference it! We didn’t put “a reference to the table we allocated at compile time” into the function. We put “the abstract syntax tree of a table literal” into our function. It doesn’t matter that every one of those tables in the abstract syntax tree is actually the same table. When Janet’s compile function sees a table – any table – it interprets that as “allocate a new table.”

So we need some way to say “no no no, this value isn’t an abstract syntax tree; it’s just a value. I just want a literal reference to this exact table that I allocated at compile time; I don’t want you to interpret it as an abstract syntax tree at all.”

And you can do that, by quoting the table:

(defmacro memoize [[f & args]]
  (def results @{})
  ~(let [f ,f
         args [,;args]
         memoization-key [f args]]
    (if (has-key? ',results memoization-key)
      (in ',results memoization-key)
      (let [result (f ;args)]
        (put ',results memoization-key result)
        result))))

(memoize (+ 1 2))

We still unquote results, but we unquote it inside a quote form. We quote-unquote the table.

And this works! Every time this macro invocation appears, it will expand to an abstract syntax tree like this:

(let [f +
      args [1 2]
      memoization-key [f args]]
  (if (has-key? (quote @{}) memoization-key)
    (in (quote @{}) memoization-key)
    (let [result (f (splice args))]
      (put (quote @{}) memoization-key result)
      result)))

And, well, you can’t see this when we print it out like this, but every one of those tables is still the same table. Maybe this is an easier way to visualize what’s happening:

(let [f +
      args [1 2]
      memoization-key [f args]]
  (if (has-key? (quote <pointer-to-our-one-table>) memoization-key)
    (in (quote <pointer-to-our-one-table>) memoization-key)
    (let [result (f (splice args))]
      (put (quote <pointer-to-our-one-table>) memoization-key result)
      result)))

And any time Janet evaluates (quote _), it doesn’t look at the thing being quoted. It just returns it. Even if it’s a reference-style, mutable value like it is here.

This was a very long way to point out a pretty simple thing, but I wanted to write this post because I wish that I’d understood this sooner. It took a long time before quote “clicked” for me. I was using quote to write macros long before I actually understood how it worked, but I was not using it to its fullest.

If you’d asked me two years ago, I probably would have said that quote “returns the abstract syntax tree representing its argument.” (+ 1 2) is 3, and '(+ 1 2) is the abstract syntax tree ['+ 1 2] that represents that function call.

And while this seems kinda right, it’s just not. quote doesn’t “return the abstract syntax tree” of anything. quote returns whatever you hand it. The abstract syntax tree ['+ 1 2] came from the Janet parser. The parser created that; quote had nothing to do with it. quote just forwarded it along.

Even the fact that I’m using '+ to mean “the symbol that is just the plus sign” is a little funny. Maybe it’s easier to think of this as the abstract syntax tree [(symbol "+") 1 2]. The symbol, once again, came from the parser, not the quote. But I’m just so used to thinking of '+ as “the way you write a symbol literal.”

Anyway, we can observe this property of quote in a much simpler – albeit stranger – scenario. What does this function do?

(defn foo []
  (def x @{})
  (put x (length x) true)
  x)

It’s not a trick question; it does what you’d expect:

repl:1:> (foo)
@{0 true}
repl:2:> (foo)
@{0 true}
repl:2:> (foo)
@{0 true}

But what about this one?

(defn foo []
  (def x '@{})
  (put x (length x) true)
  x)

It’s… well, it’s not a trick question either, but this definitely would have confused me earlier in my Janet career:

repl:1:> (foo)
@{0 true}
repl:2:> (foo)
@{0 true 1 true}
repl:3:> (foo)
@{0 true 1 true 2 true}
repl:4:> (foo)
@{0 true 1 true 2 true 3 true}

It’s the same table every time, because there was only ever one table in the first place: the table that the Janet parser allocated to represent the abstract syntax tree of the characters @{}.

And we’re mutating it.

Neat.

Is this useful? Well… it’s sort of like a static storage qualifier…? But… but no. It’s not really useful. I struggle to even think of a situation where you would want a per-callsite (memoize), and in any case it would be easier to write that particular macro without using quote-unquote at all:

(defmacro memoize [form]
  (def results @{})
  (defn memoize-call [f & args]
    (def memoization-key [f args])
    (if (has-key? results memoization-key)
      (in results memoization-key)
      (let [result (f ;args)]
        (put results memoization-key result)
        result)))
  ~(,memoize-call ,;form))

In this version we allocate a single closure at compile time, and insert a reference to that into the expanded form. The closure refers to the shared table, and we no longer have to think about gensym, or argument evaluation order, or quote-unquoting, or anything else. We’re back in the safe land of writing normal code with values and closures, instead of the weird upside-down world of writing quasiquoted code with abstract syntax trees and evaluation rules.

But. Using quote-unquote to pass values from compile time to runtime is still a generally useful technique. You can’t always write a closure like this – sometimes you really do need to produce an AST with a reference to a mutable value you allocated at compile time.

The problem is, it’s useful in situations that don’t really fit into a blog post. I’ve been spending some time recently rewriting the Bauble compiler, now that I actually know Janet, and this quote-unquote pattern comes up in just about every nontrivial macro I write. These are macros that produce Janet code that you can evaluate to construct a GLSL AST, but some amount of evaluation happens at macro expansion time, and the result of that ahead-of-time evaluation gets quote-unquoted into the intermediate Janet code.

I’ve also used quote-unquote in conjunction with mutable values allocated at compile-time (like what we saw here) in Judge, my inline snapshot testing framework, to ensure that every assertion you write actually runs by the time a test completes.

But, well, those are big and complicated and hard to explain and talk about, and I just wanted to point out how I underestimated quote for so long, in case you’ve been balancing your parentheses under the same misconception.