proper tail calls

Igor Bukanov igor at mir2.org
Mon Jan 21 12:37:00 PST 2008


On 21/01/2008, Jon Zeppieri <jaz at bu.edu> wrote:
> 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.

You can not deduce that from ES4 specs that it does not require that f
should be ever dropped.

> > 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.

Even with the tail call optimization implemented, the space complexity
of f(N) with f from the above example can be O(N) if the
implementation uses heap to allocate integers.

> > 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.

I was not able to construct a single useful example where one can
reason about the space complexity of the tail calls given that ES4
does not specify the space complexity of other aspects of the runtime.
For this reason  goto return looks very strange in ES4. It allows to
assert a very specific space complexity property yet it is not
possible to assert that, say a - 1 should not use heap allocation.

Regards, Igor



More information about the Es4-discuss mailing list