tag:blogger.com,1999:blog-4195135246107166251.post5401046714209368399..comments2023-05-08T07:04:09.641-07:00Comments on Neopythonic: Tail Recursion EliminationGuido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.comBlogger66125tag:blogger.com,1999:blog-4195135246107166251.post-86436052708016727392016-02-28T04:46:58.600-08:002016-02-28T04:46:58.600-08:00<>
Well, the same happens with asyncio. You...<i><></i><br /><br />Well, the same happens with asyncio. You can't get a nice stack trace if you don't enable asyncio debugging mode.Lucas Malorhttps://www.blogger.com/profile/02021656461185309628noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-58276842776410513472015-07-04T07:56:11.446-07:002015-07-04T07:56:11.446-07:00It is much cleaner to work with combinators than w...It is much cleaner to work with combinators than with explicit recursion. It shows the intent of the programmer. Anonymoushttps://www.blogger.com/profile/02898381097003622186noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-40034835625564777052015-07-04T07:55:10.359-07:002015-07-04T07:55:10.359-07:00In a project we are working on, we are moving towa...In a project we are working on, we are moving toward a more and more functional style, because it is much easier to reason about and this "feature" made use decide to move away from python. In python 3 functional programming style is even more discouraged. <br /><br />I don't understand this decision. The debugging issue is a non issue, so what you lose some frames? It is not, that they have any interesting information in it. (f called with (3), f called with 2). And ehm, if you are really concerned about loosing information, it could be added as an optimization option to python.Anonymoushttps://www.blogger.com/profile/02898381097003622186noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-7254745938172406062014-11-18T13:28:44.375-08:002014-11-18T13:28:44.375-08:00I’ve grown to like tail recursion even though I “g...I’ve grown to like tail recursion even though I “grew up” with Python (it was the first language I really liked). My reasons are that I found recursive functions easier to debug than loops, because the variables available at the beginning of each “iteration” are always clear. I have an example of this on my site: http://draketo.de/light/english/recursion-wins<br /><br />Also it is already possible to get nice stack-traces with GCC by requiring compilation with -Og -foptimize-sibling-calls. For details see http://draketo.de/light/english/free-software/tco-debugArneBabhttps://www.blogger.com/profile/16449390422848764481noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-51219664735348921422014-04-01T09:18:51.734-07:002014-04-01T09:18:51.734-07:00My thoughts are to perhaps make TCO an opt-in feat...My thoughts are to perhaps make TCO an opt-in feature via -O/-OO or something analogous. In that case, it would be the responsibility of the invoker of the interpreter to ensure that the program plays nice and doesn't try any bizarre tricks, just like right now one needs to make sure under -OO that docstrings aren't being used (I'm looking at you, ply). Also, under optimize mode, the neatness of stack traces is presumably irrelevant because a known side effect of optimization is the removal of debugging features.ipatrolhttps://www.blogger.com/profile/06449260589817980007noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-57251699670787337802013-10-10T08:05:12.433-07:002013-10-10T08:05:12.433-07:00just use a new syntax(for example, return from ......just use a new syntax(for example, return from ...) for explicitly reuse current frame, and everything done.<br /><br />explicitly release current frame on next function call could provide more efficient gc(local variables die as soon as they were useless) and more clean debug information(traceback of many wrapper function is totally useless, such as socket.socket.__getattr__).水逝云飞https://www.blogger.com/profile/01255171563364035215noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-28009449805261681332013-10-10T07:59:38.779-07:002013-10-10T07:59:38.779-07:00TRE is explicitly enabled by the special return sy...TRE is explicitly enabled by the special return syntax(for example, return from ...).<br /><br />with the new "return from", current frames is reused, and traceback is replaced by the further call. <br /><br />using "return from" to explicitly release current frame provide more efficient gc (local variables die as soon as they were useless) and more clearly debug information (traceback of some wrapper function is totally useless, such as socket.socket.__getattr__).<br /><br /><br /><br />水逝云飞https://www.blogger.com/profile/01255171563364035215noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-18254530095627690882013-07-17T00:10:30.816-07:002013-07-17T00:10:30.816-07:00I like Dan's proposal very much. I would make ...I like Dan's proposal very much. I would make use of the new language feature immediately!Anonymoushttps://www.blogger.com/profile/07136457974650632281noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-12700458618075463022013-07-11T16:11:15.783-07:002013-07-11T16:11:15.783-07:00Dan: your proposal has the redeeming quality of cl...Dan: your proposal has the redeeming quality of clearly being a language feature rather than a possible optimization. I don't really expect there to be enough demand to actually add this to the language though. Maybe you can use macropy to play around with the idea though?Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-42204159909246769912013-07-11T15:58:36.341-07:002013-07-11T15:58:36.341-07:00Definitely seems to be complicated/impossible to d...Definitely seems to be complicated/impossible to determine a function is tail recursion 'compliant' statically in python, however, what if it were an 'opt in' feature that uses a different 'return' keyword?<br /><br /> def f(n):<br /> if n > 0:<br /> tailcall f(n - 1)<br /> return 0<br /><br />Where tailcall would have special semantics similar to return but with the side effect of 'Tail Recursion'. You could easily use return here, but in the case where n is very large, you could replace the return with tailcall to 'fix the bug' vs rewriting the entire function to be iteration vs recursion. Arguably, the final effect of return and tailcall is the same (a value is returned), but the process in which you get there is significantly different. One results in a deep stack that possibly blows up vs the other results in a single frame that is harder to debug (but I think that could be mitigated, for instance: a tailcall frame/function could be specially marked in the stack trace).<br /><br />Arguably, it would add yet another 'return-like' keyword (where yield and return are similar), but perhaps its simple and un-intrusive enough to benefit those that would like to use tail recursion.<br /><br />Obviously, it's not as glamorous as being able to optimize 'return' to tail recursion automagically, but it does allow those familiar with its semantics to opt into its use. Other languages could easily implement it and it would not affect already written code.<br /><br />Just had the thought, not sure if it has already been discussed. I know python does not attempt to be a functional language, but this would certainly open it up to more of a possibility.<br /><br />Thanks for your time.Anonymoushttps://www.blogger.com/profile/13682155400650729376noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-74124464580329950202013-02-11T09:52:33.838-08:002013-02-11T09:52:33.838-08:00You can absolutely have Python-like stack traces i...You can absolutely have Python-like stack traces in a properly tail-call handled language. Take:<br /><br />(define loop <br />````(lambda (n)<br />```````(if (= n 0)<br />```````````(no-such-function)<br />```````````(loop (- n 1)))))<br />(loop 10)<br /><br />Produces:<br /><br />Traceback (most recent call last):<br /> File "/home/dblank/gluezilla/Untitled.ss", line 7, col 1, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 5, col 13, calling 'loop'<br /> File "/home/dblank/gluezilla/Untitled.ss", line 4, col 14<br />RunTimeError: unbound variable 'no-such-function'<br /><br />in Calico Scheme.Doug Blankhttps://www.blogger.com/profile/17756588602580974678noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-61859514657387199132012-03-13T04:09:14.032-07:002012-03-13T04:09:14.032-07:00Anirvan: sorry that I am late here. Its true that ...Anirvan: sorry that I am late here. Its true that python does not have private function naming the way JavaScript does, and therefore you would have to write something like (replace ` with two spaces):<br /><br />def make_fact():<br />``def fact(n): <br />````return 1 if n < 2 else n * fact(n - 1)<br />``return fact <br />fact = make_fact()<br /><br />It is also true that unfortunately Python, like JavaScript, doesn't support macros (code that writes code), so you cannot wrap that whole beast in a simple decorator. It's a pity, it would be nice to be able to at the very least say something like:<br /><br />@!self_scoped<br />def fact(n): <br />``return 1 if n < 2 else n * fact(n - 1)<br /><br />...with `@!` being a sort of "macro decorator" so that you do not have to worry if someone else redefines fact. On the other hand, there is a Python principle that "we're all adults here, if I redefine 'fact' within your code that's only really going to affect me," etc. Still, you can see where it lacks power.<br /><br />Beni: I am even later in responding to you, but I will make this point anyways. The right way to think about tail calls is 'iterorecursively'. You write an iterative algorithm by declaring the variables as arguments and recursing rather than looping. So you might have written an iterative factorial as:<br /><br />def fact(n):<br />``product = 1<br />``for i in range(1, n + 1):<br />````product *= i<br />``return product<br /><br />To write this iterorecursively you could instead write:<br /><br />def fact(n, product=1, i=1):<br />``return product if i > n else fact(n, product * i, i + 1)<br /><br />That is a tail-recursive function. Many lispers get so used to them that they instead decrement on `n` to save a variable:<br /><br />def fact(n, product=1):<br />``return product if n <= 0 else fact(n - 1, product * n)<br /><br />The point is, GvR's advice here is mostly blustery crap. If I use @!tail_recursive (again with these fake macros that don't exist!), then the very least you can do is assume the @!self_scoped macro, too: whenever I refer to `name` it means the present function. The fact that the macro depends on this doesn't matter, because We Are All Adults Here, and if we say "I'm doing X" then we should be content to say "oh, look, he's doing X." The other problem that GvR highlights -- that sometimes it's syntactically incorrect to describe something as @!tail_recursive -- is probably the domain of throwing a ValueError. However, it <i>is</i> suggestive of the fact that we shouldn't even have to discuss this sort of thing, and tail call optimization can just happen for free on compilation. If you look at the Abelson-Sussman lectures here:<br /><br />http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/<br /><br />they discuss compiler design in Scheme, and the result is actually absurdly simple: there is a tiny, almost trivial difference where you realize that it doesn't matter which order two lines of compiler output are, so you put them in the opposite order that you might have expected, and then you don't leave behind any stack when the thing actually is tail-recursive, but you still gracefully handle the case where it is not (since you haven't lost generality). <br /><br />So at least in principle Guido is wrong. Scheme proves that you don't need a special syntax to provide tail-call optimization, and I'm really not sure that things like debuggability fundamentally <i>can't</i> be done in this context.Chris Drosthttps://www.blogger.com/profile/13319424865794352000noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-30432525333748661852012-01-02T11:58:20.180-08:002012-01-02T11:58:20.180-08:00As a newcomer to Python, Guido's example with ...As a newcomer to Python, Guido's example with function name rebinding is a bit scary to me...<br /><br />How can I refer to a function from within the body of that function without using its name to prevent this? I haven't been able to find an equivalent of "self" for functions.Anirvanhttps://www.blogger.com/profile/02453650186787649553noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-1738169483694086122011-05-15T22:05:43.603-07:002011-05-15T22:05:43.603-07:00@Adam Olsen
"it changes the algorithmic compl...@Adam Olsen<br />"it changes the algorithmic complexity..."<br /><br />how does tco change algorithmic complexity?david pasquinellihttps://www.blogger.com/profile/14317139024673582070noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-18377741638608842532009-06-03T10:34:17.505-07:002009-06-03T10:34:17.505-07:00Not Python-related, I just figured the perfect exa...Not Python-related, I just figured the perfect example of tail call for the layman, and had to share it with somebody:<br /><br />You know how you have a browser tab whose only interesting content is 5 links, so you middle-click 4 of them to new tabs but open the 5th link in the original tab? That's tail call!<br /><br />[Strictly speaking, that's imprecise because you have history (=stack) on each tab. So it's more like "tail spawn" for threads or processes: it's like some launcher shell scripts whose last line is "exec" (*). But coding-wise, in the abstraction level of a shell script, it looks exactly like tail call - because "calls" in the the shell are asynchronous.<br /><br />(*) ironically, the reason launcher scripts use "exec" is precisely that they *want* to drop the "stack frame". Leaving the shell alive would just clatter the process table with no real benefit.]Beni Cherniavsky-Paskinhttps://www.blogger.com/profile/10500835143321767281noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-75797523818598200982009-05-31T19:21:03.090-07:002009-05-31T19:21:03.090-07:00Why not make a cleaned-up tail call an explicit va...Why not make a cleaned-up tail call an explicit variation on the return statement? Then you get the stack trace you asked for. And like what Kumar says, it's also the stack trace you probably would want in that situation.<br /><br />I thought I read that Python was intended for both beginners and math types. I like Python because both those sides of myself like it.<br /><br />The application that led me eventually to here, was a generator for a directory tree. It just seems wrong for each [[great...] grand] parent to loop over each [[great...] grand] child's results and re- [re-...] yield them.<br /><br />I googled about that and found a <A HREF="http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg03165.html" REL="nofollow">discussion </A>that said a tail-recursive "yield_all" would be very hard in Python.<br /><br />Then I started trying to write an iterator subclass that does explicit continuation passing. My first try ended up having its space savings depend on a tail-recursive method call. Hmm, does that work in Python? Googling that question got me here. (No it doesn't work, back to the drawing board.)<br /><br />Meanwhile, Guido, you wondered what possible use a tail- recursive method call could have. Hope this seems plausible. Imagine trees with >1000- deep chains of only children, but also bushy parts.<br /><br />There are ways to do TCO in pure stack languages. What it does to the readability of your code and how it integrates with things like external C functions, are different matters.FutureNerdhttps://www.blogger.com/profile/17103481765366134475noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-70027342178649573512009-04-29T12:28:00.000-07:002009-04-29T12:28:00.000-07:00I actually find the best use case to be when you h...I actually find the best use case to be when you have functions that aren't just self-recursive. If you have two or three functions that recurse between each other, suddenly you have an unbounded stack problem.<br /><br />I would love a syntax change. I had previously proposed "recurse", but I like send even better. If we do add syntax, I think that we should add an API. Callables should support a __send__ method that does optimized tail recursion.<br /><br />The advantage of this is that we can write classes that can support __send__ and use them in concert with things like Threading to build much better actor systems.<br /><br />What would be REALLY cool would be if generators used this API as well (since X.send(blah) is not quite as nice as send X(blah) ). Although, there is the problem that we are clouding the meaning what would otherwise looks like a normal function call, so it probably would be too confusing.<br /><br />On the plus side, it would be very cool to have a subclass of threading.Thread that wraps a generator and will yield incoming "send" messages into generator, etc.<br /><br />In the end, I'm pretty sure that to get a really good actor paradigm, we need to go further than just generators, probably with a whole new construct. Lots of things that work great in an actor model are the kind of thing that having this kind of feature is really good for.Jayson Vantuylhttps://www.blogger.com/profile/12699845108719516586noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-83804630505838569792009-04-29T11:42:00.000-07:002009-04-29T11:42:00.000-07:00"Is it really such a big deal to rewrite your func..."<I>Is it really such a big deal to rewrite your function to use a loop? </I>"<br /><br />It is not. But I'd have to say it would definitely affect readability in the case of self recursive functions. <br /><br />An interesting way to address this would be to use coroutines and instead of calling the function recursively one could send the arguments to the function. But then again, coroutines cant send values to themselves AFAIK. <br />If they did, one could use a pattern like this:<br /><br />def tail_rec_func():<br /> args, kwargs = (yield)<br /> ...<br /> send(new_args, new_kwargs)<br /><br />The good thing about this is that it is explicit. It would be a fairly advanced trick and people would know what to expect from it (i.e.: a non-trivial stack trace).<br /><br />Another way would be through new syntax (something different than return) for making a tail call (I know adding syntax is not to be taken lightly, please don't set me on fire). Someone mentioned Clojure which has similar syntax.nicolaslarahttps://www.blogger.com/profile/15167966852380794888noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-89565497549097734412009-04-27T16:09:00.000-07:002009-04-27T16:09:00.000-07:001- your proposed alternative to tail-calls, loops,...1- your proposed alternative to tail-calls, loops, are WORSE wrt debug info. Tail-calls are trivially transformed into calls w/ debugging info; equivalent loops not so much. http://fare.livejournal.com/142410.html<br /><br />2- PTC (proper tail calls) are not a mere optimization. They essentially change the space complexity of programs, and they allow code to be decentralized where loops require big spaghetti centralization.<br /><br />3- lisp-style lists and recursion are completely different concepts. One does not imply the other. Tail-calls allow to build iterators on arbitrary data-structures in a modular and compositional way. (Felleisen has some nice papers on that.)<br /><br />4- any Turing tar-pit is able to emulate proper tail-call through one extra level of indirection. But then in addition to the run-time cost, you pay the programmer-time cost of having to enforce convention and not being able to freely interoperate with code that doesn't use the convention.Faréhttps://www.blogger.com/profile/14063105144178880818noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-28378087403514631322009-04-27T09:43:00.000-07:002009-04-27T09:43:00.000-07:00>> The call to g(5) invokes the
>> ea...>> The call to g(5) invokes the <br />>> earlier f, but the "recursive" <br />>> call no longer recurses!<br /><br />This is, of course, why scheme doesn't generally do tail call elimination this way either.<br /><br />It is interesting in that it can be done without any modification to the byte code interpreter, but so can trampoline loops like is employed in Clojure.<br /><br />But why the avoidance of tampering with the byte code interpreter?Aaronhttps://www.blogger.com/profile/10658555678500278995noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-13597242171000915282009-04-26T18:21:00.000-07:002009-04-26T18:21:00.000-07:00Not having a lot of experience or knowledge of tai...Not having a lot of experience or knowledge of tail recursion, I am not in any position to argue about using it or not using it. I love python the way it is, and I trust you're making the right decisions.<br /><br />However, a point that does bother me slightly is your general preference for loops in place of recursion. I feel like recursion is closer to the way my mind reasons about problems in many cases. And since programming languages are just a way of translating my thoughts for the cpu, it seems like a handy tool.<br /><br />In any case, I would like to hear more on your preferences regarding recursion vs. loops and am hoping for another post exploring this.<br /><br />I'm loving the posts here and at History of Python. Keep them up. :)brad dunbarhttps://www.blogger.com/profile/15657776321096054721noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-65664394828285249462009-04-26T17:07:00.000-07:002009-04-26T17:07:00.000-07:00This comment has been removed by the author.EMhttps://www.blogger.com/profile/00794986337274390041noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-8342858627133493622009-04-25T23:28:00.000-07:002009-04-25T23:28:00.000-07:00@jto
Writing a virtual machine using opcodes ( st...@jto<br /><br />Writing a virtual machine using opcodes ( states ) and a stack is just fine. Writing applications in that style is simply not adequate and a step backwards.kay schluehrhttps://www.blogger.com/profile/18193908805797245856noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-13295049462126423182009-04-24T17:00:00.000-07:002009-04-24T17:00:00.000-07:00Just out of sheer curiosity, is there any reason w...Just out of sheer curiosity, is there any reason why you could not do something similar to clojure's loops? I suppose the syntax could look something like this:<br /><br /><br />def some_func():<br /> loop(x=0):<br /> if x <= 10:<br /> x += 1<br /> recur(x, y)<br /><br />That would roughly translate into something like this:<br /><br />def some_func():<br /> def _loop(x):<br /> if x <= 10:<br /> x += 1<br /> _loop(x, y)<br /><br /> _loop(0)<br /><br />Granted, this is a contrived case. But sometimes I find it easier to think of problems recursively rather than iteratively. And the second version just seems ugly to me.Jason Bakerhttps://www.blogger.com/profile/02649532819140192045noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-4562549097062717682009-04-23T23:16:00.000-07:002009-04-23T23:16:00.000-07:00Damn you <stdin>! :PDamn you <stdin>! :Pnamekuseijinhttps://www.blogger.com/profile/02436340179949427584noreply@blogger.com