tail call optimisation

last call optimisation

tail call optimization

last call optimisation

tail circuit

<communications>

A circuit which connects the serial lines of two modems together.

[Why do that?]

Last updated: 1996-10-16

tail recursion

<programming>

When the last thing a function (or procedure) does is to call itself. Such a function is called tail recursive. A function may make several recursive calls but a call is only tail-recursive if the caller returns immediately after it. E.g. 

 f n = if n < 2 then 1 else f (f (n-2) + 1)
In this example both calls to f are recursive but only the outer one is tail recursive.

Tail recursion is a useful property because it enables tail recursion optimisation.

If you aren't sick of them already, see recursion and tail recursion.

[Jargon File]

Last updated: 2006-04-16

tail recursion modulo cons

<programming, compiler>

A generalisation of tail recursion introduced by D.H.D. Warren. It applies when the last thing a function does is to apply a constructor functions (e.g. cons) to an application of a non-primitive function. This is transformed into a tail call to the function which is also passed a pointer to where its result should be written. E.g. 

 f []     = []
 f (x:xs) = 1 : f xs
is transformed into (pseudo C/Haskell): 

 f [] = []
 f l  = f' l allocate_cons

 f' []     p = { *p = nil;
 	 return *p
 	      }
 f' (x:xs) p = { cell = allocate_cons;
 	        *p = cell;
 	 cell.head = 1;
 	 return f' xs &cell.tail
 	      }
where allocate_cons returns the address of a new cons cell, *p is the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University of Edinburgh 1980].

Last updated: 1995-03-06

tail recursion optimisation

<programming>

(TRO) Discarding the calling environment (call stack frame) when the last thing a function or procedure does is to call itself. This is important when a procedure calls itself recursively many times since, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the last call terminated.

Tail recursion optimisation is a special case of last call optimisation but it allows the further optimisation that some arguments may be passed in situ, possibly in registers. It allows recursive functions to be compiled into iterative loops.

See also conversion to iteration, tail recursion modulo cons.

Last updated: 2006-04-16

tail-strict

A tail-strict function evaluates every cons cell in its (list) argument. It will therefore fail to terminate if its argument is an infinite list or if any tail of its argument fails to terminate. The archetypal tail-strict function is length. See also Head-strict, Hyper-strict.

Nearby terms:

tag name ♦ tail call optimisation ♦ tail call optimization ♦ tail circuit

Try this search on Wikipedia, Wiktionary, Google, OneLook.

Loading