Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > getrecursiondepth

Reply
Thread Tools

getrecursiondepth

 
 
Manlio Perillo
Guest
Posts: n/a
 
      09-25-2004
Why the sys module does not have a function like getrecursiondepth?
It is very easy to implement:


#include "Python.h"


static PyObject *
getrecursiondepth(PyObject *self, PyObject *args)
{
PyThreadState *tstate;

if (!PyArg_ParseTuple(args, ":recursion_depth"))
return NULL;

tstate = PyThreadState_GET();
return Py_BuildValue("i", tstate->recursion_depth);
}




Thanks and regards Manlio Perillo
 
Reply With Quote
 
 
 
 
Michael Hoffman
Guest
Posts: n/a
 
      09-25-2004
Manlio Perillo wrote:

> Why the sys module does not have a function like getrecursiondepth?


I might be ignorant, but how does this differ from sys.getrecursionlimit()?
--
Michael Hoffman
 
Reply With Quote
 
 
 
 
Manlio Perillo
Guest
Posts: n/a
 
      09-25-2004
On Sat, 25 Sep 2004 14:21:43 +0100, Michael Hoffman
<(E-Mail Removed) > wrote:

>Manlio Perillo wrote:
>
>> Why the sys module does not have a function like getrecursiondepth?

>
>I might be ignorant, but how does this differ from sys.getrecursionlimit()?



>>> def foo(n = 0):

print 'n = %d and recursion depth = %d' % (n,

getrecursiondepth())
if n > 5: return
foo(n + 1)


>>> foo()

n = 0 and recursion depth = 1
n = 1 and recursion depth = 2
n = 2 and recursion depth = 3
n = 3 and recursion depth = 4
n = 4 and recursion depth = 5
n = 5 and recursion depth = 6
n = 6 and recursion depth = 7



N.B.
The real recursion depth starts at 2 in foo, I have redefined the
origin.



Regards Manlio Perillo
 
Reply With Quote
 
Andrew Dalke
Guest
Posts: n/a
 
      09-26-2004
Manlio Perillo wrote:
>>>>foo()

>
> n = 0 and recursion depth = 1
> n = 1 and recursion depth = 2
> n = 2 and recursion depth = 3
> n = 3 and recursion depth = 4


Why is it needed?

Unlike getrecursionlimit it is something that can be
calculated pretty easily.

>>> def getdepth():

.... f = sys._getframe()
.... i = -1
.... while 1:
.... try:
.... f = f.f_back
.... except AttributeError:
.... return i
.... i = i + 1
....
>>> def test(n):

.... if n==0: return getdepth()
.... return test(n-1)
....
>>> test(10)

12
>>> test(30)

32
>>> test(sys.getrecursionlimit()-3)

999
>>>


Anything which depends on the exact number is going
to have problems because that depends on the environment.
For example, in idle getdepth() from its shell
returns 4 instead of the 2 found in the command-line
shell.

Andrew
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Manlio Perillo
Guest
Posts: n/a
 
      09-26-2004
On Sun, 26 Sep 2004 00:09:02 GMT, Andrew Dalke <(E-Mail Removed)>
wrote:

>Manlio Perillo wrote:
>>>>>foo()

>>
>> n = 0 and recursion depth = 1
>> n = 1 and recursion depth = 2
>> n = 2 and recursion depth = 3
>> n = 3 and recursion depth = 4

>
> Why is it needed?
>


1) To write code that execute once in a function (as C static
variables)
2) To guard against too many recursion


> Unlike getrecursionlimit it is something that can be
>calculated pretty easily.
>


I think getrecursiondepth is easy to calculate!

>
>Anything which depends on the exact number is going
>to have problems because that depends on the environment.
>For example, in idle getdepth() from its shell
>returns 4 instead of the 2 found in the command-line
>shell.
>
>


Wait!
I have said that the real getrecursiondepth 'redefines' the origin, so
that outside any function it always returns 0.

Here is the complete source:

