MLton and polymorphic recursion through datatypes?

[Stephen Weeks]

> I don't have a recent version of MLton running, but wanted to check
> with you or one of the other MLton creators as to whether polymorphic
> recursion through datatypes is supported.  In particular does the
> following program compile, run, and produce 3?

Yes.  To be absolutely precise, I tried the following program and it prints 3.

datatype ('a, 'b) altlist = nil | cons of 'a * ('b, 'a) altlist
val x = cons (1, (cons (true, cons (2, nil))))
fun f (cons (n, (cons (_, (cons (m, _)))))) = n + m
val _ = print (concat [Int.toString (f (x)), "\n"])

> That program will not compile in CIL, nor in RML since in both cases
> the implementors decided not to support polymorphic recursion through
> datatypes.  The program compiles and produces 3 when typed in at the
> SML/NJ prompt.  I couldn't get my (very old) copy of MLton to compile
> the program, but wondered if a more recent version would. 

Must have been a bug in the old MLton.  The new one works, and the monomorphizer
(was supposed to) handled that from its first design.

> This sort of recurring through a datatype with the order of type
> parameters changed is a nuisance to implement in a monomorphizing
> language: one can design such a datatype with n-1 constructors, each
> changing the order of 2 out of n type parameters, resulting in n!
> mutually recursive datatypes after monomorphization for a particular
> set of disjoint type parameters.

MLton's monomorphiser expands the polymorphic datatypes completely lazily, only
creating a new monomorphic datatype when a constructor is used in the program at
a given type.  I don't think this can lead to this problem you mention (but I've 
thought about it < 1 minute).

> I haven't seen any program which makes use of this feature of SML.

Me neither.