proper tail calls

liorean liorean at gmail.com
Mon Jan 21 23:52:12 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.

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

On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
> You can not deduce that from ES4 specs that it does not require that f
> should be ever dropped.

Unless I'm entirely mistaken, neither ES3 nor ES4 places any
significant requirements on the implementation of memory allocation,
dead object detection or garbage collection systems used in an engine.
They leave all that up to the common sense of the engine developers.

However, once f has exited, there's no single live reference to it's
closure in that example. And it's closure is the only reference to f2.
That means that, at the discretion of the DoD and GC systems, the
memory could at any time be reclaimed. If the recursion exhibits a
space growth such that GC may be called for, then all those closures
should be collected, including the f2 from each closure and any other
heap stored values whose only reference comes from one of those
closures.

On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
> > > 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.

IIRC, at least ES3 (and probably ES4 as well... since I haven't seen
any actual spec text written for ES4, I can't say either way) makes no
statements whatsoever about the internal storage used by the engine.
ES3 doesn't even contain the word "heap", and the only uses of the
word "stack" are the following two:

~~~~
10 Execution Contexts
When control is transferred to ECMAScript executable code, control is
entering an execution context. Active execution contexts logically
form a stack. The top execution context on this logical stack is the
running execution context.
~~~~

Even when a stack is mentioned it's just a logical stack, it doesn't
say anything about the actual implementation of anything.

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

Well, I make a difference here between the live objects space and the
dead objects space. Whether there are tons of dead objects or not
makes no difference as to the space consumption of the live object
space. And the live object space in presence of proper tail calls will
grow only by the last closure unless the function explicitly makes
values externally reachable.



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


> On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
> > You can not deduce that from ES4 specs that it does not require that f
> > should be ever dropped.

On 21/01/2008, Igor Bukanov <igor at mir2.org> wrote:
> Sorry for bad English here. I wanted to say:
>
> You can not deduce that from ES4 specs. The specs does not require
> that closures created during execution of a function would ever be
> dropped.

You can't deduce that any memory needed at any time by an ES3 engine
will be recovered, either. Garbage collection is left up to the engine
implementors.
-- 
David "liorean" Andersson



More information about the Es4-discuss mailing list