From: Peter Seibel
Subject: How does Lisp know what the car of a cons is pointing at?
Date: 
Message-ID: <41gpme$mn5@kadath.zeitgeist.net>
I hope this question makes some sort of sense. It's not really about how to use Lisp but
rather how it works underneath. My understanding of cons cells is they are basically two
pointers (i.e. memory addresses). The car points to another thing (which can be any sort
of thing) and the cdr points to the next cons in the list. So when Lisp goes to what the
cons points at how does it know what it is, another cons (i.e. the beginning of another
list), a string, a number, some struct? Does the cons cell actually contain more
information than just two pointers and if so, does anyone know how it codes what the
thing is? If anyone can explain this to me it will be a big help.

Thanks,
Peter


---------------------------------------------
Peter Seibel           ······@motherjones.com
The MoJo Wire      http://www.motherjones.com
---------------------------------------------

From: Peter Seibel
Subject: Re: How does Lisp know what the car of a cons is pointing at?
Date: 
Message-ID: <41ib39$73l@kadath.zeitgeist.net>
In article <··········@kadath.zeitgeist.net> I, ······@mojones.com
wrote:
>I hope this question makes some sort of sense.

Well I guess it made _some_ sense. Thanks to everyone who responded,
It was a big help.

P.S. Sorry for the 90 char lines. I had set my preferences wrong on my
newsreader. Should be fixed now.

---------------------------------------------
Peter Seibel           ······@motherjones.com
The MoJo Wire      http://www.motherjones.com
---------------------------------------------
From: MAEDA Atusi
Subject: Re: How does Lisp know what the car of a cons is pointing at?
Date: 
Message-ID: <MAD.95Aug25181646@tanzanite.math.keio.ac.jp>
>>>>> "seibel" == Peter Seibel <······@mojones.com> writes:
In article <··········@kadath.zeitgeist.net> Peter Seibel <······@mojones.com> writes:


    seibel> I hope this question makes some sort of sense. It's not
    seibel> really about how to use Lisp but rather how it works
    seibel> underneath. My understanding of cons cells is they are
    seibel> basically two pointers (i.e. memory addresses). The car
    seibel> points to another thing (which can be any sort of thing)
    seibel> and the cdr points to the next cons in the list. So when
    seibel> Lisp goes to what the cons points at how does it know what
    seibel> it is, another cons (i.e. the beginning of another list),
    seibel> a string, a number, some struct? Does the cons cell
    seibel> actually contain more information than just two pointers
    seibel> and if so, does anyone know how it codes what the thing
    seibel> is? If anyone can explain this to me it will be a big
    seibel> help.

Lisp is a 'dynamically typed language'.  It means that type of objects
in variables cannot be known until runtime because variables are
typeless.  In Lisp, objects (or pointers to objects) have type
information that can be decoded dynamically.

There are several type encoding schemes:

(1) Encode type information in unused bits (e.g. least significant 3
    bits) of pointer word (tagged pointer scheme).
(2) Add extra header word to object and store type information there
    (object tag).
(3) Divide heap into pages of 2^N bytes each.  Fill each page with
    identically typed objects.  Use separate page table and store type
    information there (Big Bag of Pages or BIBOP scheme).  Type of an
    object can be determined by extracting page number from object
    address (logical shift right) and looking up the page table.
(4) Hybrid scheme combining two or more of the above.  For example,
    encode some frequently used types by (1) above and other
    types by (2).

More thorough description and implementation details can be found in:

 o Gudeman. Representing Type Information in Dynamically Typed Languages. 
  http://www.cs.indiana.edu/scheme-repository/doc/pubs/typeinfo.ps.gz

Cheers,
				--mad