Tail recursion Re: list of polynomial functions
In article [EMAIL PROTECTED], Matteo wrote: This last approach could, at least theoretically, create an arbitrarily long list of polys, without overflowing any kind of stack. In practice, python does not seem to perform tail recursion optimizations, and conks out after makepolys(997) on my machine. You can find out the conking-out limit and change it, within reason. import sys help (sys.getrecursionlimit) [...] help (sys.setrecursionlimit) [...] Here is a recipe for tail recursion optimization at ASPN: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691 Python doesn't do any kind of tail recursion optimization by default because Guido has decided it shouldn't (at least so far). I'm sure it has been discussed in detail in Python development forums lists, but I don't know those details. This Google search is a start, but it gives too many hits for me to shift through now: http://www.google.fi/search?q=site%3Apython.org+tail+recursion Pka -- http://mail.python.org/mailman/listinfo/python-list
Re: Tail recursion Re: list of polynomial functions
Pekka Karjalainen [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] Python doesn't do any kind of tail recursion optimization by default because Guido has decided it shouldn't (at least so far). I'm sure it has been discussed in detail in Python development forums lists, but I don't know those details. Giving Python's late name resolution, the transformation would be a change in semantics. Something might be proposed for 3.0. Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
Josiah Manson wrote: In the following program I am trying to learn how to use functional programming aspects of python, but the following program will crash, claiming that the recursion depth is too great. I am attempting to make a list of polynomial functions such that poly[0](3) = 1, poly[1](3) = 3, poly[2](3) = 9, etc. Could someone point me in the right direction? Thanks. def make_polys(n): Make a list of polynomial functions up to order n. p = lambda x: 1 polys = [p] for i in range(n): polys.append(lambda x: polys[i](x)*x) return polys # construct a vector of polynomials polys = make_polys(5) # print for p in polys: print p(3) Many wise things have been said in this thread. I would like to proffer another solution which does not rely on default arguments, just for a more functional flavor. def makepolys(n): if n==0: return [lambda x: 1] else: tailfunc=makepolys(n-1) return tailfunc + [ lambda x: x * tailfunc[-1](x)] Another way, which is properly tail recursive is the following: def makepolys2helper(n,retval): if n==0: return retval else: return makepolys2helper(n-1,retval+[lambda x: x* retval[-1](x)]) def makepolys2(n): return makepolys2helper(n,[lambda x: 1]) (Note: this could be collapsed into a single function either with a default argument, or a nested function, but I thought this was a bit clearer) This last approach could, at least theoretically, create an arbitrarily long list of polys, without overflowing any kind of stack. In practice, python does not seem to perform tail recursion optimizations, and conks out after makepolys(997) on my machine. And yes - I did just sit in on my first functional programming class :) -matt -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
In [EMAIL PROTECTED], Tim Chase
wrote:
My understanding is that the lambda-defined functions are not
called until the actual application thereof, with the
mypolys = make_polys(8)
mypolys[5](2) #the lambda call happens here, no?
Yes, that's right.
/F's original statement read like a koan...there was more in it
than I was getting out of it. There seem to be several concepts
I've not yet wrapped my head around. My understanding (likely
wrong) was that lambda was sort of like defining a function
inline, along the lines of
def f(x):
return x+5
being somewhat equiv to
k = lambda x: x+5
you could then do
f(20)
25
j = f
j(20)
25
k(20)
25
j = k
j(20)
25
There does seem to be some subtle difference, as
f
function f at 0xb7d87e9c
k
function lambda at 0xb7d8c0d4
k clearly knows it's a lambda just as f knows its an f
(whether asked for by the aliased name or not).
That understanding is mostly correct. Just that there's no subtile
difference. `k` doesn't know it's a lambda function, it's just an
ordinary function at this point which happens to have the name 'lambda'.
That's somewhat unusual but it behaves like any ``def``-ed function.
[lightbulb begins to go on...sorta]
However, in the OP's example, slightly modified, it seems that
polys, even when it doesn't exist in the calling scope, it
doesn't matter.
def mp(n):
... p = lambda x: 1
... polys = [p]
... for i in range(n):
... polys.append(lambda x: polys[i](x)*x)
... return polys
...
f = mp(5)
polys
Traceback (most recent call last):
File stdin, line 1, in ?
NameError: name 'polys' is not defined
for p in f: print p(3)
...
1
Traceback (most recent call last):
File stdin, line 1, in ?
File stdin, line 5, in lambda
:
:
:
I'm curious why the very first attempt to call p(3) doesn't bomb
out with the NameError that polys wasn't defined before it even
got to the point of attempting to call it.
Well, because `polys` does not exist in the module scope. But it exists
in the local scope of the functions in `f`.
An example:
In [2]:def outer(a):
.2.:b = 42
.2.:def inner(c):
.2.:print a, b, c
.2.:print locals()
.2.:
.2.:return inner
.2.:
In [3]:f = outer(1)
In [4]:f(2)
1 42 2
{'a': 1, 'c': 2, 'b': 42}
If `outer` returns `inner` the inner function still has a reference to the
locals of the enclosing function. So they won't go away if the outer
function returns. `a` and `b` are looked up when `f` is called. That's a
problem if you create more than one function in `outer` and use a name
from outer's locals that changes:
In [7]:def pitfall():
.7.:functions = list()
.7.:for i in range(3):
.7.:functions.append(lambda: i)
.7.:print 'pitfall: i=%d' % i
.7.:return functions
.7.:
In [8]:for function in pitfall():
.8.:print function()
.8.:
pitfall: i=2
2
2
2
At the time the list with the functions is returned `i` is 2. So if you
call any of the functions it looks up this `i`.
Ciao,
Marc 'BlackJack' Rintsch
--
http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
In [EMAIL PROTECTED], Josiah Manson wrote: def make_polys(n): Make a list of polynomial functions up to order n. p = lambda x: 1 polys = [p] for i in range(n): polys.append(lambda x: polys[i](x)*x) The `i` is the problem. It's not evaluated when the lambda *definition* is executed but when the lambda function is called. And then `i` is always == `n`. You have to explicitly bind it as default value in the lambda definition: polys.append(lambda x, i=i: polys[i](x)*x) Then it works. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
The `i` is the problem. It's not evaluated when the lambda *definition* is executed but when the lambda function is called. And then `i` is always == `n`. You have to explicitly bind it as default value in the lambda definition: polys.append(lambda x, i=i: polys[i](x)*x) Then it works. Just to sate my curiosity, why can the lambda find polys, but not find i? If what you're describing is the case, then it seems to me that the following code should work too: def make_polys(n): p = lambda x: 1 polys = [p] for i in range(n): p = polys[i] polys.append(lambda x: (p(x) * x)) return polys yet it suffers the same problem as the original. Outside the scope of make_polys, neither polys[] nor i exists. There's some subtle behavior here that I'm missing. -tkc -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
Tim Chase wrote: The `i` is the problem. It's not evaluated when the lambda *definition* is executed but when the lambda function is called. And then `i` is always == `n`. You have to explicitly bind it as default value in the lambda definition: polys.append(lambda x, i=i: polys[i](x)*x) Then it works. Just to sate my curiosity, why can the lambda find polys, but not find i? If what you're describing is the case, then it seems to me that the following code should work too: it's not that it cannot find it, it's that if you use a closure, i will have the same value for all lambdas. There's some subtle behavior here that I'm missing. lexical closures bind to names, default arguments bind to values. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
Fredrik Lundh wrote: Tim Chase wrote: The `i` is the problem. It's not evaluated when the lambda *definition* is executed but when the lambda function is called. And then `i` is always == `n`. You have to explicitly bind it as default value in the lambda definition: polys.append(lambda x, i=i: polys[i](x)*x) Then it works. Just to sate my curiosity, why can the lambda find polys, but not find i? If what you're describing is the case, then it seems to me that the following code should work too: it's not that it cannot find it, it's that if you use a closure, i will have the same value for all lambdas. There's some subtle behavior here that I'm missing. lexical closures bind to names, default arguments bind to values. Just to be a bit more explicit: In code like: def make_polys(n): Make a list of polynomial functions up to order n. p = lambda x: 1 polys = [p] for i in range(n): polys.append(lambda x: polys[i](x)*x) i=3 The lambda-defined functions will be called after the for loop is done, at which time the i (from the surrounding environment) will have a value of 3. Hope this makes it a bit clearer. --Scott David Daniels [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
The `i` is the problem. It's not evaluated when the lambda *definition* is executed but when the lambda function is called. And then `i` is always == `n`. You have to explicitly bind it as default value in the lambda definition: polys.append(lambda x, i=i: polys[i](x)*x) Thank you for your help. -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
Just to be a bit more explicit: In code like: def make_polys(n): Make a list of polynomial functions up to order n. p = lambda x: 1 polys = [p] for i in range(n): polys.append(lambda x: polys[i](x)*x) i=3 The lambda-defined functions will be called after the for loop is done, ::boggle:: My understanding is that the lambda-defined functions are not called until the actual application thereof, with the mypolys = make_polys(8) mypolys[5](2) #the lambda call happens here, no? /F's original statement read like a koan...there was more in it than I was getting out of it. There seem to be several concepts I've not yet wrapped my head around. My understanding (likely wrong) was that lambda was sort of like defining a function inline, along the lines of def f(x): return x+5 being somewhat equiv to k = lambda x: x+5 you could then do f(20) 25 j = f j(20) 25 k(20) 25 j = k j(20) 25 There does seem to be some subtle difference, as f function f at 0xb7d87e9c k function lambda at 0xb7d8c0d4 k clearly knows it's a lambda just as f knows its an f (whether asked for by the aliased name or not). So at some point, the Python interpreter is compiling this function/lambda, and expanding matters with or without some sort of scope. The OP's example seems to pull both polys and i from the local scope. However, Python must only be tokenizing and making references to future-ly available stuff, as, without spam, blah, tapioca, or spatula defined in my environment, I can do arbitrary things like q = lambda x: spam[spatula](x) + blah / tapioca and Python swallows the whole lot as syntactically kosher, even though none of these items exist. It seems to only evaluate them at the point that q is called. [lightbulb begins to go on...sorta] However, in the OP's example, slightly modified, it seems that polys, even when it doesn't exist in the calling scope, it doesn't matter. def mp(n): ... p = lambda x: 1 ... polys = [p] ... for i in range(n): ... polys.append(lambda x: polys[i](x)*x) ... return polys ... f = mp(5) polys Traceback (most recent call last): File stdin, line 1, in ? NameError: name 'polys' is not defined for p in f: print p(3) ... 1 Traceback (most recent call last): File stdin, line 1, in ? File stdin, line 5, in lambda : : : I'm curious why the very first attempt to call p(3) doesn't bomb out with the NameError that polys wasn't defined before it even got to the point of attempting to call it. Hope this makes it a bit clearer. like chocolate. :-/ Thanks for trying though... -tkc (who is certainly *not* a LISP programmer, as evidenced here...) -- http://mail.python.org/mailman/listinfo/python-list
Re: list of polynomial functions
I'm curious why the very first attempt to call p(3) doesn't bomb out with the NameError that polys wasn't defined before it even got to the point of attempting to call it. In the first call, the 0th lambda function is evaluated, and it was defined as the constant function 1. The functions after that each refer to the previous polynomial, so they mess up. The first doesn't so it's fine. I'm new to this, as evidenced by my original posting, so I may be missing something. I hope I helped, Josiah -- http://mail.python.org/mailman/listinfo/python-list
