Off 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.
Re:Not Lisp again (2009)
by abecedarius on Thursday March 14, 2013 @10:50PM
(#5378983)
Some 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).
Re:Not Lisp again (2009)
by jcampbell1 on Thursday March 14, 2013 @04:43PM
(#5377566)
You are recovering the stack by creating another one.
Yeah. 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.
Re:Not Lisp again (2009)
by CJefferson on Thursday March 14, 2013 @04:34PM
(#5377528)
That seems to defeat the main advantage (not eating up lots of memory with deep recursion)?
Parent 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.
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:
will output: If Python did TCO, you'd get: 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.