Tail recursion in Python(chrispenner.ca) |
Tail recursion in Python(chrispenner.ca) |
lru_cache, from the functools library.
The example given in the docs [0] is:
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
[0] https://docs.python.org/3/library/functools.html#functools.l..."Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time." -- Steven Skiena
lru_cache decorator is great for people who are happy to let the language handle the caching of results for them, and often leads to code which is much more concise than the dynamic programming approach. The limitation you are referring to is that the decorator uses a dictionary to cache results and that dictionary uses the arguments as keys so the arguments need to be hashable. That limitation can be avoided by using immutable data structures (Clojure also has a higher order function called memoize which does the same thing and has no limitations because the core data structures in Clojure are immutable) and although Python not having structural sharing can mean that this approach can hurt memory and GC efficiency a bit, but that trade-off is at least worth considering :)
Still have to keep the stack depth less than sys.getrecursionlimit() so no substitute for tail recursion but surely a substitute for dynamic programming in a lot of cases.
You side-step some recursion through previously stored results. It works well for some class of algorithms, which coincides with quite a large subsection of problems where TCO would help formulate algorithms.
There are still a bunch of limits, because you're caching results, not eliminating call frames.
The first obvious drawback is performance and memory use: All results get stored in a dictionary.
Your memorization helps, but seems you will still run out of stack space if you call it with a big number without a warm up.
When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is generally a lot simpler than having to force the looping facility of one language into the semantics of another language.
The only one I can actually imagine porting other loops to is the common lisp loop macro, but that is probably the most flexible looping facility known to man.
Edit: and oh, cool thing: racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer. This is pretty handy when implementing something like map, since you can write a non-tail-recursive procedure so that you don't have to reverse the list at the end.
https://gist.github.com/ChrisPenner/c0b3f4feb054daa2f6370d2e...
https://gist.github.com/ChrisPenner/c958afbf6e7a763c188d8b83...
I mean, I personally don't care; I've always been a little weird. But it is funny to see technical preferences as a signaling mechanism.
Funny, that is, until it hits a certain point... http://www.wired.co.uk/article/chinese-government-social-cre...
This was one of the best quality of life decision in terms of web browsing I have ever made.
The vast majority of pages that I randomly access (e.g. from hacker news) are text based and usually work just fine without js. But the time until I can start reading is much faster (less jumping around of content) and I don't get the growth hackers modals shoven down my throat two paragraphs in. The pages I use regularly are usually white listed
Also avoiding downloading JS libraries bigger than Quake while on the go.
> if n == 0: return 1
> else: return tail_factorial(n-1, accumulator * n)
The second line should be "if n == 0: return accumulator"
EDIT: Oops. As pointed out below, the code is indeed incorrect, and my comment is irrelevant.
I'm not sure if there is any advantage when language/compiler does not provide a proper tail recursive optimization.
This statement in the beginning is not entirely correct. A more accurate statement would be that all recursive programs that are _iterative_ (if they are loops in disguise), can be rewritten in a tail-call form. That is, there must be a single chain of function calls.
The inherently recursive procedures cannot be converted into a tail-call form.
> So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic.
[0] http://neopythonic.blogspot.com.au/2009/04/tail-recursion-el...
I tried making such a patch in the past, got stuck in the much of trying to update the grammar file in a way that wouldn't complain about ambiguity
Main thing to get from tail calls vs loops is the case of mutually recursive functions
Edit: I didn't see shakna's comment.
[0] http://neopythonic.blogspot.de/2009/04/tail-recursion-elimin...
1. https://tomforb.es/adding-tail-call-optimization-to-python/
2. https://gist.github.com/orf/41746c53b8eda5b988c5#file-tail_c...
It'll effectively side-steps the recursion limit in Python. For runs under the limit anyway, it'd be interesting to see whether it's any faster. It trades function call overhead for exception handling overhead.
By the way, the first example where it has `return 1` is wrong. It shoudl `return accumulator`. Clicking the GitHub link someone suggested this in December.
def tail_factorial(n, accumulator=1):
if n == 0: return 1
else: return tail_factorial(n-1, accumulator * n)
This just returns 1 every time. def tail_factorial(n, accumulator=1):
if n == 0: return accumulator
else: return tail_factorial(n-1, accumulator * n)If I wanted to do this in practice, I'd just write the trampoline out explicitly, unless I wanted to do it a huge number of times. Doing it this way only takes a couple of extra lines of code but I think that's worth it for the improvement in explicitness, which is a big help for future maintainers (possibly me!).
from functools import partial
def _tail_factorial(n, accumulator):
if n == 0:
return accumulator
else:
return partial(_tail_factorial, n - 1, accumulator * n)
def factorial(n):
result = partial(_tail_factorial, n, 1)
while isinstance(result, partial):
result = result()
return resultScheme also did not just introduce tail recursion, but full tail call optimization.
Python sure does not need it, it already has a more complex iteration stuff like generators.
while some_condition:
x = one_generator(y)
y = other_generator(x)
where the generators yield values. No need for goto, no TCO, no magic.Even in languages like C, a nicer way to express it may be via two explicit state machines rather than going full Duff's device at this problem.
> if n == 0: return 1
> else: return tail_factorial(n-1, accumulator * n)
Does this ever return the accumulator?
[ed: ah, no. I see the first comment on the article is about this bug; it should return accumulator, not 1]
I do think it's a shame that Python doesn't have general TCO. It's said to be unpythonic because it means there will be two ways to do things. But some things are so easily expressed as a recursion but require considerable thought to be turned into a loop.
Do you have some examples of problem+solutions where tco works fine (in a language with tco) - but the manual translation is hard(ish)?
I wonder in part after reading the Julia thread on tco - and difficulties with providing guarantees in the general case with tco:
The usual complaint I hear is about stack traces, not “two ways to do things”, which Python rather often provides anyway.
Gambit seems to also not grow the stack dynamically, but I could be wrong.
I'm not familiar with how these two in particular work internally, but this may actually be more a side effect related to the implementation of call/cc than recursion. A popular technique is to truncate the stack when a continuation is captured. So you obviously need a stack that can expand.
There are trade-offs for both. The TCO'd map is a lot faster to restore when using continuations, but is not multi-shot continuation safe.
More like "disabled by default," actually. It's mostly ads/tracking, popovers, and other annoyances, and it's easy to selectively turn it back on where you really need it. This approach isn't for the general public yet.
[1] https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
Gambit definitely does grow the Scheme continuation stack; if you let it grow infinitely, it increases memory use of the whole process until it swaps or runs into a memory limit set via ulimit -v; in the latter case the Gambit runtime throws an out of memory exception in some situations, or reports an out of memory error and exits the system in others. If the procedure returns, the memory is given back first to the heap and then at some point (if not re-used) to the OS.
With regards to Chicken, as you say, it transforms the code into continuation passing style, allocates every continuation frame first on the C stack and then copies surviving frames into a second zone (it basically uses a generational garbage collector with 2 generations). Each long term continuation frame is essentially allocated on the heap (or whatever it is that the second zone is allocated from). Hence I expect that there is no limit on the size of the continuation stack in Chicken, either.
At the time, an explicit style, with patch, was proposed to python-ideas. [0] It was based around continuation-passing-style, and the conclusion reached then by the community was the same. TCO, explicit or not, isn't wanted in Python.
> And that's exactly the point -- the algorithms to which TCO can be applied are precisely the ones that are not typically expressed using recursion in Python. - Greg Ewing [1]
> <sarcasm>Perhaps we should implement "come from" and "go to" while we're at it. Oh, let's not leave out "alter" (for those of you old enough to have used COBOL) as well! </sarcasm> - Gerald Britton [2]
Feel free to try again, maybe things have changed.
To be clear, I wish Python did have a mechanism to express these sorts of problems, but I don't think the Python team themselves want them. This issue has come up more than a few times, and the dev team have never been satisfied that Python really needs it.
[0] https://mail.python.org/pipermail/python-ideas/2009-May/0044...
[1] https://mail.python.org/pipermail/python-ideas/2009-May/0045...
[2] https://mail.python.org/pipermail/python-ideas/2009-May/0045...
This isn't dismissive. lru_cache is one of my favorites too, but it has limitations.
The idea of function calls is much simpler - no yield magic necessary.