What is CDR-coding?
CDR-coding is a space-saving way to store lists in memory. It is normally only used in Lisp implementations that run on processors that are specialized for Lisp, as it is difficult to implement efficiently in software. In normal list structure, each element of the list is represented as a CONS cell, which is basically two pointers (the CAR and CDR); the CAR points to the element of the list, while the CDR points to the next CONS cell in the list or NIL. CDR-coding takes advantage of the fact that most CDR cells point to another CONS, and further that the entire list is often allocated at once (e.g. by a call to LIST). Instead of using two pointers to implement each CONS cell, the CAR cell contains a pointer and a two-bit “CDR code”. The CDR code may contain one of three values: CDR-NORMAL, CDR-NEXT, and CDR-NIL. If the code is CDR-NORMAL, this cell is the first half of an ordinary CONS cell pair, and the next cell in memory contains the CDR pointer as described above. If the CDR code i
