With regards to stacks that can use all of the memory: Gambit and AFAIK Chicken behave that way, too. This is one of the reasons I chose Scheme over OCaml (and Haskell) over a decade ago when looking for a new language to move to.
Even Python doesn't need to have stack limit - just make sure C stack is large enough (e.g. using ulimit or pthread_attr_setstacksize) and use `sys.setrecursionlimit(1000000000)`.
Yes, you could make the stack larger, or, you could avoid needing to keep a gigantic useless stack in memory with this technique in the first place.
A patch that implements TCO in Python with explicit syntax like 'return from f(x)' could likely get accepted, ending these hacks
Would it? My impression is that Guido is fairly against any such thing occurring [0]. > 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...
His primary concern is with implicit tail recursion
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
Someone recently pointed out to me you can bypass the recursion limit with an inbuilt decorator, because it's basically a memoiser. 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 [0] https://docs.python.org/3/library/functools.html#functools.l...
This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
It's worth pointing out that python expands the datatype of numbers as needed (ending up at BigInt or similar, I belive). So any stack rewriting would have to accommodate an accumulator that starts as an integer and expands to arbitrarily many bits. It might be easily handled as I guess all arguments are references to python objects, and the regular code for expanding numbers could switch out the reference - but the point remains that proper tail call optimization in python needs to deal with objects as arguments.
This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
It's worth pointing out that python expands the datatype of numbers as needed (ending up at BigInt or similar, I belive). So any stack rewriting would have to accommodate an accumulator that starts as an integer and expands to arbitrarily many bits. It might be easily handled as I guess all arguments are references to python objects, and the regular code for expanding numbers could switch out the reference - but the…
This does not seem to me like a big hurdle. Surely this is the sort of thing that should be hidden in the Integer class?
This is the same as recur in Clojure. It's not general TCO, though, which is much more powerful. 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.
The nice thing about recur in Clojure is that it won't even compile if the call isn't in the tail position. I've inadvertently made a code change that moved the recur call out of the tail position and the error became immediately obvious. With TCO you might not even notice until your stack blows up on a deep nesting.
Don't dismiss one of my favorite higher order functions so soon :) "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 limitat…
You can only avoid the recursion limit in cases where dynamic programming would also work, as you have to explicitly call the function in reverse stack order to avoid having the stack build up. If you want fib(10000) you need to call fib(1) through fib(9999) first, as if you were implementing a dynamic programming solution. This isn't dismissive. lru_cache is one of my favorites too, but it has limitations.
But that isn't a limitation of lru_cache, for example the same higher order function when used in Clojure i.e. memoize with recur for tail recursion will not cause stack overflow. The stack build up is because python doesn't support tail call optimization, not a limitation of lru_cache, just wanted to make it clear because you can use similar higher order functions in other languages which support tail call optimization without any limitations. Deep recursion in Python without sys.setrecursionlimit() is probably not a good idea, memoization can't help you in that. My point was geared towards presenting this pattern of memoization using a higher order function + recursion as an alternative to dynamic programming and in languages with tco and immutable data structures it works beautifully :)
Someone recently pointed out to me you can bypass the recursion limit with an inbuilt decorator, because it's basically a memoiser. 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 [0] https://docs.python.org/3/library/functools.html#functools.l...
Is that really tail recursion though ? Seems like you are making two recursive calls to fib(). I thought tail recursion requires a single final call to recursive function.
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.
The hackyness/speed issues aside: 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…
> racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer
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.
The hackyness/speed issues aside: 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…
To add onto the point about expanding stacks: What's especially nice about this feature is that it means that you don't need to tune your algorithms to be tail recursive when they could be expressed more clearly as non-tail recursion. Functions like map would actually be less efficient on average if it was tail recursive because you would need to re-iterate the list to reverse it.
The hackyness/speed issues aside: 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…
> racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer 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.
It was not by accident, but it might have something to do with the delimited continuations implemented for guile 2.2