It's a suboptimal implementation but it's interesting for the purpose of transpiling something like Scheme or ML or maybe Purescript to 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.
Certain function calls that were unable to be run in Python can now be run. From that perspective, my thinking was that this was a net good since one can preserve the "clean syntax" from recursion while still being able to access the performance benefits of an iterative solution.
From the description, it doesn't really seem to be full Tail Call Optimization, but only optimizes tail recursion. At least all the examples are about tail recursion, where the function calls itself in tail position, which can indeed easily be changed to a loop. Tail Call Optimization would mean it optimizes any function call in tail position. Typically you'd implement that with a trampoline, but it doesn't seem like this does that.
Edit: It's actually called out under limitations "No mutual recursion: Only direct self-recursion is optimized"
It's always amusing to see what Python has become thanks to NumPy and Django and how widely deployed it became when its intended purpose was always to be easy to understand, not performant. But just like JavaScript, people are going to hack it to death to make it fast anyway.
Cool. Recursion in python is common bottleneck in competitive programming. Will give it a try. I created a similar tool for recursion [1]. But ended with rewriting AST and emulating stack. Pros - no need for accumulator, cons - almost unusable in real world.
EcmaScript too, but most browser JS runtimes don't (didn't?) support it. It's also part of .NET CIL but only F# uses it so support for it has historically been flakey outside the CLR's main JIT mode.
Safari's JSC (and much more recently, WebAssembly) are the only ones that actually implement it. In practice I don't think it actually ends up being any better than V8, which I believe has some amount of logic to replace them with iterators or trampolines when it can.
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.
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.
Readit News
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.
Deleted Comment
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...