getrecursiondepth

[Manlio Perillo]

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

 

[Michael Hoffman]

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

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

 

[Manlio Perillo]

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

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

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

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

 

[Andrew Dalke]

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.
.... f = sys._getframe()
.... i = -1
.... while 1:
.... try:
.... f = f.f_back
.... except AttributeError:
.... return i
.... i = i + 1
........ if n==0: return getdepth()
.... return test(n-1)
....
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
(e-mail address removed)

 

[Manlio Perillo]

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

 

[Andrew Dalke]

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.
.... if x == "t": del d["p"]
....
Traceback (most recent call last):

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.

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 address removed)

 

[Manlio Perillo]

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!

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.


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

 

[Andrew Dalke]

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
.... if firsttime():
.... print "Hello!"
.... print "called"
....

Hello!
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 address removed)

 

[Manlio Perillo]

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
... if firsttime():
... print "Hello!"
... print "called"
...

Hello!
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.

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

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


An example: print firstlevel_call()
print 'n =', n
if n == 5: return
foo(n + 1)
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:
if firstlevel_call():
pystate.rescale()

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


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

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

 

[Andrew Dalke]

Me:

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.

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 address removed)

 

[Manlio Perillo]

[...]

And here is an example:
if firstlevel_call():
pystate.rescale()

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


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

Actually this can be done without using getrecursiondepth:
if pystate.firstlevel_call():
foo2.recursiondepth = 0
else:
foo2.recursiondepth += 1

#print 'n = %s, recursion depth = %s' % (n,
foo2.recursiondepth)
if n == 5: return
foo2(n + 1)


I have timed the two versions
(Python 2.3.3 (#51, Dec 18 2003, 20:22:39) [MSC v.1200 32 bit (Intel)]
on win32)

timeit.py -s "from time_pystate import foo" "foo()"
10000 loops, best of 3: 21.5 usec per loop

timeit.py -s "from time_pystate import foo2" "foo2()"
10000 loops, best of 3: 26.8 usec per loop



Regards Manlio Perillo

 

[Andrew Dalke]

Actually this can be done without using getrecursiondepth:



if pystate.firstlevel_call():
foo2.recursiondepth = 0
else:
foo2.recursiondepth += 1

That's not thread-safe. Suppose two different threads
called foo2() at the same time. The second one ends
up resetting the recursiondepth so the first one will
get messed up.

Andrew
(e-mail address removed)

 

[Andrew Dalke]

if pystate.firstlevel_call():
foo2.recursiondepth = 0
else:
foo2.recursiondepth += 1

#print 'n = %s, recursion depth = %s' % (n,
foo2.recursiondepth)
if n == 5: return
foo2(n + 1)

In addition, if you aren't supporting threads
then the following will also work.

def foo3(n=0):
foo3.recursiondepth += 1
try:
if n == 5: return
foo3(n+1)
finally:
foo3.recursiondepth -= 1

foo3.recursiondepth = 0

% timeit.py -s "import spam" "spam.foo2()"
10000 loops, best of 3: 70.8 usec per loop
% timit.py -s "import spam" "spam.foo3()"
10000 loops, best of 3: 47.6 usec per loop

Still, the fastest solution, which is also
concise, thread-safe and portable (meaning
that can be easily translated to other
languages) is

def _foo4(n, depthlimit):
if depthlimit == 0: return
_foo4(n+1, depthlimit-1)

def foo4(n=0):
_foo4(n, 5)


% timeit.py -s "import spam" "spam.foo4()"
100000 loops, best of 3: 16.4 usec per loop


Andrew
(e-mail address removed)

 

[Manlio Perillo]

Me:



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

It's my fault.
It is long time I'm not using C++ that I forgot that static variable
function initialization is done once during program.
However firstlevel_call is what I want.

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.

Ok. Thanks

That's not recursive, so I don't know how to
interpret your question.

This is only the function signature!
The problem is that I can't do:

def my_function(a, b, *args, **kwargs, __max_depth = 4): ...

The only way is to do:
def my_function(a, b, max_depth = 4, *args, **kwargs): ...

But in this way max_depth is 'exposed' to public.
In the first example it is private.

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))

What's the purpose of such a function?



Thanks and regards Manlio Perillo

 

[Andrew Dalke]

This is only the function signature!
The problem is that I can't do:

def my_function(a, b, *args, **kwargs, __max_depth = 4): ...

The only way is to do:
def my_function(a, b, max_depth = 4, *args, **kwargs): ...

But in this way max_depth is 'exposed' to public.
In the first example it is private.

My point, mentioned several times now, is that there's
nothing preventing you from making *two* functions.
The private one doesn't need the *args, **kwargs parameter
definition, and the public one doesn't need the depth
limit.

def _my_function(a, b, args, kwargs, max_depth = 4):
# do your recursive work here

def my_function(a, b, *args, **kwargs):
# the public entry to your system
return _my_function(a, b, args, kwargs)

What's the purpose of such a function?

It's a standard recursive function used for
benchmarks. It's often used to test how
well a language supports recursion because it
very quickly hits stack limits instead of
numeric limits.

I used it to make my example concrete by
showing how to have a public API which is
different than the API used by the actual
recursive function. I also used it to show
how that sort of split makes it easier to
add parameter checking, if it's needed.

Andrew
(e-mail address removed)

 

[Manlio Perillo]

This is only the function signature!
The problem is that I can't do:

def my_function(a, b, *args, **kwargs, __max_depth = 4): ...

The only way is to do:
def my_function(a, b, max_depth = 4, *args, **kwargs): ...

But in this way max_depth is 'exposed' to public.
In the first example it is private.

Sorry, forget about this post!



Regards Manlio Perillo