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. 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
