DIP: Tail call optimization

[qznc via Digitalmars-d-announce]

On Sunday, 10 July 2016 at 17:10:32 UTC, Dietrich Daroch wrote:
> On Sunday, 10 July 2016 at 16:52:09 UTC, Ola Fosheim Grøstad 
> wrote:
>> On Sunday, 10 July 2016 at 05:03:46 UTC, Dietrich Daroch wrote:
>>> Hi everyone (=
>>>
>>> I've just added a new proposal to add a new attribute to 
>>> ensure TCO is applied.
>>>
>>> The proposal is really simple, but I'm clueless on how to 
>>> implement it and also interested on getting feedback on it.
>>
>> Why should it be part of the function prototype? @nogc makes 
>> sense, because it is a guarantee for the caller.
>>
>> @tco does not bring any guarantees to the caller, so you might 
>> as well annotate the call-site with some compiler specific 
>> feature.
>
> Annotating every callsite seems uncomfortable, being able to 
> perform TCO is a property of the function and not something 
> that might look call-site dependant.

You are thinking about recursive functions only, but actually a 
"tail call" has nothing to do with recursion. Example:

    int foo() { return 42; }
    int bar() { return foo(); }

There is no recursion, but a tail call in bar and you may want 
the the compiler to optimize it.

If you want to turn recursive functions into loops, then you 
should change to name imho. Maybe @stackbounded.

It could be a function property, if you want recursions of more 
than one function to be bounded wrt stack space. You could then 
require that @tco functions can only call other @tco functions. 
Example:

     @tco int foo(int x) { if (x < 42) return x; else return 
bar(x-1); }
     @tco int bar(int x) { if (x < 41) return x; else return 
foo(x-5); }

Also, you might want to compiler switch to disable to 
optimization for debugging. TCO may be confusing, when you run 
your in a debugger.

Overall, this DIP is not as trivial as it looks. I would like to 
see a more convincing use case/example as a justification.