On Sat, Aug 15, 2020 at 10:45 PM Antoon Pardon
<antoon.par...@rece.vub.ac.be> wrote:
>
> Op 7/08/20 om 18:45 schreef Chris Angelico:
> > On Sat, Aug 8, 2020 at 2:21 AM <2qdxy4rzwzuui...@potatochowder.com> wrote:
> >>
> >> On 2020-08-07 at 17:55:45 +0200,
> >> Marco Sulla <marco.sulla.pyt...@gmail.com> wrote:
> >>> @Chris: note that "real" recursion in Python is not possible, since
> >>> there's no support for tail recursion. Maybe something similar can be
> >>> done using async functions.
> >>
> >> Python has real recursion. Whether or not there's tail recursion on the
> >> inside is an implementation detail.
> >
> > More specifically: Python has real recursion. Whether or not tail
> > recursion is optimized away is an implementation detail.
> >
> > Tail call optimization (there's no reason to restrict it to recursion
> > alone) is something a Python implementation could choose to do, but
> > the trouble is that full optimization tends to destroy traceback
> > information, so it's often not worth doing.
>
> I don't understand this argument. The trace back information that is
> destroyed with this optimization, is information that isn't available
> anyway if you write the code in an iterative fashion.
Your counter-argument applies only to recursion, but TCO applies to
*any* tail call. Consider this:
@some_deco
def spam(n):
...
return spam(n // 2)
Not a recursive tail call and cannot be rewritten as a loop, unless
you know for sure that some_deco returns the original function. But
TCO can still optimize this - by collapsing the stack frames. Which
loses traceback info, unless you deliberately preserve it.
> And the cases where
> > partial optimization is of value just aren't compelling enough for
> > anyone to implement it into CPython, nor any other major
> > implementation (to my knowledge). The biggest uses for TCO tend to be
> > the situations where recursion is the wrong solution to the problem.
>
> I think writing code that is at heart a state machine would be a lot more
> easy if python would have TCO. Then each state could be implemented by
> a function and transitioning from one state to the next would be just
> calling the next function.
I'm honestly not sure how much you'd gain by writing the transitions
as additional calls. But then, I don't tend to write pure state
machines in Python. If anything, they're "state machines with
resumption" or something, and the additional wrinkles mean it's best
to maintain state in a data structure and maintain code in a function,
instead of trying to do both on the call stack.
ISTM that everyone who begs for tail recursion optimization is trying
to write loops as recursion. Maybe that's why Python has never
bothered - because it's an optimization for an inferior way to write
the same logic. Prove me wrong. Show me something where it actually
couldn't be better written iteratively, yet it still benefits from the
optimization.
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
