This paper presents a data compaction method for list processing languages, such as various dialects of LISP. The method is a generalization of MIT cdr-coding that uses linked vectors to represent lists. The major goal is to decrease storage requirements. The method’s behavior during LISP program runs was simulated, and in this environment it achieved its goal. With a vector length of one, this technique simulates cdr-coding; with increased vector lengths, substantial improvements over cdr-coding are realized. One open question concerns the optimum vector length for maximum average compaction. Other issues relating to implementation complexity are discussed, including encoding strategies, destructive functions, and garbage collection.
This is a well-organized and clear paper which should be of interest to implementors of list processing languages. Summaries of other compaction methods make it possible for the reader with a more casual interest to understand the significance of the work. The figures are especially helpful in illustrating the methods under discussion. I would recommend this paper to anyone with an interest in implementations of list processing languages.