[MLton] improved overloading for SML

skaller skaller@users.sourceforge.net
Mon, 17 Oct 2005 11:36:26 +1000


On Sun, 2005-10-16 at 15:56 -0700, Stephen Weeks wrote:

> signature NUM =
>    sig
>       type 'a t (* 'a is int or real *)

Hehe .. in Felix, I did this the other way! Felix always had
overloading. The problem was that it supports all the C integer
types discretely with separate overloads .. and there are WAY too many.
This included signed and unsigned char .. long long, plus the C99 exact
integers [u]int<n>_t, ptrdiff_t and size_t. So originally, I generated
a subset of the C overloads like:

>       val + : 'a t * 'a t -> 'a t
>       val - : 'a t * 'a t -> 'a t
>       val * : 'a t * 'a t -> 'a t

using a Python script. But this is nasty in that you have to cast
operands to the same type: it makes sense for addition, but not
multiplication, shift, or exponentiation (for example).

OTOH you could write:

 fun add[t]: t * t -> t = "$1+$2";

and make addition polymorphic.. allowing you to add arbitrary types,
which is of course wrong. So I added type constraints:

type integer = typesetof (short, int, long);
fun add[t:integer]: t * t -> t = "$1+$2";

and you can even do this:

typedef fun max(t1:TYPE, t2:TYPE) = 
  typematch t1,t2 with
  | short,short => short
  | int,short => int
  | short,int => int
  | long,_ => long
  | _,long => long
  endmatch
;

fun add[t1:integer,t2:integer]: t1 * t2 -> max (t1,t2) = "$1+$2";

[The type system is a typed lambda calculus with extensions
including matching as a destructor, TYPE is the type of a type.
The reduction rule for typematch is interesting .. :]

>  Furthermore, the signature constraint ensures that
> clients maintain this invariant.

      type 'a t (* 'a is int or real *)

I see a comment, not a constraint?

> MLton convinces itself that RealI is useless by observing that the
> only uses of RealI as a constructor are on the right-hand side of
> cases that require a RealI value.  For example, look at the definition
> of +I
> 
>   val +I = fn (IntI (z, i1), IntI (_, i2)) => IntI (z, Int.+ (i, j))
>             | (RealI (z, r1), RealI (_, r2)) => RealI (z, Real.+ (x, y))
>             | _ => bug ()
> 
> Useless-variant elimination is smart enough to understand the
> circularity, and, since there is no "base case" that creates a RealI
> value, is smart enough to eliminate RealI entirely.

That's quite clever :)

Apart from the use here, what was the original purpose of
useless variant elimination? I see an advantage in reducing
a sum to one variant (eliminates the tag entirely). Any other?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net