Path: utzoo!mnetor!uunet!husc6!hao!ames!pasteur!ucbvax!PEBBLES.BBN.COM!jr
From: jr@PEBBLES.BBN.COM (John Robinson)
Newsgroups: comp.emacs
Subject: Re: alist help for an elisp beginner
Message-ID: <8803211907.AA05014@ucbvax.Berkeley.EDU>
Date: 21 Mar 88 17:51:33 GMT
References: <232@stylus.cme-durer.ARPA>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: jr@BBN.COM
Organization: The Internet
Lines: 54

Ken described trying to find definitions of cons, car and cdr.  I went
to the source (John McCarthy, "Recursive Functions of Symbolic
Expressions and Their Computation by Machine," CACM v. 3 pp. 184-195,
April 1960, as reprinted in Saul Rosen, _Programming Systems and
Languages_, McGraw-Hill, 1967).  I think his definition makes it
pretty apparent what is meant by a cons cell, and also what the origin
of car and cdr are:

  {\it car.}  Computing car [x] involves getting the _c_ontents of the
  _a_ddress part of the _r_egister x.  This is essentially
  accomplished by the single instruction CLA 0, i, where the argument
  is the index register i, and the result appears in the address part
  of the accumulator.  (We take the view that the places from which a
  function takes its arguments and into which it puts the results are
  prescribed in the definition of the function, and it is the
  responsibility of the programmer or the compiler to insert the
  required data-moving instructions to get the results of one
  calculation in postion for the next.)  ("car" stands for "_c_ontents
  of the _a_ddress part of _r_egister.")

  {\it cdr.}  cdr is handled in the same way as car, except that the
  result appears in the decrement part of the accumulator.  ("cdr"
  stands for "_c_ontents of the _d_ecrement part of _r_egister.")

  {\it cons.}  The value of cons [x; y] must be the location of a
  register that has x and y in its address part and decrement part,
  respectively.  There may not be such a register in the computer and,
  even if there were, it would be time-consuming to find it.
  Actually, what we do is to take the first available register from
  the {\it free-storage list,} put x and y in the address part and
  decrement part, respectively, and make the value of the function the
  location of the register taken.  ("cons" is an abbreviation for
  "construct.")

  It is the subroutine for cons that initiates the reclamation when
  the free-storage list is exhausted.  In the version of the system
  that is used at present cons is represented by a closed subroutine.
  In the compiled version, cons is open.  ["open" means "in-line" -
  jr]

This description sounds quaint at first, but in fact it is very
precise and, though a little circular, conveys the necessary
information.  LISP was the first language where the distinction
between use and mention (value and name) was so visible, and it made
for difficulty in getting definitions right.

LISP originally ran on the IBM 704 at the MIT AI Lab.  "Address part"
and "Decrement part" refer to the way the 704 did address and index
arithmetic.  It was a 36-bit machine, and the two parts were the
18-bit word halfs (plenty to address the whole machine!).  Love of
36-bit-ness has persisted in the LISP world to this day.

/jr
jr@bbn.com or jr@bbn.uucp