Possibly Pythonic Tail Call Optimization (TCO/TRE)

Chris Angelico rosuav at gmail.com
Wed Jul 15 14:13:47 CEST 2015


On Wed, Jul 15, 2015 at 10:00 PM, MRAB <python at mrabarnett.plus.com> wrote:
> On 2015-07-15 12:22, Mark Lawrence wrote:
>>
>> On 15/07/2015 10:13, Gregory Ewing wrote:
>>>
>>> Chris Angelico wrote:
>>>>
>>>> I'm still interested in the explicit "replace current stack frame with
>>>> this call" operation. Calling it "goto" seems wrong, as most languages
>>>> with goto restrict it to _within_ a function,
>>>
>>>
>>> This just suggests to me is that most language designers
>>> are not very imaginative. :-)
>>>
>>> A tail call *is* a goto. That's how you implement one in
>>> assembly language -- you write a jump instruction instead
>>> of a call instruction. The jump doesn't have to be to
>>> the same function.
>>>
>>
>> IIRC the realms of the C setjmp and longjmp.  I'm just wondering out
>> aloud if anybody has ever tried playing with cPython using these, or
>> whether the code and/or Python itself is just too complex to allow this
>> to even be tried, let alone succeed.
>>
> The problem with longjmp is that it could inadvertently bypass some
> clean-up code or deallocation, or, in the case of CPython, a DECREF.

Which really says that TCO is impossible if you have any sort of
clean-up or deallocation to be done after the call begins. The only
way to truly turn your tail call into a GOTO is to do all your cleanup
first. "try: return x() finally: more_code" is not a tail call, nor is
it if you have "except:" in place of "finally:".

ChrisA


More information about the Python-list mailing list