Re: Detecting endless recursion?

torbenm@diku.dk (Torben Ęgidius Mogensen)
16 Jan 2004 22:35:21 -0500

          From comp.compilers

Related articles
Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-12)
Re: Detecting endless recursion? jmcenerney@austin.rr.com (John McEnerney) (2004-01-12)
Re: Detecting endless recursion? fjh@cs.mu.oz.au (Fergus Henderson) (2004-01-12)
Re: Detecting endless recursion? nmm1@cus.cam.ac.uk (2004-01-16)
Re: Detecting endless recursion? jgd@cix.co.uk (2004-01-16)
Re: Detecting endless recursion? derkgwen@HotPOP.com (Derk Gwen) (2004-01-16)
Re: Detecting endless recursion? torbenm@diku.dk (2004-01-16)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-16)
Re: Detecting endless recursion? witness@t-online.de (Uli Kusterer) (2004-01-16)
Re: Detecting endless recursion? Martin.Ward@durham.ac.uk (Martin Ward) (2004-01-16)
Re: Detecting endless recursion? vbdis@aol.com (2004-01-16)
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)
[20 later articles]
| List of all articles for this month |

From: torbenm@diku.dk (Torben Ęgidius Mogensen)
Newsgroups: comp.compilers
Date: 16 Jan 2004 22:35:21 -0500
Organization: Department of Computer Science, University of Copenhagen
References: 04-01-050
Keywords: debug
Posted-Date: 16 Jan 2004 22:35:21 EST

Uli Kusterer <witness@t-online.de> writes:


> I've implemented my own programming language compiler and byte-code
> interpreter. Since this language is intended for beginners, I'd like
> it to be robust. When a user creates a function that calls itself
> unconditionally, like:
>
> 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.


> my app just bombs because it runs out of memory (because my fake
> stack keeps growing and growing). And the OS doesn't let me know it's
> out of memory because it's happily paging out VM.


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:


  1) The return address is not changed, so the callee will return
        directly to the function who called the caller (avoiding a chain
        of returns).


  2) As no variable is live after the tail call, the parameters and
        other variables in the frame of the caller can be overwritten with
        parameters and variables of the callee.


You may have to be careful about the order in which things are done
and you may need temporary stack-space during the call-sequence. It
depends on the details of the VM.


> The best suggestion I've been able to get from some mailing lists was
> to just put a limit on the size of my pseudo-stack and when that is
> exceeded raise an error. This is very straightforward and would be
> easy to implement (and I feel stupid for not thinking of this), but I
> have no idea how to determine this limit.


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).


Torben


Post a followup to this message

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