[plt-scheme] [BUG?] Breaking out of a tight infinite recursion

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Thu Dec 18 15:09:06 EST 2003

At Wed, 10 Dec 2003 10:53:18 -0500, Jim Witte wrote:
> (define infinite
>    (letrec ((loop (lambda (x)
>                    ((< x 1000000) (loop (+ x 1))))))
>      (loop 1)))
> it will go into an infinite loop, at least for a (long) while.  But 
> this execution appears to not only block the thread of the running 
> program, but also the thread of the DrScheme GUI environment itself, 
> preventing one from breaking out of the program.

Unless your machine is thrashing horribly, DrScheme actually breaks the
program right away when you click the "Break" button.

But when the broken thread raises the break exception, DrScheme tries
to process debugging information in the exception, and this information
is proportional to the size of thread's continuation. Things go bad
when DrScheme processes this information with non-tail recursion;
processing the information makes a new continuation that's proportional
to the size of the stopped thread's continuation, except the constant
factor is even larger because DrScheme is doing more work per
continuation frame....

The non-tail loop was in `filter' from `(lib "list.ss")'. In CVS, I
changed it to a loop (using `reverse!', of course). The time to process
a break is still proportional to the size of the program's continuation
(perhaps we can improve that eventually), but the constant factor is an
order of magnitude smaller.

We had considered changing `filter' before, and I'm not sure why we
left it alone. In any case, this problem was a good example of why it
really needed to be changed.


Posted on the users mailing list.