Representations of Dynamic Type Information

I'm preparing a document that is intended to be an encyclopedic summary
of all of the different ways of encoding the type of a value in
dynamically typed languages. In order to make this list as comprehensive
as possible, I thought I'd post to some relevant groups on the net to see
if anyone has a technique I'm not aware of. Instead of asking for
techniques and having to go through all of the responses looking for new
ones, I thought I'd list the ones I know about and hope that some
implementers will be willing to go through my list looking for their own
favorite technique, and let me know if it is missing. Also, many of these
techniques are either folk-lore, or (probably re-)invented by me, so I
would appreciate knowing if anyone can give me references that have some
claim to originiality.


I don't need to know about cdr-coding or other methods to represent data,
I'm only interested in methods to encode dynamic type information.


If you can help I prefer to get replies by mail. If you post a follow-up
to this article, please notice that there are a lot of groups in the
subject line, and some replies may not be relevant for some groups (I
recommend comp.lang.misc for general discussions of representational
schemes).


Any and all help is greatly appreciated.


The LIST:


tagged-words (type information is in the machine word)
    tag fields (word is broken up into tag and data fields)
        tag field in high end (most-significant bits) of word
              use tag of all zeros for one type to avoid tagging cost
              negative ints get a tag of all ones, non-negative ints
                                                                    get a tag of all zeros
              use sign bit for one type
                  use sign-bit = 0 for one type and optimize another type by
                                                                    giving it the tag of all ones in the
                                                                    high end and tagging by negation.
        tag field in low end of word
            use two-bit tags to represent word pointers to avoid shifting
                use the tag 00 for word pointers to save the cost of tagging
            use all zeros to optimize integer arithmetic
            optimize integer arithmetic by adding/subtracting tag
                                                                    after subtraction/addition
        tag field in both ends of word
              various combinations of tricks from the other two options
    partitioning by magnitude (type is encoded in the magnitude
                                                          of the word used to represent it)
        simple range tests to identify types
        segments with statically determined types
        segments with dynamically determined types
            use BIBOP to identify types
            identify type in the segment itself
                first word of segment
                last word of segment
object-pointers (untagged pointers refering to self-identifying blocks
                                  on the heap)
    combinations of this scheme with the tagged-word scheme
descriptors (two-word data elements divided into a type word and a
                          value word)
    encoding a qualifier in a descriptor
    encoding a cons cell in a descriptor
--
David Gudeman
gudeman@cs.arizona.edu
--

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