Re: pointer elimination in C

Robin Popplestone <pop@dcs.gla.ac.uk> writes:
|> I would be interested to know what that language is - any serious language
|> -does- in effect provide pointers, but restricts the operations you can do
|> on them in the interests of hygene. LISP for example, provides almost
|> nothing but pointers - typically only short integers and possibly short
|> floats will not be pointers.
...


The general point above about Lisp is partially correct, but in the
interset of dispelling confusion about Lisp, I should point out that at
least in Lucid Common Lisp (and presumably any other Common Lisp) many
datatypes involve non-pointers. In such cases there is a header word,
which indicates the length of the object and whether it is composed of
pointers or raw bits. (The garbage collector examines such headers when
deciding whether and how to move objects and/or update any pointers within
them.)


Some objects have non-pointers as data:
      code objects (i.e., actual machine-executable code) [also viewed as
      data in lisp!]
      strings
      bignums (indefinitely large integers, or at least up to millions of bits)
      floats
      bit-vectors
      numeric arrays (8-bit integers, 32-bit integers, single floats, double
      floats, etc.)
      ...


Some objects include a mixture of pointers and non-pointers as data:
      symbols (e.g., a non-pointer hash code value might be included in one
      slot) procedures (a ptr at code, ptrs at data used by the code, plus
      other slots that encode information about the procedure)
      ...


Other objects have the non-pointer header followed by just pointers as
      data: structures (as defined via defstruct)
      ...


Cons cells are so special and ubiquitous that we arrange for them not to
need a header. Instead, pointers at them are typed to indicate they point
at a cons cell. (On most machines, this can be implemented with zero
direct overhead.)


A slot that nominally contains a pointer might instead encode a 30-bit
fixnum or short float, etc., which perhaps is what prompted Popplestone's
comment. (Some type bits tell the system what the intended interpretation
is.)


A brief aside about pointer hygeine:


Since executing code can be interrupted between almost any two
instructions (a few critical regions such as the start of the interrupt
handler itself are exempted) and the resulting interrupt could execute a
garbage collection that moves many objects, the system needs to be very
hygenic about knowing at all times which registers contain typed pointers
and which contain raw data. Nonetheless, it is possible to have raw
pointers at memory locations inside moveable objects by correlating those
raw pointers with typed pointers at the start of the object--the gc just
needs a little post-processing to update them to have the same relative
offset they had before the gc. So some internal routines essentially do
things like foo(ptr++), in spite of the fact that ptr could potentially
leap around in memory between successive examinations of it, if
interrupting gc's move the object it points into. (I don't remember one
way or the other if the compiler generates code of this form for
user-defined procedures.)


Another approach to allowing raw pointers into the middle of objects is to
use a conservative gc and never move an object if there is any chance live
registers might point inside it. This would have the added advantage of
not confusing C code intermixed with Lisp code if the two pass such
pointers back and forth.


In short, lisp implementors spend a lot of time thinking about ways to
handle pointers efficiently and robustly, so that users are largely freed
from doing so.
--
James McDonald
Kestrel Institute mcdonald@kestrel.edu
3260 Hillview Ave. (415) 493-6871 ext. 339
Palo Alto, CA 94304 fax: (415) 424-1807
--

Return to the comp.compilers page.
Search the comp.compilers archives again.