On Tue, May 28, 2013 at 2:24 PM, Ram Rachum <r...@rachum.com> wrote: > Thanks for your critique, Bart. > > One counter-point I'd like to make to your third argument, which I had to > make over at python-ideas as well: I am not advocating recursive > programming. There is no need to convince me that the loop version of the > algorithm is superior to the recursive version. The reason I care about > optimizing recursive algorithms is because sometimes these algorithms are > forced on you, and when they are, you want them to be as efficient as > possible. > > There's the example of the `pickle` module. In Python, pickling is > recursive. I had a case where a program of mine failed to run because it > involved pickling an object that referenced a large number of small objects > that referenced each other. I had no choice except using recursion, because > Python's `pickle` uses recursion. (Except of course writing my own pickle > module...) > > So I want recursive algorithm to be faster not because I'd like to use them, > but because I want them to be faster when I'm forced to use them.
stackless does allow you to have deep recursion by copying the stack away FYI. > > > On Tue, May 28, 2013 at 3:12 PM, Bart Wiegmans <bartwiegm...@gmail.com> > wrote: >> >> Hi Ram, >> >> That is a daring idea, really. But since you asked it, I will tell you >> what I think. >> >> I think it is a bad idea. >> >> First of all, the complexity of implementation. I see two 'obvious' >> implementations of your idea, which is a): an 'on-line' stack >> compressor, which will slow down functions calls farther than they are >> already (in CPython, anyway), or b): a 'just-in-time' stack compressor >> that is initiated when the 1000th stack frame is reached. I can >> imagine this happening in-place, but it won't be efficient. >> Now consider what happens when an exception is raised from the bottom >> to the top.Or worse, from the bottom to somewhere-in-the-middle. >> >> The second point concerns the possible gains. Suppose your recursive >> factorial stack is compressed. At the very least, any compression >> algorithm must store the decreasing integer that is multiplied. (You >> might get away with detecting the pattern, but don't count on it). At >> best, you might run your recursive algorithm a bit longer, but it will >> overflow eventually. In other words, on a machine with a finite stack >> size, the algorithm is *wrong*. The correct recursive implementation >> looks like this: >> >> def factorial(x): >> def recursive(x, c): >> if x <= 1: >> return c >> return recursive(x-1, x * c) >> return recursive(x, 1) >> >> Which doesn't need to store the decreasing x on any stack, and is >> thus a prime candidate for TCO. >> >> The third point concerns the reason why python does not have TCO in >> the first place. I've read Guido's blog as well, and in my opinion, >> he's wrong to make such a distinction between what are essentially >> nearly identical processes: jumping to new code locations. As it is, >> however, he's dictator. In python, you're simply not /supposed/ to use >> deep recursive algorithms. It is considered un-pythonic. >> >> Nevertheless, I like the style of your idea :-). >> >> Kind regards, >> Bart Wiegmans >> >> >> >> 2013/5/28 <pypy-dev-requ...@python.org>: >> > Send pypy-dev mailing list submissions to >> > pypy-dev@python.org >> > >> > To subscribe or unsubscribe via the World Wide Web, visit >> > http://mail.python.org/mailman/listinfo/pypy-dev >> > or, via email, send a message with subject or body 'help' to >> > pypy-dev-requ...@python.org >> > >> > You can reach the person managing the list at >> > pypy-dev-ow...@python.org >> > >> > When replying, please edit your Subject line so it is more specific >> > than "Re: Contents of pypy-dev digest..." >> > >> > >> > Today's Topics: >> > >> > 1. Cross-post from python-ideas: Compressing the stack on the >> > fly (Ram Rachum) >> > 2. pypy (Samir Tigrine) >> > >> > >> > ---------------------------------------------------------------------- >> > >> > Message: 1 >> > Date: Mon, 27 May 2013 13:39:01 +0300 >> > From: Ram Rachum <r...@rachum.com> >> > To: pypy-dev@python.org >> > Subject: [pypy-dev] Cross-post from python-ideas: Compressing the >> > stack on the fly >> > Message-ID: >> > >> > <CANXboVaE_HsQt0CQhJwBwNOL8F+qPzCLbZZsdoLLQZvY4nSx=a...@mail.gmail.com> >> > Content-Type: text/plain; charset="iso-8859-1" >> > >> > Hi guys, >> > >> > I made a post on the Python-ideas mailing list that I was told might be >> > relevant to Pypy. I've reproduced the original email below. Here is the >> > thread on Python-ideas with all the >> > >> > discussion.<https://groups.google.com/forum/?fromgroups#!topic/python-ideas/hteGSNTyC_4> >> > >> > -------------- >> > >> > Hi everybody, >> > >> > Here's an idea I had a while ago. Now, I'm an ignoramus when it comes to >> > how programming languages are implemented, so this idea will most likely >> > be >> > either (a) completely impossible or (b) trivial knowledge. >> > >> > I was thinking about the implementation of the factorial in Python. I >> > was >> > comparing in my mind 2 different solutions: The recursive one, and the >> > one >> > that uses a loop. Here are example implementations for them: >> > >> > def factorial_recursive(n): >> > if n == 1: >> > return 1 >> > return n * factorial_recursive(n - 1) >> > >> > def factorial_loop(n): >> > result = 1 >> > for i in range(1, n + 1): >> > result *= i >> > return result >> > >> > I know that the recursive one is problematic, because it's putting a lot >> > of >> > items on the stack. In fact it's using the stack as if it was a loop >> > variable. The stack wasn't meant to be used like that. >> > >> > Then the question came to me, why? Maybe the stack could be built to >> > handle >> > this kind of (ab)use? >> > >> > I read about tail-call optimization on Wikipedia. If I understand >> > correctly, the gist of it is that the interpreter tries to recognize, on >> > a >> > frame-by-frame basis, which frames could be completely eliminated, and >> > then >> > it eliminates those. Then I read Guido's blog post explaining why he >> > doesn't want it in Python. In that post he outlined 4 different reasons >> > why >> > TCO shouldn't be implemented in Python. >> > >> > But then I thought, maybe you could do something smarter than >> > eliminating >> > individual stack frames. Maybe we could create something that is to the >> > current implementation of the stack what `xrange` is to the old-style >> > `range`. A smart object that allows access to any of a long list of >> > items >> > in it, without actually having to store those items. This would solve >> > the >> > first argument that Guido raises in his post, which I found to be the >> > most >> > substantial one. >> > >> > What I'm saying is: Imagine the stack of the interpreter when it runs >> > the >> > factorial example above for n=1000. It has around 1000 items in it and >> > it's >> > just about to explode. But then, if you'd look at the contents of that >> > stack, you'd see it's embarrassingly regular, a compression algorithm's >> > wet >> > dream. It's just the same code location over and over again, with a >> > different value for `n`. >> > >> > So what I'm suggesting is an algorithm to compress that stack on the >> > fly. >> > An algorithm that would detect regularities in the stack and instead of >> > saving each individual frame, save just the pattern. Then, there >> > wouldn't >> > be any problem with showing informative stack trace: Despite not storing >> > every individual frame, each individual frame could still be accessed, >> > similarly to how `xrange` allow access to each individual member without >> > having to store each of them. >> > >> > Then, the stack could store a lot more items, and tasks that currently >> > require recursion (like pickling using the standard library) will be >> > able >> > to handle much deeper recursions. >> > >> > What do you think? >> > >> > >> > Ram. >> > -------------- next part -------------- >> > An HTML attachment was scrubbed... >> > URL: >> > <http://mail.python.org/pipermail/pypy-dev/attachments/20130527/5723bc1f/attachment-0001.html> >> > >> > ------------------------------ >> > >> > Message: 2 >> > Date: Tue, 28 May 2013 11:19:53 +0200 >> > From: Samir Tigrine <tigrine.sa...@gmail.com> >> > To: pypy-dev@python.org >> > Subject: [pypy-dev] pypy >> > Message-ID: >> > >> > <cac3411-qckued5yrxq6p5o7bon46ttr+a3-htqjidwr3wzh...@mail.gmail.com> >> > Content-Type: text/plain; charset="iso-8859-1" >> > >> > Hello >> > >> > now I intend to use pypy >> > >> > It is compatible with zope ? >> > >> > cordially >> > -------------- next part -------------- >> > An HTML attachment was scrubbed... >> > URL: >> > <http://mail.python.org/pipermail/pypy-dev/attachments/20130528/5832754f/attachment-0001.html> >> > >> > ------------------------------ >> > >> > Subject: Digest Footer >> > >> > _______________________________________________ >> > pypy-dev mailing list >> > pypy-dev@python.org >> > http://mail.python.org/mailman/listinfo/pypy-dev >> > >> > >> > ------------------------------ >> > >> > End of pypy-dev Digest, Vol 25, Issue 39 >> > **************************************** >> _______________________________________________ >> pypy-dev mailing list >> pypy-dev@python.org >> http://mail.python.org/mailman/listinfo/pypy-dev > > > > _______________________________________________ > pypy-dev mailing list > pypy-dev@python.org > http://mail.python.org/mailman/listinfo/pypy-dev > _______________________________________________ pypy-dev mailing list pypy-dev@python.org http://mail.python.org/mailman/listinfo/pypy-dev
