You are here: irt.org | FOLDOC | 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 xsis 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].

(1995-03-06)

Nearby terms: tail call optimization « tail circuit « tail recursion « **tail recursion modulo cons** » tail recursion optimisation » tail-strict » TAL

FOLDOC, Topics, 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, ?, ALL