A musing on scoping

musing.md

This is the second attempt at writing this musing. This stuff is hard.

Scheme is lexically scoped: all possible variable bindings in a program unit can be analyzed by reading the text of the program unit without consideration of the contexts in which it may be called. — Wikipedia

Dylan macros are always hygienic. The basic idea is that each named value reference in a macro expansion means the same thing as it meant at the place in the original source code from which it was copied into the macro expansion. — Dylan Reference Manual

Let's talk about variable lookup. It's that thing where you write a variable name like file, and the runtime somehow knows the memory location of the value in that variable.

Even better, let's talk about lexical variable lookup, in which a variable can always be found defined earlier in the same scope or a surrounding scope. As the Wikipedia quote points out, lexical lookup is great because you can find the definition by looking at the program text (or the AST), rather than having to run or simulate running the program. We like static program properties, and we take them where we can get them.

Variable names are for humans. Computers don't care and could easily use numbers instead. The compiler could "erase" the names and replace each unique name by a unique index. The index would then be used for lookup.

my x;   # 0
{
    my y;   # 1
    say(x); # 0
    say(y); # 1
}
say(x); # 0

As lookup schemes go, this one works fine until block re-entrancy becomes a feature, as in the same block being entered multiple times before it's exited. Here's a concrete example with recursion:

func walk(dir, fn) {
    for dir.listing() -> file {
        if file ~~ Directory {
            walk(file, fn);
        }
        else {
            fn(file);
        }
    }
}

Think about dir in the concrete case of this file hierarchy:

root/
  dir-a/
    file-a
  file-b

walk will be called twice, once for root/ and once (recursively) for root/dir-a/. After the latter call is finished, execution finds itself back in the former call, and the dir parameter should once again point to root/, not to root/dir-a/.

In order to make this work, variables need to be stored in a frame. A frame arises every time a block is entered; the new frame holds that block's variables. After a block has been exited its frame can be discarded — or rather, the usual GC rules apply. Something might still want the frame even after it's finished executing — cf. "closure semantics".

Variable lookup is local if the definition is in the same block. For the other cases, a frame holds an outer pointer to another frame. All frames fit together in a singly-linked tree via their outer pointers. Conceptually what we are doing in a lookup is to traverse up the tree and find the first definition of the variable.

Here is a small table showing the analogues between static and dynamic concepts:

static	dynamic
parsing	running
block	frame
1-to-1 with { .. } in code	1-to-n with { .. }, 1-to-1 with block entries
block's outer pointer	frame's outer pointer
variable declaration	allocating a slot in a frame
variable use	lookup

In order to do lookup, we now provide two numbers (t, i). t is the number of outer pointers we need to follow, and i is the index of the variable within the frame we find. Notice in particular that these two numbers are a static property of the lookup; they never change. But what can change is the current frame and the traversed outer frames — that's why we can't reduce it to less than these two numbers.

(Maybe this reminds you of De Bruijn indexing? Then again, maybe not.)

Going back and re-annotating our original example:

my x;   # x: (0, 0)
{
    my y;   # y: (0, 0)
    say(x); # x: (1, 0)
    say(y); # y: (0, 0)
}
say(x); # x: (0, 0)

And the recursive walk example:

func walk(dir, fn) {                # walk: (0, 0), dir: (0, 1), fn: (0, 2)
    for dir.listing()               # dir: (0, 1)
                      -> file {     # file: (0, 0)
        if file ~~ Directory {      # file: (0, 0), Directory: (?, ?) (some builtin)
            walk(file, fn);         # walk: (2, 0), file: (1, 0), fn: (2, 2)
        }
        else {
            fn(file);               # fn: (2, 2), file: (1, 0)
        }
    }
}

Besides frames having outer pointers, each routine also has a caller pointer to the frame where the routine was called. Dynamic lookup uses the caller pointer at routine boundaries. Lexical and dynamic lookup start to differ when a function value is passed across frames as a parameter or return value. For example:

my count = 0;
func increment(_) {
    count = count + 1;
}

walk(root, increment);      # same root as above, with 2 files
say(count);                 # 2

Lexical lookup means count will be incremented from inside increment even though the function was passed into walk and is called as the parameter fn in a completely different context inside. In this code, count can even be declared after the call to fn inside walk, and it'll all work out fine.

Closures are cool that way. But in the end, closures are a natural consequence of lexical scoping working the way it should even when first-class function values have been passed and separated from their point of definition.

The donkey bridge slogan here could be "the variable gets looked up where the code was written". Not where it's called from.

Then it gets... interesting

I think the thing to understand about macro semantics is that we like closures so much that we want them to happen with macros too, even though macros are built on code generation and copying of code, rather than passing functions.

A quick example, inspired by #176 but rendered using the latest understanding of 007 syntax:

@parsed(/"[" <infix> "]"/)
macro term:reduce(op: Q.Infix) {    # op: (0, 0)
    return quasi {
        (func (...values) {
            return values.reduce({{{op.identifier}}})   # op: (2, 0)
        })
    };
}

This macro lets you write mainline code like this:

[+](1, 2, 3);      # 6

The op inside of the quasi block is the one appearing to operate by ordinary closure mechanics. The [+] has generated an anonymous function which gets called with the arguments 1, 2, 3 in the mainline code. The + in the middle of the [+] is parsed in the @parsed annotation and shows up as a parameter op to the macro. It's then looked up from within that anonymous function. This is ordinary lexical lookup as we know it.

