Name the Data Structure

What is the name of CDR encoding, Lisp Machines used to store cons-lists in array form? I guess it way used to store closures as arrays, at the same time allowing them to be accessed like cons-lists (for &rest arglists).

Array

Damn bud, can you rephrase your question. I'm only just starting out with pure Javascript (fuck coffeescript).

Zipper

here is one of these cons-encodings, called hash-linking
http://reports-archive.adm.cs.cmu.edu/anon/scan/CMU-CS-76-clark.pdf

>>2

in a computer, everything is an array of bits

VIPPER

JEW

CDRs are encoded with an ``eight-to-fourteen modulation'' lookup table, to prevent extended repetition of zeros or ones from confusing the tracking laser.

At a higher level, the ISO 9660 filesystem is often used, although there is no reason you can't record a TAR archive directly.

>>9
I don't think he meant CDRs as in CD-ROMs. I think he meant CDR as in my other CD-ROM is a cudder.

Czech 'em.

>>10

But what if I play the CDR in my CAR stereo?

>>10

Yeah. I meant the linked list data structure.

In computer science CDR coding is a compressed data representation for Lisp linked lists. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines derived from the MIT 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 pointers, 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 objects, 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 of the store. This problem is typically avoided by using CDR coding only on immutable data structures.

Unrolled linked lists are simpler and often higher-performance than CDR coding (no "tagged pointers"; typically less fragmentation).[citation needed] For short lists, CDR coding uses the least amount of space.

>>12
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.

The awesome fact about this data structure is that a sequence of calls to CONS would produce an array, just like push_front in C/C++ does, but without mutating the original array. Not as flexible as monoidal trees, but a lot more efficient.