Ahead-of-Time eval

In Search of... Hygienic Macros

Motivation

I've not yet encountered a macro system with an elegant theoretical basis. At least, that it how it seems to me. The ones I have seen have all seemed ad hoc and convoluted in some way. Just my opinion, of course! But it's been quite aesthetically unsatisfactory, you see, and this write-up was done in the pursuit of one that is — I can only hope — coherent and conceptually simple and perhaps even elegant, as a sort of counter-example: a testament to the fact that it is possible to have such a design.

However, this line of inquiry has not led quite where I had hoped it would. The result of the investigation, which I have called Ahead-of-Time eval, is not a means to hygienic macros, but rather, it is its own thing: conceptually simple and elegant, sort of an "evaluation scheme" that is a particularly good setting for doing things with macros, including dispensing with them entirely. But it does not by itself get you hygienic macros, and exactly what macro hygiene might look like in this setting remains to be seen.

But the thing itself is worth examining, in itself, so I am conceptually separating the two issues, and presenting that thing here.

Background

The definition of the Scheme programming language includes a rule that essentially says

If a procedure call can be replaced with a tail call without changing the meaning of the expression, it must be replaced with a tail cail.

In the Scheme report, this is called "proper tail recursion" [Footnote 1] and it is somewhat unusual, as language implementation requirements go, in that it is an operational rule rather than a semantic one; it doesn't define the result that is computed by the procedure, it only constrains the method by which that result is to be computed.

I mention this rule because in this article I would like to consider a rule with a similarly operational character, which is:

If the value of an expression can be computed ahead of time without changing the meaning of the expression, it must be computed ahead of time.

Since this is a kind of constant folding [Footnote 2], we could ape the phrase "proper tail recursion" and call this "proper constant folding". However, I don't think that carries quite the right connotation here, because we're in a slightly different situation than Scheme was in when it adopted that. So instead, we will call this mandated constant folding.

It is, in essence, a restricted form of offline partial evaluation, one where functions are only specialized when the values of all of their arguments are known ahead-of-time.

In this article, I'd like to demonstrate some of the remarkable properties of combining mandated constant folding with a reflective evaluation facility (conventionally called eval). My hope is that this combination provides a conceptually clean setting for certain desirable classes of macros (which I have called "circumspective" and "ergonomic" macros), and maybe more importantly, an alternative frame for thinking about macros.

For the purpose of this demonstration, we'll assume we have an eagerly-evaluated, dynamically-typed, lexically-scoped functional programming language, based loosely on Scheme, to write our example code snippets in. This language will have mandated constant folding and eval (and quote), but will otherwise be much simpler than full Scheme.

Aside: "But eval is evil!"

The reputation eval has in some circles is not a positive one, and this reputation is not wholly undeserved, so I will try to persuade you that the eval we're using here can be used in a highly controlled way:

• The core idea of Ahead-of-Time eval is to use eval ahead of time, and we could in fact forbid eval at runtime entirely;
• Even if we don't, we can insist that some of the arguments to eval (in particular, the quoted form) have been evaluated ahead-of-time (i.e. are constants), a restriction that makes eval at runtime no more powerful than lambda.

These restrictions put strong limits on how much "evil" is brought into the picture.

We will call the first variation strictly ahead-of-time eval, and it will be the focus of this write-up (and our example language will have the usual lambda construct). But we will discuss some of the implications of the second variation (which we could call flexibly ahead-of-time eval) in a follow-up section at the bottom.

Constant folding

Let's begin by defining "constant folding" more rigorously, starting with what it means for an expression to be a constant:

• Literals such as 1 and "Hello, world!" are constants.
• A name bound to a constant, is a constant.
• Any built-in function of the language (such as the function represented by *) is a constant.
• A function value is a constant, if the expression that defines it (its body) is a constant under the assumption that it arguments are all constants. Put another way, a function is a constant unless its body refers to some name that is not one of its arguments and is not known to be constant.

If f is a function value that is constant and a1, a2, ... an are constants, then the function application (f a1 a2 ... an) is constant (i.e. we can, and thus must, compute it ahead of time), assuming that f is referentially transparent (i.e. the result of evaluating f depends only the values of a1, a2, ... an, and this evaluation does not have any side-effects.)

There are a number of issues we now consider:

(1) How we determine that f is referentially transparent is orthogonal to the main point of this article [Footnote 3]. For our purposes, we'll simply assume that all the functions we're working with are referentially transparent, i.e. that this is a purely functional language.

(2) We must also consider the case where evaluating (f a1 a2 ... an) does not terminate. This is not really an issue in practice, for it will now simply fail to terminate ahead-of-time, instead of later on at runtime. In some cases this might actually be advantageous, as it allows the condition causing non-termination to be detected at an earlier stage.

(3) Even though we say all arguments must be constant, we can adapt this towards partial evaluation, if functions are curried. If we have (f a) where f and a are constant, then (f a) can evaluate (ahead-of-time) to another function g, which can itself be constant, and can itself be applied (ahead-of-time) to another constant, and so forth, or not, as the case may be.

(4) We'll go even a tiny bit further and say that an argument must either be constant or the formal parameter into which the argument being passed must not be used by the function (i.e. if it is a user-defined function, that formal parameter must not appear in the function body.) The argument clearly cannot affect evaluation, so evaluation can proceed even if the argument is not constant. This gives us a simple way to do a little "mandated dead code removal" along with our mandated constant folding.

Now, if (f a1 a2 ... a2) can be computed ahead of time, we do so, replacing it (either conceptually or concretely) with the constant value we obtained by doing so, repeating this process in the manner of a transitive closure algorithm, until we can find no more function applications that can be replaced by constants [Footnote 4].

That is the basic idea. It's not really earth-shattering, and can be found in good expositions of constant folding or partial evaluation [Footnote 5]. The trick comes in when we combine it with eval.

quote and eval

To pursue the application of mandated constant folding to macros, the language will need an eval facility, and in order to employ that facility in a reasonable way, it will need a way to represent program texts as expressible values in the language.

For concreteness we will call such values "quoted forms". Following Scheme, our language will provide literal (and thus constant) quoted forms in expressions by way of the quote operator.

Meanwhile, eval is a built-in function that takes an environment and a quoted form, and evaluates to the value that the form, were it not quoted, would evaluate to in that environment.

Note that eval, being a built-in function, is a constant. An application of eval is not essentially different from any other function application, so, for example, by the rules of our mandated constant folding,

(eval std-env (quote (* 2 2)))

is a constant (the constant value 4) — under the assumption that std-env is a value representing an environment (presumably the "standard" environment) in which the symbol * is bound to a conventional multiplication function.

Note that no bindings from the current environment can be seen by the eval. If it were desired to expose those bindings to the eval one would need to add them explicitly to the environment in use; looking something like