--------------------------------------------------
------------ module _pystate.c --------------

#include "Python.h"


static PyObject *
getrecursiondepth(PyObject *self, PyObject *args)
{
PyThreadState *tstate;

if (!PyArg_ParseTuple(args, ":recursion_depth"))
return NULL;

tstate = PyThreadState_GET();
return Py_BuildValue("i", tstate->recursion_depth);
}


/* List of functions defined in the module */

static PyMethodDef pystate_methods[] = {
{"getrecursiondepth", getrecursiondepth, METH_VARARGS,
PyDoc_STR("Returns the current recursion level")},
{NULL, NULL} /* sentinel */
};

PyDoc_STRVAR(module_doc,
"Provides acces to some thread state attributes not present in module
sys");

/* Initialization function for the module */

PyMODINIT_FUNC
init_pystate(void)
{
Py_InitModule3("_pystate", pystate_methods, module_doc);
}


--------------------------------------------------------------
----------------- module pystate.py -------------------

from _pystate import getrecursiondepth as _getrecursiondepth

_recursion_base = _getrecursiondepth()

def getrecursiondepth():
return _getrecursiondepth() - _recursion_base

--------------------------------------------------------------



Regards Manlio Perillo
 
Reply With Quote
 
Andrew Dalke
Guest
Posts: n/a
 
      09-26-2004
Manlio Perillo wrote:
> 1) To write code that execute once in a function (as C static
> variables)
> 2) To guard against too many recursion


Here's a way to get 1). (And I don't know how
checking the stack depth can be used to emulate
C's static variable.)

def spam(x):
if spam.first_time:
spam.first_time = 0
spam.data = read_data_file("blah.dat")
return spam.data.compute(x)

spam.first_time = 1

Or without the post-definition initialization

def spam(x):
if not hasattr(self, "data"):
spam.data = read_data_file("blah.dat")
return spam.data.compute(x)

"2) To guard against too many recursion"? You
could catch the RuntimeError. Though there
are several things that can raise that error.

>>> for x in d.iterkeys():

.... if x == "t": del d["p"]
....
Traceback (most recent call last):
File "<stdin>", line 1, in ?
RuntimeError: dictionary changed size during iteration
>>>


You could check the exception's data to see
if it contains the string 'maximum recursion
depth exceeded' except that exception messages
isn't guaranteed to be the same on different
versions of Python. Looking at the code I should
be able to get "maximum recursion depth
exceeded in cmp" but I can't seem to force
that string.

Regexps can cause a recursion limit problem.
Turns out its error message is "maximum recursion
limit exceeded" so a slightly different message.

Should there be a specific exception type for
when the stack limit is exceeded?

In any case, what you're saying is that you
want to take over control of how to limit
Python's stack use. This means you'll have
your own stack check and your own way to
set the limit. That makes it harder for anyone
to use your code because they have to understand
that as well.

It also means you can't call someone else's
code because you don't know how that might
affect the stack. If you don't call someone
else's code then you can always track your
stack use yourself by passing a stack depth
value into your recursion

def my_function(x, y, z, max_depth = 20):
if max_depth == 0: raise RuntimeError( ....)
...
my_function(x-1,y+3,z/2, max_depth-1)
...

That is a more common way to solve your problem.

>> Unlike getrecursionlimit it is something that can be
>>calculated pretty easily.
>>

>
> I think getrecursiondepth is easy to calculate!


True, and I feel somewhat silly in retrospect for
having said that. For some reason I was thinking
of a non-recusive way to get that information.

> Wait!
> I have said that the real getrecursiondepth 'redefines' the origin, so
> that outside any function it always returns 0.


