[MLton] HOL's Moscow ML implementation, and pushing MLton to emulate it

[Daniel C. Wang]

I forgot an extra level of indirection...  here is some example code.
Assume that listF is always a fully boxed rep.
(i.e)' it's always a null pointer or a pointer to a pair of pointers.

Notice that wrapIntList and wrapRealList are constant time operations.
Shao's approach makes polymorphic/intrerpter code pay a penalty. There is no 
polymorphic penalty for monomorphic/host code.

structure List =
   struct
     datatype ('a,'b) listF =
       Nil
     | Cons of ('a * 'b)

     fun length wrap Nil =  0
       | length wrap (Cons(_,b)) = 1 + length wrap (wrap b)

     fun wrapIntList [] = Nil
       | wrapIntList (x::xs) = Cons(x,xs)

     fun wrapRealList [] = Nil
       | wrapRealList (x::xs) = Cons(x,xs)

     val v1 = length wrapIntList (wrapIntList [1,2,3,4])
     val v2 = length wrapRealList (wrapIntList [1.0,2.0,3.0,4.0])
   end

Stephen Weeks wrote:
>>>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!
> 
> 
> That is the universal representation of "real * real list", not "real
> list".  It's the recursive type that causes problems.
> 
> _______________________________________________
> MLton mailing list
> MLton@mlton.org
> http://mlton.org/mailman/listinfo/mlton