Re: Detecting endless recursion?

  torbenm@diku.dk (Torben Ęgidius Mogensen) wrote:


> > int foo( int n )
> > {
> > return foo( n+1 );
> > }
>
> This simple case can easily be detected by the compiler: There is no
> branch of this function that does not have a recursive call, so
> nontermination is trivial.


  Are there any good texts on how to best do such code analysis when
compiling? I could probably build a parallel data structure while
compiling that keeps track of all branches and recursive calls, or I
could try to wiggle my way through the actual bytecode my parser
eventually generates, but is there a smarter, more elegant or faster way?


  I'd still need something that usefully catches stack size (right now
only low limits seem to work, and all others send the computer
thrashing, so I guess I'll have to find out the exact reasons that make
it thrash, and how to detect them in a smart way).


> It sounds like you are not implementing tail calls properly. This
> program should run in constant space (assuming fixed-size integers).
> Proper tail calls exploit the observation that if a call is the last
> that happens in a function, then the called function (the callee) can
> reuse the same stack frame as the caller:


  Actually, I'm not implementing any tail call optimizations right now.
I'll probably want to do some optimizations of that sort later on, but
it's a very specific optimization for a very rare case.


  I guess I picked too simple an example. I just meant an endless
recursion of some kind.


  But this optimization definitely sounds interesting, I'll look into it
some more.


> As other people have pointed out, recursion can go quite deep without
> being an error, so any limit be fairly high, e.g., 100000. Ideally,
> the limit should be easily user-modifiable, either by a command-line
> option or (better still) by specifying it in the source program
> (e.g. in a comment).


  Yeah, a fixed limit won't do. But I'd really like to avoid that my
users have to know about this and increase the limit for special cases...


Thanks for the input,
-- Uli
http://www.zathras.de <-- back up again!

Return to the comp.compilers page.
Search the comp.compilers archives again.