[MLton-user] Questions on MLton

[shivers@cc.gatech.edu]

   BTW, you are probably gonna pay a lot for destructive lists in SML
   with MLton, since the ref cell costs an extra two words.  We don't
   have an optimization to flatten ref cells into their containing
   structures, although we would love to see one.

Ah, well. Let us suppose we have something like

    datatype 'a mlist = Mnil | Mpair of ('a * 'a mlist ref)

SML/NJ will arrange things so that the Mpair constructor does no allocation --
an Mpair value is just represented as the pair, and an Mnil value is
represented as a constant with a non-address low type tag. Will Mlton do this
much?

(BTW, caml allows mutable fields in records... but the Mpair constructor
boxes things, so you *still* have to put up with a double indirection!
Bah.)

My destructive-list sorting algo will take a list and sort it. While
running, 
  - it will require a stack of O(lg n) depth.
  - it will run in O(n lg n) worst-case and O(n) best-case time.
  - it will allocate nothing -- zero cons cells.
The list becomes sorted simply by wandering around it and redirecting
the links. These SET-CDR!'s are the only side effects performed.

   True.  But the C codegen may not be as bad as you would think.  We've
   put some work into generating C code so that gcc will optimize well.
   Interestingly enough, our experiments on X86 have shown that the C
   codegen and the native codegen aren't that far apart.  The C codegen
   produces executables that almost always run within a factor of 2 of
   the native one, and often within 1.5.

I will give it a try.
    -Olin