tail call optimisation

last call optimisation

Nearby terms:

tag nametail call optimisationtail call optimizationtail circuit

Try this search on Wikipedia, OneLook, Google

tail call optimization

last call optimisation

Nearby terms:

tail call optimisationtail call optimizationtail circuittail recursion

Try this search on Wikipedia, OneLook, Google

tail circuit

<communications>

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

[Why do that?]

Last updated: 1996-10-16

Nearby terms:

tail call optimizationtail circuittail recursiontail recursion modulo cons

Try this search on Wikipedia, OneLook, Google

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

Nearby terms:

tail circuittail recursiontail recursion modulo constail recursion optimisation

Try this search on Wikipedia, OneLook, Google

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

Nearby terms:

tail recursiontail recursion modulo constail recursion optimisation

Try this search on Wikipedia, OneLook, Google

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

Nearby terms:

tail recursion modulo constail recursion optimisationtail-strict

Try this search on Wikipedia, OneLook, Google

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:

tail recursion modulo constail recursion optimisationtail-strictTALTALE

Try this search on Wikipedia, OneLook, Google


Loading