proper tail calls
Jon Zeppieri
jaz at bu.edu
Mon Jan 21 12:05:07 PST 2008
On 1/21/08, Igor Bukanov <igor at mir2.org> wrote:
>
> 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.
But the above example *does* only require O(1) space. On each call to
f, a new closure is constructed, but it's dropped on the floor as soon
as the next iteration occurs. PTC makes no guarantees about when
garbage collection will or will not occur.
> 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).
What is N here? Surely, it's has nothing to do with the number of
calls to f. This example has nothing do to with PTC.
> Hence the questions:
> how useful to specify the details of tail call optimizations without
> putting restrictions on the rest of the runtime?
In my experience, very.
-Jon
>
> Regards, Igor
>
More information about the Es4-discuss
mailing list