On Wednesday, 23 September 2020 at 14:05:50 UTC, Steven Schveighoffer wrote:

> It makes me wonder -- can the compiler determine identical lambdas and reduce template instantiations? This was one of the problems with moving from string lambdas to actual lambdas.

In general no. Even for string lambda's that'd be wrong.
We have context dependent tokens ...

On 9/23/20 10:17 AM, Stefan Koch wrote:
> On Wednesday, 23 September 2020 at 14:05:50 UTC, Steven Schveighoffer wrote:
> 
>> It makes me wonder -- can the compiler determine identical lambdas and reduce template instantiations? This was one of the problems with moving from string lambdas to actual lambdas.
> 
> In general no. Even for string lambda's that'd be wrong.
> We have context dependent tokens ...
> 
> 

The lambda I wrote has no context dependent tokens.

String lambdas were instantiated in one place, so there were not problems with context (as long as the string was the same).

-Steve

On 9/23/20 10:15 AM, Meta wrote:
> On Wednesday, 23 September 2020 at 14:05:50 UTC, Steven Schveighoffer wrote:
>> On 9/23/20 9:38 AM, Stefan Koch wrote:
>>> static_map_tf.d(12): vtemplate: 3 (3 unique) instantiation(s) of template `static_map_tf(alias F)(alias_array types...)` found
>>
>> Ah ok. You meant the static map template is going to be different because the lambdas are considered different aliases.
>>
>> That's standard behavior for the current compiler too. I thought you meant that type functions have an extra problem with templates using lambdas.
>>
>> It makes me wonder -- can the compiler determine identical lambdas and reduce template instantiations? This was one of the problems with moving from string lambdas to actual lambdas.
>>
> 
> There was some limited support for lambda comparison added in 2.079:
> https://dlang.org/changelog/2.079.0.html#lambdacomp

OK, so this is possible in some circumstances. A good update to dmd would be to identify such "comparable" lambdas, and merge their template instantiations into one.

-Steve

On Wednesday, 23 September 2020 at 14:32:46 UTC, Steven Schveighoffer wrote:

> OK, so this is possible in some circumstances. A good update to dmd would be to identify such "comparable" lambdas, and merge their template instantiations into one.
>
> -Steve

Only if you can keep the complexity out of the template system/general semantics.
And I doubt that you could.

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.

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.

I see a few reasons to prefer type functions, wherever applicable (they cant do everything):

1) type functions admit a simpler/bounded compiler implementation

2) type functions admit simpler meta programs and the related

3) type functions should be easier to debug, eager rather than lazy/latent compile time errors for one thing

4) type functions exhibit better locality than templates

5) to achieve type function like simplicity/debuggability with templates you need to rely more heavily on "best practices"

On 9/23/2020 4:59 PM, Bruce Carneal wrote:
> On Wednesday, 23 September 2020 at 22:36:55 UTC, Walter Bright wrote:
>> 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.
> 
> I see a few reasons to prefer type functions, wherever applicable (they cant do everything):
> 
> 1) type functions admit a simpler/bounded compiler implementation
> 
> 2) type functions admit simpler meta programs and the related
> 
> 3) type functions should be easier to debug, eager rather than lazy/latent compile time errors for one thing
> 
> 4) type functions exhibit better locality than templates
> 
> 5) to achieve type function like simplicity/debuggability with templates you need to rely more heavily on "best practices"

I don't really understand these points.

Using the existing recursive template calls is well-known and well-understood functional style programming. It even aesthetically looks and acts like function calls, except with a bang (!).

Making existing constructs work better is better than adding an ever-expanding list of new constructs.

On Thursday, 24 September 2020 at 00:44:21 UTC, Walter Bright wrote:
> On 9/23/2020 4:59 PM, Bruce Carneal wrote:
>> On Wednesday, 23 September 2020 at 22:36:55 UTC, Walter Bright wrote:
>>> 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.
>> 
>> I see a few reasons to prefer type functions, wherever applicable (they cant do everything):
>> 
>> 1) type functions admit a simpler/bounded compiler implementation
>> 
>> 2) type functions admit simpler meta programs and the related
>> 
>> 3) type functions should be easier to debug, eager rather than lazy/latent compile time errors for one thing
>> 
>> 4) type functions exhibit better locality than templates
>> 
>> 5) to achieve type function like simplicity/debuggability with templates you need to rely more heavily on "best practices"
>
> I don't really understand these points.
>
> Using the existing recursive template calls is well-known and well-understood functional style programming. It even aesthetically looks and acts like function calls, except with a bang (!).
>
> Making existing constructs work better is better than adding an ever-expanding list of new constructs.

