Re: Tail recursion, etc.

[ramsdell@linus.mitre.org (John D. Ramsdell)]

"Guillermo J. Rozas" <gjr@martigny.ai.mit.edu> writes:

> I don't like the term "tail expression".

I don't have an alternative at this time so I'll continue using it.

> One thing that the proposed formalizations do not seem to embody is
> that the notions of "tail call", "tail expression", "reduction",
> etc. are not absolute, but relative to some starting point.

Yes.  I agree.  This is one feature that was present in the
formalization of tail combinations I presented for the lambda calculus
using tail combination contexts that was lost when I tried to apply
that formalism to Scheme.  I close with an incomplete version of the
text that attempts to fix this problem.

Procedure calls that are also \emph{tail expressions} are \emph{tail
calls.}  An inductive definition gives the subexpressions that are the
tail expressions of a given Scheme expression E.

* If an expression of the form (lambda F E ... T) occurs in E,
  then the expression T is a tail expression of E.

* If an expression of the form (if E' T T') is a tail expression of E,
  than both T and T' are tail expressions of E.

Many missing cases...

* If an expression of the form (E' E"...) is a tail expression of E,
  than it is a tail call.

John