Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z 


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)


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017