Macro templates [Was: Re: Compile-time fold expression vs recursive template]

[Paul Backus]

On Friday, 19 June 2020 at 17:36:54 UTC, Stefan Koch wrote:
>
> We should talk and band together.
> Multiple competing proposals won't help here.
>
> We at least have gained some clarity about the problem.
> Now let's gain some clarity about the solution space.

Here's my idea: we introduce a new kind of template called "macro 
templates" (working title).

Macro templates are like regular templates, but with two 
differences. First, they are subject to the following 
restrictions:

- A macro template may only contain `enum` and `alias` 
declarations.
- A macro template must have an eponymous member.

Second, each instantiation of a macro template is evaluated 
independently, and once evaluated is immediately replaced in the 
source code with the value of its eponymous member. All 
intermediate results are discarded.

To give a concrete example, here's how `staticMap` could be 
written as a macro template:

macro template staticMap(alias F, Args...)
{
     static if (Args.length == 0)
         alias staticMap = AliasSeq!();
     else
         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, 
Args[1 .. $]));
}

And here's how an instantiation of that version of `staticMap` 
would be evaluated:

alias result = staticMap!(ConstOf, int, char, double);

... = AliasSeq!(
           ConstOf!int,
           staticMap!(ConstOf, char, double));

... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               staticMap!(ConstOf, double)));


... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               AliasSeq!(
                   ConstOf!double,
                   staticMap!(ConstOf))));

... = AliasSeq!(
           ConstOf!int,
           AliasSeq!(
               ConstOf!char,
               AliasSeq!(
                   ConstOf!double,
                   AliasSeq!())));

The total cost here, in terms of symbol-table bloat, is:
- 4 instances of `AliasSeq`
- 3 instances of `ConstOf`

Notice that `staticMap` itself has completely disappeared. By 
making `AliasSeq` and `ConstOf` into macro templates as well, we 
can get the entire thing to reduce down to:

alias result = (const(int), const(char), const(double));

That is, we can eliminate *all* symbol-table bloat, and retain 
only the final result.

To achieve Nick Treleaven's goal of re-using the same Scope for 
each "iteration", all that is necessary is for the compiler to 
implement tail-call optimization for macro templates (a 
well-known and well-studied technique). `staticMap` can then be 
easily re-written to use a tail-recursive helper template.

One big advantage of this approach is that it is largely 
backwards compatible. Many existing templates can be converted 
simply by adding the `macro` keyword to their definition, without 
breaking existing code that depends on them.