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

tail recursion

I have a different definition to propose.  Suppose we enumerate
the kinds of things that are *not* tail-recursive: evaluation
of the predicate part of an IF and evaluation of the subexpressions
of a call, for example.  Suppose also that we can agree what we mean
by the state of a program (including all observable data structures,
the remainder of the computation to be performed, etc.).

Then I define an implementation to be properly tail-recursive if,
   for every program state P,
      if continued execution eventually causes state P to recur,
         and every non-tail-recursive evaluation begun since
             the first occurrence of state P has completed
             before the second occurrence of state P
      then state P will recur indefinitely many times without
	 running out of resources

An interesting question is whether we can show the two proposed
definitions to be equivalent or otherwise related.