proper tail calls

Lars T Hansen lth at acm.org
Tue Jan 22 12:14:48 PST 2008


One issue with requiring the explicit syntax is that the requirement
isn't worth anything as a restriction.  The compiler will have to
figure out whether a phrase could be a tail call to find out if the
ditto phrase using explicit syntax is a legal tail call.  It is but a
short step from that to optimizing the call even if the explicit
syntax is not used; in fact, the implementer would almost be
delinquent in not doing so.  Ergo some implementations will have this
improvement; users will start depending on it; other implementations
will follow; and the explicit syntax is useful *only* as an assert
that the tail call can in fact take place, and will be useful only to
people who know about it and value it.  Like type annotations, I
guess.

Maciej asked:

> Here is another thing I don't understand: if goto must flag runtime
> errors in cases where otherwise implicit type conversion would occur,
> then does that not itself break proper tail recursion (something has
> to hang around to do the typecheck on the actually returned type)? Or
> is the intent that it throws a runtime error before the call if it
> can't statically prove that return types match? Does that mean you can
> never goto an untyped function from one with a declared return type?

IMO it would have to check before the call, and throw then.  Also IMO,
this is another nail in the coffin for requiring explicit syntax,
because it would mean that people don't get the benefit of tail calls
unless they ask for them, and then they have to be really sure that
they will always work.  This straightjacket is probably unacceptable
to most.

IMO, the best design is that (a) a call that is syntatically in tail
position is executed as a tail call when that is possible, but as a
non-tail call when type conversions or type checking interferes, and
that this happens without the programmer having to think about it, and
(b) an annotation ("goto", whatever) can be used to check that the
tail call is in fact possible, and it will cause an error (at compile
time in strict mode, possible) if that is not possible.  Thus we have
tail call annotations like we have type annotations; people use them
if they feel that provides benefit.  For everyone else it "just works
except when it doesn't" -- again, exactly like typing.

--lars



More information about the Es4-discuss mailing list