proper tail calls

Igor Bukanov igor at mir2.org
Mon Jan 21 10:15:19 PST 2008


On 21/01/2008, Peter Michaux <petermichaux at gmail.com> wrote:
> On Jan 20, 2008 8:01 PM, Brendan Eich <brendan at mozilla.org> wrote:
...
> > Proper tails calls are not an optimization; they certainly do change
> > semantics, insofar as you can't write certain programs without them
> > being guaranteed.
>
> I've been trying to find out how they are not an optimization.

I second that. Consider the following case:

let f2;

function f(a)
{
    f2 = function() { return a; }
    goto return g();
}

function g() {f2 = null; ... }

Here in f "return g()" is in tail position yet the frame of f can not
be eliminated completely since it is referenced through a global
variable. On the other hand a smart implementation may figure out
that, given the structure of g, there is no leak of the frame and it
can be eliminated completely.

So in reality due to this closure leakage there is no guarantees about
the space complexity unless one restricts the code that can present in
a function with a tail call. As such a tail call can be treated only
as an optimization hint as in general it is not possible to ensure
O(1) in space behavior for calls in the tail positions.

Regards, Igor



More information about the Es4-discuss mailing list