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 {em cons} cells, with each {em cons} cell containing a {em car} (the data) and a {em 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 {em nil}) and data dependences (in fetching {em cdr} fields). We present a data structure for ``unrolled lists,'' where each cell has several data items ({em car} fields) and one link ({em 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. 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. We sketch the proof of soundness of our analysis---which is based on refinement types---and present some preliminary measurements of our technique.

This technical report has been published as

Unrolling Lists. Zhong Shao, John H. Reppy, and Andrew W. Appel, Proc. 1994 ACM Conf. on Lisp and Functional Programming, June 1994.