1. tail recursion modulo cons 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].
tail recursion modulo cons |
