Macros are code templates. Just like HTML templates allow you to specify a mostly-constant HTML document with some interesting values inserted here and there, a macro allows you to specify a mostly-constant chunk of code with some interesting parametric chunks of code here and there.
Perl 6 allows you to dynamically prepare the template that gets inserted into the mainline code. That's right, the macro runs right in the middle of compile-time, much like a BEGIN block. This creates some interesting challenges having to do with crossing from compiling the program to running it, and back.
Much of the unique power of macros stems from straddling this boundary, essentially allowing you to program your program.
Before we dive into macros, let's make sure we understand lexical scoping and ordinary routines fully.
Lexical scoping is the idea that a variable declaration is scoped to the block it appears in:
{
# $var not defined here
my $var;
# $var defined here
}
# $var not defined here
What's especially powerful about this is that the scope information is available to the parser. We don't have to wait until runtime to get scoping errors. (This is what we mean by lexical scoping, as opposed to dynamic scoping.)
We all know the "shape" of arrays and hashes: arrays hold sequences and let us access them with an integer to get stuff out. Hashes hold mappings and let us access them with a string to get stuff out.
What is the shape of a routine?
Well, routines remember computations and let us access them with a bunch of parameters. Essentially, they are shaped like little programs. They can contain anything, including access to variables and its own variable declarations.
A closure is a function value with at least one variable defined outside of itself. Like so:
sub outer {
my $x = 42;
sub inner {
say $x; # 42
}
inner();
}
Together, those outside variables make up the environment of the closure. I do this a lot in my Perl 6 programming, because the environment of inner subs contains the parameters of outer subs, and so the inner subs need much fewer parameters.
It's so straightforward it doesn't even feel strange. But it actually is kinda strange and wonderful. It gets more obviously strange and wonderful when allow the closure to escape the scope of its environment.
Note that an anonymous function is not the same as a closure. An anonymous function is just a function literal that lacks a name. (Why are we so obsessed with functions having names? We don't go around calling integer literals "anonymous integers".) The confusion arises because we often use anonymous functions for their capacity to generate closures, like here:
sub counter-constructor(Int $start) {
my $counter = $start;
return sub { $counter++ };
}
(The sub is included to make this more readable to Perl 5 people. It's not really necessary in Perl 6.)
We've now returned the closure out of its environment. The environment lives on because it is referenced by the closure.
my $c1 = counter-constructor(5);
say $c1(); # 5
say $c1(); # 6
say $c1(); # 7
And we can prove to ourselves that each invocation to the outer function yields a unique closure with its separate environment:
my $c2 = counter-constructor(42);
say $c2(); # 42
say $c1(); # 8
say $c2(); # 43
Because a closure behave like this, a variable that's part of the closure's environment, like $counter, will have to be allocated on the heap rather than on the stack. Put differently, the presence of closures in a programming language necessitate garbage collection. See also the funarg problem.
Note that the $counter variable is completely encapsulated inside the outer function. We can provide piecemeal access to it in exactly the same way as we can with objects. Closures and objects are equal in power. Which carries us into the next section.
Because closures and objects are equal in power, they can be defined in terms of one another, like so:
- An object can be made out of a closure. Data hiding comes from declaring variables in the closure's environment. Behavior comes from calling the closure. We can emulate method dispatch by passing the method name as a first parameter.
- A closure is a kind of function object with its environment stored as data, and one method:
apply.
This duality has been immortalized in a koan by Anton van Straaten:
The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
For the purposes of this text, a closure is a callable thing with internal state, just like an object. An object's private environment is its class, and a closure's private environment is the totality of the variables defined outside of itself.
AST objects are closures. They are not like closures, they are closures. They are a representation of executable code (potentially) using variables declared outside of themselves.
If our actions are limited to the following, we can work with ASTs while preserving their environments:
- Extracting a sub-AST out of an AST.
- Inserting an AST into another.
- Inserting synthetic AST nodes into an existing AST.
If we manage to talk about an AST without an environment (by creating one from scratch, for example), we could make that AST do things and participate in code, as long as we don't refer to any outside variables.
Let's look at the lifetime of an ordinary subroutine through compilation and running. For simplicity, let's assume it's called exactly once.
- α: The subroutine is parsed.
- β: The subroutine call is parsed. (This may happen before the subroutine is parsed, actually, because subs can be post-declared. Nevermind.)
- γ: The subroutine call is run.
- δ: The subroutine runs.
Macros are more entwined in the process of parsing than that, and so for macros we can identify five stages:
- a: The macro and the
quasiare parsed. - b: The macro call is parsed. Immediately as the macro call has been parsed, we invoke the macro.
- c: The macro runs. As part of this, the
quasigets incarnated and now has no holes anymore. An AST is returned from the macro. - d: Back in parse mode, this AST is inserted into the call site in lieu of the macro call.
- e: At some point in the distant future, when compiling is over, the inserted macro code is run.
The steps b and d correspond to the relatively uninteresting step β. The runtime step c, corresponding to step γ, is sandwiched between the parse-time steps b and d. In short, subroutines have a clear separation of parse-time and runtime. Macros deliberately mix runtime with parse-time.
According to Wikipedia, "Hygienic macros are macros whose expansion is guaranteed not to cause the accidental capture of identifiers." That is, we don't want variables (or other names) to collide between the macro and the rest of the program. If we make it so that they don't, we've successfully made the macro hygienic.
Hygiene is a big deal for all languages with macros in them, since the lack of hygiene can cause weird behaviors due to unintentional collisions. We'll get back to various techniques used to achieve hygiene.
Let's reach for an example to illustrate how hygiene just falls out naturally when we treat ASTs as closures.
macro foo($ast) {
my $value = "in macro";
quasi {
say $value;
{{{$ast}}};
}
}
my $value = "in mainline";
foo say $value;
Keeping in mind that ASTs retain a "link" to their point of origin, we step through the stages of a macro:
- a
- The macro and the
quasiare parsed. $valuein thequasiblock is recognized to refer to the declared variable in themacroblock.
- The macro and the
- b
- The macro call is parsed. Immediately as the macro call has been parsed, we invoke the macro.
- An AST is created out of
say $valueas a natural effect of parsing. This AST is rooted in the mainline, so the$valuevariable refers to the one in the mainline.
- c
- The macro runs. As part of this, the
quasigets incarnated and now has no holes anymore. say $valuegets inserted, but retains its link to the mainline.- An AST is returned from the macro.
- This AST retains its link to the
macroblock.
- The macro runs. As part of this, the
- d
- Back in parse mode, this AST is inserted into the call site in lieu of the macro call.
- Because of how it was constructed, the AST as a whole links to the
macroblock, but a part of it links to the mainline.
- e
- At some point in the distant future, when compiling is over, the inserted macro code is run.
- And voila, it prints
in macroand thenin mainline.
This is perhaps the smallest example that shows how things stay out of the way of each other. Each step is simple and fully general. It works out similarly even for more composed cases, when the going gets really tough.
Wikipedia lists five ways to achieve hygiene in macros:
- Obfuscation. Using strange names that won't collide with anything else.
- Temporary symbol creation. Also known as "gensym".
- Read-time uninterned symbol. Essentially giving symbols inside of a macro their own namespace.
- Packages. Keeping the macro's symbols in a separate package.
- Hygienic transformation. The macro processor does gensym for you.
None of these ways rely on ASTs-as-closures. And yet that seems to be all that's required to solve the problem of macro hygiene.
When I have this working — and, after thinking about this for over half a year, I don't see any reason it shouldn't — I'm going to edit the Wikipedia page to include Closures as a sixth option.
Lexical scoping and all of its consequences may be the best idea in computer science, ever. Closures are a natural consequence of taking both lexical scoping and first-class function values seriously.
Function values are shaped not just according to the computation they perform, but also according to the environment they perform it in. This may sound like a weakness, but it's actually a great strength. We can use it to achieve encapsulation and data hiding, just like with objects.
The work on macros in Rakudo is coming along fine. I feel I have gained a deeper appreciation of lexical scoping and closures because of it. And there's more to come.