Tail call optimization in dmd

[Andrei Alexandrescu]

On 10/6/10 14:26 CDT, Denis Koroskin wrote:
> Hi guys!
>
> Does anyone have an experience with tail recursion (in dmd in particular)?
>
> I have (at least) 3 functions that are invoked recursively like this:
>
> A -> B -> C -> A -> B -> ...
>
> Problem is that even though I turned all three of them into tail
> recursive functions, each cycle still consumes about 80 bytes of stack.
>
> After hours of debugging I've noticed that dmd does terrible work on
> TCO. For example, the following produces stack overflow:
>
> void foo()
> {
> {
> }
>
> bar();
> }
>
> void bar()
> {
> {
> }
>
> foo();
> }
>
> void main()
> {
> foo();
> }
>
> I compile code with -O -release -inline if that matters.
>
> Any tips would be highly appreciated.

dmd currently optimizes tail recursion but not tail calls. Tail 
recursion == function calls itself as the last expression. Tail call == 
function issues a call to another function as the last expression. 
Without tail call optimization, mutual recursion will consume stack as 
you noted.

Andrei