Do tail-recursive functions reuse a single environment in Scheme?

I'm currently taking an undergraduate course in functional programming, and we just learned about environments in Scheme. From what I understand, an environment is the context in which a function is executed, i.e., every function call creates a new environment (a child of the existing one) with additional symbol bindings for the function's body.

My question is specifically about tail-recursive functions. The Scheme specification guarantees that tail-recursive calls use O(1) space. However, I've encountered two different explanations of how this is implemented:

The current environment is replaced by the new environment at the point of the tail call (which seems more efficient).
A new environment is created for each tail call, but the old environments are garbage collected, keeping the overall space complexity at O(1).

The second explanation seems less efficient, and I'm wondering whether this is an accurate description of how tail recursion works in practice. I reviewed the R5RS specification, but I couldn't find a clear answer on this point.

Is this behavior an implementation detail? If so, how do popular Scheme implementations handle tail-recursive function calls in terms of environment management?

Solution

I don't think you can really destroy the parent environment just because you're making a tail call. It's true, the recursive call won't need to return to it, but it could be the parent of another environment, if the recursive function creates a closure before making the recursive call. This often happens in "continuation-passing style" (CPS).

Here's an example of how that might happen. Let's say we work with trees. We represent an empty tree with the empty list, and a non-empty tree with a 3-element list, containing the node's value, left child, and right child. We want a function that tells us all the nodes on the path from the root to the leftmost leaf.

(define (path-to-leftmost-leaf k t)
  (cond ((null? t) (k '()))
        (else (let ((x (car t))
                    (left (cadr t)))
                (path-to-leftmost-leaf (lambda (path) (k (cons x path)))
                                       left)))))

We accumulate a "continuation", k, that will build the result list¹. To call this function, you need to pass it a continuation to start with; (lambda (x) x) is suitable if you don't want to call some other CPS function with the resulting list. For example:

> (path-to-leftmost-leaf (lambda (x) x) '(k (l (l () ())) (r () ())))
(k l l)

If the recursive call to path-to-leftmost-leaf replaced its environment with a new one, where would the various k functions live?

The above discussion, and your question, are both in the context of "the environment model". It's called a model because it doesn't (necessarily) reflect how the compiler/interpreter actually work, but rather provides you with a way to reason about what results a given program will produce. The interpreter is free to do things in a more efficient way, provided that this way still produces the expected results. I'm not an expert, but I think that in practice modern Scheme implementations don't really use a chain of environments, so the question of destroying or replacing an environment doesn't really arise.

¹ No, writing this in CPS isn't really any more efficient than direct recursion - in fact it's less efficient. But it's a simple enough function that demonstrates CPS and how the parent environment could still be needed.