tail recursion modulo cons

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

(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