Ahh, I see your point. But then you don't know
how much stack space you have available. What
if the shell was 900 deep so only 100 was available
to what it executes. Your software will assume
the stack depth is small (because it ignores the
shell's depth), see the normal stack size of 1000,
so wrongly assume it has that much available.

BTW, I can fool your code

def fool_recusion_base(n=950):
if n == 0:
import pystate
return
fool_recursion_base(n-1)

fool_recursion_base()
import pystate
print pystate.getrecursiondepth()


This will probably print a number near -950.

To summarize, I don't see how your solution helps
you with #1 and think there are better ways to
handle #2. Could you post code to show how you
would use your new function?

Andrew
(E-Mail Removed)
 
Reply With Quote
 
Manlio Perillo
Guest
Posts: n/a
 
      09-28-2004
On Sun, 26 Sep 2004 17:45:38 GMT, Andrew Dalke <(E-Mail Removed)>
wrote:

>Manlio Perillo wrote:
>> 1) To write code that execute once in a function (as C static
>> variables)
>> 2) To guard against too many recursion

>
>Here's a way to get 1). (And I don't know how
>checking the stack depth can be used to emulate
>C's static variable.)


def spam(x):
if getrecursiondepth() == 1:
# initialization code

This is equivalent to C++ code:

struct Init
{
Init() { /* initialization code */ }
};

void spam(int x)
{
static Init init;
...
}

> [...]


>
>In any case, what you're saying is that you
>want to take over control of how to limit
>Python's stack use.


Not really...

>It also means you can't call someone else's
>code because you don't know how that might
>affect the stack.


I don't think that calling someone else's code can affect the current
recursion depth.


>If you don't call someone
>else's code then you can always track your
>stack use yourself by passing a stack depth
>value into your recursion
>


This is simply what I want to do!

>def my_function(x, y, z, max_depth = 20):
> if max_depth == 0: raise RuntimeError( ....)
> ...
> my_function(x-1,y+3,z/2, max_depth-1)
> ...
>
>That is a more common way to solve your problem.
>


I have already used this 'pattern'.
But sometimes I don't want to expose the 'limit' on the argument list.
Actually I have resolved this by doing:

def my_function(x, y, z, __max_depth = 20)

But this means I can't use keyword argument in my function!

>>> Unlike getrecursionlimit it is something that can be
>>>calculated pretty easily.
>>>

>>
>> I think getrecursiondepth is easy to calculate!

>
>True, and I feel somewhat silly in retrospect for
>having said that. For some reason I was thinking
>of a non-recusive way to get that information.
>
>> Wait!
>> I have said that the real getrecursiondepth 'redefines' the origin, so
>> that outside any function it always returns 0.

>
>Ahh, I see your point. But then you don't know
>how much stack space you have available.


This is not a problem!.
getrecursiondepth is not intended for such things.

> [...]


>BTW, I can fool your code
>
>def fool_recusion_base(n=950):
> if n == 0:
> import pystate
> return
> fool_recursion_base(n-1)
>
>fool_recursion_base()
>import pystate
>print pystate.getrecursiondepth()
>
>


Ok, but remember the Python paradigm: we are adult programmers...

>This will probably print a number near -950.
>
>To summarize, I don't see how your solution helps
>you with #1 and think there are better ways to
>handle #2. Could you post code to show how you
>would use your new function?
>


Anyway I have asked why getrecursiondepth is not included in sys
module because many members of the PyThreadState struct are accessible
from Python.



Regards Manlio Perillo
 
Reply With Quote
 
Andrew Dalke
Guest
Posts: n/a
 
      09-28-2004
Manlio Perillo wrote:
>>>1) To write code that execute once in a function (as C static
>>>variables)
>>>2) To guard against too many recursion


> def spam(x):
> if getrecursiondepth() == 1:
> # initialization code
>
> This is equivalent to C++ code:
>
> struct Init
> {
> Init() { /* initialization code */ }
> };
>
> void spam(int x)
> {
> static Init init;
> ...
> }


No, it isn't. It requires that spam() be called from
the top-level code. But what if it's called from
the unittest framework? Then the depth will be lower.

Try this as a alternate solution for your style
of use. It's still not the right one because it
doesn't handle reloads nor multiple functions
created through exec's.

