DIP: Tail call optimization

[Andrew Godfrey via Digitalmars-d-announce]

On Monday, 11 July 2016 at 15:27:54 UTC, Dietrich Daroch wrote:
> On Monday, 11 July 2016 at 14:36:22 UTC, Andrew Godfrey wrote:
>> On Monday, 11 July 2016 at 10:25:36 UTC, Tofu Ninja wrote:
>>> On Sunday, 10 July 2016 at 13:15:38 UTC, Andrew Godfrey wrote:
>>>> Btw here's a thread from 2014 that touches on the idea of a 
>>>> "tailrec" annotation. At the time, Walter viewed the 
>>>> optimization as the compiler's business and not something 
>>>> he'd elevate to a language feature:
>>>>
>>>>
>>>> http://forum.dlang.org/post/lqp6pu$1kkv$1@digitalmars.com
>>>
>>> I find it odd that something like tail recursions that 
>>> actually makes certain things possible that wouldn't be 
>>> otherwise is seen as only an optimization, when things like 
>>> inlining which really is only an optimization is seen as 
>>> important enough to have a pragma.
>>
>> I agree. Maybe Walter has reconsidered since then. He did also 
>> say, though, that he thinks D supports enough different 
>> programming styles already.
>>
>> Would you be satisfied with a pragma? I'd intuited (but could 
>> be wrong) that the focus of your proposal was to get a 
>> compiler error if someone makes a change to a recursive 
>> function, that causes the compiler to be unable to apply the 
>> TCO optimization. If that is your focus, it has heavy 
>> implications and the feature can't just be a pragma.
>
> Pragma does not seem enough, at least current pragmas can be 
> ignored by the compilers 
> (http://dlang.org/spec/pragma.html#predefined-pragmas), but if 
> it's required for tco it can make it.

Ola addressed the "bounded stack" idea. TCO is hard enough, I'll 
stick to that:

When people say "it should be a pragma", I think they 
particularly are saying, "it should be ignorable by the 
compiler". That is a different feature. I think you need to lay 
out *exactly* what you want it to do - because doing so will 
raise the questions that need to be answered.

I'll take a stab, but this may not be the direction you're 
pushing in. This is a straw man to illustrate the difficulties I 
see:

* It must not be ignorable by the compiler.

* It must generate an error if that compiler would be unable to 
do the TCO. Otherwise, the compiler *may* (not "must") apply the 
TCO, unless compiled under (some optimization level, please 
specify), in which case it *must* apply TCO.

One difficulty with this is the words "that compiler". I.e. other 
compilers are free to be unable to make the TCO. This means that 
by using this feature, you have made your code non-portable.

If you additionally want to make it portable, then you need to 
specify the conditions under which *any valid compiler* must be 
able to apply the TCO. Also, you need to make the feature 
generate a compiler error if it is used under other conditions. 
This all seems rather difficult; at any rate, I don't see any 
hints in the current proposal about what these rules would be. 
(Even a rule as simple as "the call must be to the same function" 
could be tricky.)

P.S. You have proposed annotating the function with @tco - it 
seems more like it's the call site that needs to be annotated.