proper tail calls
P T Withington
ptw at pobox.com
Mon Jan 21 10:50:59 PST 2008
I think talking about stacks and stack overflows might be muddying
this discussion. The language is a garbage-collected language and a
function context (stack frame) should be subject to garbage collection
just like any other object. A stack frame that is no longer
'reachable' (because it will be returned through) should be
collected. A clever implementation trick is to notice this at compile
time and simply reuse the frame.
The use of `goto` is darn cute, and a nice way to make that assertion
to the compiler and give a clue to the reader. It's a lot like
`delete` though. `delete` doesn't mean that the referenced object
will actually be collected, it just drops that reference. You may
intend that by deleting a reference an object will be collected, but
the language has no way for you to assert that.
You could still argue that in strict mode the compiler should complain
if a frame you `goto` out of is not going to be unreachable (and hence
collected) after all (either because you don't really have a tail
call, or because a closure or type error may capture the frame). But
by the same token, I might like the compiler to warn me if I am
allocating closures in a loop (easy to overlook).
What I wonder is, why are we obsessing about this particular garbage
collection problem? Because there is a clever implementation trick
that solves it? Do we have other requirements on implementation's of
garbage collection? Or just a general assumption that the garbage
collector has to work?
If I re-write my recursive tail-call algorithm as a loop that
allocates a state object each time around the loop (and drops the
reference to the previous state), do we require all implementations to
not run out of space because I have a 'proper' bounded resource
More information about the Es4-discuss