[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: requiring proper tail recursion

Aubrey Jaffer asked:
> Doesn't the term `asymptotic' allow an implementation to consume space
> for continuations, so long as those continuations can be collected?

Yes, in most cases.  I should have mentioned this.

I didn't want to get into this too much because the notion of how
much space is allocated for a continuation (as opposed, say, to
space allocated for closures) is inherently implementation-dependent.
For example, an implementor might plausibly claim that converting
everything to CPS before compiling it means that no space is ever
allocated for continuations, only for closures.  Nonetheless I
think the proposed language provides adequate guidance for both
users and implementors.

As I tried to show a while back, it is possible to give a more
precise definition of proper tail recursion without relying on
implementation-dependent notions such as the space occupied by
continuations, but the less precise definition in terms of
continuations may be more useful because it is more widely