tag:blogger.com,1999:blog-8288194986820249216.post7466352849321336181..comments2024-03-22T05:09:17.789-07:00Comments on Abstract Heresies: You knew I'd say something.Joe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-8288194986820249216.post-58488531741457282642009-04-30T09:10:00.000-07:002009-04-30T09:10:00.000-07:00It seems like it’d be better to talk about TCO and...It seems like it’d be better to talk about TCO and leave recursion out of it. The benefits to recursion are a subset of the benefits of TCO.<br /><br />Just about every language implementer I’ve ever met would be very proud of implementing TCO. It’s hard to imagine one arguing against it.<br /><br />Although, I suppose Python tends to conflate specification with implementation. I can understand wanting to keep it out of the specification.<br /><br />Still, it’s hard for me to understand a language specification not wanting to give programmers more tools—balanced against other issues, of course—rather than fewer. Although, that’s Python’s “there’s only one way to do it” philosophy.<br /><br />Isn’t Faré right: Implementing loops on top of TCO is easier than implementing TCO on top of loops? Scheme’s path of putting TCO in the spec and providing macros to allow looping constructs to be build on top of it in a library seems awfully sensible to me.Roberthttps://www.blogger.com/profile/16733274876782876659noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-44319410164946502402009-04-28T15:15:00.000-07:002009-04-28T15:15:00.000-07:00FWIW: Your odd? function is missing a base case. T...FWIW: Your odd? function is missing a base case. The functions can never return #f!Unknownhttps://www.blogger.com/profile/13627876893153890512noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-49142538770126271642009-04-28T00:09:00.000-07:002009-04-28T00:09:00.000-07:00Bubblesort is not bad because it is slow. It is ...Bubblesort is not bad because it is slow. It is bad because it is surprising.<br /><br />Performance (and other) surprises should be avoided. The fact that python consumes stack space for tail calls surprises no-one.<br /><br />Bubble sort has surprisingly bad performance for large data.<br /><br />The use of reference counting garbage collection is much more likely could create surprises, perhaps they should fix that?Unknownhttps://www.blogger.com/profile/18001815881633914931noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-3045224725874489042009-04-27T19:15:00.000-07:002009-04-27T19:15:00.000-07:00Constance Eustache: "tail-recursive calls are conv...Constance Eustache: "tail-recursive calls are convertable to loops and back"<br /><br />Yes, but that's a GLOBAL program transformation from t ail-calls to loops, and if you allow such transformation, INTERCAL is just as good a language as Python.<br /><br />On the other hand, loops can be quite elegantly macro-expressed in tail-calls (see notably Olin Shivers' article on loops), which is a matter of purely local transformations.<br /><br />PS: my take on Guido's article: http://fare.livejournal.com/142410.html<br />http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html?showComment=1240873740000#c8956549754909773441Faréhttps://www.blogger.com/profile/14063105144178880818noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-17025030496783443782009-04-26T18:45:00.000-07:002009-04-26T18:45:00.000-07:00The difference is that foo releases its resources ...<I>The difference is that foo releases its resources before transferring to bar in the tail recursive case, and after bar's computation in the non tail recursive case.</I>I think you meant that sentence to reference baz, not bar.<br /><br />Excellent article! I hadn't before thought about non-TCO hanging on to variable references. Thanks!David Vandersonhttps://www.blogger.com/profile/00334549959328743800noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-39015859706836067592009-04-26T15:33:00.000-07:002009-04-26T15:33:00.000-07:00I find Krishnamurthi's example of a finite state m...I find Krishnamurthi's example of a finite state machine as something that inherently requires tails calls to be... curious at best.<br /><br />Every procedural programmer I know can easily implement a finite state machine with (using C as an example) an enum, a switch, and a for loop.<br /><br />Not only that, but this kind of implementation is *far* easier to convert to an asynchronous state machine (i.e. where the tokens being evaluated arrive in sequence separated by other events and by time). <br /><br />I personally have nothing terribly against TCO (as long as you can turn it off for debugging when needed). But I think we're still looking for an example of an easily-understood killer app for it.hacksoncodehttps://www.blogger.com/profile/16810160033437736677noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-46875768308545080592009-04-26T15:10:00.000-07:002009-04-26T15:10:00.000-07:00constance eustace said...
I could be wrong, but I ...constance eustace said...<br /><I>I could be wrong, but I am almost 100% certain that tail-recursive calls are convertable to loops and back without hacks like implementing your own stack.</I>There is an entire set of design patterns that are not available in languages that lack tail recursion. They are patterns that cannot be converted into loops without breaking open abstraction boundaries, or without losing compositionality.<br /><br />It is normal that programmers that have never coded in a language with tail recursion would not be familiar with these pattern, and wouldn't miss them. Inversely, programmers that are familiar with them feel their absence.<br /><br />This box is too small to give examples of these patterns. They are medium- and large-scale modularity patterns, and so presenting them takes some time. I suggest you read the following two papers:<br /><br /><A HREF="http://www.cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/" REL="nofollow">Automata via Macros</A>, <br />by Shriram Krishnamurthi, in the<br />Journal of Functional Programming, 2006<br /><br /><A HREF="http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html" REL="nofollow">Why Functional Programming Matters</A>, by John Hughes, in the Computer Journal and the Year of Programming, 1990.Guillaumehttps://www.blogger.com/profile/00722827827627546541noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-13870013343436330032009-04-26T14:33:00.000-07:002009-04-26T14:33:00.000-07:00Purely in the spirit of "all generalizations are w...Purely in the spirit of "all generalizations are wrong":<br /><br />Bubble sort is only O(n^2) on randomly sorted lists. <br /><br />On nearly sorted lists, its performance can exceed that of mergesort, shellsort, and/or quicksort, depending on the exact nature of the mis-sorting.<br /><br />It's really O(N*avg(distanceToSortedPosition)).<br /><br />Just a pet peeve, and it's only relation to this debate is that tail-recursion's efficiency gains are highly sensitive to programmer proficiency, and are extremely easy to reverse by careless maintenance.hacksoncodehttps://www.blogger.com/profile/16810160033437736677noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-25598749087722689302009-04-26T13:41:00.000-07:002009-04-26T13:41:00.000-07:00I could be wrong, but I am almost 100% certain tha...I could be wrong, but I am almost 100% certain that tail-recursive calls are convertable to loops and back without hacks like implementing your own stack.<br /><br />Any Recursive algorithm can be converted to a loops if you implement a stack, and any loop can be implemented as a recursion.<br /><br />A space-constant tail-recursive call would certainly convert to a loop that doesn't need a local stack. Because the tail-recursive version doesn't need one.<br /><br />And Zed Shaw knocked it out of the park.constance eustacehttps://www.blogger.com/profile/10766996152700797287noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-4135153965585047862009-04-26T13:22:00.000-07:002009-04-26T13:22:00.000-07:00Arachnid: Tail-calls would either be part of the l...Arachnid: Tail-calls would either be part of the language standard or not, and all implementations which conform would implement it.<br /><br />A multitude of Scheme implementations do as such.grant rettkehttps://www.blogger.com/profile/09439997834215273665noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-50680126022655320402009-04-26T11:25:00.000-07:002009-04-26T11:25:00.000-07:00You seem to be saying that stack space is an 'impl...You seem to be saying that stack space is an 'implementation detail' that an implementer is not expected to know about, and can increase the space complexity of an algorithm. However, if that's the case, merely supporting tail calls isn't going to fix it - any other recursion is going to run into the same issue.<br /><br />Further, one (significant one) of Guido's points remains completely untouched by your argument: There are many implementations of Python. Either they all have to implement tail recursion (and how likely is that?), or implementers won't be able to rely on tail recursion being present, in which case is there any point in having it?Unknownhttps://www.blogger.com/profile/03657901505827400722noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-2999596634689657682009-04-26T06:07:00.000-07:002009-04-26T06:07:00.000-07:00Hey, nice article and this is no big deal, but you...Hey, nice article and this is no big deal, but your time complexity analysis is a tad misleading. When you said merge sort is O(n log(n)) you said as an example that 1000 data points would connote ~1000*4 operations, but it is actually more around 1000 * 10 because the log is base 2. This is still significantly better than Bubble sort and such, just wanted you to be correct.Joe Lynchhttps://www.blogger.com/profile/08368941809679857418noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-5394325097035392462009-04-26T05:45:00.000-07:002009-04-26T05:45:00.000-07:00LOL, thats pretty good dude!
RT
www.anonymity.es....LOL, thats pretty good dude!<br /><br />RT<br />www.anonymity.es.tcHarold Fowlerhttps://www.blogger.com/profile/08018983019271676117noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-49794336230082207022009-04-26T05:43:00.000-07:002009-04-26T05:43:00.000-07:00Zed,
It's certainly true that you could expliciti...Zed,<br /><br />It's certainly true that you could explicitize the TCO by rewriting all of your code in CPS. However:<br /><br />a) To implement CPS in the Haskell style (as a monad) you /NEED TCO/ to avoid stack overflow!<br />b) If your language provides CPS with TCO built-in as a primitive then your scheme will work, but rewriting your code in this manner is still highly boring :-)<br /><br />In fact, Appels' embedding of SSA into CPS relies crucially on continuation-entering not requiring any stack operations!<br /><br />BTW, I work on a Haskell compiler (GHC), and we do both TCO /and/ treat certainly-dead variables as not being roots for the GC. I.e. TCO alone is not in general sufficient to realise all of the benefits discussed in the post.<br /><br />Having said all this, I'm not sure TCO is suitable for OO languages like Python. If you do things like inject "aspects" around your function calls - which can happen quite a lot when metaprogramming - then things that look like tailcalls can end up needing to push a stack frame, changing your asymptotic space behaviour.<br /><br />The loss of debugging info is also a blow :(. In fact, in Haskell if you get an exception there is no stack trace AT ALL! This is because in a lazy language in a sense every call is a tail call.<br /><br />Cheers,<br />MaxMax Bolingbrokehttps://www.blogger.com/profile/05003540528496327090noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-9672640805662958232009-04-26T04:15:00.000-07:002009-04-26T04:15:00.000-07:00I agree with Reid, yoru summary of the reasons is ...I agree with Reid, yoru summary of the reasons is good. One important point is that implementing tail recursion in Python pretty much changes the language, so programmers will write code depending on it. It does affects the O(N) properties of programming, and my understanding of Guido's comments is simply he doesn't like that style, and that Python is none the worse for it. I don't see why Python should be all thing to all people, and I do hope that Python does not catch such a case of C++ivitis at some point.Unknownhttps://www.blogger.com/profile/13102826647975435672noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-21960018210235259232009-04-26T03:27:00.000-07:002009-04-26T03:27:00.000-07:00This comment has been removed by the author.Sean McQuillanhttps://www.blogger.com/profile/16477373572593034581noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-57755027710693476872009-04-26T03:24:00.000-07:002009-04-26T03:24:00.000-07:00Zed,
I feel that there is a disconnect here. If ...Zed,<br /><br />I feel that there is a disconnect here. If I re-read the original post, I believe the example he is correctly citing would more properly be called inductive programming rather than recursive programming.<br /><br />Coming up with a "real world" example is putting me at a loss offhand, but some of the data structures I've seen come out of genetics might qualify :). I'll assume for the rest of this post that I for whatever reason want to process an acyclic graph with nodes that contain lists that may point back into the graph.<br /><br />In my example, it should be pretty obvious that no realistic loop short of a few hundred lines is going to handle both the graph structure, the list structure, and the jump from lists back into the graph. However, a fairly trivial inductive algorithm can handle this data structure cleanly.<br /><br />With proper tail recursion I can expect O(1) space requirements for my stack while executing my algorithm. Without tail recursion I can expect to cry when trying to analyze the complexity, so I shaln't, but it's obviously going to be something nasty and much much larger than O(1).<br /><br />I think this as a motivating example for TCO is fairly solid, and probably a much better selling point than "I can write fib with O(n) runtime!"<br /><br />That said, as you noted, everything can be rewritten in CPS by hand and TCO can be unrolled manually. However, at that point we're just as well arguing that everything is better in assembly?<br /><br />PS: I'm not saying I really disagree with you here, I just think you missed the motivating example and how it was not explicitly recursive.Sean McQuillanhttps://www.blogger.com/profile/16477373572593034581noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-78305405685173291832009-04-26T02:35:00.000-07:002009-04-26T02:35:00.000-07:00Perhaps I'm mistaken then, it's been a while since...Perhaps I'm mistaken then, it's been a while since I've done windows development. However, my reading of <A HREF="http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx" REL="nofollow">this MSDN page</A> is that Windows doesn't allocate any space in physical memory for the stack until it is referenced.Peterhttps://www.blogger.com/profile/03799579139256306118noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-57072593706093196892009-04-26T02:20:00.000-07:002009-04-26T02:20:00.000-07:00By default, Windows programs request that stack sp...By default, Windows programs request that stack space be committed when it is allocated.<br /><br />You can override this and allocate stack space without committing it, but that's pretty rare.Jonathan Allenhttps://www.blogger.com/profile/16213908463228592960noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-57152031604137982232009-04-26T02:13:00.000-07:002009-04-26T02:13:00.000-07:00In Windows the stack space is pre-allocated. Short...<I>In Windows the stack space is pre-allocated. Short of actually overflowing the stack, it doesn't usually matter how much you use.</I>This is untrue, though it looks that way to a user program. Modern operating systems keep most of the stack's potential size unallocated until the stack grows and throws a page fault. This makes creating new processes fast and saves space (at the cost of a jump into kernel code every now and then).<br /><br />More info: <A HREF="http://en.wikipedia.org/wiki/Virtual_memory" REL="nofollow">http://en.wikipedia.org/wiki/Virtual_memory</A>Peterhttps://www.blogger.com/profile/03799579139256306118noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-85712820071592231902009-04-26T02:09:00.000-07:002009-04-26T02:09:00.000-07:00Excellent article.Excellent article.Jens Axel Søgaardhttps://www.blogger.com/profile/15211030864341077735noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-55194912179801070432009-04-26T01:25:00.000-07:002009-04-26T01:25:00.000-07:00> That is to say, if your implementation is not...> That is to say, if your implementation is not properly tail recursive, you will often find that a program that ought to run in O(1) space is actually taking O(n) space or even worse.<br /><br />I would like to see this claim proven.<br /><br />In Windows the stack space is pre-allocated. Short of actually overflowing the stack, it doesn't usually matter how much you use.Jonathan Allenhttps://www.blogger.com/profile/16213908463228592960noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-67202789388082570502009-04-26T00:27:00.000-07:002009-04-26T00:27:00.000-07:00Your even?/odd? example is not complete: (odd? 0) ...Your even?/odd? example is not complete: (odd? 0) never returns. <br /><br />It is a nice example of doubly tail recursive functions, but is quite easy to get wrong.Pierrehttps://www.blogger.com/profile/02105344081263526130noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-89816289045288950122009-04-25T19:50:00.000-07:002009-04-25T19:50:00.000-07:00What I think stood out most as mistaken about Guid...What I think stood out most as mistaken about Guido's post was his conflating recursion and recursive data structures in his third point. "For practical purposes, Python-style lists (which are flexible arrays, not linked lists), and sequences in general, are much more useful to start exploring the wonderful world of programming than recursion... Most of Python's library is written with sequences and iterators as fundamental building blocks (and dictionaries, of course), not linked lists, so you'd be locking yourself out of a lot of pre-defined functionality by not using lists or sequences." Well, chained cons cells are lists, too, and recursive functions are good for much more than operating over recursive data structures. Recursion is often the only simple solution in messy real world stuff. Just last week I wrote recursive code to do one of the most real-worldy and least Computer Science-y thing imaginable: get data from a public API. I didn't see any reasonable alternative to recursion. (But since that project was, sadly, not written in a language with TCO I am stuck with a function that's going to break if our little Twitter app gets popular, at which point I'll have to do unreasonable hack. Or maybe I'll port it to Scheme instead.)<br /><br />But I admire Guido and could be misinterpreting what he said.Ethan Herdrickhttps://www.blogger.com/profile/15171781429775587563noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-4476062914525137442009-04-25T19:03:00.000-07:002009-04-25T19:03:00.000-07:00Grant: I cornered Will in a dark alley and forced...Grant: I cornered Will in a dark alley and forced them out of him. (Actually, I got them from the paper I referenced at the top of the post.)Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.com