Re: How to implement dynamic typing?

"George Neuner" <gneuner2@comcast.net> wrote in message
> 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


>>>> I don't get
>>>> how you are supposed to store the type information with each variable


>>> as others have said, it is not stored with the variable.


>>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.


Perhaps my descriptor is different. I store:


(tag, copy-byte, (pointer,length) or value)


So simple, small objects (eg integer values) are stored directly in the
descriptor. The descriptor size was 16 bytes but I'm now trying 12 (for
x86-32).


I've been trying to move to a pointer-only format for years, but have always
had problems. One of them is the 'copy-byte' element I've shown above. I use
this to manage temporary heap objects, as I don't make use of garbage
collection.


With pointer-only, I would still either need a 64-bit value to be pushed
around (32+8 bits), or mess about with the low bits of the pointer (I
believe the bottom 4 bits are always zero), which is fiddly. Also, functions
returning simple values would need to allocate space for them, while the
descriptor method works better for this.


> 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'd considered my implementation (using 16-byte descriptors) slow, but it
generally outperforms languages such as Ruby and Python.


A different version with 12-byte descriptors was 2-3 times faster still
(about 3-10 times slower than optimised C), but it uses a method for
operator dispatching (based on the types of two operands) that is not easily
scaleable. I'm hoping to come up with a different idea for that that will
still perform well.


(The language also gives the choice of using static typing, so that fast
dynamic typing is no longer so critical.)


--
Bartc

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