Re: How to implement dynamic typing?

David Belier <davidbleier@hotmail.com> wrote:
+---------------
| Recently I finished chapter 7 of the dragon book (2nd edition) but I
| still don't understand how to implement dynamic typing. I don't get
| how you are supposed to store the type information with each variable
| and check it every time using an acceptable amount of resources and
| time. Can someone please name papers or websites to read?
+---------------


One of my favorite surveys of the topic is the following classic
survey [despite its age]:


        ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz
        David Gudeman, "Representing Type Information in Dynamically Typed
        Languages", University of Arizona at Tucson, Technical Report TR 93-27
        (1993). [The .gz is ~104 KB]


        Abstract:
        This report is a discussion of various techniques for representing
        type information in dynamically typed languages, as implemented on
        general-purpose machines (and costs are discussed in terms of modern
        RISC machines). It is intended to make readily available a large body
        of knowledge that currently has to be absorbed piecemeal from the
        literature or re-invented by each language implementor. This discussion
        covers not only tagging schemes but other forms of representation
        as well, although the discussion is strictly limited to the
        representation of type information. ...


+---------------
| Note: I have a strong C++ background and know x86 assembler. I can
| imagine a way to implement it doubling memory requirements and making
| the program dead slow in the process so there must be better ways.
+---------------


I don't know about other languages, but members of the Lisp family
(Scheme, Common Lisp, etc.) often use a mixture of tagged immediate data,
"low-bit(s) tagged" pointers, and generic pointers to heap structures
with explicit type fields. These may also be combined with typed
allocation regions [q.v. BIBOP typing ("Big Bag Of Pages")].
The Gudeman survey covers all of these [IIRC].


The type information in immediate data and low-tagged pointers is
essentially "free"; explicit type fields in generic heap objects
is typically only a small fraction of the object size; and the
type descriptors for BIBOP regions are a *tiny* fraction of each
region's size. So in all of these cases the type overhead (usually)
results in far less than "doubling" the amount of allocated memory.


-Rob


-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
[The Lisp literature is certainly where I'd look to find out how people make
programs with dynamic typing run fast. -John]

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