_firsttime_db = {}
def firsttime():
frame = sys._getframe(1)
tag = (frame.f_lineno, frame.f_code.co_filename)
if tag in _firsttime_db:
return 0
_firsttime_db[tag] = 1
return 1

>>> def spam():

.... if firsttime():
.... print "Hello!"
.... print "called"
....
>>> spam()

Hello!
called
>>> spam()

called
>>> spam()

called
>>>


You could make it a bit safer with

import weakref
_firsttime_dict = weakref.WeakKeyDictionary()
def firsttime(obj):
if obj in _firsttime_dict:
return 0
_firsttime_dict[obj] = 0
return 1

def spam():
if firsttime(spam):
print "Hello"
print "called"


> I have already used this 'pattern'.
> But sometimes I don't want to expose the 'limit' on the argument list.
> Actually I have resolved this by doing:
>
> def my_function(x, y, z, __max_depth = 20)
>
> But this means I can't use keyword argument in my function!


then do

def _my_function(x, y, z, __maxdepth = 20):
.. do your recursive code here ..

def my_function(x, y, z):
return _my_function(x, y, z)

How would you solve this problem using your stack depth
function? Any solution I come up with is more
complicated than what I just showed here and is no
longer thread safe.

> This is not a problem!.
> getrecursiondepth is not intended for such things.

...
> Ok, but remember the Python paradigm: we are adult programmers...


As an adult I still don't know what you would want
to use this value. The first example you give
(static init) fails if someone looks at it funny.
I'm adult, but I can't be that cautious. The second
example (recursion), well I just don't see how knowing
the depth makes the code any easier to write or clearer
to understand.

> Anyway I have asked why getrecursiondepth is not included in sys
> module because many members of the PyThreadState struct are accessible
> from Python.


Maybe they're useful?

Andrew
(E-Mail Removed)
 
Reply With Quote
 
Manlio Perillo
Guest
Posts: n/a
 
      09-30-2004
On Tue, 28 Sep 2004 16:26:16 GMT, Andrew Dalke <(E-Mail Removed)>
wrote:

>Manlio Perillo wrote:
>>>>1) To write code that execute once in a function (as C static
>>>>variables)
>>>>2) To guard against too many recursion

>
>> def spam(x):
>> if getrecursiondepth() == 1:
>> # initialization code
>>
>> This is equivalent to C++ code:
>>
>> struct Init
>> {
>> Init() { /* initialization code */ }
>> };
>>
>> void spam(int x)
>> {
>> static Init init;
>> ...
>> }

>
>No, it isn't. It requires that spam() be called from
>the top-level code. But what if it's called from
>the unittest framework? Then the depth will be lower.


You are right. Thanks.

>
>Try this as a alternate solution for your style
>of use. It's still not the right one because it
>doesn't handle reloads nor multiple functions
>created through exec's.
>
>_firsttime_db = {}
>def firsttime():
> frame = sys._getframe(1)
> tag = (frame.f_lineno, frame.f_code.co_filename)
> if tag in _firsttime_db:
> return 0
> _firsttime_db[tag] = 1
> return 1
>
> >>> def spam():

>... if firsttime():
>... print "Hello!"
>... print "called"
>...
> >>> spam()

>Hello!
>called
> >>> spam()

>called
> >>> spam()

>called
> >>>

>


No, I don't want this. "Hello!" should be printed every times.

Here is a functions that returns True if the caller's 'recursion
depth' is 1.
Please check if this is correct.


>>> def firstlevel_call():

return sys._getframe(1).f_code != sys._getframe(2).f_code

N.B.: sys._getframe(2) can raise an exception


An example:
>>> def foo(n = 0):

print firstlevel_call()
print 'n =', n
if n == 5: return
foo(n + 1)

>>> foo()

True
n = 0
False
n = 1
False
n = 2
False
n = 3
False
n = 4
False
n = 5



Using firstlevel_call one can 'rescale' the getrecursiondepth
function.
Here is the correct pystate module:

---------------------------
from _pystate import getrecursiondepth as _getrecursiondepth

