proper tail calls
jaz at bu.edu
Mon Jan 21 15:31:29 PST 2008
Unfortunately, this issue has become confused, and I've helped confuse it.
First of all, I'm sure you're right that ES4 does not mandate the
reclamation of memory for unreachable objects. R6RS doesn't mandate
it either: "The reason that implementations of Scheme do not
(usually!) run out of storage is that they are permitted to reclaim
the storage occupied by an object if they can prove that the object
cannot possibly matter to any future computation." Permitted, not
On the other hand R6RS does mandate PTC, which "allows the execution
of an iterative computation in constant space..."
Note the word 'allows.' Obviously, it can't guarantee that an
arbitrary iterative computation can be performed in constant space,
since the computation may depend on allocating memory on every
iteration. The only guarantee is that the activation frame of the
tail-callee does not need to preserve the activation frame of the
caller. As you've demonstrated, a procedure may close over some
variable that's part of the caller's activation frame, requiring that
variable to be preserved, but the frame itself does not need to be
preserved. It's possible that all of the variables in the frame will
need to be preserved (if they all occur free in the inner closure),
but this doesn't mean that the call isn't a proper tail call. It just
means that the storage needs to be preserved for reasons that have
nothing to do with the call semantics.
(I can imagine an implementation that might actually use the same data
structure for an activation frame and a closure environment. Such an
implementation might heap allocate all of its activation frames and
keep a frame live -- from the GC's perspective -- if a closure needs
access to any of its bindings. Unless the spec requires
safe-for-space closure representations, this would be perfectly legal
-- though wasteful -- and would still have nothing to do with PTC.)
This brings us back to Graydon's and my original responses to your
message from early this afternoon. While the examples you gave do
allocate memory on each iteration, the allocation doesn't prevent the
calls in tail position from being proper tail calls.
Really, all of our back-and-forth since those messages has been pretty
much off topic.
More information about the Es4-discuss