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:
tag name « tail circuit « tail recursion « tail
recursion modulo cons » tail recursion
optimisation » tail-strict » TAL
|
