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
---------------------------------------------
>>>>> "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