Tree @master (Download .tar.gz)

..
README.md

Ahead-of-Time `eval`

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 the current write-up is about 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 is, in its way, conceptually simple and perhaps even elegant; but as of this writing it remains to be seen, to me, what the full implications are for macros. So I'm choosing to present what I've got so far, while leaving that question open for the time being.

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. 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 would ultimately be able to provide a conceptually simple foundation for certain desirable classes of macros ("circumspective" and "ergonomic" macros).

For the purpose of this demonstration, we'll assume we have a strict, dynamically-typed, and 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.

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 easily adapt this to 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 a quoted form and an environment, 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 (quote (* 2 2)) std-env)

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 (quote (* a a))
    (extend-env 'a a std-env)))

Before moving on, can we just stress that 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.

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

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.

Typically, in practice, one would make it go one step further: have the resulting quoted form be converted, ahead of time, using eval, into executable code - that is, 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; if some of the actual arguments are not constants, the quoted form will not be transformed and evaled until the values of the non-constant arguments are known, i.e. at runtime [Footnote 8].

One subtlety here is the distinction between the function that transforms the quoted form and evals it, and the function produced by that eval. The latter function 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.

Suppose our Scheme-like language has only if conditionals and we want to define cond. If we pass in the branches as lambdas, then even without any macros at all we can write

(define cond (lambda (arms)
  (if (null? arms)
    (error "ran out of arms")
    (let* ((arm  (car arms))
           (test (car arm))
           (expr (cadr arm))
           (rest (cdr arms)))
      (if (test) (expr) (cond rest))))))

If arms was a quoted form then yes, it would be constant. But then it would almost certainly contain names whose values aren't bound until runtime, so obviously it could not be reduced ahead of time.

If arms was a list of lambda functions, then it might be constant; but lambda functions are only constant if all the names that occur within them are bound to constants; and the chances of that are slim.

If arms was some sort of quasi-quoted structure, were all the non-constant parts were inserted in slots in the quasi-quote, then the non-slot "template" part of the quasi-quote would be constant, and it could be manipulated and evaluated ahead-of-time. But the arms of a cond does not provide a good example of that situation.

Example of Ergonomic Macro

With the above in mind, as an example, if we were to define a conditional based on the law of trichotomy in our putative Scheme-like language, we might have

(define trich (level)
  (eval
    `(lambda (cand fabove fequal fbelow)
      (if (> cand ,level)
        (fabove)
        (if (< cand ,level)
          (fbelow)
          (fequal))))
    std-env))

(using quasiquoting for succinctness) and this macro could be applied like so:

((trich 0) c
  (lambda () "c is negative!")
  (lambda () "c is zero!")
  (lambda () "c is positive!"))

(There is of course nothing stopping a language from supporting language constructs to hide some of this syntactic complexity, in the name of making macro definition and usage less awkward. But we need to reveal it here in order to show how the mechanism works.)

Since 0 is a constant, level is a constant in the body of the trich function; so both arguments to eval are constant; so the eval is evaluated ahead of time, and this application of trich is morally equivalent to writing

((lambda (cand fabove fequal fbelow)
      (if (> cand 0)
        (fabove)
        (if (< cand 0)
          (fbelow)
          (fequal)))) c
  (lambda () "c is negative!")
  (lambda () "c is zero!")
  (lambda () "c is positive!"))

If trich were passed some expression (say, xyz) that was not a constant like 0 is, it would still be called and have the same semantics, except that it would execute the eval at runtime, as if we had written:

((eval
    `(lambda (cand fabove fequal fbelow)
      (if (> cand xyz)
        (fabove)
        (if (< cand xyz)
          (fbelow)
          (fequal))))
    std-env) c
  (lambda () "c is negative!")
  (lambda () "c is zero!")
  (lambda () "c is positive!"))

On the other hand, if we passed 0 to trich and c was also constant (for example, if it were all inside (let ((c 100)) ...)), the whole thing would be constant, and would be reduced to

"c is positive!"

Hygiene

I'd like to think that the manipulation of syntax by functions that take syntax to syntax, as we've done here, is naturally hygienic. This is because, at the time the eval happens, it only has access to the constant values known ahead-of-time. It doesn't even have access to the bindings only known at runtime, so how could it possibly accidentally capture them? Especially since we need to pass the bindings we want to use in the evaluation as an explicit argument to eval.

The best it can do, is take a constant (quasi-)quoted form, fold staple and mutilate it, and turn it into a lambda function for the runtime to apply to some runtime values at runtime. But the hygienic nature of that application is well-understood, and nothing we need to worry about.

However, I'm not convinced there are no holes in that reasoning. Couldn't we, for example, still accidentally capture a binding, if it so happens that what it is bound to is a constant?

So, it may be that the statements in the above few paragraphs, while not untrue, are in the final analysis, somewhat underwhelming. To get into why that is though, I think we need to examine the assumptions more closely. What makes a macro "hygienic" anyway?

I would submit that a programmer perceives a macro as un-hygienic when the names used in the macro become bind to values that they did not expect them to become bind to, almost always resulting an unpleasant surprise.

In other words, hygiene is relative to the programmer's expectations, and the particular expectations are set up by what the particular programming language provides in regards to scope and binding.

This problem becomes even more pervasive when you consider that advanced macros can implement their own rules for scope and bindings, thus setting up new hygiene expectations of their own, over and above what the programming language itself sets up.

So it would seem that ultimately there is no escape from the relativity of hygiene.

But it's also entirely possible that in practical terms, that is a moot point.

It's probably a matter of precisely identifying the (or a) proviso that hits the (or a) sweet spot, and then articulating it. I'm not there yet.

More research is needed.

"But `eval` is evil!"

As a sort of closing note, for now:

The reputation eval has in some circles is not a positive one, and this reputation is not wholly undeserved. But this reputation is attached to using eval at runtime. The core ideas of Ahead-of-Time eval only necessitate using eval ahead of time. It would in fact be quite possible to couple it with forbidding runtime eval: at some point after the mandated constant folding pass, we look for any remaining instances of eval in the program, and we raise an error if any are found.

I have no clear idea whether this is novel or not, or to what degree. The basic mechanism (mandate constant folding, and allow (eval k) to be treated as a constant and folded along with everything else) is so straightforward that I can hardly expect that no one has ever thought of it before. On the other hand, I've not to my knowledge come across this arrangement of things elsewhere.

Clearly it is related to constant folding; but constant folding is most often considered a compiler optimization, not something that's specified by the language.

Clearly it is also related to partial evaluation. 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.) But I've not to my knowledge seen partial evaluation associated with macros, nor applied to eval.

Clearly it is also related to hygienic macros, but I refer back to my opinion at the beginning of the article. Hygienic macro systems often seem to either start with conventional (unhygienic) macros and then patch them up so that they're hygienic, or with a whole-cloth redefinition of scoping and name binding, with little or no explicit regard to the relevant stages of computation. Ahead-of-Time eval seems to approach the entire problem from a different angle, obviating the very need for macros in some instances.

It also seems to be related to evaluation techniques for functional languages, although my impression is that much of the existing work there is to support more performant ways of implementing lazy languages. Ahead-of-Time eval can perform optimization in much the same way macros do, and in much the same way memoization does, by computing a result once and using it many times instead of recomputing it each time. But, like macros, it is not restricted to memoization, and, unlike macros, it can gracefully degrade into runtime computations when the arguments are not constant.

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

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 8

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). Since we partially evaluate from left to right (in the same manner as conventional currying), this is an argument for choosing the leftmost argument to be the ones most likely to be constant.