Re: Detecting endless recursion?

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

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