Subject: Re: How Lisp's Nested Notation Limits The Language's Utility
From: (Rob Warnock)
Date: Wed, 09 May 2007 04:13:44 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Pascal Costanza  <> wrote:
| Jon Harrop wrote:
| To cite from John McCarthy's "History of Lisp" from 1979 [1]:
| "The unexpected appearance of an interpreter tended to freeze the form 
| of the language, and some of the decisions made rather lightheartedly 
| for the ``Recursive functions ...'' paper later proved unfortunate. 
| These included the COND notation for conditional expressions which leads 
| to an unnecessary depth of parentheses, and the use of the number zero 
| to denote the empty list NIL and the truth value false. Besides 
| encouraging pornographic programming, giving a special interpretation to 
| the address 0 has caused difficulties in all subsequent implementations.

Note that equating of 0 with NIL is *not* necessary in current
implementations. For example, in CMUCL-19c under either FreeBSD or
Linux, the pointer representation of NIL happens to be 0x28f0000b(!):

    cmu> (kernel:get-lisp-obj-address nil)

    cmu> (format nil "0x~x" *)

    cmu> (logand ** 7)

    cmu> (list x86:list-pointer-type x86:other-pointer-type)

    (3 7)

Though, since CL requires that NIL be *both* a LIST and a SYMBOL,
there still *is* a bit of magic going on here: that 0x28f0000b
descriptor value can be interpreted as both a cons cell and a
symbol struct. The "magic" is that while the "lowtag" (low three bits)
of the NIL pointer denotes that it is a cons -- which means that if
you subtract X86:LIST-POINTER-TYPE (3) from it you get the address
of a pair of NILs [car & cdr at 0x28f00008 & 0x28f0000c, resp.] --
it is *also* true that if you subtract X86:OTHER-POINTER-TYPE (7)
from it [symbols are "other-pointers"] you get the address of the
*symbol* NIL [which has that above-mentioned pseudo-cons buried in it
in the "value" and "hash" cells of the symbol]. [And, yes, that means
that the NIL list/symbol heap object *must* be placed at a specific
location in CMUCL's virtual memory. (Some of us consider that a bug.)]

But since you need to check for NIL explicitly *anyway* pretty much
everywhere you might have a LIST or a SYMBOL, another equally-simple
method one might choose would be to simply assign some small constant
"immediate" pointer-value to NIL ["immediates" being Lisp objects for
which the entire object is specified in the bit pattern of its "pointer",
sometimes used for chars, unbound-markers, EOF, etc.]. Since x86_64
has 32-bit immediate compares, that representation would be fairly
cheap on that architecture.


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607