tail recursion modulo cons

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)