Please stay on the list, this is NOT off topic for Tutor.
At 19:35 2003-01-09 -0700, Poor Yorick wrote:
>Magnus Lycka wrote:
>>A method like below would call itself until the stack breaks.
>>
>> def __setattr__(self, attr, val):
>> # do some error checks
>
>I know I'm asking a lot here, but would you mind tendering a short=20
>explanation of what the stack is. I'm not just being lazy. Most of the=
=20
>information on the web assumes more knowledge of computer science than I=
=20
>have. I generally understand stacks, like fifo and lifo, but what is "t=
he=20
>stack"?
Does anyone know of a resource that explains this in a way that
is understandable by people who don't already know what it's about?
Is http://www.stackless.com/spcpaper.htm#_Toc470444065 helpful?
This is a bit outside of my expertise. I hope someone will correct me if
I'm confused about something in Python's internals.
Anyway, Python has to be able to keep track of many different contexts
at the same time. Let's look at some silly code:
def addOne(x):
return x + 1
def addTwo(y):
return 1 + addOne(y)
def addThree(z):
return 1 + addTwo(z)
def main():
a =3D 5
print addThree(a)
a =3D 7
print addThree(a)
main()
When we run this program, Python needs to keep track of
many contexts at once. First, we get into the local scope
of main. There we have a local variable a with the value
5 to begin with. When we call addThree, we get into a new
scope, a new context. Now the only local variable i z and
we don't know about a, although z is also 5 as it's passed
in with that value. addThree calls addTwo; again a new
scope / context, where we only know about the variable y.
Finally addTwo calls addOne and we reach a fourth scope,
with the local variable x. Now addOne will reach its return
statement, and we get back to addTwo. This means that we
get back to our old scope, and have to remember the values
of all local variables as they were before we switched scope
to addOne. We will continue to revert to old scopes until we
get back to main again. So, if we forgot a scope as we left it
in a function call, we'll be in trouble. Eventually we will
even end the main function, and we will be in the global scope
of our program, but that's less of a problem.
A na=EFve idea would be to solve this problem by having a
storage for local variables in each function, but that
won't do what we want. First of all, we might use a function
again before we can drop the provious context (this is
called recursion) and normally, we don't want functions
to remember their state from a previous incarnation. We
use classes instead when we want such memory.
The normal way of solving this problem is instead to use
a stack where we store these contexts. For each function
call, we push a new context on the stack, and for each
function return we pop it off again. If we raise an exception,
we will have to pop the stack until the exception is caught.
The results of all this popping is shown in the wellknown
traceback...
The normal C implementation of Python uses the stack which
is provided for this purpose by the C runtime system. It has
a limited size, which you can change as shown below.
Let's look at this little example using the classical factorial
function. N.B. Don't do this in a GUI python interpreter. If
you like to do things that you are told not to do, make sure you
don't have unsaved work.
>>> import sys
>>> sys.getrecursionlimit()
1000
>>> sys.setrecursionlimit(5)
>>> def fact(x):
... if x < 2:
... return x
... else:
... return x * fact(x-1)
...
>>> print fact(3)
6
>>> print fact(4)
24
>>> print fact(5)
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 5, in fact
File "<stdin>", line 5, in fact
File "<stdin>", line 5, in fact
File "<stdin>", line 5, in fact
RuntimeError: maximum recursion depth exceeded
Here we reduced the size of the stack, and ran out of it very
quickly. You see the ordinary Traceback, which will give some
information about each context on the Python interpreter stack.
--=20
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/ mailto:magnus@thinkware.se