Recently 2 ideas have been proposed to reduce the need for recursive templates:

* A `Seq...` expression to expand inline a named sequence, or an expression containing one or more named sequences.
https://www.digitalmars.com/d/archives/digitalmars/D/I_dun_a_DIP_possibly_the_best_DIP_ever_337252.html#N337252

This is essentially just a compiler intrinsic to perform the std.meta.Map operation, so it cannot wholly implement the other recursive templates in std.meta (though in some cases it may help).

* 'Type functions' - special functions which can mutate aliases and sequences using the syntax of runtime constructs.
https://forum.dlang.org/thread/qdirevtnhnejmrpetcpr@forum.dlang.org

This is more general, but it cannot be used internally in std.meta because it is a different paradigm. AIUI, for example, instead of passing a template predicate to std.meta.Filter you would pass a type function to a type-function-based version of Filter. It would have a fairly big impact on Phobos to make wide use of it.

So I've come up with something that is between the two, but hopefully is still general enough to implement a fairly wide class of recursive templates. The idea is to have an expression which recursively evaluates arguments for the next iteration, similar to std.algorithm.fold but at compile-time.
https://dlang.org/phobos/std_algorithm_iteration.html#fold

FoldExpression:
    __Fold(AccumulatorDecls) if (Expression) {FoldStatements}
AccumulatorDecl:
    Identifier
    BasicType Identifier
    alias Identifier
    Identifier...
FoldStatement:
    __Fold!(Expressions);
    static if (Expression) FoldStatement else FoldStatement

Here's how you could implement std.meta.Map:

alias Map(alias Tem, S...) =
    __Fold(Acc...) if (Acc.length != S.length) {
        __Fold!(Acc, Tem!(S[Acc.length]));
    };

Initially, Acc is an empty sequence. The __Fold!() expression defines what the next iteration's parameters will be, in this case `Tem!(S[0])` if s.length > 0. The second iteration will evaluate to __Fold!(Tem!(S[0]), Tem!(S[1])) if s.length > 1. When the `if` expression is false, the FoldExpression evaluates to a sequence of its last parameter values, i.e. Acc above.

If you like, you can also implement that with an index as a parameter:

alias Map(alias Tem, S...) =
    __Fold(uint i = 0; Acc...) if (i != S.length) {
        __Fold!(i + 1, Acc, Tem!(S[i]));
    }[1..$];

The result of the __Fold expression is a sequence (i, Acc), so we slice just the Acc part to remove the final index element and obtain just the mapped items.

Within the FoldStatements, we can use `static if`, so we can easily implement Filter:

alias Filter(alias pred, S...) =
    __Fold(uint i = 0; Acc...) if (i != S.length) {
        static if (pred!(S[i]))
            __Fold!(i + 1, Acc, S[i]);
        else
            __Fold!(i + 1, Acc);
    }[1..$];

We can also implement std.meta templates that don't create a sequence:

enum anySatisfy(alias pred, S...) =
    __Fold(bool found = false; uint i = 0)
        if (!found && i != S.length) {
            static if (pred!(S[i]))
                __Fold!(true, i);
            else
                __Fold!(false, i + 1);
        }[0];

Note: core.internal.traits actually implements anySatisfy with `static foreach` rather than template recursion, but I'm hoping the above can be competitive with that. The same is true for std.meta.staticIndexOf:

enum staticIndexOf(alias A, S...) =
    __Fold(bool found = false; uint i = 0)
        if (!found && i != S.length) {
            static if (isSame!(A, S[i]))
                __Fold!(true, i));
            else
                __Fold!(false, i + 1);
        }[1];

Note: isSame is a private template of std.meta.

How about templates that can't be implemented with `static foreach`?

// similar to std.traits.fullyQualifiedName (the real version would
// instantiate a formatting template instead of using stringof).
enum fqn(alias A) =
    __Fold(string acc = A.stringof; alias S = A)
        if (__traits(compiles(parent, S))) {
            __Fold!(__traits(parent, S).stringof ~ '.' ~ acc,
                __traits(parent, S));
        }[0];

FoldExpression can't replace divide and conquer recursion, but for std.meta.staticSort it can replace the private template staticMerge:

