Re: Detecting endless recursion?

Uli Kusterer <witness@t-online.de>
1 Feb 2004 12:33:40 -0500

          From comp.compilers

Related articles
[11 earlier articles]
Re: Detecting endless recursion? joachim.durchholz@web.de (Joachim Durchholz) (2004-01-18)
Re: Detecting endless recursion? nmm1@cus.cam.ac.uk (2004-01-22)
Re: Detecting endless recursion? lex@cc.gatech.edu (Lex Spoon) (2004-01-22)
Re: Detecting endless recursion? torbenm@diku.dk (2004-01-31)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-31)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-02-01)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-02-01)
Re: Detecting endless recursion? joachim.durchholz@web.de (Joachim Durchholz) (2004-02-01)
Re: Detecting endless recursion? joachim.durchholz@web.de (Joachim Durchholz) (2004-02-01)
Re: Detecting endless recursion? nmm1@cus.cam.ac.uk (2004-02-01)
Re: Detecting endless recursion? derkgwen@HotPOP.com (Derk Gwen) (2004-02-01)
Re: Detecting endless recursion? lex@cc.gatech.edu (Lex Spoon) (2004-02-01)
Re: Detecting endless recursion? bear@sonic.net (Ray Dillinger) (2004-02-04)
[9 later articles]
| List of all articles for this month |

From: Uli Kusterer <witness@t-online.de>
Newsgroups: comp.compilers
Date: 1 Feb 2004 12:33:40 -0500
Organization: T-Online
References: 04-01-050 04-01-086
Keywords: courses, debug
Posted-Date: 01 Feb 2004 12:33:40 EST

  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!


Post a followup to this message

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