Re: Detecting endless recursion?

"Maarten D. de Jong" <>
8 Feb 2004 22:03:29 -0500

          From comp.compilers

Related articles
[23 earlier articles]
Re: Detecting endless recursion? (Lex Spoon) (2004-02-01)
Re: Detecting endless recursion? (Ray Dillinger) (2004-02-04)
Re: Detecting endless recursion? (2004-02-04)
Re: Detecting endless recursion? (Uli Kusterer) (2004-02-04)
Re: Detecting endless recursion? (Joachim Durchholz) (2004-02-08)
Re: Detecting endless recursion? (Alex Colvin) (2004-02-08)
Re: Detecting endless recursion? (Maarten D. de Jong) (2004-02-08)
Re: Detecting endless recursion? (Ken Rose) (2004-02-12)
Re: Detecting endless recursion? (Uli Kusterer) (2004-02-13)
Re: Detecting endless recursion? (Joachim Durchholz) (2004-02-26)
Re: Detecting endless recursion? (Lex Spoon) (2004-02-26)
| List of all articles for this month |

From: "Maarten D. de Jong" <>
Newsgroups: comp.compilers
Date: 8 Feb 2004 22:03:29 -0500
Organization: Delft University of Technology
References: 04-01-104 <bvjd1o$aho$>
Keywords: debug
Posted-Date: 08 Feb 2004 22:03:29 EST

Uli Kusterer <> wrote:
> Quinn Tyler Jackson <> wrote:
>> Allow the programmer to define an event callback function that is called
>> when some function reaches the default limit of recursion on any given
>> function, and if that callback returns > 0 -- go deeper by up to that
>> amount. If it returns 0 -- terminate the program with a "recursion limit
>> exceeded" error.
>> My thinking is that this would allow beginning programmers to be notified
>> that they have entered a deep recursion scenario, at which point they will
>> have to make a conscious decision as to whether or not it is called for.
> Sadly, in my case they wouldn't really be applicable. I'm trying to
> insulate my users from all those details, like stack size. They
> shouldn't need to know about this. I'd just give them an "Not enough
> memory to call another function" error. It's easier to accept that
> they just ran out of memory, than to find out there's some hard-coded
> limit that for some reason is too low. They'll just increase it by
> principle and be surprised when something crashes later...

> However, I have some recovery planned. I intend to make the
> interpreter throw an exception when it runs out of stack space for a
> function call or an expression. That way, the user can catch the
> exception in code and handle it gracefully.

While I'm far from an expert in language and compiler design, I happen
to know that in the programs used to drive the text-oriented Multi
User Dungeon-games (a.k.a. MUDs) the VM makes use of a concept known
as an evaluation cost or 'eval cost' for short. Basically it is a
counter which is increased everytime a VM instruction is executed. If
the counter exceeds a given amount, an error is thrown and execution
is aborted. It is very crude, but very effective: not only does it
guard against too deep recursion, but against (un)intentional code
such as

      for (;;)

as well. The counter is of course reset between execution
threads. Game prac- tice has shown that most threads require less than
about 30.000 evaluations to finish. The standard limit is about one
order of magnitude higher and is invariably hit by bad code.

Most executables do not provide functionality to allow code to extend
the limit, although adding compile- or runtime support for this is
fairly easy. Combinations with the scheduler---if you choose to
implement such a construct---are of course also a possibility.

Kind regards,

Post a followup to this message

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