For me, the overriding reason for adding functionality (type functions) is to achieve a net simplification.  A compounding-over-time simplification that reduces the number of compiler bugs experienced and, much more importantly, the number of bugs experienced by meta progammers generally.

A few questions:

1) Is iteration sometimes simpler than recursion?

2) Is left leaning code (early exit) sometimes simpler than single exit (or nested static ifs)?

3) As experienced today, are CTFE functions sometimes easier to debug than templates?  Are the almost always at least as easy?

4) Are any companies with large code bases hitting a wall with non-templates?

5) Are programmers more adept at debugging functions or pattern matchers?

6) Will new programmers correctly adopt templates more quickly than type functions?

7) Is the template subsystem (in the compiler) already one of the least stable, most fragile, bug-fraught subsystems within the compiler?

8) In their fully general form, do templates admit an implementation that is as bounded, as likely to be correct, as convergent, as type functions?

9) Are templates better at defining interfaces than CTFE functions?

10) Is it easier to bound the sphere of dependency with templates or CTFE functions?

Templates can do everything (Turing complete) so why don't we use them for everything?  Because they're not the simplest approach to everything.

On Thursday, 24 September 2020 at 00:44:21 UTC, Walter Bright wrote:
> On 9/23/2020 4:59 PM, Bruce Carneal wrote:
>> On Wednesday, 23 September 2020 at 22:36:55 UTC, Walter Bright wrote:
>>> 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.
>> 
>> I see a few reasons to prefer type functions, wherever applicable (they cant do everything):
>> 
>> 1) type functions admit a simpler/bounded compiler implementation
>> 
>> 2) type functions admit simpler meta programs and the related
>> 
>> 3) type functions should be easier to debug, eager rather than lazy/latent compile time errors for one thing
>> 
>> 4) type functions exhibit better locality than templates
>> 
>> 5) to achieve type function like simplicity/debuggability with templates you need to rely more heavily on "best practices"
>
> I don't really understand these points.
>
> Using the existing recursive template calls is well-known and well-understood functional style programming. It even aesthetically looks and acts like function calls, except with a bang (!).
>
> Making existing constructs work better is better than adding an ever-expanding list of new constructs.

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.

Behold:

template staticMap(alias F, T...)
{
    static if (T.length == 0)
    {
        alias staticMap = AliasSeq!();
    }
    else static if (T.length == 1)
    {
        alias staticMap = AliasSeq!(F!(T[0]));
    }
    /* Cases 2 to 8 improve compile performance by reducing
     * the number of recursive instantiations of staticMap
     */
    else static if (T.length == 2)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]));
    }
    else static if (T.length == 3)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]));
    }
    else static if (T.length == 4)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]), F!(T[3]));
    }
    else static if (T.length == 5)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]), F!(T[3]), F!(T[4]));
    }
    else static if (T.length == 6)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]), F!(T[3]), F!(T[4]), F!(T[5]));
    }
    else static if (T.length == 7)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]), F!(T[3]), F!(T[4]), F!(T[5]), F!(T[6]));
    }
    else static if (T.length == 8)
    {
        alias staticMap = AliasSeq!(F!(T[0]), F!(T[1]), F!(T[2]), F!(T[3]), F!(T[4]), F!(T[5]), F!(T[6]), F!(T[7]));
    }

    else
    {
        /* While:
         *   alias staticMap = AliasSeq!(F!T[0], staticMap!(F, T[1 .. $]));
         * does fewer template instantiations, the compiler implements
         * recursive template instantiations with recursion, and long
         * sequences overflow the compiler's stack.
         * The divide-and-conquer approach uses log_2(n) stack frames.
         */
        alias staticMap =
            AliasSeq!(
                staticMap!(F, T[ 0  .. $/2]),
                staticMap!(F, T[$/2 ..  $ ]));
    }
}

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.