[MLton] HOL's Moscow ML implementation, and pushing MLton to
emulate it
Daniel C. Wang
danwang@CS.Princeton.EDU
Fri, 08 Apr 2005 18:31:05 -0400
Stephen Weeks wrote:
>>>Sort of. But he imposes a *severe* restriction on what host
>>>representations are allowed, that in particular rules out many
>>>representations that MLton uses.
>>
>>Hmmm perhaps here is where the point of confusion is. I don't actually think
>>that is the case. There are restrictions on the representation of the
>>universal type, but not on the underlying native rep.
>
>
> But one must be able to coerce in constant time, so those restrictions
> on the universal type impact the underlying rep as well.
>
>
>>Can you give me an example of what exactly you mean in the context of a
>>list? What MLton opts are you thinking about?
>
>
> Sure. MLton represents a Real64.real list using 12 bytes per list
> element, while it represents an Int32.int list using 8 bytes per list
> element.
In this case the universal rep is just a pair of pointers one to the head
and one to the tail... i.e. you can build that in constant time!
[1,2,3]
Native MLton rep
| 1 | +
|
+ | 2 | +
|
+ | 3 | *
partially boxed rep
/--|hd|tl|
/ /
| 1 | + /
|/
+ | 2 | +
|
+ | 3 | *