Hyper Dictionary

English Dictionary Computer Dictionary Video Dictionary Thesaurus Dream Dictionary Medical Dictionary


Search Dictionary:  

Meaning of TAIL RECURSION MODULO CONS

 
Computing Dictionary
 
 Definition: 

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

 

 

COPYRIGHT © 2000-2013 HYPERDICTIONARY.COM HOME | ABOUT HYPERDICTIONARY