@InProceedings{shao94:_unrol_lists,
  author =	 {Zhong Shao and John H. Reppy and Andrew W. Appel},
  title =	 {Unrolling Lists},
  booktitle =	 {Proc. 1994 ACM Conf. on Lisp and Functional
                  Programming},
  pages =	 {185-195},
  year =	 1994,
  address =	 {Orlando, FL},
  month =	 {Jun},
  abstract =	 {Lists are ubiquitous in functional programs, thus
                  supporting lists efficiently is a major concern to
                  compiler writers for functional languages. Lists are
                  normally represented as linked \emph{cons} cells,
                  with each \emph{cons} cell containing a \emph{car}
                  (the data) and a \emph{cdr} (the link); this is
                  inefficient in the use of space, because 50\% of the
                  storage is used for links. Loops and recursions on
                  lists are slow on modern machines because of the
                  long chains of control dependences (in checking for
                  \emph{nil}) and data dependences (in fetching
                  \emph{cdr} fields). \par We present a data structure
                  for ``unrolled lists,'' where each cell has several
                  data items (\emph{car} fields) and one link
                  (\emph{cdr}). This reduces the memory used for
                  links, and it significantly shortens the length of
                  control-dependence and data-dependence chains in
                  operations on lists. \par We further present an
                  efficient compile-time analysis that transforms
                  programs written for ``ordinary'' lists into programs
                  on unrolled lists. The use of our new representation
                  requires no change to existing programs. \par We
                  sketch the proof of soundness of our
                  analysis---which is based on \emph{refinement
                  types}---and present some preliminary measurements
                  of our technique. \par }
}