On 21/01/2008, Graydon Hoare <[EMAIL PROTECTED]> 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
_______________________________________________
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