template Merge(alias Less, uint half, S...)
{
    alias Result = __Fold(uint i = 0; uint j = half; Acc...)
        if (i != half && j != S.length) {
            static if (Less!(S[i], S[j]))
                __Fold!(i + 1, j, Acc, S[i]);
            else
                __Fold!(i, j + 1, Acc, S[j]);
        };
    // fold handles min(half, S.length - half) elements of S
    // then append any remaining elements
    alias Merge = AliasSeq!(Result[2..$],
        S[Result[0]..half], S[Result[1]..$]);
}

But is a FoldExpression really more efficient than a recursive template? Yes:

* It doesn't insert templateName!args strings into a symbol table
* It doesn't permanently cache the result of each iteration
* It doesn't declare any symbol, so it doesn't need its own scope
* For __Fold(T[] acc), a __Fold!(acc ~ element) expression could reuse any spare capacity in the array to append element.
* For __Fold(Acc...), a __Fold!(Acc, Element) expression  could reuse any spare capacity in the memory allocated for Acc to append Element.

What do you think?

On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:
> Recently 2 ideas have been proposed to reduce the need for recursive templates:
>
[...]
>
> So I've come up with something that is between the two, but hopefully is still general enough to implement a fairly wide class of recursive templates. The idea is to have an expression which recursively evaluates arguments for the next iteration, similar to std.algorithm.fold but at compile-time.
> https://dlang.org/phobos/std_algorithm_iteration.html#fold
>
[...]
>
> What do you think?

This is fundamentally the same kind of thing as the proposed `...` operator--a single AST macro added to the language as a special-case feature, rather than a general facility for doing AST-macro-like things.

Of course, Walter has vetoed full-fledged AST macros, so we won't be seeing those in D any time soon, but I think it is perhaps worth taking a look at which features of AST macros would be useful to have (e.g., not storing intermediate values in the symbol table), and attempting to design a general-purpose facilities that give the programmer access to those features.

On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:
> Recently 2 ideas have been proposed to reduce the need for recursive templates:

The reason for these is that recursive template expansion is slow and can use a lot of memory which is never freed.

> * A `Seq...` expression to expand inline a named sequence, or an expression containing one or more named sequences.

Sorry, this should've read: "`Expression...` to expand an expression containing one or more named sequences". Here's the DIP link:
https://github.com/dlang/DIPs/blob/f9790ee6760b2d3cd0dbc1e816080c29c00c6dc2/DIPs/DIP10xx.md#add-unary-operator-

> This is essentially just a compiler intrinsic to perform the std.meta.Map operation, so it cannot wholly implement the other recursive templates in std.meta (though in some cases it may help).

Manu did propose a follow up to that would support a very basic fold expression, but it seems to be limited to using an operator between element expressions (no `static if`):

>> Static reduce would allow `...` as an argument to a BinOp
>> Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
>> You could do `is(FindType == Tup) || ...`, and it would evaluate true if
>> FindType exists in Tup, with no junk template instantiations!

https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d@puremagic.com

On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:
> the FoldExpression evaluates to a sequence of its last parameter values

Actually it probably would be OK to use the parameter names as properties of the FoldExpression.

> template Merge(alias Less, uint half, S...)
> {
>     alias Result = __Fold(uint i = 0; uint j = half; Acc...)
>         if (i != half && j != S.length) {
>             static if (Less!(S[i], S[j]))
>                 __Fold!(i + 1, j, Acc, S[i]);
>             else
>                 __Fold!(i, j + 1, Acc, S[j]);
>         };
>     // fold handles min(half, S.length - half) elements of S
>     // then append any remaining elements
>     alias Merge = AliasSeq!(Result[2..$],
>         S[Result[0]..half], S[Result[1]..$]);
> }

alias Merge = AliasSeq!(Result.Acc,
    S[Result.i .. half], S[Result.j .. $]);

Easier to understand.

