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  
algorithm?



More information about the Es4-discuss mailing list