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