Proposal: lazy, context-based macro expansion

[jonathanvdc]

Hey there. I think I may have an elegant solution to the problem of semantic macros that works well for a full compiler like ecsc and provides a best-effort service for macro expansion utilities like LeMP.exe. This proposal deals with changes to the LeMP library.

My proposal

I'd like to propose a change to how LeMP expands macros. Specifically, I want it to support lazy, context-based macro expansion.

I'll try to explain what I mean by that:

• Lazy macro expansion: when LeMP is instructed to macro-expand a Loyc tree, it expands the root node only and wraps the resulting root node in an LNode implementation (say, ExpandedNode) that behaves exactly like this result when its non-LNode properties are accessed but automatically and lazily expands LNode values. The advantage of this approach is that it's entirely transparent: to an end-user, it feels like they're traversing a tree that's already been macro-expanded, but the expansion is actually happening on the fly. So this shouldn't break existing code.
• Context-based macro expansion: an ExpandedNode would also have a context implementation (the context may be defined as an interface: IMacroContext), which should at least include a method object Evaluate(LNode node) that evaluates a node. It should also be possible to take an ExpandedNode and create a new ExpandedNode with a different context from it. Since the original ExpandedNode will likely be discarded after this, its child nodes will never be expanded (thanks to lazy expansion) and the (potentially different) tree defined by the new ExpandedNode can be traversed without incurring a serious performance overhead.

So how does this solve the problem of semantic macros?

Whenever a full-stack EC# compiler stumbles across a construct that creates a new scope, it simply changes the context of the node it's evaluating. It implements this context's object Evaluate(LNode node) method by analyzing node and then evaluating the resulting IR. In other words, built-ins can be evaluated at macro-expansion time because macros are actually evaluated during the semantic analysis phase.

[qwertie]

I'm afraid this proposal isn't clear enough to evaluate as-written. Could you work through an example macro expansion and explain the order in which everything happens? How are nested macro invocations handled? Is all well if a macro pre-expands its children?

[jonathanvdc]

Could you work through an example macro expansion and explain the order in which everything happens? How are nested macro invocations handled?

I'm using my phone right now but I'll do my best to craft an example.

Let #isa(x, y) be a macro that checks if x is known to be an instance of y at compile-time. It expands to #builtin_static_is(#builtin_decltype(x), y).

Now suppose that we have the following snippet of code.

