3 ms·
> Which is actually what TCO means: translation of recursive functions into functions that use loops, at the AST level. That's not correct. It's not TRO, TCO.
by munificent 14y ago
> Which is actually what TCO means: translation of recursive functions into functions that use loops, at the AST level.
That's not correct. It's not TRO, TCO. So as it's normally understood any call in tail position would be eliminated.
In Python today, this program:
def foo():
bar()
def bar():
baz()
def baz():
raise Exception('OH NOES')
foo()
will output:
Traceback (most recent call last):
File "raise.py", line 10, in <module>
foo()
File "raise.py", line 2, in foo
bar()
File "raise.py", line 5, in bar
baz()
File "raise.py", line 8, in baz
raise Exception('OH NOES')
Exception: OH NOES
If Python did TCO, you'd get:
Traceback (most recent call last):
File "raise.py", line 8, in baz
raise Exception('OH NOES')
Exception: OH NOES
Not wanting to lose helpful information like this is a valid cause for concern. I used to think Guido was wrong for not wanting TCO in Python but I've yet to see anyone give a clear example of what having it would let you express more easily than you can now with iterators/loops/yield etc.
TCO is a fine feature in languages where its deeply engrained and part of its natural idioms. Bolting it on twenty years later doesn't seem that helpful to me.
- kenko 14y agoOff the top of my head I can think of a doubtless unsophisticated way to recover the "stack" in this situation: namely, the same way you recover the "stack" in the factorial example, by using an accumulator hidden in the interpreter. When foo calls bar(), the interpreter passes along, when it makes the tail call, an explicit list of predecessors (in this case ["foo()"]); when bar calls baz(), the invocation of baz receives ["bar()", "foo()"], etc.
- CJefferson 14y agoThat seems to defeat the main advantage (not eating up lots of memory with deep recursion)?
- mercurial 14y agoParent wasn't suggesting to keep full stack frames, but something like (file/function name/line number) tuples, that's not the end of the world. By making it a fixed-size list, you can ensure your memory usage won't blow up.
- jcampbell1 14y agoYou are recovering the stack by creating another one.
- kenko 14y agoYeah. But you could decide how much of the stack to keep, at least. Nevertheless, I know that some smart persons (I just can't remember who!) have addressed this issue in a significantly subtler way---wish I could find the reference.
- abecedarius 14y agoSome Schemes (like MIT Scheme) do this with a circular buffer of bounded capacity. Another Scheme interpreter (a little one by Jake Donham) had a switch to turn off TCO to help debugging. Yet another approach is full omniscient debugging (being able to go backward in time).