Editing CDR coding

{{multiple issues|
{{Cleanup rewrite|date=April 2021}}
{{No footnotes|date=October 2011}}
}}
In [[computer science]] '''CDR coding''' is a [[data compression|compressed]] [[data (computing)|data representation]] for [[Lisp programming language|Lisp]] [[linked list]]s. It was developed and patented by the [[MIT Artificial Intelligence Laboratory]], and implemented in [[computer]] hardware in a number of [[Lisp machine]]s derived from the MIT [[CADR (computing system)|CADR]].

CDR coding is in fact a fairly general idea; whenever a data object ''A'' ends in a [[reference]] to another data structure ''B'', we can instead place the structure ''B'' itself there, overlapping and running off the end of ''A''. By doing this we free the space required by the reference, which can add up if done many times, and also improve [[locality of reference]], enhancing performance on modern machines. The transformation is especially effective for the [[cons]]-based lists it was created for; we free about half of the space for each node we perform this transformation on.

It is not always possible to perform this substitution, because there might not be a large enough chunk of free space beyond the end of A. Thus, some objects will end in a real reference, and some with the referenced object, and the machine must be able to tell by reading the final cell which one it is. This can be accomplished with some inefficiency in software by the use of [[tagged pointer]]s, which allow a pointer in a final position to be specifically tagged as such, but is best done in hardware.

In the presence of [[mutable object]]s, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause [[fragmentation (computer)|fragmentation]] of the store. This problem is typically avoided by using CDR coding only on [[immutable object|immutable]] data structures.

==External links==
* {{cite web | editor1 = Mark Kantrowitz | editor2 = Barry Margolin | url = http://www.faqs.org/faqs/lisp-faq/part2/section-9.html | work = FAQ: Lisp Frequently Asked Questions | title = (2-9) What is CDR-coding? | publisher = Advameg, Inc. | access-date = 2011-10-09 }}
* L. Peter Deutsch: A LISP Machine with Very Compact Programs. IJCAI 1973, Pages 697 - 703
* Greenblatt, R., LISP Machine Progress Report, memo 444, A.I.Lab., M.I.T., Cambridge, Mass., Aug. 1977.
* L. Peter Deutsch: Experience with a microprogrammed Interlisp system. MICRO 11: Proceedings of the 11th annual workshop on Microprogramming, November 1978, Pages 128–129
* {{cite book | first = John | last = Allen | title = The Anatomy of Lisp | publisher = McGraw-Hill | date = 1978 }} Pages 399-401

[[Category:Lisp (programming language)]]
[[Category:Data compression]]


{{compu-prog-stub}}