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)
Read Also:
- Tail recursion optimisation
programming (TRO) Discarding the calling environment (call stack frame) when the last thing a function or procedure does is to call itself. This is important when a procedure calls itself recursively many times since, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the […]
- Tail rotor
noun 1. a small propeller fitted to the rear of a helicopter to counteract the torque reaction of the main rotor and thus prevent the body of the helicopter from rotating in an opposite direction
- Tails
adjective, adverb 1. (of a coin) with the reverse facing up: On the next toss, the coin came up tails. Compare heads. noun 2. tail1 (def 6). noun 1. the hindmost part of an animal, especially that forming a distinct, flexible appendage to the trunk. 2. something resembling or suggesting this in shape or position: […]
- Tailskid
noun 1. a runner under the tail of an aircraft 2. a rear-wheel skid of a motor vehicle
- Tail-skid
noun, Aeronautics. 1. a runner under the tail of an airplane.