Re: Detecting endless recursion?

Nick Maclaren wrote:


> Joachim Durchholz <joachim.durchholz@web.de> writes:
>> Torben Ęgidius Mogensen wrote:
>>> 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. Since
>> the tool is going to be educational, I assume that the users will
>> be able to halt the execution and inspect the stack state. In this
>> situation, tail call optimization is something that should not be
>> done: the users will complain that the tool has removed information
>> (all those intermediate stack frames that got eliminated due to
>> tail call optimization).
>
> What does educational have to do with it?


If users are supposed to learn, irritating them about technical
details isn't the best way to go ahead. Of course, an educational
interpreter might offer a tail call optimizing mode if the course
talks about it later.


> While tail recursion removal has its advantages, any
> language/compiler/program that RELIES on it is misdesigned at best.
> Inter alia, it has the following problems (all of which I have seen
> in real life):
>
> 1: Unless tail recursion removal is specified in the language, you
> are immediately relying on an implementation-dependent feature and so
> are writing non-portable code.


This makes it only misdesigned if it's not in the specs. Actually,
tail recursion elimination is part of a language though not all
language references explicitly mention it (probably because it's so
obvious in some communities that this item got overlooked). In
general, if a language relies heavily on recursion, you can safely
assume that all implementations do tail call optimization. If the
language doesn't, you can't (often, exception-related issues prevent
tail call optimizations).


> This is the same problem as relying on garbage collection, writ
> small.


Automatic GC is totally unrelated. A language can have misdesigned
manual memory management of well-designed automatic GC.


> 2: Recompile for debugging, or insert your own tracing of function
> returns, and the program fails before it reaches the code you are
> testing. The best 'solution' to this that I was told was to use a
> supercomputer for debugging the codes you are intending to run on a
> low-end PC :-)


Such a compiler would be very badly designed.


If a compiler that does tail-call optimization compiles for debugging,
it should insert a breakpoint instruction before emitting the code the
pops the stack in preparation for an optimized tail call. (To avoid the
slowdown in breakpoint handling, the compiler could insert enough NOPs
to allow the debugger to insert a breakpoint.)
The debugger can then take note whenever the running program enters an
optimized tail call. It can then look in what function the code is, and
keep a note of the fact (and it can also save the to-be-overwritten
parameters and locals if desired).


Entering print statements is easy, too.
I.e. if you have this snippet:


      return foo (some_complicated_expression)


you rewrite this as


      new_arg := some_complicated_expression
      print ("tail call is with " + new_arg.to_string)
      return foo (new_arg)


and everything that was a tail call remains one.
(You'll probably keep the code that way even after removing the print
statement, simply because the code will be easier to read anyway.)


> 3: Don't recompile for debugging, and try to unpick a dump, and you
> are faced with the problem of failing in a utility function called
> from everywhere and not a clue of how you got there. So you add some
> tracing to find that out, and you mutually recurse into problem 2.


The compiler might restrict the optimization to tail *recursive* calls.
In that case, the function that got you where you are is bound to be
somewhere on the stack, though you won't get more than the "loop entry
call".
(Tail recursive calls are equivalent to the jump back up to the start of
a loop.)


> Like many advanced optimisations,


Tail recursion removal is as far from advanced as I can imagine.
Actually I have seen it taught in undergraduate courses.


Regards,
Jo
--
Currently looking for a new job.

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