Tail recursion modulo cons

Tail recursion modulo cons is 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. For example,

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

---

This article was originally based on material from FOLDOC, used with permission. Update as needed.