But! Not so fast. In order for the above to work, two miracles need to happen.

The first is that it's not actually the code in the quasi running. Quasi code never runs, it's full of holes and not complete yet. The actual code is injected in place of the [+] in the mainline; we call this code an injectile. Injectiles correspond to some code from a macro, but there is one independent injectile for every macro call made during parsing.

Because the injectile is somewhere completely different in the code but the lexical lookup still needs to work, the injectile gets a dislodged outer pointer, same as the quasi's pointer. The dislodged outer pointer is what guarantees lexical hygiene, the guarantee that same-named variables in macro code and mainline code will never interfere.

In a way, the donkey bridge slogan still works: "the variable gets looked up where the code was written". But it might be clearer to say "where the code was originally written", since the injectile is code generated by the parser using your original quasi as a template.

We are not done.

A macro is an opaque routine that the parser calls with some (Qnode) arguments, and it gets a (Qtree) result back. The second miracle that needs to happen is that in order to properly dislodge the injectile's outer pointer, it needs to somehow have access to the quasi's outer pointer; a quasi that it never itself saw, because it delegated the whole work to the macro. By the sacred covenant of variable locality, we're not allowed to ask the macro about its quasi.

(Heck, it might not even be a quasi! A macro is allowed to produce a Qtree to return completely synthetically, just by constructing Qnodes. Or, you know, it might be several quasis, each with its own outer pointer, patched together into a return value somehow.)

The only viable solution I've come up with is this: the Qnode corresponding to the quasi block needs to carry information about its outer pointer. It then gets returned from the macro to the thing in the parser that handles injection into the mainline, and this thing can then do the outer pointer dislodging as it needs to.

Note how completely backwards this is. Up until this point, only runtime values cared about frames. Qnodes are compile-time values, and blocks in particular are the static "analogue" of frames. But here we need a block pointing to a frame.

(In retrospect it can be explained, of course: a macro runs at compile time, so maybe it's not so strange that it produces compile-time values (ASTs) with some runtime dependencies?)

Again, there's a corresponding thing happening with function values: as a function value is created from a function declaration, it needs to hold an outer pointer to the frame it was created in. This is then used in each invocation of that function as the new frame's outer pointer. (Had we used the caller's frame as the outer pointer, we'd have gotten dynamic lookup.)

Spelling out the correspondence here, in a table:

closures	macro hygiene
function definition	quasi
function value	quasi's Qtree
function value's outer pointer	quasi Qtree's outer pointer
function invocation	macro invocation / quasi templating / mainline injection
function's frame	injectile's frame
outer/caller are different	injectile is dislodged
function's frame's outer pointer	quasi's frame's outer pointer / injectile's frame's outer pointer
"lookup where code was written"	"lookup where code was originally written"

Lexical lookups are great. They are so great that macros, quasis and injectiles are willing to break a few eggs to get the appearance lexical lookup even when code has been generated and several scopes from both macro and mainline need to interact.

Omitted from the above: a similar-but-opposite dislodging needs to happen when macro arguments from the mainline get used in the quasi block, because we expect their outer pointer to be the mainline, not the quasi.

Appendix: jnthn's version

After talking to jnthn about the above, I learned a few more things:

• There's really no such thing as a "dislodged outer pointer". That is, the mechanism described above which helps us achieve macro hygiene does not exist in MoarVM.
• But for a very good reason we're still within the realm of the possible, namely:
• Macros are run during compile-time, so every lookup into a macro scope can be precomputed and replaced by its result, the location itself in the macro scope.
• (This is exactly the thing that we can't do with functions running during runtime, because what's dynamic about them is that the same function is called multiple times and create multiple frames, and the same variable in the program text ends up looking up multiple locations in various frames. With macros that's not an issue, because whereas a macro may very well be called several times, each new call results in a new injectile — so within each injectile a given variable resolving its lookup into a macro frame resolves to a unique/unchanging location. Phew!)

This is perhaps best described using the colors metaphor I developed long ago to think about the different scopes:

macro moo(arg) {
    my macrovar = ...;      | RED CODE
                            | RED CODE
    return quasi {          | RED CODE
        ...macrovar...;     | RED CODE
        ...{{{arg}}}...;      (hole)
        ...macrovar...;     | RED CODE
    }
}

my mainlinevar = ...;       | BLUE CODE
moo(mainlinevar);             (macro call)

The injectile, which we'll never see in the actual source code because it's generated by the macro system, ends up looking like this:

...macrovar...;             | RED CODE
...mainlinevar...;          | BLUE CODE
...macrovar...;             | RED CODE

What my proposal above amounts to is that the injectile will need to dislodge its outer pointer in order for macrovar to be visible from the macro call into the injectile — and then each macro argument also needs to dislodge its outer pointer back to the mainline code in order to be able to see the mainline code's variable bindings.

What jnthn's proposal amounts to is that each red-code variable lookup gets precomputed at macro injection time and replaced with a direct "reference" to its memory location inside the macro's frame. If we rule out the concept of dislodged outer pointers, there's no lexical lookup in general that would find macrovar (since the macro is not a block that surrounds the mainline). But that doesn't matter, because the lookup has been compiled away.

Even more elegantly, with the macro arguments, we don't need to take any action at all, because normal lexical lookup will just work for them.

Semantically, the "dislodged outer pointer" and the "precompute macro frame lookups" come out indistinguishable. It's even possible that we will have to live with the former at some stages of the compilation pipeline, and then later "collapse" it into the latter as we near the actual bytecode.