By Letter: Non-alphabet | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
  Email this page to a friend

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.


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].

< Previous Terms Terms Containing tail recursion modulo cons Next Terms >
tagged queueing
tagged types
tag name
tail circuit
tail recursion
tail recursion optimisation
University of Edinburgh
tail recursion optimisation

Web Standards & Support:

Link to and support Powered by LoadedWeb Web Hosting
Valid XHTML 1.0!Valid CSS! FireFox Extensions