How templates work (1)

[tsbockman]

On Friday, 29 May 2020 at 11:13:17 UTC, Stefan Koch wrote:
> However:
> We have not covered how names are resolved in scopes;
> Nor the intricacies of how to pick the right overload for a 
> template.
> And which implicit conversion happen for that;
> Neither have we talked about deferred resolution of templates or
> which steps semantic analysis has to take.

Don't forget to discuss template memoization. As I'm sure you're 
well aware, it has massive performance consequences, both good 
and bad, as well as being semantically essential to some uses of 
templates.

Greenspun's tenth rule of programming states: "Any sufficiently 
complicated C or Fortran program contains an ad hoc, 
informally-specified, bug-ridden, slow implementation of half of 
Common Lisp." D very nearly fulfills this law (a tongue-in-cheek 
version of the "inner-platform effect") through its template 
system, except that it's probably not fair to call it 
"informally-specified".

I argue that the root causes of the terrible compile-time 
performance, and especially memory consumption, of D's template 
system are forced memoization of intermediate results, and the 
lack of the tail recursion optimization. Who ever heard of a pure 
functional language without tail recursion optimization, or *any* 
programming language with inescapable memoization?

There is no good reason to assign a long, permanent symbol to 
each and every partially sorted scrap of an AliasSeq that is 
generated in the midst of a compile-time sort, instead of just 
garbage collecting them. But my understanding is currently those 
intermediate results just stick around forever, massively raising 
the asymptotic memory complexity of otherwise benign algorithms.