static map as a type function

[Jackel]

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 ..  $ ]));
     }
}