Aggressive Constant Folding + eval = Hygienic Macros
I started writing this because it seemed to me that I had never seen a hygienic macro system that wasn't ad hoc and convoluted in some way (just my opinion, of course!) and I wanted to present one that is — I can only hope — coherent and conceptually simple instead, as a sort of counter-example: a testament to the fact that it isn't impossible to have such a design.
This is a write-up only, and contains no code. If you prefer to see code, many of the ideas in this article are implemented in the toy language Durito.
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 affect the result that the procedure computes, instead it constrains the method by which the 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 follow the example of "proper tail recursion" and call this "proper constant folding"; however, that phrasing doesn't quite fit here for a number of reasons, so instead, we will call this aggressive constant folding [Footnote 3].
In this article, I'd like to demonstrate that the combination of
aggressive constant folding together with a reflective evaluation facility
(conventionally called eval) provides an alternative to a dedicated macro
system which is both conceptually simple and hygienic, and has a number of
other benefits.
For the purpose of this demonstration, we'll assume we have a functional programming language, based on Scheme but presumably much simpler, that has these two features, and we'll write our example code snippets in it.
Let's begin by defining "aggressive constant folding" more rigorously.
Literals such as 1 and "Hello, world!" are constants.
A literal function, that is, a lambda expression
such as (lambda (x) (* x x)), is also a constant.
Built-in functions, such as the function represented by *,
are also constants.
If f is a constant function and a1, a2, ... an are constants,
then the function application (f a1 a2 ... an) can be
computed ahead of time, assuming the following things about f:
fis referentially transparent, i.e. the result of evaluatingfdepends only the values ofa1,a2, ...an, and this evaluation does not cause any side-effects; andfis always terminating, i.e. evaluatingfalways returns a result after a finite time, for any choice of arguments passed tof.
Now, how we determine whether f is referentially transparent and always
terminating is an altogether different matter; but it is one that is orthogonal
to the main point of this article [Footnote 4].
For our demonstrations, we'll simply assume that all the functions we're
working with are both referentially transparent and always terminating.
There is a third constraint:
- All names used inside the definition of
f, apart from the formal arguments off, are bound to constants.
This third constraint is particularly relevant if f uses names
that are defined in an outer scope, for example the formal arguments
of the function inside which f is defined.
Now, if (f a1 a2 ... a2) can be computed ahead of time, we do so,
then replace it (either conceptually or concretely) with the
constant value we obtained by doing so.
Once replaced, we repeat 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 5].
That is the basic idea.
There are a few more details we could mention:
When analyzing an expression that contains a name, we must have some way of telling if we know that it is bound to a constant or not, in order to determine if the expression is constant. Typically some kind of environment structure mapping names to values would be maintained during analysis. When a name is discovered to refer to a constant, that name-value pair is added to this map. If a name is not present in the map, we must err on the side of safety and assume it does not represent a constant.
The propagation of constanthood will typically occur in some
language constructs that aren't function applications, as well.
For example, in an (if x t f) expression, x may be a constant;
if x is a "truthy" constant then the entire expression reduces
to t, otherwise it reduces to f.
To demonstrate our point about hygienic 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".
We've already stated our language here is similar to Scheme, and
the standard way to represent quoted forms in Scheme is as list
structures, using the quote construct to express literal
(and thus constant) quoted forms in expressions.
Meanwhile, eval is a built-in function that takes a quoted form
and an environment, and evaluates to the value that that form,
were it unquoted, would evaluate to in that environment. Again,
this is very similar to Schemes's eval; the main difference
is that we use a slightly more nuanced conception of
"environment" (see below).
We note also that eval, being a built-in function, is itself a constant.
An application of eval is not essentially different from any other
function application, so, for example, by the rules of aggressive
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 suitable
integer multiplication function.
Before launching into how all this relates to hygienic 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 [Footnote 6]. Or, if we build a program without debugging, we leave out the debug logging function and all the calls to it too.
Happily, aggressive constant folding by itself 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.
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 can be implemented with macros.
However, Ahead-of-Time eval as we've described it
requires that the functions involved are referentially transparent.
And part of the point of raise the abstraction level of the program
with "pure" functional programming like this, is to allow the compiler to
be able to select and make these kinds of optimizations itself, rather than
leaving it up to the programmer to address these 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.
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 nothing 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 referentially-transparent,
always-terminating functions that are passed constant quoted forms:
reduce them, ahead of time, to other constant quoted forms.
Such "macros" also happen to "gracefully degrade" back into functions; if not all actual arguments are constants, the function will not be applied until the values of the non-constant arguments are known, i.e. at runtime.
There is a subtlety when using Ahead-of-Time eval to form an ergonomic
macro, however. (At least, I must assume it's a subtlety as it took me
a while to figure it out; I wasn't clearly seperating circumscription
macros from ergonomic macros in my head.) Some of the arguments to the
"macro", the syntax parts, are constant and translated ahead of time; while
other arguments (such as the expression in the case statement example
above) are not known until runtime. It would be a mistake to treat
those arguments as things that we can compute ahead of time.
The resolution to this is to have the function that takes syntax as input, produce as its output a function which takes arguments. It is those arguments that are the runtime arguments of the macro.
As an example, if we were to try to define a Perl-like unless form
in our putative Scheme-like language, we might have
(define unless (qa qb)
(eval
`(lambda (x) (if (not x) ,qa ,qb))
std-env))
(Here we are using quasiquoting for succinctness.) This macro would be applied like so:
((unless '(do-one-thing 123) '(do-something-else 456)) (> c 0.5))
The two argument to unless are syntax for the branches that are
incorporated, ahead of time, into the if statement in the function.
The (> c 0) expression is not evaluated until runtime, and the
result of evaluating it is passed to the function.
This simple version only works if we are content to have our true and false branches be computable ahead of time, which probably isn't very useful in practice. If we want them to have components that aren't known until runtime, we need to treat them as functions, too.
unless is perhaps too simple to make a good demonstration of
this, so let's fancy it up a tiny bit, even at the cost of it looking
a bit contrived. Let's make a macro called if-greater that selects
the first branch if the test value is greater than a constant threshold,
and the second branch otherwise.
(define if-greater (threshold)
(eval
`(lambda (x fa fb) (if (> x ,threshold) (fa) (fb)))
std-env))
And then the usage would be something like
(let ((x something-known-only-at-runtime)
(y something-else-known-only-at-runtime))
((if-greater 0.5) c
(lambda () (do-one-thing x))
(lambda () (do-some-other-thing y))))
where x and y aren't known until runtime.
Note that even though x was used in the definition of the
macro, there is no danger mentioning x in the first branch;
it has already been bound to something-known-only-at-runtime.
There is of course nothing stopping a language from supporting language constructs to hide some of this 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.
The manipulation of syntax by functions that take syntax to syntax as we've
done here is naturally hygienic. This is because the environment passed
to eval is explicitly given, and only the bindings in that environment
will be used during the evaluation of eval. Supplying only a standard
environment, which does not contain any bindings specific to the active
program, makes it impossible to capture a program binding during the
evaluation of eval.
It also makes it possible to strategically subvert hygiene, either by manipulating the environment that is passed in so that it no longer resembles the "standard" one, or by manipulating the quoted form and replacing referents with other values.
Runtime values for ergonomic macros, meanwhile, are passed in as arguments to formed functions. The formed function does have formal arguments, and the possibility of using a name that collides with the name of a formal argument does still exist; but there appear to be mitigating factors when doing things this way. Namely, the runtime values are always passed as arguments, and thus referred to by the formal name of the argument, which will shadow any pre- existing bindings for that name; and if a function does happen to refer to bindings that aren't known ahead of time, it won't be computed ahead of time itself. So if the language supports some way of annotating what is expected to be computed ahead of time, it could, e.g., warn the user that such a collision has occurred.
Now, the statements in the above few paragraphs aren't untrue, but they're perhaps 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 there is really no escaping the relativity of hygiene.
In the most general case, what macro authors need is control over the bindings
used in the evaluation of the body of a macro, and tools to examine the
bindings in effect at the points in the program where the macro is used. Such
tools are out of scope of this write-up, as the possibilities are vast and
they don't really affect the core idea of Ahead-of-Time eval one way or the
other; but the other core need, control over the bindings during evaluation,
has been granted.
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 aggressive constant
folding pass, look for any remaining instances of eval in the program, and
raise an error if any are found.
I have no idea how novel this is; the basic mechanism is so simple that I can hardly expect that no one has ever thought of it before; yet I haven't come across this arrangement of things before either.
Clearly it is related to constant folding; but constant folding is often considered only as a compiler optimization, and not something that is specified by the language.
Clearly it is also related to partial evaluation; but partial evaluation usually goes much further. Partial evaluation generally aims at statically generating a new function when any of its arguments are constant; while aggressive constant folding only reduces the function to a constant when all of its arguments are constant.
Clearly it is also related to staged computation. It is a kind of strategy
for computation that moves as much computation as it can to an earlier
"precomputation" stage. However, this does not seem to be the concern that
staged computation usually aims to address; discussions of the concept seem
to centre around compilation and generating executable code at runtime
[Footnote 7]. But Ahead-of-Time eval happens ahead of time
only, and need not involve compiling.
Clearly it is also related to hygienic macros, but I refer back to my opinion
at the beginning of the article. Hygienic macro systems almost always seem
to start with conventional (unhygienic) macros and then patch them up so that
they're hygienic. 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.
See, for example, section 3.5 of the Revised^5 Report on the Algorithmic Language Scheme.
For more background on constant folding, see, for example, the Wikipedia article on Constant folding, though note that the Wikipedia article focuses on it as a compiler optimization, rather than as a language specification rule as we're doing here.
We also avoid the phrase "compile-time" as it is technically inaccurate, as we might never actually compile the given code; instead we say "ahead of time".
There are several approaches that can be taken. The language can be designed to only be capable of expressing such functions; the properties can be specified as part of a type system; we can use static analysis to conservatively infer these properties; or we can simply assume that any function that is not referentially transparent and always terminating will be marked as such by the programmer and that any incorrect marking is a bug just like any other bug.
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.
Never mind how terribly antiquated delivering software directly to an individual customer sounds in this modern, Cloud-polluted world of ours. Actually, it still does happen in some of the more arid corners of the industry.
See, for example, the answers to the question What are staged functions (conceptually)? on the Computer Science StackExchange.