Alan Kay <Alan.Kay at disney.com> wrote:
	A scheme like this was used in BBN Lisp in the late sixties ....d 
	worked well given the propensity of most lists to run in the cdr 
	direction ....
	
BBN Lisp became Interlisp became Interlisp-D.

Let's see if I can remember how Interlisp-D worked (does Medley still work
this way, I wonder)?

Addresses were 24 bits, addressable units were 16-bit words.
Pages were 256 words (512 bytes).  Tagging was BiBoP (Big Bag of Pages;
use the page number to index an array of bytes and there's the 8-bit tag).

List cells had the form
	+--------+------------------------+
	|CDR    F|                   CAR  |
	+--------+------------------------+
         8 bits                    24 bits
Note that this is 2 words (32 bits), so that a list-cell-within-page
address must be even.  I think there were four cases:
	(CDR,F) = (0,x)		CDR is NIL
	(CDR,F) = (0,~x)	whole cell has been redirected to CAR
	(CDR,F) = (x,0)		CDR is cell 2x in this page
	(CDR,F) = (x,1)		cell 2x in this page holds pointer to CDR.
I'm not terribly sure about the first two any more.

On a machine with 4MB of physical memory, 32MB of virtual memory, and
(if you were terribly terribly lucky) 80MB of disc, this made it possible
to do an amazing amount of useful work on what was basically a 16-bit machine.

CAR and CDR were done in microcode, and were sufficiently complex that they
were done once.  Xerox Quintus Prolog, on the same hardware, used
	+--------+------------------------+
	|car tag | car word ptr           |
	|cdr tag | cdr word ptr           |
	+--------+------------------------+
for list cells (except for tag location, pretty much obvious).  Car and cdr
were so simple that they were replicated about a dozen times in various
microinstructions, and XQP ended up running list processing code about 5
times as fast as Interlisp-D (my measurements).

In short, CDR-coding and similar tricks are great for compression, but
they don't come free.

Interlisp-D:  multiple threads of control, user defined data types, a fast
straightforward window system, fully networked, 16-bit characters and
virtual keyboards, it was 1984 and I didn't know how lucky I was.