TIP #87: Allow Tcl Access to the Recursion Limit
Stephen Trier
TIP #87: ALLOW TCL ACCESS TO THE RECURSION LIMIT
==================================================
Version: $Revision: 1.1 $
Author: Stephen Trier <sct_at_po.cwru.edu>
State: Draft
Type: Project
Tcl-Version: 8.4
Vote: Pending
Created: Tuesday, 19 February 2002
URL: http://purl.org/tcl/tip/87.html
WebEdit: http://purl.org/tcl/tip/edit/87
Discussions-To: news:comp.lang.tcl
Post-History:
-------------------------------------------------------------------------
ABSTRACT
==========
An extension to the [interp] command, [interp recursionlimit], will
permit Tcl scripts to control their own recursion limits. Until now,
this limit has been changeable from a C API, but not from within Tcl.
RATIONALE
===========
As of Tcl 8.4a3, Tcl scripts must live with the default recursion depth
of 1000 nested calls to the _Tcl_Eval_ family of functions or resort to
C code to change the limit. Nevertheless, Tcl programmers may find it
useful to reduce the limit when debugging or to increase it for scripts
that include deeply recursive functions. The changes proposed in this
TIP will make this possible in pure Tcl code.
SPECIFICATION
===============
generic/tclInterp.c:
Add subcommands to [interp] and to the slave interpreter object
command with the following syntax:
interp recursionlimit _interp_ _?newlimit?_
_slave_ recursionlimit _?newlimit?_
The parameter _newlimit_ must be a positive integer. When it is
present, the limit is changed to _newlimit_ and the command
returns the new recursion limit. If the _newlimit_ parameter is
absent, the command returns the current recursion limit.
No maximum value is enforced. It is the programmer's
responsibility to ensure the recursion limit will not overflow
the process stack.
A safe interpreter is not allowed to change the recursion limit
for itself nor for any other interpreter. Attempting to do so
will generate an error. Safe interpreters are allowed to query
recursion limits.
doc/interp.n:
Add documentation for the new subcommands, including a warning
about stack overflow, much like the warning in the documentation
for ;;Tcl_SetRecursionLimit()_.
test/interp.test:
Add tests for the new subcommands.
COMMENTS RECEIVED
===================
Using a command or variable _::tcl::recursionLimit_ to manipulate the
limit was initially considered, but Miguel Sofer suggested making the
function a subcommand of [interp] because the recursion limit is
logically an attribute of each interpreter. Miguel also observed that
implementing _TclpCheckStackSpace()_ for Unix (a future TIP?) would
mitigate the dangers of setting the recursion limit too high.
<URL:http://groups.google.com/groups?hl=en&threadm=3C6D0A88.5DC9D8B4%40utdt.edu>
REFERENCE IMPLEMENTATION
==========================
An implementation is in progress.
COPYRIGHT
===========
This document is in the public domain.
-------------------------------------------------------------------------
TIP AutoGenerator - written by Donal K. Fellows
[[Send Tcl/Tk announcements to tcl-an...@mitchell.org
Send administrivia to tcl-announ...@mitchell.org
Announcements archived at http://groups.yahoo.com/group/tcl_announce/
The primary Tcl/Tk archive is ftp://ftp.neosoft.com/pub/tcl/ ]]
Hemang Lavana
> interp recursionlimit _interp_ _?newlimit?_
>
> _slave_ recursionlimit _?newlimit?_
>
> The parameter _newlimit_ must be a positive integer. When it is
> present, the limit is changed to _newlimit_ and the command
> returns the new recursion limit. If the _newlimit_ parameter is
> absent, the command returns the current recursion limit.
>
> No maximum value is enforced. It is the programmer's
> responsibility to ensure the recursion limit will not overflow
> the process stack.
Since it is possible to have any large value for newlimit, how about
letting the user specify its value as "-1". A value of "-1" would remove
the recursion limit altogether.
I don't know whether the ability to remove such a recursion limit would
be useful or not.
Hemang.
Jeffrey Hobbs
> I don't know whether the ability to remove such a recursion limit would
> be useful or not.
With the current lack of implementation for TclpCheckStackSpace on Unix,
you are really just providing a certain way to crash the system that way
(by creating any infinite recursion case). The real solution of course
is to remove the whole mechanism (unless you want it to limit CPU usage
for safe interps), and figure out how to implement TclpCheckStackSpace
on various platforms (efficiently).
--
Jeff Hobbs The Tcl Guy
Senior Developer http://www.ActiveState.com/
Darren New
> With the current lack of implementation for TclpCheckStackSpace on Unix,
> you are really just providing a certain way to crash the system that way
> (by creating any infinite recursion case).
Aren't you missing the distinction between unbounded recursion and
infinite recursion? Infinite recursion is going to crash regardless of
checking stack space.
--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
To the user, everything works just as expected,
assuming the user's expectations are correct.
Jeffrey Hobbs
>
> Jeffrey Hobbs wrote:
> > With the current lack of implementation for TclpCheckStackSpace on Unix,
> > you are really just providing a certain way to crash the system that way
> > (by creating any infinite recursion case).
>
> Aren't you missing the distinction between unbounded recursion and
> infinite recursion? Infinite recursion is going to crash regardless of
> checking stack space.
Errr... think Tcl here. There is no infinite recursion - you will
hit the recursion limit internally and the proc will throw an error.
However, if you really removed the limit, you would eventually seg
fault - that's what I mean when I say crash. You "crash" both ways,
but one is recoverable (and even says "possible infinite loop?"),
whereas the other is ... bad.
--
Jeff Hobbs The Tcl Guy
Senior Developer http://www.ActiveState.com/
Tcl Support and Productivity Solutions
Jeffrey Hobbs
>
> Jeffrey Hobbs wrote:
> > With the current lack of implementation for TclpCheckStackSpace on Unix,
> > you are really just providing a certain way to crash the system that way
> > (by creating any infinite recursion case).
>
> Aren't you missing the distinction between unbounded recursion and
> infinite recursion? Infinite recursion is going to crash regardless of
> checking stack space.
Errr... think Tcl here. There is no infinite recursion - you will
hit the recursion limit internally and the proc will throw an error.
However, if you really removed the limit, you would eventually seg
fault - that's what I mean when I say crash. You "crash" both ways,
but one is recoverable (and even says "possible infinite loop?"),
whereas the other is ... bad.
--
Jeff Hobbs The Tcl Guy
Senior Developer http://www.ActiveState.com/
Darren New
> Errr... think Tcl here. There is no infinite recursion - you will
> hit the recursion limit internally and the proc will throw an error.
Oh, alright. Fair enough.
> However, if you really removed the limit, you would eventually seg
> fault - that's what I mean when I say crash. You "crash" both ways,
> but one is recoverable (and even says "possible infinite loop?"),
> whereas the other is ... bad.
If you made the recursion limit large enough, wouldn't this happen
anyway?
Jeffrey Hobbs
> > However, if you really removed the limit, you would eventually seg
> > fault - that's what I mean when I say crash. You "crash" both ways,
> > but one is recoverable (and even says "possible infinite loop?"),
> > whereas the other is ... bad.
>
> If you made the recursion limit large enough, wouldn't this happen
> anyway?
Yes, and that is why we need the TclpCheckStackSpace call implemented
whereever possible. This hasn't been a known problem with the default
limit of 1000 (recursion depth) in the regular build. However, when
built with threads, threads on many platforms have a more restricted
stack size, and you can blow the stack (seg fault) in a thread before
you hit the default recursion depth.
Arjen Markus
>
> Darren New wrote:
> > > However, if you really removed the limit, you would eventually seg
> > > fault - that's what I mean when I say crash. You "crash" both ways,
> > > but one is recoverable (and even says "possible infinite loop?"),
> > > whereas the other is ... bad.
> >
> > If you made the recursion limit large enough, wouldn't this happen
> > anyway?
>
> Yes, and that is why we need the TclpCheckStackSpace call implemented
> whereever possible. This hasn't been a known problem with the default
> limit of 1000 (recursion depth) in the regular build. However, when
> built with threads, threads on many platforms have a more restricted
> stack size, and you can blow the stack (seg fault) in a thread before
> you hit the default recursion depth.
>
How about providing information to avoid such stacking in the first
place?
Some (most? many? quite a few?) algorithms can be structured in such
a way that you can avoid recursion as Tcl knows it and do tail recursion
as Tcl knows it (at least two solutions):
(The trampoline is my favourite)
Regards,
Arjen
Donal K. Fellows
> How about providing information to avoid such stacking in the first
> place?
Tricky.
> Some (most? many? quite a few?) algorithms can be structured in such
> a way that you can avoid recursion as Tcl knows it and do tail recursion
> as Tcl knows it (at least two solutions):
While many algorithms can have tail-recursion elimination applied to them, not
all can be handled like this. Typically, you'd expect the optimisation to be
applicable exactly when a function directly returns the result of another
function call (especially in the case where it is a recursive or co-recursive[1]
call.) The problem comes with when you start wanting to do some operations to
the result before passing it back; optimising these sorts of things can be much
harder. As an example of what I mean, the natural definition of the factorial
function[2] (in Tcl) is:
proc fact {n} {
expr {$n<2 ? $n : $n*[fact [expr {$n-1}]]}
}
This is not tail-recursive since you need to keep the value of $n about until
after the recursion ends. Of course, this is fixable using an
accumulator-argument scheme, but in general that's difficult to do:
proc fact {n {accum 1}} {
expr {$n<2 ? $accum : [fact [expr {$n-1}] [expr {$accum*$n}]]}
}
Indeed, for some algorithms (depth-first tree traversal, for example) you need a
stack *somewhere* and it may well be easiest to maintain the stack through
recursive calls (it usually depends what else is going on at the same time.)
Trampolining (I *like* that code[3]) becomes unwieldy as the amount of
information stored on the stack increases (I've got co-recursive tree-traversal
code that uses [upvar] to access large arrays in parent contexts as part of an
elaborate code generator, which would be very hard to make tail-recursive.)
However, if you can bound your recursion depth neatly (pretty easy in practise
with non-worst-case trees because of the sheer quantity of data even fairly
shallow trees can hold) then a recursive algorithm may well be the best way to
solve a problem.
Donal.
[1: A calls B, and B calls A. ]
[2: Fibonacci and GCD functions lend themselves to this treatment as well. ]
[3: If we had first-class stack-frame objects, this would be even cooler! ]
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ fell...@cs.man.ac.uk
-- The guy who sells me my audio hardware explained that a computer will never
produce the same level of sound quality that a stereo will b/c stereo have
transistors and sound cards don't. --Matthew Garson <mga...@world.std.com>
Stephen Trier
I don't know of an argument other than completeness in favor of making
the limit optional. Without a practical reason to make the change, I'd
rather not do it.
Besides, the workaround of setting the limit to some value near 2^31-1
is still available. Functionally, that does the same thing as removing
the recursion limit.
Stephen
--
Stephen Trier
Technical Development Lab
Cleveland FES Center
s...@po.cwru.edu
Ken Fitch
interp recursionlimit _interp_ _?newlimit?_
to no less than the current recursion depth? If for example someone
changed the limit to 250 from code running at depth 500, it seems to
me like something bad
might happen.
Don Porter
"Something bad" would be "raise an error". And how would we
constrain user choice? By raising an error. So doesn't really
matter much. If we raise the error, we might give a better error
message though.
--
| Don Porter Mathematical and Computational Sciences Division |
| donald...@nist.gov Information Technology Laboratory |
| http://math.nist.gov/~DPorter/ NIST |
|______________________________________________________________________|
miguel sofer
>
> Ken Fitch wrote:
> > Have you considered constraining the user's choice of _newlimit_ in
> >
> > interp recursionlimit _interp_ _?newlimit?_
> >
> > to no less than the current recursion depth? If for example someone
> > changed the limit to 250 from code running at depth 500, it seems to
> > me like something bad
> > might happen.
>
> "Something bad" would be "raise an error". And how would we
> constrain user choice? By raising an error. So doesn't really
> matter much. If we raise the error, we might give a better error
> message though.
What do you have in mind? I guess that we differentiate in the error
message between
* "you just hit the interp's recursion limit"
* "TclpCheckStackSpace got nervous about your stack consumption"
Miguel
Don Porter
>> > Have you considered constraining the user's choice of _newlimit_ in
>> >
>> > interp recursionlimit _interp_ _?newlimit?_
>> >
>> > to no less than the current recursion depth?
Don Porter wrote:
>> If we raise the error, we might give a better error message though.
miguel sofer wrote:
> What do you have in mind? I guess that we differentiate in the error
> message between
> * "you just hit the interp's recursion limit"
> * "TclpCheckStackSpace got nervous about your stack consumption"
No, I'm talking about the situation posed by Ken Fitch. Your interp
is running at depth 300, and it evaluates a command to set the limit
to 250. An error stack like:
can't set recursion limit less than current level
while executing
interp recursionlimit 250
...
is better than
too many nested calls to Tcl_Eval (infinite loop?)
while executing
command that follows interp recursionlimit
...
Donal K. Fellows
> No, I'm talking about the situation posed by Ken Fitch. Your interp
> is running at depth 300, and it evaluates a command to set the limit
> to 250. An error stack like:
>
> can't set recursion limit less than current level
> while executing
> interp recursionlimit 250
I'm not sure if that should be an error, or at least not one worded like that;
the setting of the recursion limit to less than the current level is reasonable
of itself, so the error message should indicate that the setting happened but
nothing other than error recovery is possible from here on. Perhaps like this:
falling back due to new recursion limit
while executing
interp recursionlimit 250
...
Donal.
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ fell...@cs.man.ac.uk
-- If that's dead, sign me up for necrophilia classes.
-- Mark Loy <ml...@iupui.edu>
lvi...@yahoo.com
According to Donal K. Fellows <fell...@cs.man.ac.uk>:
Hopefully when such a request to set new recursion limit occurs one has not
already exceeded the new value...
--
"I know of vanishingly few people ... who choose to use ksh." "I'm a minority!"
<URL: mailto:lvi...@cas.org> <URL: http://www.purl.org/NET/lvirden/>
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.
Stephen Trier
Donal K. Fellows <fell...@cs.man.ac.uk> wrote:
>[T]he setting of the recursion limit to less than the current level is
>reasonable of itself, so the error message should indicate that the
>setting happened but nothing other than error recovery is possible
>from here on.
I like this idea, but it will interact strangely with [catch] if the
[catch] is also deeper than the new recursion limit. Suppose, for
instance:
# At a recursion depth of 300...
if {[catch {interp recursionlimit {} 250]} {
puts $errorInfo
}
If I'm not mistaken, the helpful error message from [interp recursionlimit]
will get eaten by the [catch], and the good old "too many nested calls to
Tcl_Eval (infinite loop?)" error will be generated when the if statement
tries to evaluate the "puts" clause.
This would not be a problem if [interp recursionlimit] did not change the
limit when generating an error.
Donal K. Fellows
> I like this idea, but it will interact strangely with [catch] if the
> [catch] is also deeper than the new recursion limit. Suppose, for
> instance:
>
> # At a recursion depth of 300...
> if {[catch {interp recursionlimit {} 250]} {
> puts $errorInfo
> }
>
> If I'm not mistaken, the helpful error message from [interp recursionlimit]
> will get eaten by the [catch], and the good old "too many nested calls to
> Tcl_Eval (infinite loop?)" error will be generated when the if statement
> tries to evaluate the "puts" clause.
The obvious workaround is to make [catch] not catch unless it has at least one
stack level left over to work with. (In fact, it might at some point in the
future be a good idea to consider another class of untrappable exceptions; those
that occur when an interpreter has performed too many operations. This would
provide for a way of stopping other kinds of overuse of resources by safe
interpreters, which could otherwise lead to denial-of-service attacks. But this
is way outside the scope of what is being discussed here.)
Donal.
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ fell...@cs.man.ac.uk
-- Thanks, but I only sleep with sentient lifeforms. Anything else is merely
a less sanitary form of masturbation.
-- Alistair J. R. Young <avatar...@arkane.demon.co.uk>