tail recursion modulo cons from FOLDOC

tail recursion modulo cons

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 recursion ♦ tail recursion modulo cons ♦ tail recursion optimisation

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