|How to implement dynamic typing? email@example.com (David Belier) (2010-04-02)|
|Re: How to implement dynamic typing? firstname.lastname@example.org (glen herrmannsfeldt) (2010-04-06)|
|Re: How to implement dynamic typing? email@example.com (andy johnson) (2010-04-06)|
|Re: How to implement dynamic typing? firstname.lastname@example.org (2010-04-06)|
|Re: How to implement dynamic typing? email@example.com (bartc) (2010-04-06)|
|Re: How to implement dynamic typing? firstname.lastname@example.org (Paul Biggar) (2010-04-06)|
|Re: How to implement dynamic typing? email@example.com (Ian Lance Taylor) (2010-04-06)|
|Re: How to implement dynamic typing? firstname.lastname@example.org (Barry Kelly) (2010-04-07)|
|Re: How to implement dynamic typing? email@example.com (2010-04-07)|
|Re: How to implement dynamic typing? firstname.lastname@example.org (Ctalk Project) (2010-04-07)|
|[21 later articles]|
|From:||email@example.com (Rob Warnock)|
|Date:||Tue, 06 Apr 2010 04:21:12 -0500|
|Organization:||Rob Warnock, Consulting Systems Architect|
|Posted-Date:||07 Apr 2010 01:44:40 EDT|
|Originator:||firstname.lastname@example.org (Rob Warnock)|
David Belier <email@example.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]:
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]
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 Warnock <firstname.lastname@example.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
Search the comp.compilers archives again.