proper tail calls

Jon Zeppieri jaz at bu.edu
Mon Jan 21 12:58:46 PST 2008


On 1/21/08, 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.

f has nothing to do with it.  f2 is the closure that is constructed on
each iteration (assuming it is not optimized away in the specific
example you cited -- and I am stipulating that it is *not* optimized
away for the sake of argument).

At each iteration, the previous value of f2 is not reachable.
Therefore, it no longer consumes space.  If the ES4 spec makes no
mention of this, I'm not sure what to say.  Why would anyone want
unreachable objects to consume space (except for debugging purposes)?

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

How?  I think there may be a basic misunderstanding here.  Let's
assume the integers are heap allocated.  So, on each iteration, we
heap allocate an integer.  However, the integer that we allocated for
the previous iteration is no longer reachable.  It can be garbage
collected.  Therefore, it does not take up space.  Again, PTC does
*not* guarantee that the garbage collector will not run.


Yes, I am assuming that ES4 mandates that unreachable objects do not
consume space.  That doesn't seem like a terribly bold assumption to
me.



More information about the Es4-discuss mailing list