On Thursday, 24 September 2020 at 02:42:00 UTC, Paul Backus wrote:
>
> On the other hand, if you can fix recursive template bloat somehow (tail-call elimination?), you get good performance *and* nice code. It's the best of both worlds.

good performance yes.
But where is the nice code, when you are confined to recursive templates?

On Thursday, 24 September 2020 at 03:04:46 UTC, Stefan Koch wrote:
> On Thursday, 24 September 2020 at 02:42:00 UTC, Paul Backus wrote:
>>
>> On the other hand, if you can fix recursive template bloat somehow (tail-call elimination?), you get good performance *and* nice code. It's the best of both worlds.
>
> good performance yes.
> But where is the nice code, when you are confined to recursive templates?

I suppose whether you think recursion is pleasant or unpleasant is a matter of taste. Personally, I rather like it. :)

On 9/23/20 10:42 PM, Paul Backus wrote:
> On Thursday, 24 September 2020 at 02:09:31 UTC, Jackel wrote:
>>
>> It's basically what D is to C++ template metaprogramming.
>>
>> Compare the staticMap implementation with a type function implementation and it's pretty clear which one is more readable and easier to maintain. The current D implementation will also create a bunch of template bloat with numerous instantiations that aren't actually required.
>>
>> StaticMap, and many other templates like it also need a workaround to reduce the number of instances, otherwise they fail. Which isn't as intuitive and not something someone will really know to do.
> 
> On the other hand, if you can fix recursive template bloat somehow (tail-call elimination?), you get good performance *and* nice code. It's the best of both worlds.

The recursive version is not nice code. It's hard to understand and difficult to follow. It's main advantage is that because it's essentially a functional language, and all templates are cached, in certain cases, you can see a performance gain because the compiler can avoid actually redoing what it did. In practice, for things like staticMap, this doesn't ever pan out.

I don't see how you solve the tail recursion thing anyway -- each template instance cannot rely on the work that has already been done, because of static if.

The static map type function is a loop over an array. Easy to understand, easy to write. It's actually boring code. Static map shouldn't be interesting code at all.

-Steve

On Thursday, 24 September 2020 at 02:42:00 UTC, Paul Backus wrote:
> On Thursday, 24 September 2020 at 02:09:31 UTC, Jackel wrote:
>>
>> It's basically what D is to C++ template metaprogramming.
>>
>> Compare the staticMap implementation with a type function implementation and it's pretty clear which one is more readable and easier to maintain. The current D implementation will also create a bunch of template bloat with numerous instantiations that aren't actually required.
>>
>> StaticMap, and many other templates like it also need a workaround to reduce the number of instances, otherwise they fail. Which isn't as intuitive and not something someone will really know to do.
>
> On the other hand, if you can fix recursive template bloat somehow (tail-call elimination?), you get good performance *and* nice code. It's the best of both worlds.

It would be a very welcome performance improvement for current template programming, yes but, for me, type functions are about a lot more than the compile time performance improvement they would bring.  Making a big chunk of meta programming easier to understand, easier to debug, easier to compose, is the big payoff.  "It's just like your other programming".

And yes, it would be nice if we could get the performance associated with iterative implementations guaranteed rather than hope the compiler can find actual recursion within the unrestricted polymorphic context of templates.

On Wednesday, 23 September 2020 at 22:36:55 UTC, Walter Bright wrote:
> On 9/23/2020 4:49 AM, Per Nordlöw wrote:
>> Great work. Has Andrei given any advice on how to proceed regarding dip, reviews and acceptance? I presume this will get merged behind a -preview if it gets merged.
>
> The other way to do it is just have the compiler recognize recursive templates and implement them directly. This would provide the speedup, while not adding new features or requiring any user code changes - it'll just run faster.

The problem here is just.
As you might be aware, I have been looking into this problem for a while.

The issue is that templates are polymorphic, which means that static analysis of a template is not possible, in the general case.

The case which I have identified where analysis of a template is possible is this one:

- template does not use string mixin dependent on a parameter or outer template context.
- template does not use static if's dependent on parameters or outer template context.
- template does not use static foreach or foreach dependent on parameters or outer template context.

that means no static if, no foreach, and no mixin.
If you can write useful metaprogramming  templates given those constraints then it's possible to optimize them.

On Thursday, 24 September 2020 at 03:17:44 UTC, Steven Schveighoffer wrote:
> On 9/23/20 10:42 PM, Paul Backus wrote:
>> On Thursday, 24 September 2020 at 02:09:31 UTC, Jackel wrote:
>>>
>>> It's basically what D is to C++ template metaprogramming.
>>>
>>> Compare the staticMap implementation with a type function implementation and it's pretty clear which one is more readable and easier to maintain. The current D implementation will also create a bunch of template bloat with numerous instantiations that aren't actually required.
>>>
>>> StaticMap, and many other templates like it also need a workaround to reduce the number of instances, otherwise they fail. Which isn't as intuitive and not something someone will really know to do.
>> 
>> On the other hand, if you can fix recursive template bloat somehow (tail-call elimination?), you get good performance *and* nice code. It's the best of both worlds.
>
> The recursive version is not nice code. It's hard to understand and difficult to follow. It's main advantage is that because it's essentially a functional language, and all templates are cached, in certain cases, you can see a performance gain because the compiler can avoid actually redoing what it did. In practice, for things like staticMap, this doesn't ever pan out.
>
> I don't see how you solve the tail recursion thing anyway -- each template instance cannot rely on the work that has already been done, because of static if.