(let ((a 123))
  (eval (extend-env 'a a std-env) (quote (* a a))))

[Footnote 6]

Macros

Kinds of Macros

Before launching into how all this might relate to macros, it might be good to have an overview of the common use cases of macros.

I submit that there are three major purposes for which macros are used: circumspection, optimization, and ergonomics.

Circumspection — which we might call "conditional compilation" if we were restricting ourselves to compilers, which we're not — means omitting code that we don't strictly need, in the version of the program that executes. So for example, if one of our customer agreements stipulates they do not have access to some special feature of our product, we leave out that feature in the build we supply to that customer. Or, if we build a program without debugging, we leave out the debug logging function and all the calls to it too.

Happily, mandated constant folding by itself often gives us circumspection "for free". Instead of #ifdef DEBUG, for instance, we simply define debug as a function that returns a constant and use plain if tests on it; we have a strong guarantee that this will all have been accounted for ahead of time, and it will not appear in the code or impose any cost at runtime [Footnote 7]. We can even do this if if is a plain function that takes function values for its branches, as long as it is curried, and we have done "mandated dead code removal" as described earlier, to prune the unused branch.

Optimization, where it is not already accomplished by circumspection (less stuff in program = less work to do), usually consists of arranging instructions in a particular way so that their pattern of execution is closer to optimal. For example, array striding, vectorization, and loop unrolling are optimizations to achieve better cache- and processor-level behaviour when executing vector or matrix based code, and these are sometimes implemented with macros. [Footnote 8]

However, Ahead-of-Time eval as we've described it requires that the functions involved are referentially transparent. And part of the point of raising the abstraction level of the program in this way, is to allow the compiler the freedom to be able to select and make these kinds of optimizations itself, rather than relying on the programmer to address these concerns with explicit handiwork.

So I'm happy to concede that Ahead-of-Time eval is not really suited to writing macros for optimization tasks, and won't worry too much about it here.

Ergonomics is where Ahead-of-Time eval can really focus. An ergonomic macro is one designed to improve the usability of the language itself in some way; for example, defining a case statement in a language that only supports if statements, by translating the case to a sequence of ifs. This idea of improving the constructs of the language "from within" can be taken quite far, to the point of creating entire embedded domain-specific languages (EDSLs).

In this setting, a macro is little more than a function that takes syntax to syntax. Given some syntax as input, it reduces that to a (presumably different) syntactic form, before program execution begins.

Since quoted forms represent syntax, this matches exactly what Ahead-of-Time eval will do to the referentially transparent functions in the program that are passed constant quoted forms: reduce them, ahead of time, to other constant quoted forms.

Then "defining a macro" is to have the resulting quoted form be converted, ahead of time, using eval, into executable code - generally, into a function that can be called from other point(s) in the program.

Such "macros" also happen to "gracefully degrade" back into "regular" functions when some of their actual arguments are not constants; the implementation will not be able to constant-fold them, and will leave them as the functions defined over runtime-supplied argument that they are. This is, however, most applicable to flexibly ahead-of-time eval -- these functions, being "macros", presumably work on a quoted form, and would still want to eval that quoted form, requiring eval to be available at runtime. [Footnote 9].

One subtlety here is the distinction between the function that transforms the quoted form and evals it, and the function that contains the result of that eval. The latter is what is used at runtime. As such, it can have extra arguments which are perfectly expected to be dynamic and only known at runtime. The former function, the one that transformed the quoted form, cannot; any extra arguments it has must also be known ahead of time.

Ergonomic Macros vs. Higher-Order Functions

It's high time we gave an example of an ergonomic macro. The thing is, in a setting with higher-order functions, it's difficult to find an example of an ergonomic macro that's significantly different from a higher-order function, the kind that you know and love from functional programming. And this tends to make it look like AoT-eval is "just an optimization" - which it kind of is, but it's at the language level rather than the compiler level.

To illustrate what I mean, suppose our Scheme-like language has only if conditionals. We can build a general Scheme-style cond that takes a list of (test, result) pairs, where each test and result is a lambda:

(define cond (arms)
  (if (null? arms)
    (quote no-match)
    (let* ((arm (car arms))
           (rest (cdr arms))
           (test (car arm))
           (result (cdr arm)))
      (if (test) (result) (cond rest)))))

And we would use it like

(let ((a 100) (b 200))
  (cond (list
    (cons (lambda () (> a b)) (lambda () a))
    (cons (lambda () (> b a)) (lambda () b))
    (cons (lambda () #t) (lambda () (quote equal))))))

This is an admirable attempt at ergonomicity, but mandated constant folding helps very little here. The tests and results are zero-argument lambdas which, for the most part, can't be evaluated ahead of time, because they close over values that are in scope where the cond appears.

What holds this back from being an improvement in ergonomicity, is that it requires the programmer to supply lambdas in all the arms, which is tiresome. What we'd like is to be able to omit those. We'd like to have a more streamlined syntax, that gets compiled to the above. Such as:

(let ((a 100) (b 200))
  (cond '(
    ((> a b) a)
    ((< b a) b)
    (#t (quote equal)))))

Our macro, then, is a function that takes syntax to syntax. (This idea is as old as Common Lisp, but here it requires no special form like defmacro; it just happens when it is able to happen.) In this instance, such a function would look like this:

(define expand-cond-arms (arms)
  (if (null? arms)
    (quote ())
    (let* ((arm (car arms))
           (rest (cdr arms))
           (test (car arm))
           (result (car (cdr arm))))
      (cons
        (list (quote cons)
              (list (quote lambda) (quote ()) test)
              (list (quote lambda) (quote ()) result))
        (expand-cond-arms rest)))))

(define expand-cond (arms)
  (list (quote cond)
        (cons (quote list) (expand-cond-arms arms))))

Of course, this only translates one quoted form to another. We need to execute it. For this, we have eval. But this reveals another wrinkle: we need the execution to be able to see the values of a and b, and they're part of the quoted form, but not known ahead of time. So we wrap the whole thing in a lambda and pass them in. Of course, the programmer probably has their own ideas about which "upper variables" they used in the arms, so instead of hardcoding a and b, we allow them to pass in a list of names:

(define mk-cond (names arms)
  (eval std-env `(lambda ,names ,(expand-cond arms))))

Note that this doesn't execute the cond structure, it just returns a function. The caller still has to call this function themselves. This is because we want all the arguments to the "macro" function mk-cond, to be known ahead-of-time. The values being passed in (in this case, for a and b) will most likely not be known ahead-of-time. So we need an extra call for that, one that happens at runtime.

((mk-cond '(a b) '(
    ((> a b) a)
    ((< b a) b)
    (#t (quote equal))))
  100 200)

This is somewhat awkward, perhaps - but see [Footnote 9].

Now, despite what I said earlier about focusing on ergonomic macros and eschewing optimization macros, if we felt we should second-guess the language implementation and assume that unfolding the cond directly into a nested sequence of if tests would result in "better code", whatever that means to us, we could write expand-cons like this:

(define expand-cond (arms)
  (if (null? arms)
    (quote (quote no-match))
    (let* ((arm (car arms))
           (rest (cdr arms))
           (test (car arm))
           (result (car (cdr arm))))
      (list (quote if) test result (expand-cond rest)))))

mk-cond would remain the same, but the above usage of it would expand to

(lambda (a b)
  (if (> a b) a (if (< b a) b (if #t (quote equal) (quote no-match)))))

and the constant folding would probably reduce the final term to just (quote equal), given the test in the if is the constant #t.

In general, the pattern for a macro constructed using Ahead-of-Time eval looks like this:

• We have some syntax
• We transform this syntax into some eval-able syntax
• We eval this syntax, ahead-of-time, into some code
• We execute that code at runtime (a macro application site).

In other words, a "macro" is a function that takes syntax to syntax. That syntax needs holes, for the values that aren't known ahead-of-time to be plugged into, but those holes need to be provided by something that still exists at runtime, like lambda.

Comparison to Hygienic Macros

In some weak sense, the manipulation of syntax by functions that take syntax to syntax, as we've done here, is naturally hygienic - the eval has only access to what we explicitly expose in its environment, and since it is resolved ahead-of-time, it only has access to the constant values known ahead-of-time.

But this is a weak sense. In the sense usually meant by the phrase "hygienic macro", we mainly want two things:

• When you say foo in the macro definition, it means what foo means when the macro is defined, not what foo means when it is applied.
• When you say bar in the macro application, it means what bar means when and where the macro is applied, not what bar means inside the definition of the macro [Footnote 10].

You get the first automatically with AoT-eval, simply because bindings are lexically scoped rather than dynamically scoped; the client code can't go and redefine what foo means (or rather, it can only do that for itself, and not something that has already been established, like the macro definition.)

You don't get the second automatically with AoT-eval. The construction of quote isn't policed. Hygienic macros would involve policing quote in some way. I have some ideas for that, but they're out of scope here.

Strictly vs Flexibly Ahead-of-Time eval

As mentioned earlier, we have the option of requiring eval to be evaluated ahead-of-time (and thus not appearing in the runtime at all), or allowing it but with a constancy restriction on the quoted form being eval'ed.

The latter makes eval roughly equivalent to lambda, in the sense that the following algebraic identity holds:

(eval (extend-env 'a a std-env) '𝛃) = (lambda (a) 𝛃)

where 𝛃 stands in for a literal form which does not rely for its meaning on any identifiers other than what are in the standard environment, and the argument a. That is to say: it does not close over any other identifiers.

Making eval more or less equivalent to lambda has the interesting side-effect that we could use eval instead of lambda; our language need not have lambda as a built-in, as we could essentially derive a (slightly-weaker-than-usual) form of it from eval.

This derivation is reasonably well-understood in the world of fexprs and Shutt's vau calculus: you can define lambda in terms of eval.

It's tempting to think that the constancy restriction might let us guarantee a degree of efficiency that, per Wand's "The theory of fexprs is trivial", can't be guaranteed in the general case of fexprs: because the body is required to be known ahead-of-time, we should be able to substitute these evals with lambdas in a constant-folding pass. But whether the way is clear to do this, remains to be seen -- it seems a little too easy and it would not surprise me if something about it that I'm not currently seeing makes it degrade into a whole-program analysis in the worst case, which would simply affirm Wand's result.

Related Work

You may well ask if any of this is novel, and to what degree. I asked myself that for a good span of time. The answer I eventually arrived at is that it is a novel combination of a number of mostly well-established ideas.

Clearly, the basic mechanism of mandated constant folding is related to constant folding; and constant folding is usually considered a compiler optimization rather than a language feature, although there are languages that define some support for it. constexpr in C++, static in the D, and comptime in Zig all assert that some code is evaluated at compile-time rather than runtime, and in each case the effort is to support macro-like or "templated" code. But these are explicit pragmas that the programmer must craft, in languages that frame themselves as compiled languages, while mandated constant folding is an implicit (or tacit, if you prefer) behaviour stemming from a requirement in the language spec: conforming implementations (whether compilers, interpreters, or otherwise) must do constant folding where-ever possible, or they're not conforming implementations. I haven't seen that formulation of this idea elsewhere, and it appears to be novel.

Clearly it is also related to partial evaluation [Footnote 5]. Constant folding is a restricted form of partial evaluation where function applications are only reduced when all of their arguments are constants. (But if functions are curried, they can be partially constant folded left-to-right.)

Closely related is the idea of staged evaluation, where the language defines different phases of evaluation, and the conditions that determine what gets evaluated at what stage. These techniques are well-trodden, although exploring the design space where they dovetail with the idea of macros seems more recent. One recent experimental language in this area is MacoCaml, described in MacoCaml: Staging Composable and Compilable Macros by Ningning Xie et al (2023). This paper highlights, like we do, that macros are almost always functions (where the body has been transformed in some way). Being based on stages rather than quoted forms, however, restricts MacoCaml to one-level generative macros; having the quoted form be a data type, as we have here, allows introspective macros, as well as multi-level macros -- eval can appear within a quoted form, and mandated constant folding is uniform; it happens just as well when such a nested eval is evaluated.

---

Document History

• Aug 2026: the current, even more less confused, published version
• Jan 2025: another, bit less confused, published version
• Aug 2023: initial, rather confused, published version

Footnote 1

See section 3.5 of the Revised^5 Report on the Algorithmic Language Scheme.

Footnote 2

For more background on constant folding, see, for example, the Wikipedia article on Constant folding, but note that the Wikipedia article focuses on it as a compiler optimization, rather than as a language specification rule as we're doing here.

Footnote 3

There are several approaches that can be taken to restrict to properties such as this. The language can be designed to only be capable of expressing functions with such properties; the properties can be specified as part of a type system; we can use static analysis to conservatively infer these properties; or we can rely on the programmer to correctly mark functions that have and do not have these properties, with any incorrect marking considered a bug just like any other bug.

Footnote 4

In most languages we ought to be able to proceed, for the most part, in a bottom-up fashion: when we have reduced a function application to a constant, consider whether the function application containing this new constant, is itself constant, and so on. But we should take care with where names are used; if an expression that a name is bound to is reduced to a constant, all the sites where that name is referenced should also be checked to see if those sites can now be reduced to constants.

Footnote 5

See, for example, Tutorial on Online Partial Evaluation by William R. Cook and Ralf Lämmel (2011) for an introductory exposition of partial evaluation. The differences are that we are not interested in partial residuals — we only reduce a function application when all the arguments are constant, which makes things considerably simpler — and that we are doing this offline (but this is also a minor consideration given that we are not considering the input of the program).

Footnote 6

I'd like to note the situation wouldn't be essentially different if our built-in reflective evaluation function took strings which it parsed as program text fragments (like Python's eval). The parsing step is referentially transparent and the eval function is still a constant.

Footnote 7

I admit we're glossing over the fact here that the debug function needs to be considered referentially transparent even though it produces output. This seems like a reasonably minor consideration; the output is always to a dedicated "debug stream" which we stipulate cannot affect the execution of the program.

Footnote 8

Implementing these sorts of optimizations appears to be one of the major drivers behind Julia's support for macros, both hygienic and non-hygienic.

Footnote 9

This is one area where partial evaluation has an advantage: given a function call where some of the arguments (including the quoted form) are known ahead-of-time while other arguments aren't, it will produce a specialized function where the quoted form has already been evaled into a form which is executable (and presumably more efficiently so). Although, as we've mentioned, we approximate this, if functions are curried; and in this circumstance there is a strong argument for choosing the leftmost arguments of a function to be the ones most likely to be constant.

Footnote 10

You could say that there are "reasonable" macro definitions that depart from these rules; but then you would also classify those definitions as "reasonable" intentionally unhygienic ones.