Access Restriction

Author Clark, Douglas W. ♦ Green, C. Cordell
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword List structure measurement ♦ Pointer entropy ♦ List linearization ♦ Zipf's law ♦ Lisp ♦ List structure regularity ♦ Pointer compression
Abstract Static measurements of the list structure of five large Lisp programs are reported and analyzed in this paper. These measurements reveal substantial regularity, or predictability, among pointers to atoms and especially among pointers to lists. Pointers to atoms are found to obey, roughly, Zipf's law, which governs word frequencies in natural languages; pointers to lists usually point to a location physically nearby in memory. The use of such regularities in the space-efficient representation of list structure is discussed. Linearization of lists, whereby successive cdrs (or cars) are placed in consecutive memory locations whenever possible, greatly strengthens the observed regularity of list structure. It is shown that under some reasonable assumptions, the entropy or information content of a car-cdr pair in the programs measured is about 10 to 15 bits before linearization, and about 7 to 12 bits after.
Description Affiliation: Stanford Univ., Stanford, CA (Green, C. Cordell) || Carnegie-Mellon Univ., Pittsburgh, PA, and Xerox Palo Alto Research Center, Palo Alto, CA (Clark, Douglas W.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 2
Page Count 10
Starting Page 78
Ending Page 87

Open content in new tab

   Open content in new tab
Source: ACM Digital Library