static map as a type function

[Steven Schveighoffer]

On 9/23/20 11:51 PM, Paul Backus wrote:
> 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.
>>
> 
> 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?

It fails to explicitly say what the resulting size of the AliasSeq will 
be, unlike the type function code (result.length = types.length)

The transformation call to F is buried in the logic to construct the 
result. Compare to:

result[i] = F(t);

One has to mentally work through how the recursion relationship works to 
ensure it terminates properly, I have to read every line to see how the 
thing plays out. Vs. reading each line of the typefunction code and 
deciding "yes, this does what it's supposed to".

Yes, the code writes itself. Reading and understanding it isn't as 
straightforward.

BTW, I don't see how tail-recursion can be done still. Even with your 
tail-recursive version, you still have to rebuild each instance of the 
template, because you don't know if it's going to generate different 
code via static if. Whereas runtime tail recursion builds one version of 
the function, and just jumps back into the same function with modified 
input.

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

Not bewildering, but requires more thought to understand. The array 
version requires little thought, almost every line is independent, and 
does not require the context of the whole construct to verify what it 
does or that it is correct.

It also helps that the "simple naive" version of the typefunction code 
is the best version. You don't have to write it in a special way to make 
the compiler perform well.

One of the reasons D's code generation capabilities are so approachable 
vs. C++ is because it does not need to be written in functional style. 
You can write code that does it exactly how you would do it if you were 
doing it by hand.

-Steve