tail recursion modulo cons

tail recursion modulo cons

(programming, compiler)A generalisation of tail recursionintroduced by D.H.D. Warren. It applies when the last thing afunction does is to apply a constructor functions (e.g. cons)to an application of a non-primitive function. This istransformed into a tail call to the function which is alsopassed 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, *pis the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University ofEdinburgh 1980].