Can someone give some real world examples for TCO? Every time I see this I only see fibonacci and gcd and I really want to encounter this one in the wild on something real and applicable
Once upon a time I tried to write such a decorator too in python 2.x and the byteplay bytecode disassembler library. I was trying to do the conversion at the bytecode level instead of transforming the AST. I believe I got as far as detecting simple self recursive functions, but never actually managed to implement the actual transformation.
Really impressive! For anyone who's not a pythonista, trying to implement TCO is something akin to solving the Collatz conjecture but for Python. It's often just an exercise in madness. So seeing an elegant solution to this is really cool, I myself was a victim of this madness and was unable to do it so very cool to see someone nail it! This will be a goto tool for sure.
Really cool project, fairly succinct and to the point :)
I would love to see support for arbitrarily nested functions, as it is common to wrap these into a public API function without the iteration parameters.
> Nested function definitions with @tacopy decorators are not supported. Functions decorated with @tacopy must be defined at module level. This constraint exists because inspect.getsource() on nested functions returns the source of the entire enclosing function, making it impossible to reliably extract and transform just the nested function's code. The decorator detects nested functions by checking for '<locals>' in the function's __qualname__ attribute and raises a clear error message instructing users to extract the function to module level.
> This eliminates the risk of stack overflow errors
When you get stack overflows anywhere from a thousand down to fifty(!) frames in the stack it's not a risk, it's an inevitability in anything more complex than a programming tutorial.
Yeah, I've been bitten by this in production. Writing the functionality in a clean iterative style was just too much of a hassle.
Nor can you count on Common Lisp to have TCO. People who are new to CL and treat it like Scheme run into this constantly. Basically never recur down a list, since the list could be long.
> Tacopy is a Python library that provides a decorator to optimize tail-recursive functions by transforming them into iterative loops.
Can this handle mutually recursive calls ? Because those are mostly the only place I use tail calls, rest I translate to iterative loops, list comprehension, maps and reduces.
Fun fact: In Scheme, TCO is required by the spec
Can someone give some real world examples for TCO? Every time I see this I only see fibonacci and gcd and I really want to encounter this one in the wild on something real and applicable
Once upon a time I tried to write such a decorator too in python 2.x and the byteplay bytecode disassembler library. I was trying to do the conversion at the bytecode level instead of transforming the AST. I believe I got as far as detecting simple self recursive functions, but never actually managed to implement the actual transformation.
That is an ambitious idea, and I applaud anyone who attempts such heights even if it turned out to be impractical.
OP's approach is surprisingly straight forward, only a few hundred lines.
https://github.com/raaidrt/tacopy/blob/main/src/tacopy/trans...
Really impressive! For anyone who's not a pythonista, trying to implement TCO is something akin to solving the Collatz conjecture but for Python. It's often just an exercise in madness. So seeing an elegant solution to this is really cool, I myself was a victim of this madness and was unable to do it so very cool to see someone nail it! This will be a goto tool for sure.
Taco Py. No Ta Copy. Took my brain a minute or so …
Really cool project, fairly succinct and to the point :)
I would love to see support for arbitrarily nested functions, as it is common to wrap these into a public API function without the iteration parameters.
Yes, it is quite surprised they're not allowed. I wonder what's the likely limitation, any ideas?
Found out
> Nested function definitions with @tacopy decorators are not supported. Functions decorated with @tacopy must be defined at module level. This constraint exists because inspect.getsource() on nested functions returns the source of the entire enclosing function, making it impossible to reliably extract and transform just the nested function's code. The decorator detects nested functions by checking for '<locals>' in the function's __qualname__ attribute and raises a clear error message instructing users to extract the function to module level.
https://github.com/raaidrt/tacopy/blob/8f5db70da2b7bbfafc41b...
> This eliminates the risk of stack overflow errors
When you get stack overflows anywhere from a thousand down to fifty(!) frames in the stack it's not a risk, it's an inevitability in anything more complex than a programming tutorial.
Yeah, I've been bitten by this in production. Writing the functionality in a clean iterative style was just too much of a hassle.
TCO can be implemented easily in non TC optimized langauges with a trampoline wrapper.
Why do i need a fully fledged library for something that is basically a few lines of code?
There's quite a bit of overhead.
I believe Clojure does it with trampoline as JVM does not (as far as I know) does not support tail call optimization. Ironic, given Guy Steele.
Yes, Clojure doesn't have TCO either.
You get `(loop ... (recur ...))` or `trampoline`.
Naive recursion will consume the stack.
https://clojuredocs.org/clojure.core/loop
https://clojuredocs.org/clojure.core/recur
https://clojuredocs.org/clojure.core/trampoline
Nor can you count on Common Lisp to have TCO. People who are new to CL and treat it like Scheme run into this constantly. Basically never recur down a list, since the list could be long.
> Tacopy is a Python library that provides a decorator to optimize tail-recursive functions by transforming them into iterative loops.
Can this handle mutually recursive calls ? Because those are mostly the only place I use tail calls, rest I translate to iterative loops, list comprehension, maps and reduces.
> Limitations […] No mutual recursion: Only direct self-recursion is optimized