Re: Recursive calls and stack
On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: So the effect is that mutual recursion isn't actually any harder. But some kind of language support is required in this case. At least I don't know how to handle mutual recursion (apart from inlining one function inside the other...). But I'm certainly not a program transformation guru (neither a novice!) so I would not be surprised if someone says it can be done... What happens (using the model of an imaginary virtual machine, perhaps like the Python interpreter) is the following. A normal function call pushes a call-frame onto a stack. The call-frame contains information necessary for returning from the function, and usually a place to store its local variables and parameters. A function called in tail position simply overwrites the current call-frame with the new one instead of pushing it onto the stack. -- Neil Cerutti The church will host an evening of fine dining, superb entertainment, and gracious hostility. --Church Bulletin Blooper -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: So the effect is that mutual recursion isn't actually any harder. But some kind of language support is required in this case. At least I don't know how to handle mutual recursion (apart from inlining one function inside the other...). But I'm certainly not a program transformation guru (neither a novice!) so I would not be surprised if someone says it can be done... What happens (using the model of an imaginary virtual machine, perhaps like the Python interpreter) is the following. A normal function call pushes a call-frame onto a stack. The call-frame contains information necessary for returning from the function, and usually a place to store its local variables and parameters. A function called in tail position simply overwrites the current call-frame with the new one instead of pushing it onto the stack. This is the kind of language support menctioned. For tail recursion you don't require that support. -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: So the effect is that mutual recursion isn't actually any harder. But some kind of language support is required in this case. At least I don't know how to handle mutual recursion (apart from inlining one function inside the other...). But I'm certainly not a program transformation guru (neither a novice!) so I would not be surprised if someone says it can be done... What happens (using the model of an imaginary virtual machine, perhaps like the Python interpreter) is the following. A normal function call pushes a call-frame onto a stack. The call-frame contains information necessary for returning from the function, and usually a place to store its local variables and parameters. A function called in tail position simply overwrites the current call-frame with the new one instead of pushing it onto the stack. This is the kind of language support menctioned. For tail recursion you don't require that support. I'm not sure what you mean. The above support is enough for tail recursion, mutual recursion, and any other tail call to be optimized. -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
En Thu, 15 Feb 2007 16:35:25 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: So the effect is that mutual recursion isn't actually any harder. But some kind of language support is required in this case. At least I don't know how to handle mutual recursion (apart from inlining one function inside the other...). But I'm certainly not a program transformation guru (neither a novice!) so I would not be surprised if someone says it can be done... What happens (using the model of an imaginary virtual machine, perhaps like the Python interpreter) is the following. A normal function call pushes a call-frame onto a stack. The call-frame contains information necessary for returning from the function, and usually a place to store its local variables and parameters. A function called in tail position simply overwrites the current call-frame with the new one instead of pushing it onto the stack. This is the kind of language support menctioned. For tail recursion you don't require that support. I'm not sure what you mean. The above support is enough for tail recursion, mutual recursion, and any other tail call to be optimized. I only want to say that tail *recursion* can be eliminated trivially transforming the code into a while loop, and that can be done by the programmer, and doesn't require compiler support. Head *recursion* can be eliminated too by using some storage as temporary stack, and that doesn't require external support either. Mutual recursion (and generic tail call elimination) require some sort of external support: one can't eliminate the call just by transforming the program. -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
On 2007-02-15, Gabriel Genellina [EMAIL PROTECTED] wrote: I'm not sure what you mean. The above support is enough for tail recursion, mutual recursion, and any other tail call to be optimized. I only want to say that tail *recursion* can be eliminated trivially transforming the code into a while loop, and that can be done by the programmer, and doesn't require compiler support. Head *recursion* can be eliminated too by using some storage as temporary stack, and that doesn't require external support either. Mutual recursion (and generic tail call elimination) require some sort of external support: one can't eliminate the call just by transforming the program. Ah, I see now. Had my blinders on. -- Neil Cerutti Low Self-Esteem Support Group will meet Thursday at 7 to 8:30 p.m. Please use the back door. --Church Bulletin Blooper -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
En Wed, 14 Feb 2007 04:23:46 -0300, [EMAIL PROTECTED]
[EMAIL PROTECTED] escribió:
I am OK with calls being stacked, but I wondering will the local
variables be stacked given that return statement is followed by the
function call?
def test():
x = 22
y = 33
z = x+y
return anotherFunction(z)
In this function will all the local variables (x,y,z) be pushed into
the stack before calling anotherFunction(z) or Python will find out
that the locals are no longer needed as anotherFunction(z) is just
returned?
Not exactly like pushed into the stack, but there exists a frame object,
and it contains references to its local variables, and will be alive until
anotherFunction returns. From inside anotherFunction you can even inspect
those variables:
py def test():
... x = 22
... y = 33
... z = x+y
... return anotherFunction(z)
...
py def anotherFunction(z):
... print previous frame:, sys._getframe(1).f_locals
...
py test()
previous frame: {'y': 33, 'x': 22, 'z': 55}
So x,y,z will still be there until anotherFunction actually returns to
test, and the frame object is disposed. For a highly recursive function,
that's bad news. For debugging normal programs, that's good news; the
cgitb module, by example, is able to show the values for local variables
in all previous frames when an exception is raised.
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
On Feb 14, 11:09 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Hi, I have a program which literately finds the object that overlapping a point. The horizontal and vertical search are called recursively from inside each other. Is this way of implementation fill thestackspace with the local variables inside eachcall. If this is not good, is there a better way to implement? Orpythonitself will understand that the calls happen in the last line, so local variables need not be pushed into thestack? def find_point(pt): return _hor_search(pt, random_obj) def _hor_search(pt, obj): ... object = ... ... if object meets some condition: return object else: return _ver_search(pt, object) def _ver_search(pt, obj): ... object = ... ... if object meets some condition: return object else: return _hor_search(pt, object) - Suresh I found a simpler solution: get rid of recursive calls; using while loops. - Suresh -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] I am OK with calls being stacked, but I wondering will the local variables be stacked given that return statement is followed by the function call? def test(): x = 22 y = 33 z = x+y return anotherFunction(z) In this function will all the local variables (x,y,z) be pushed into the stack before calling anotherFunction(z) or Python will find out that the locals are no longer needed as anotherFunction(z) is just returned? = To add to Gabriel's answer: Questions of this sort are implementation specific. CPython will allocate the objects on the heap. But I believe at present something will go on the C stack with each function call. I suspect that the C array that typically implements the local namespace is included but don't specifically know. The local names are deleted, and the associated heap objects released if that make the reference count 0, as part of the return process. No optimization of the sort you indicate is done. Indeed, the heap objects could have other references, and the namespace array is fixed size, so I am not sure there is anything that could, in general, be done. In any case, Python never deletes without at least implicit instruction to do so. The maximun recursion depth CPython will attempt is governed by an internal variable that you can get and set to adjust to your problem and hardware: sys.getrecursionlimit() 1000 sys.setrecursionlimit(500) sys.getrecursionlimit() 500 Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
On 2007-02-14, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 03:09:37 -0300, [EMAIL PROTECTED] [EMAIL PROTECTED] escribió: Is this way of implementation fill the stack space with the local variables inside each call. If this is not good, is there a better way to implement? Or python itself will understand that the calls happen in the last line, so local variables need not be pushed into the stack? I'm afraid not, the calls will be stacked until some object is found. Python does not do tail recursion optimization (at least, I'm not aware of that). To be just a little pedantic, it's tail call optimization. Any tail call can be optimized, not just recursive ones. But even if it could do that, in this case you have recursive calls between two functions, and that's a bit harder. So the effect is that mutual recursion isn't actually any harder. Moreover, if his functions calls really are tail-calls, then translating them by hand into iteration might be fairly easy. A simple, silly example: def sum(seq): if len(seq) == 0: return 0 else: return seq[0] + sum(seq[1:]) Above, sum is not a tail call, since the + operation must be defered until after the call to sum returns. Below, sum is a tail call. def sum(seq, accum=0): if len(seq) == 0: return accum else: return sum(seq[1:], accum+s[0]) Since no state must be retained by sum when calling sum, it's a tail call. The last version translates more or less directly into a dumb while loop. I don't believe Python does tail call optimization; at least it isn't document that it does it. -- Neil Cerutti The audience is asked to remain seated until the end of the recession. --Church Bulletin Blooper -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti [EMAIL PROTECTED] escribió: On 2007-02-14, Gabriel Genellina [EMAIL PROTECTED] wrote: Python does not do tail recursion optimization (at least, I'm not aware of that). To be just a little pedantic, it's tail call optimization. Any tail call can be optimized, not just recursive ones. Maybe, but I didn't invent the term: http://computing-dictionary.thefreedictionary.com/tail%20recursion%20optimisation It's true that tail recursion is a special case of tail call - but it's just the case that can be managed by hand, no special support on the language -trampoline or whatever- is required (just a loop, GOTO 1). But even if it could do that, in this case you have recursive calls between two functions, and that's a bit harder. So the effect is that mutual recursion isn't actually any harder. But some kind of language support is required in this case. At least I don't know how to handle mutual recursion (apart from inlining one function inside the other...). But I'm certainly not a program transformation guru (neither a novice!) so I would not be surprised if someone says it can be done... -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
[EMAIL PROTECTED] wrote: Hi, I have a program which literately finds the object that overlapping a point. The horizontal and vertical search are called recursively from inside each other. ... in case you ever need deeply nested recursion: one solution is to use the already mentioned sys.setrecursionlimit(n) another is to use your own stack dummy example: def fact_recursive(n): if n0: return fact_recursive(n-1)*n else: return 1 def fact_iterative(n): stack = [] while n 0: stack.append(n) n -= 1 ret = 1 while stack: ret *= stack.pop() return ret actually you can always rewrite recursion with a stack and iterations note that if you use version = 2.4, then collections.deque is faster for stack (and especially for queue) data structure than list. -- http://mail.python.org/mailman/listinfo/python-list
Recursive calls and stack
Hi, I have a program which literately finds the object that overlapping a point. The horizontal and vertical search are called recursively from inside each other. Is this way of implementation fill the stack space with the local variables inside each call. If this is not good, is there a better way to implement? Or python itself will understand that the calls happen in the last line, so local variables need not be pushed into the stack? def find_point(pt): return _hor_search(pt, random_obj) def _hor_search(pt, obj): ... object = ... ... if object meets some condition: return object else: return _ver_search(pt, object) def _ver_search(pt, obj): ... object = ... ... if object meets some condition: return object else: return _hor_search(pt, object) - Suresh -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
En Wed, 14 Feb 2007 03:09:37 -0300, [EMAIL PROTECTED] [EMAIL PROTECTED] escribió: Hi, I have a program which literately finds the object that overlapping a point. The horizontal and vertical search are called recursively from inside each other. Is this way of implementation fill the stack space with the local variables inside each call. If this is not good, is there a better way to implement? Or python itself will understand that the calls happen in the last line, so local variables need not be pushed into the stack? I'm afraid not, the calls will be stacked until some object is found. Python does not do tail recursion optimization (at least, I'm not aware of that). But even if it could do that, in this case you have recursive calls between two functions, and that's a bit harder. Going back to your original problem, maybe you can use some known algorithms from computational geometry; start with http://www.faqs.org/faqs/graphics/algorithms-faq/ -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Re: Recursive calls and stack
On Feb 14, 11:45 am, Gabriel Genellina [EMAIL PROTECTED] wrote: En Wed, 14 Feb 2007 03:09:37 -0300, [EMAIL PROTECTED] [EMAIL PROTECTED] escribió: Hi, I have a program which literately finds the object that overlapping a point. The horizontal and vertical search are called recursively from inside each other. Is this way of implementation fill the stack space with the local variables inside each call. If this is not good, is there a better way to implement? Or python itself will understand that the calls happen in the last line, so local variables need not be pushed into the stack? I'm afraid not, the calls will be stacked until some object is found. Python does not do tail recursion optimization (at least, I'm not aware of that). But even if it could do that, in this case you have recursive calls between two functions, and that's a bit harder. Going back to your original problem, maybe you can use some known algorithms from computational geometry; start with http://www.faqs.org/faqs/graphics/algorithms-faq/ -- Gabriel Genellina Thanks Gabriel for the response. I am OK with calls being stacked, but I wondering will the local variables be stacked given that return statement is followed by the function call? def test(): x = 22 y = 33 z = x+y return anotherFunction(z) In this function will all the local variables (x,y,z) be pushed into the stack before calling anotherFunction(z) or Python will find out that the locals are no longer needed as anotherFunction(z) is just returned? - Suresh -- http://mail.python.org/mailman/listinfo/python-list