var i = 3;
static if (#isa(i, int))
{
    // ...
}
else
{
    // ...
}

The macro expansion/semantic analysis process does the following:

1. var i = 3; is macro-expanded. But there's nothing to expand, so the assignment is wrapped in an ExpandedNode as-is and is subsequently analyzed.
2. Semantic analysis touches var, i and 3. Like the assignment, they are (trivially) "expanded" when the analysis pass sees them. Also, i is added to the local scope which is linked to the macro context.
3. The static if statement is expanded. static if is a macro, so the macro processor expands it by calling the function that implements static if.
4. The implementation for static if calls its context's Evaluate method on the condition.
5. Evaluate is implemented as macro-expansion within the current context, followed by semantic analysis. #isa(i, int) is expanded and analyzed in a fashion similar to steps 1 and 2. The resulting IR is evaluated and returned by Evaluate.
6. The static if implementation picks the first block because #isa(i, int) evaluated to true. It returns this block, which the macro processor then wraps in an ExpandedNode.
7. The block ExpandedNode is handed over to semantic analysis, which creates a new scope and a new macro context linked to that scope. The context of the ExpandedNode is replaced with the new context (by creating a new ExpandedNode, not by mutating data).
8. Semantic analysis proceeds on the new block ExpandedNode. Macro expansion happens implicitly by touching child nodes.

Is all well if a macro pre-expands its children?

That's not something I had considered. Pre-expanding children could work fine for an ahead-of-time macro expansion utility like LeMP.exe because it never has to change the context of a node.

A full-stack compiler is different. It feeds the macro processor's output into semantic analysis. To analyze a node, the compiler needs to know what it's looking at, which requires the top-level node to be expanded first. To properly macro-expand a node, its ancestors need to be analyzed by semantic analysis. So the top-level node cannot be expanded last because that leads to a chicken-egg problem: it needs to be analyzed/expanded before its children can be expanded but its children can only be analyzed/expanded after it has been expanded.

[qwertie]

I always thought of the LNode class hierarchy as merely an implementation detail; I never foresaw abuse of it to produce the lazy behavior you propose for ExpandedNode, but I'll accept some kind of lazy behavior as a given for now.

Your description uses the passive voice a lot, so I can't tell what components are involved and their responsibilities. So I would add these questions:

• Hrm. The assignment is wrapped in an ExpandedNode even though it doesn't need lazy behavior?
• By what means is semantic analysis inserted before macro expansion?
• There is no IMacroContext.Evaluate method. PreProcessChildren and PreProcess are the methods used to perform macro expansion on children. You're suggesting the implementation of static_if should be changed? What's different about Evaluate?
• static if doesn't currently create any kind of new scope. Are you saying it should create a scope now? Are we talking about a different kind of scope than that in the macro processor?

Edit: btw, PreProcess and PreprocessChildren are used pretty often. about 22 macros use the former and 3 use the latter. (Interestingly only one macro is still using MacroMode.ProcessChildrenBefore; I ought to get rid of it.)

[jonathanvdc]

Heh. Sorry about the passive voice. I sometimes find it hard to imagine data structures actually doing something. I didn't deliberately mean to be vague.

I'll go over your remarks one by one:

Hrm. The assignment is wrapped in an ExpandedNode even though it doesn't need lazy behavior?

Yes! That's because you can't (easily) tell in advance if a node needs lazy behavior. For example, bool b = { int x = 3; #isa(x, int) }; is entirely pointless (but legal) and does need the lazy behavior because the block ({ ... }) creates a new scope which implies a macro context change. If we didn't change the context here, then how else could the #isa know x's type? x is not accessible from the assignment's scope and, by extension, its context.

By what means is semantic analysis inserted before macro expansion?

That's where the laziness comes in. Lazy macro expansion happens on-the-fly, so expanding macros "first" and then applying semantic analysis will automatically interleave the two processes. Furthermore, semantic analysis can cheaply change the macro expansion context and macro expansion can trigger semantic analysis if Evaluate is implemented to do so.

Gonna grab some breakfast now. I'll try to answer the remainder of your questions as soon as possible.

[jonathanvdc]

There is no IMacroContext.Evaluate method. PreProcessChildren and PreProcess are the methods used to perform macro expansion on children. You're suggesting the implementation of static_if should be changed? What's different about Evaluate?

If I understand correctly, PreProcess and friends macro-expand an LNode in isolation. That's probably also what Evaluate would do in LeMP.exe. But in ecsc, Evaluate can be implemented to take advantage of all the information gathered by the semantic analysis phase.

Pardon my ignorance. I have just discovered IMacroContext exists already.

Still, this does not eliminate the discrepancy in terms of intent between PreProcess ("expand this tree for me") and Evaluate ("expand this tree and evaluate it as an expression"). ecsc can't just try to evaluate every PreProcessed tree on the off chance that it'll turn out to be an expression.

Perhaps ecsc's built-ins can be reimplemented as macros that rely on information from semantic analysis. But that would mean that something like static if would not support arbitrary constant Boolean expressions—it would support only those expressions for which enough macros have been defined such that they can be simplified into a literal. We could, of course, write a constant-folding macro for each type of expression. But that seems wasteful because all of this logic has already been implemented by the compiler.

static if doesn't currently create any kind of new scope. Are you saying it should create a scope now? Are we talking about a different kind of scope than that in the macro processor?

I meant to refer to a C# local scope as created by the blocks in the static if.

[jonathanvdc]

Maybe I should phrase more clearly what Evaluate does: it takes an expression LNode and tries to ascertain the value it evaluates to.

So evaluating tree 1 + 2 returns value 3, even if this is not desirable from a macro expansion viewpoint (because information is lost).

[qwertie]

Okay, so Evaluate makes sense, though it leaves the question of how to implement static_if so that it also works without ecsc. Static_if should really not create a scope, though.

I still don't really understand the proposed process. I would suggest trying to implement it yourself and see how things work out.

[jonathanvdc]

Thanks for your feedback! I'll give implementing this a shot in about a week or so. If this works out, then I'll send a PR with my proposed changes.

Also, some thoughts on your last comment:

Okay, so Evaluate makes sense, though it leaves the question of how to implement static_if so that it also works without ecsc.

If static_if is updated to call Evaluate then ecsc can simply provide its own IMacroContext implementation to make LNode evaluation "smart," right?

static_if should really not create a scope, though.

It won't —but the blocks inside a static_if will. I'm talking about these guys here:

    static if (...)
->  {
->    // ...
->  }
    else
->  {
->    // ...
->  }

[qwertie]

Er, those shouldn't create scopes either. Consider:

static if (...) {
    int _x;
    int X { get => _x; }
} else {
    float _x;
    float X { get => _x; }
}

(You can use double-curlies {{ }} to get scopes)

If static_if is updated to call Evaluate then ecsc can simply provide its own IMacroContext implementation to make LNode evaluation "smart," right?

I guess so, but then what does it do in LeMP, just act the same as PreProcess?

[jonathanvdc]

Er, those shouldn't create scopes either.

Right. I should've clarified that I thought of my example as part of a method body, not as part of a type definition. ecsc doesn't create scopes for blocks in type definitions, but it does create scopes in method body definitions.

Looking at the source code, I see that static_if special-cases block statements by splicing their children. I'm kind of in two minds about that. Injecting the contents of a block in a static_if statement into the containing statement does enable a bunch of scenarios, but on the other hand it breaks the rule that braces always introduce a scope of some kind.

Making metaprogramming workable is more important than keeping that rule, I suppose. But it did confuse me. Is this also how the D programming language handles blocks in static_if?

I guess so, but then what does it do in LeMP, just act the same as PreProcess?

That's pretty much what I had in mind. Also, LeMP's implementation of Evaluate can be enhanced with logic that performs constant-folding. Right now, static_if can reduce Boolean expressions. That logic ought to be moved into LeMP's Evaluate implementation.

It's kind of a best-effort approach, but that has more to do with how LeMP works than with how Evaluate would work.

[qwertie]

ecsc doesn't create scopes for blocks in type definitions, but it does create scopes in method body definitions.

A similar argument can be made for inside methods, though.

Is this also how the D programming language handles blocks in static_if?

Yes.

IIRC, one of my early ideas about EC# was to have a different syntax for blocks that don't create scopes: #{...} vs {...}. But I dropped that idea, deciding that # would just be an ordinary identifier character.

Right now, static_if can reduce Boolean expressions. That logic ought to be moved into LeMP's Evaluate implementation.

Okay, that makes sense.