Re: How to implement dynamic typing?

On Sun, 11 Apr 2010 11:46:24 -0000, "bartc" <bartc@freeuk.com> wrote:


>"BGB / cr88192" <cr88192@hotmail.com> wrote in message
>> "David Belier" <davidbleier@hotmail.com> wrote in message
>>
>>> 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?
>>
>> as others have said, it is not stored with the variable.
>
>Yes, quite a few people have said that.
>
>Yet, I *do* store a tag with the variable! So clearly I must be doing
>something wrong...
>
>In:
>
> A := (1, "two", 3.0)
>
>a tag is stored with the variable A (saying it is a list), but tags are also
>stored for each of the values (saying they are an integer, a string, and a
>float).
>
>(In this implementation, A is not a pointer, it is a descriptor containing,
>for this example, the list tag, the length of the list (3), and a pointer to
>the elements, each in turn being a descriptor.)


That's a way to do it ... there have been similar methods involving
capabilities rather than simple descriptors. But direct use of "heavy
pointers" has not been a popular solution for compiler writers.


At first glance it seems that having the descriptor together with the
pointer saves time, extra fetching, cache pollution, etc. for
"frequent" operations like bounds checking, object length/size
retrieval, etc. But, in fact, studies[*] of real programs have shown
that descriptor accesses occur much less frequently than simple type
checks, identity checks (comparing pointers), data accesses and object
referrals (storing an object reference). Even in OO languages, method
calls are less frequent than data accesses. YMMV, but most language
implementors have decided that it is worthwhile to trade indirect
descriptors for register-sized pointers.


[*] I don't have available links to such studies - most I've read
about in passing rather than seen directly. I know various
comparisons of pointer and descriptor representations have done for
Lisp, ML, some other FP languages and for C++. They *should be*
relatively easy to locate if you can muster the right search
incantations.




There are other ways to get typed pointers without significantly
impacting address space and without adding bits to the pointer. And
in many situations (though clearly not all), a descriptor pointer
attached to a value can be used directly as a type tag and a tag fetch
gets you the (first words of the) object as well so any further access
to the object is streamlined.




>So more accurately tags can be stored with both variables and values.


Tags can be stored anywhere and in any form that is convenient. Object
descriptors are, in the end, just a scheme for separating storage of
value and type tag.


George

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