Storing, accessing type information at run time

["His Holiness the Reverend Doktor Xenophon Fenderson, the Carbon(d)ated" <xenophon at irtnog dot org>]

As I've mentioned before, I'm thinking about writing a Lisp front-end
to GCC.  Right now, I'm trying to write a parser in C for Common
Lisp[1]; later, I'll figure out the interface to the back-end and bolt
everything together.  In writing the parser, I have decided that the
compiler will need to be able to access Lisp's package/symbol system,
its conditions system, its memory manager, and its type system.

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.

[1] After more than several false starts, I've actually got the
    beginnings of Lisp's READ, all in C.  Yow.  I never realized I
    knew so little about Lisp.  This exercise is proving to be quite
    humbling.  ;)

-- 
Rev. Dr. Xenophon Fenderson, the Carbon(d)ated, KSC, DEATH, SubGenius, mhm21x16
Pope, Patron Saint of All Things Plastic fnord, and Salted Litter of r.g.s.b
"...as a robotics designer once told me, you don't really appreciate how smart
a moron is until you try to design a robot..." --Jerry Pournelle