[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 | *