Show HN: Tacopy – Tail Call Optimization for Python
github.com
github.com
you're calling a built in function, why make obfuscate this in an "llm way"
I’m also not convinced that this actually is worth the effort, considering it’s doing runtime rewriting of Python using Python.
Historically, suggestions to make Python tail recursive were rejected on the theory that the added stack frames helped debugging, and that Python was supposed to be an imperative language. But it has been dragged into supporting some FP idioms over the years and that has seemed like a good thing.
Edit: It's actually called out under limitations "No mutual recursion: Only direct self-recursion is optimized"
Guido on tail calls 16 years ago: https://neopythonic.blogspot.com/2009/04/final-words-on-tail...
https://blog.reverberate.org/2025/02/10/tail-call-updates.ht...
[1] https://dev.to/denyspotapov/callonce-python-macro-for-unlimi...
[1] My best is around 1300 place in HackerCup.
IIRC ES6 introduced PTC (Proper Tail Calls), Chrome had an experimental flag for a while but it introduced more issues than it solved (stack traces became a mess and the stack inspection changes came with realistic security concerns). Microsoft and Firefox refused to implement it. Safari refused to un-implement it, and also refused to adopt an opt-in per function flag.
It's crazy how fast javascript has gotten. Ported a classic game earlier this year using all of the new stuff in ES5/6/onwards, the benchmarks are within a couple of percent of what the perf would be were it a standalone game. Runs with 250x monsters at 30x the original tick rate, or >1000x as many monsters at the original tick rate.
OP's approach is surprisingly straight forward, only a few hundred lines.
https://github.com/raaidrt/tacopy/blob/main/src/tacopy/trans...
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.
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.
https://github.com/raaidrt/tacopy/blob/8f5db70da2b7bbfafc41b...
Why do i need a fully fledged library for something that is basically a few lines of code?
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.
You get `(loop ... (recur ...))` or `trampoline`.
Naive recursion will consume the stack.
https://clojuredocs.org/clojure.core/loop
This problem also shows up in cases where TCO is not possible. For example, suppose we have a syntax tree for some program and need to traverse the tree. Nodes that represent lists of things might have a long list of children, and in a sufficiently large program recursing down that list can blow out the stack. Just recurse on list elements, which one can reasonably assume don't nest too deeply.
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.
Also even in procedural languages there are some problems that are easier to understand and model if you use recursion, for example tree or graph like structures.
For instance: you have a large graph and you are traversing a particular path through it — say a R/B tree seeking a node. You can write it iteratively or recursively. Neither needs to hold more than 1 node reference at a time, the choice is which you prefer to read and write.
I prefer to write that recursively. Sounds like you may not. Observing “well I can write it iteratively so why do I need TCO” is obvious and uninteresting; that’s the point.
But, for languages that don't have loop constructs and you need to rely on recursion, all you need to do is write your recipe in standard loop form, and then map back to a tail-call syntax. This is often a LOT easier than trying to think of the problem in a recursive mindset from scratch. (though occasionally, the reverse is also true.)
So the only constraint for re-implementing such looped logic onto tailcalls is that this relies on the stack, which may overflow. By providing TCO you are effectively removing that restriction, so it's a very useful thing for a language to support (especially if they don't provide low-level loops).
The title "tail call optimisation" in the package above is a bit of a misnomer, since this is more of a "transformation" than an "optimisation", but effectively the whole loop-tailcall equivalence is exactly what the package mentioned above relies on to work; it uses decorators to transform tail-call recursive functions to their equivalent loop-based formulations, and thus passing the need to create multiple stacks for the recursion (and risk stack overflow), since the translated loop will now take place in a single stack frame.
Because it's hard to imagine real "modularity" between a bunch of functions that can cyclically call each other.
so as for tail recursion examples, one nice example i had in the past which made thinking about the problem a lot easier than loops, was when I was designing a 3D maze-like game. The recuraion allowed me to draw each subsequent "step" visible on the screen without having to kniw in advance hiw many steps should be visible. you just draw the "next" room at increasing vanishing distance, until you hit a "wall" (the base case). It was a very simple, elegant result for minimal code; where the equivalent loop would have been long and horrible.
Also it wouldn't help with Fibonacci, since while it's recursive, it's not tail-recursive (yes, it can be written that way, but I'm talking about the idiomatic naive definition).