<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 18 July 2018 at 10:03, John McCall <span dir="ltr"><<a href="mailto:rjmccall@apple.com" target="_blank">rjmccall@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">We all know what tail-recursion is.  Template instantiation is not naturally tail-recursive from the perspective of the compiler implementation because, while you might think of your template as a function which computes the constant initializer of the `value` member, class template instantiation is in fact a complex process which produces (and memoizes) an entire instantiated class, and (w.r.t your example) the recursive instantiation of the base clause is merely one step in that process.  In other words, the product of instantiation is a class, not a value, and the production of the value is not in tail position in the instantiation function.<div><br></div><div>The compiler must provide a template-instantiation engine which produces actual classes in order to satisfy the main purpose of class template instantiation, which is to produce types that are normally usable in the language.  To naturally tail-recurse as you would like would require the compiler to include a recognizer of such templates and their uses which instead triggers a second, separate instantiation engine for the sole purpose of evaluating constant initializers in metaprograms; this would be a source of great redundancy, complexity, and bugs, and I suspect it would provide marginal value to most C++ compilations, even metaprogramming-heavy ones.</div><div><br></div><div>Alternatively, within the compiler implementation we avoid using direct recursion when recursively instantiating class templates and instead apply generic recursion-to-iteration techniques, such as iterating on a worklist and resuming previous instantiations from a stored continuation point when they become unblocked.  However, that would require an extremely invasive restructuring of the compiler implementation, because it turns out that a rather shockingly long list of things in C++ can trigger class template instantiation, from name lookup to essentially every aspect of type-checking, and they would all need to be restructured to be paused and resumed.  So instead we use direct recursion like pretty much every other C++ implementation, meaning we cannot recursively instantiate templates to an infinite depth without blowing out the stack.</div></div></blockquote><div><br></div><div>Thanks for such an in-depth and informative answer to my question.</div><div><br></div><div>Have a nice day,</div><div><br></div><div>degski<br></div></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><i><b>"If something cannot go on forever, it will stop" - Herbert Stein</b></i><br></div></div>
</div></div>