On Sun, Jun 14, 2020 at 9:50 PM Nick Treleaven via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On Saturday, 13 June 2020 at 10:52:46 UTC, Nick Treleaven wrote:
> > Recently 2 ideas have been proposed to reduce the need for recursive templates:
>
> The reason for these is that recursive template expansion is slow and can use a lot of memory which is never freed.
>
> > * A `Seq...` expression to expand inline a named sequence, or an expression containing one or more named sequences.
>
> Sorry, this should've read: "`Expression...` to expand an expression containing one or more named sequences". Here's the DIP link:
>
> https://github.com/dlang/DIPs/blob/f9790ee6760b2d3cd0dbc1e816080c29c00c6dc2/DIPs/DIP10xx.md#add-unary-operator-
>
> > This is essentially just a compiler intrinsic to perform the std.meta.Map operation, so it cannot wholly implement the other recursive templates in std.meta (though in some cases it may help).
>
> Manu did propose a follow up to that would support a very basic fold expression, but it seems to be limited to using an operator between element expressions (no `static if`):
>
> >> Static reduce would allow `...` as an argument to a BinOp
> >> Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
> >> You could do `is(FindType == Tup) || ...`, and it would
> >> evaluate true if
> >> FindType exists in Tup, with no junk template instantiations!
>
>
> https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d@puremagic.com
>
>

It's implemented in my branch too if you wanna try it out!

On Sunday, 14 June 2020 at 12:01:51 UTC, Manu wrote:
> On Sun, Jun 14, 2020 at 9:50 PM Nick Treleaven via Digitalmars-d < digitalmars-d@puremagic.com> wrote:
>> Manu did propose a follow up to that would support a very basic fold expression, but it seems to be limited to using an operator between element expressions (no `static if`):
>>
>> >> Static reduce would allow `...` as an argument to a BinOp
>> >> Ie; `Tup + ...` would expand `Tup[0] + Tup[1] + Tup[2] + ...`
>> >> You could do `is(FindType == Tup) || ...`, and it would
>> >> evaluate true if
>> >> FindType exists in Tup, with no junk template instantiations!
>>
>> https://forum.dlang.org/post/mailman.2786.1587566241.31109.digitalmars-d@puremagic.com
>>
> It's implemented in my branch too if you wanna try it out!

https://github.com/TurkeyMan/dmd/commit/e150fa03521e1d5d12c77477c6dbcb46c9292fac

Haven't tried it, but it doesn't seem to be able to help with recursive templates much. It can do std.meta.anySatisfy and allSatisfy, but probably can't do much other folding of sequences that don't contain values.

On Saturday, 13 June 2020 at 12:35:58 UTC, Paul Backus wrote:
> This is fundamentally the same kind of thing as the proposed `...` operator--a single AST macro added to the language as a special-case feature, rather than a general facility for doing AST-macro-like things.
>
> Of course, Walter has vetoed full-fledged AST macros, so we won't be seeing those in D any time soon, but I think it is perhaps worth taking a look at which features of AST macros would be useful to have (e.g., not storing intermediate values in the symbol table), and attempting to design a general-purpose facilities that give the programmer access to those features.

I realized my FoldExpression feature invented too much syntax. Really all we need is a way to limit what a template can do, i.e. (1) not cache instantiations and (2) not declare symbols (aside from eponymous symbols) so it can share a single Scope instance in dmd. That Scope instance would be reused upon each recursion, and only one recursion is allowed in each inner `static if` branch. That could be done just by recognizing a special identifer __Fold:

template staticIndexOf(alias A, S...)
{
    template __Fold(uint i = 0)
    {
        static if (i != S.length)
        {
            static if (isSame!(A, S[i]))
                enum __Fold = i;
            else
                enum __Fold = __Fold!(i + 1);
        }
        else
            enum __Fold = -1;
    }
    alias staticIndexOf = __Fold!();
}

Or we could have separate template attributes for wider applicability. In fact those attributes could potentially be inferred, although doing that by default might slow compilation. Then existing code could even benefit from the new attributes.

On Friday, 19 June 2020 at 17:04:57 UTC, Nick Treleaven wrote:
> On Saturday, 13 June 2020 at 12:35:58 UTC, Paul Backus wrote:
>> [...]
>
> I realized my FoldExpression feature invented too much syntax. Really all we need is a way to limit what a template can do, i.e. (1) not cache instantiations and (2) not declare symbols (aside from eponymous symbols) so it can share a single Scope instance in dmd. That Scope instance would be reused upon each recursion, and only one recursion is allowed in each inner `static if` branch. That could be done just by recognizing a special identifer __Fold:
>
> [...]

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.

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.

On Friday, 19 June 2020 at 18:30:28 UTC, Paul Backus wrote:

> 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.

I've tried to implement TCO, and it's really hard to do.
I would think it's best to present iteration as well interation.
There is no need to go into awkward recusion patterns.