Storing, accessing type information at run time

I'm thinking about writing a Lisp compiler.


My reading of the Common Lisp HyperSpec implies the existence of type
information at run time, not just at compile time. This is consistent
with how I've used Lisp in the past, i.e. as a glorified interpreter.
If type information needs to be available to a running program, what's
the best way to store (or access) type information?


In thinking about this problem, I've come up with two scenarios:


  1. Store type information with each object, i.e. each object is
        prefixed with a bit-field denoting its type.


Advantages: O(1) access to type information, no need to do any kind of
accounting (registration of the object with the type system), and
simplifies garbage collection (unregistration of the object).


Disadvantages: Makes interfacing to other languages more complex
(e.g. the foreign functions interface must encode/decode Lisp objects
before passing them to external functions).


I think this is how most Lisp implementations work (e.g. EMACS,
Bigloo).


  2. Store type information outside of each object, e.g. in a hash.


Advantages: Passing data to foreign functions is simple (no
pre/post-processing).


Disadvantages: No longer O(1) to access type information, accounting
is more difficult (must remember to unregister the object upon
deallocation, etc.)


Since I know relatively little about run-time type systems, would
anyone point me to the relevant literature, or, better yet, comment on
my thoughts thus far? Appel's _Modern Compiler Implementation in X_
is no help (it barely even discusses run-time systems!), and
Queinnec's Scheme-to-C compiler in _Lisp in Small Pieces_ tags each
Scheme object (idea #1 above).


Actually, I don't know enough about what I'm trying to do to even
formulate a good question. Any references to useful literature would
be appreciated.
--
[There's been a great deal of work over the years on generating
efficient Lisp code, and the particular issue of storing type info.
The two techniques you list have been used, as well as others. One
that at least used to be popular is called BBOP for Big Bag of Pages,
in which each page of memory contains a single type of data, a table
of moderate size says what type is in each page, so you can tell the
type of a pointer by shifting it right enough bits to extract the page
number and look that up in the type table. -John]

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