CODEWITHSUNDEEP
recursiontail-recursion
AnotherPerson
AnotherPerson

Reputation: 141

What is the tail context of a function?

During lecture I was given the definition of a tail call as being a call expression which occurs in a tail context. I looked up the definition of tail context in The Revised Report on the Algorithmic Language Scheme:

A tail call is a procedure call that occurs in a tail context. Tail contexts are defined inductively. Note that a tail context is always determined with respect to a particular lambda expression.

I don't feel that any of this has actually clarified exactly what a tail context is, can someone give an explanation which might be more comprehensible to a beginner?

Upvotes: 3

Views: 1077

Answers (1)

rici
rici

Reputation: 241731

The tail is the very end of the animalfunction. Intuitively, an evaluation happens in a tail context if the function will do nothing more other than return the result of the evaluation to its caller.

The key observation about a tail context is that nothing in the call frame is needed (except the reference to the caller) allowing the call frame to be reused by the call performed in the tail context. Doing so can change the space requirements of some recursive algorithms from O(N) to O(1), or O(log N) in the case of algorithms like quicksort which do imperfect partitioning.

Program flow analysis can identify other possible opportunities for recycling call frames, but in many languages, tail contexts can be recognised by a simple syntactic analysis. In the case of Scheme, the procedure is specified in the language document, linked in the original post. Scheme requires that tail calls be optimized if they can be identified in this way.

In many other languages, tail call optimization is not required and in some cases is not even possible. In C++, for example, there may be implicit destructors which need to be run following the last call and before the return; also, the value returned may need to be converted to a different type. In languages in which the call frames are available for introspection (Javascript, for example), call frame recycling would modify observable program behaviour.

Upvotes: 1

Related Questions