Yes.  Didn't want to speak to these points first, thanks for speaking up Steve, but if I'm channeling Stefan correctly template memoization/recursion is pretty close to useless in practice.  Maybe there's some magic breakthrough possible but from what I've been able to pick up, it's not looking good, even theoretically.  Instead we're looking at a never ending series of hacks that almost work, sometimes, and break opaquely down the road.

>
> The static map type function is a loop over an array. Easy to understand, easy to write. It's actually boring code. Static map shouldn't be interesting code at all.

Boring is great.

On Thursday, 24 September 2020 at 03:17:44 UTC, Steven Schveighoffer wrote:
> The recursive version is not nice code. It's hard to understand and difficult to follow. It's main advantage is that because it's essentially a functional language, and all templates are cached, in certain cases, you can see a performance gain because the compiler can avoid actually redoing what it did. In practice, for things like staticMap, this doesn't ever pan out.
>
> I don't see how you solve the tail recursion thing anyway -- each template instance cannot rely on the work that has already been done, because of static if.
>
> The static map type function is a loop over an array. Easy to understand, easy to write. It's actually boring code. Static map shouldn't be interesting code at all.
>
> -Steve

I feel the same way about the naive recursive version:

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

One base case, one recursive case, one line for each. The code practically writes itself. How could it be any clearer or more obvious?

Making it tail-recursive takes away some of the elegance, but doesn't make it any more "interesting":

template staticMap(alias F, Args...) {
    template loop(size_t i, Args...) {
        static if (start == Args.length)
            alias loop = Args;
        else
            alias loop = loop!(i + 1, Args[0 .. i], F!(Args[i]), Args[i+1 .. $]);
    }
    alias staticMap = loop!(0, Args);
}

If you have spent any time at all writing code in a functional language with tail-call elimination, this pattern will be immediately familiar to you. There's nothing about it that's hard to understand, or difficult to follow. It's completely textbook.

Of course, for someone who lacks that background, it might very well look bewildering--in the same way that, say, the Visitor pattern might look bewildering to someone unfamiliar with the idioms of OOP. Does that mean it's a bad pattern? Or does it just mean it's a pattern they haven't learned yet?

On Thursday, 24 September 2020 at 03:51:55 UTC, Paul Backus wrote:
>
> template staticMap!(alias F, Args...) {
>     static if (Args.length == 0)
>         alias staticMap = AliasSeq!();
>     else
>         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, Args[1 .. $]));
> }
>

This code only works because tuples auto expand!
Without that piece of knowledge the template can't be understood.
And even then I find it a stretch to say this immediately looks like a loop over a parameter tuple.

On Thursday, 24 September 2020 at 04:07:40 UTC, Stefan Koch wrote:
> On Thursday, 24 September 2020 at 03:51:55 UTC, Paul Backus wrote:
>>
>> template staticMap!(alias F, Args...) {
>>     static if (Args.length == 0)
>>         alias staticMap = AliasSeq!();
>>     else
>>         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, Args[1 .. $]));
>> }
>>
>
> This code only works because tuples auto expand!
> Without that piece of knowledge the template can't be understood.
> And even then I find it a stretch to say this immediately looks like a loop over a parameter tuple.

I agree that tuple auto-expansion is weird, but what are we supposed to do about it, just never use tuples? It's not like the type function version gets rid of them either--the alias[] only exists inside the function, so you still have to deal with tuples if you want to use the result.

As far as "not looking like a loop" goes--of course it doesn't! It's not a loop. It's a recursive traversal of a list, same as you'd write in any functional language.

On Thursday, 24 September 2020 at 03:51:55 UTC, Paul Backus wrote:
> On Thursday, 24 September 2020 at 03:17:44 UTC, Steven Schveighoffer wrote:
>> [...]
>
> I feel the same way about the naive recursive version:
>
> template staticMap!(alias F, Args...) {
>     static if (Args.length == 0)
>         alias staticMap = AliasSeq!();
>     else
>         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, Args[1 .. $]));
> }
>
> One base case, one recursive case, one line for each. The code practically writes itself. How could it be any clearer or more obvious?
>
> Making it tail-recursive takes away some of the elegance, but doesn't make it any more "interesting":
>
> template staticMap(alias F, Args...) {
>     template loop(size_t i, Args...) {
>         static if (start == Args.length)
>             alias loop = Args;
>         else
>             alias loop = loop!(i + 1, Args[0 .. i], F!(Args[i]), Args[i+1 .. $]);
>     }
>     alias staticMap = loop!(0, Args);
> }
>
> If you have spent any time at all writing code in a functional language with tail-call elimination, this pattern will be immediately familiar to you. There's nothing about it that's hard to understand, or difficult to follow. It's completely textbook.
>
> Of course, for someone who lacks that background, it might very well look bewildering--in the same way that, say, the Visitor pattern might look bewildering to someone unfamiliar with the idioms of OOP. Does that mean it's a bad pattern? Or does it just mean it's a pattern they haven't learned yet?

Recursion is great if you're actually partitioning a space, if you need backtracking, if ... Experienced programmers will reach for it in those situations.  Recursion is somewhat less awe inspiring if you're using it as a loop.

Regardless, unless I'm missing something, the recursive form you put forward doesn't meet Stefan's optimizability criteria.  Recursion aficionados, along with the "use a loop if it fits" crowd, should both see faster code when type functions apply.