Unrolling lists

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 cons cells, with each cons cell containing a car (the data) and a 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 dependencies (in checking for nil) and data dependencies (in fetching cdr fields).We present a data structure for “unrolled lists”, where each cell has several data items (car fields) and one link (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.

REFERENCES

• 1: William E. Aitken and John H. Reppy. Abstract value constructors. In A CM SIGPLAN Workshop on ML and its Applications, June 1992.
• 2: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 3: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Martin Wirsing, editor, Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer-Ver}ag.
• 4: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 5: Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
• 6: Daniel G. Bobrow , Douglas W. Clark, Compact Encodings of List Structure, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.266-286, Oct. 1979 [doi>10.1145/357073.357081]
• 7: Luca Cardelli, Compiling a functional language, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.208-217, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802037]
• 8: Douglas Wells Clark, List structure: measurements, algorithms, and encodings., 1976
• 9: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 10: L. P. Deutsch. A lisp machine with very compact programs. In Proc. 3rd IJA CI, pages 697-703, 1973.
• 11: Tim Freeman. Carnegie Mellon University, personal communication, 1992.
• 12: Tim Freeman , Frank Pfenning, Refinement types for ML, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.268-277, June 24-28, 1991, Toronto, Ontario, Canada
• 13: R. Greenblatt. Lisp machine progress report memo 444. TechnicMreport, A.i. Lab., M.I.T., Cambridge, MA, August 1977.
• 14: Cordelia V. Hall, Using Hindley-Milner type inference to optimise list representation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.162-172, June 27-29, 1994, Orlando, Florida, United States
• 15: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 16: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 17: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 18: Kai Li , Paul Hudak, A new list compaction method, Software—Practice & Experience, v.16 n.2, p.145-163, Feb. 1986 [doi>10.1002/spe.4380160206]
• 19: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 20: Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
• 21: Simon L. Peyton Jones , John Launchbury, Unboxed values as first class citizens in a non-strict functional language, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.636-666, June 1991, Cambridge, Massachusetts, United States
• 22: Chris Reade, Elements of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 23: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 24: P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]
• 25: D. Weinreb and D. Moon. Lisp machine manual. Technical report, Symolics Corp., Cambridge, Mass., 1981.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Compilers

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Algorithms, Experimentation, Languages, Measurement