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