_recursion_base = 0

def rescale(depth = None):
global _recursion_base

if depth is None:
_recursion_base = _getrecursiondepth()
else:
_recursion_base = depth


def getrecursiondepth():
return _getrecursiondepth() - _recursion_base

---------------------------

And here is an example:

>>> def foo(n = 0):

if firstlevel_call():
pystate.rescale()

print 'n = %s, recursion depth = %s' % (n,
pystate.getrecursiondepth())
if n == 5: return
foo(n + 1)



>>> foo()

n = 0, recursion depth = 0
n = 1, recursion depth = 1
n = 2, recursion depth = 2
n = 3, recursion depth = 3
n = 4, recursion depth = 4
n = 5, recursion depth = 5



>> I have already used this 'pattern'.
>> But sometimes I don't want to expose the 'limit' on the argument list.
>> Actually I have resolved this by doing:
>>
>> def my_function(x, y, z, __max_depth = 20)
>>
>> But this means I can't use keyword argument in my function!

>
>then do
>
>def _my_function(x, y, z, __maxdepth = 20):
> .. do your recursive code here ..
>
>def my_function(x, y, z):
> return _my_function(x, y, z)
>


Sorry, I don't understand.
Here is my_function:


def my_function(a, b, *args, **kwargs):
print 'a, b, args, kwargs:', a, b, args, kwargs




Thanks and regards Manlio Perillo
 
Reply With Quote
 
Andrew Dalke
Guest
Posts: n/a
 
      09-30-2004
Me:
>>Try this as a alternate solution for your style
>>of use. It's still not the right one because it
>>doesn't handle reloads nor multiple functions
>>created through exec's.


Manlio Perillo wrote:
> No, I don't want this. "Hello!" should be printed every times.


I see. I was writing code to emulate C's "static" behaviour
which is not what you wanted.


> Here is a functions that returns True if the caller's 'recursion
> depth' is 1.
> Please check if this is correct.


>>>>def firstlevel_call():

>
> return sys._getframe(1).f_code != sys._getframe(2).f_code


> N.B.: sys._getframe(2) can raise an exception


Looks like it should work, and be thread-safe. Again,
I don't suggest using it. It's going to be slower than
one where you use pass the stack depth in as a parameter.
It's also going to depend on implmentation behaviour.
Someday a Python system may not instantiate the stack
information until it's requested, causing a big run-time
hit. But that's only theoretical.

> Sorry, I don't understand.
> Here is my_function:
>
>
> def my_function(a, b, *args, **kwargs):
> print 'a, b, args, kwargs:', a, b, args, kwargs


That's not recursive, so I don't know how to
interpret your question. Let's suppose you're
doing Ackermann's function

def Ackermann(m, n):
if m == 0:
return n+1
if n == 0:
return Ackermann(m-1, 1)
return Ackermann(m-1, Ackermann(m, n-1))

You might want to add some parameter checking
and add some stack checking. You can do it like this

def _Ackermann(m, n, depth):
if not depth:
raise AssertionError("too deep")
if m == 0:
return n+1
if n == 0:
return _Ackermann(m-1, 1, depth-1)
return _Ackermann(m-1, _Ackermann(m, n-1, depth-1), depth-1)

def Ackermann(m, n):
if (m < 0 or n < 0 or int(m) != m or int(n) != n):
raise TypeError("Bad parameter")
return _Ackermann(m, n, 20)


When I run

print Ackermann(3,2)

I get the following

Traceback (most recent call last):
File "<stdin>", line 28, in ?
File "<stdin>", line 13, in Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 8, in _Ackermann
File "<stdin>", line 7, in _Ackermann
File "<stdin>", line 3, in _Ackermann
AssertionError: too deep

and when I run

print Ackermann(-1, -2)

I get the checking from the entry point, which is

Traceback (most recent call last):
File "<stdin>", line 14, in ?
File "<stdin>", line 12, in Ackermann
TypeError: Bad parameter

Andrew
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments