proper tail calls

Igor Bukanov igor at mir2.org
Mon Jan 21 11:11:34 PST 2008


On 21/01/2008, Graydon Hoare <graydon at mozilla.com> wrote:
> Igor Bukanov wrote:
>
> > I am saying that even for calls in the tail position an implementation
> > may not eliminate the parent frame completely as it still may be
> > exposed via closures. As such the tail call optimization cannot
> > guarantee that the space complexity of the tail recursion is O(1).
>
> This is much like saying "if the function in the tail call appends a
> value to an array, it is not O(1)". We're talking about stack growth,
> not side-effects on escaped heap objects. They have indefinite lifetime
> anyways. Who's to say the storage is even freed when g() runs and nulls
> out f2?

Consider another example:

function f(a) {
   function f2 { return a * 2; }
   if (a == 0) return 0;
   goto return f(a - 1);
}

f(1 << 20);

One may expect that this would require O(1) space. But this is not the
case as the implementation may not eliminate f2. Moreover, even for a
case like:

function f(a) {
   if (a == 0) return 0;
   goto return f(a - 1);
}

f(1 << 20);

the implementation is still allowed to use heap for integers.  So even
in this example the space complexity may be O(N). Hence the questions:
how useful to specify the details of tail call optimizations without
putting restrictions on the rest of the runtime?

Regards, Igor



More information about the Es4-discuss mailing list