Three subtle cases of tail recursion (Re: DMD 1.001 release)

[Kazuhiro Inaba]

> http://www.digitalmars.com/d/changelog.html
> tail recursion works again 

Fine!! But it seems buggy in some corner cases.

1. Nested function

    // quirky way to call dg() n times
    void repeat( int n, void delegate() dg ) {
      if( n&1 ) dg();
      if( n/2 ) repeat( n/2, {dg();dg();} );
    }
    void main() {
      repeat( 10, {printf("Hello\n");} );
    }

  If compiled with -O flag, this program goes into an infinite loop.
  Tail recursive call of repeat function reuses the stack frame, which is
  still referenced by the anonymous delegate, too early.

2. Scope statemenmt

    int scp( int n ){
      if( n==0 ) return 0;
      scope(exit) printf("%d",n);
      return scp(n-1);
    }
    void main() {
      scp(5);
    }

  Without -O flag, it emits 12345 (correct).
  With -O flag enabled, it emits 43210 (at least in my environment.)

3. Conditional expression

    // return in an if statement is optimized as a tail recursion
    long f_if( long n, long acc=0 ) {
      if(n) return f_if( n-1, n+acc ); else return acc;
    }
    // same function written with a conditional statement is not
    long f_cd( long n, long acc=0 ) {
      return n ? f_cd( n-1, n+acc ) : acc;
    }
    void main() {
      printf("%lld\n", f_if(1000000)); // 500000500000
      printf("%lld\n", f_cd(1000000)); // Error: Stack Overflow
    }

  This is not a bug, but it would be preferable if dmd detects and
  optimizes the "return cond ? recursive_call : ..." form.


-- 
Kazuhiro Inaba