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 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?
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 list1. 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.
1 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.