[MLton] improved overloading for SML

Vesa Karvonen vesa.karvonen@cs.helsinki.fi
Mon, 17 Oct 2005 11:40:27 +0300


Quoting Stephen Weeks <sweeks@sweeks.com>:
> This note describes an approach to overloading in SML that has the
> following properties.
> 
>   * It can be expressed in SML'97 without any special front-end
>     support (_overload declarations, overloading resolution). 
>   * Type checking ensures as much as with current SML overloading.
>   * Functions can be defined using overloaded operators and retain 
>     the ability to be used at all overloaded types.  There is no
>     "default" type for operators.
>   * Overloading can be extended in different ways in different client
>     code to support additional types.
>   * With appropriate compiler optimizations (already present in
>     MLton), there is no runtime space or time cost.  That is, all
>     overloading is resolved at compile time and there is no runtime
>     tagging or tag dispatch.

Cool!

Are you familiar with G'Caml?

  http://pauillac.inria.fr/~furuse/generics/

I have not yet read any G'Caml papers, but the G'Caml examples and this
approach for overloading in SML seem to (my eyes) have some resemblance.
It would be interesting to know how much of G'Caml can be expressed using
this approach.

> The only drawback of this approach w.r.t. the current ad-hoc approach
> is that there is no automatic constant overloading, and so constants
> require some additional syntax.  I personally don't find that very
> debilitating, since most constants are named and not sprinkled
> throughout code.

Yes, it should not be a significant hindrance.

> signature NUM =
>    sig
[snip]
>    end

While compiling the Test functor I noticed that the Num signature omits:

      val toString: 'a t -> string

> [...] An
> alternative is to disable the pass in MLton that eliminates unused
> type variables, by compiling with "-drop-pass xmlSimplifyTypes".  I
> chose to include the 'a and the bogus zero values so that the program
> will compile efficiently out of the box.

Hmm... Would it possible to do a separate pass before xmlSimplifyTypes to
detect this sort of thing and introduce the unnecessary uses of the type
variables or otherwise tell xmlSimplifyTypes not to eliminate some type
variables? (I have no idea of how to that. I'm just thinking out loud.)

[...]
> Once the RealI variant is eliminated, tI becomes:
> 
>   datatype tI = IntI of int * int
> 
> MLton's useless component analysis will then eliminate the first int,
> which is always zero, leaving it free to represent tI as a raw int.
> 
> Whew.

Indeed!

> [...] I took a look at the ILs for a simple program and it
> seems to bear my analysis out.

Would it be possible to give MLton an interface (an extension) that would
allow you to query information related to optimizations? Instead of manually
checking the ILs one would just, for example, ask MLton whether a certain
piece of code is present in the final output or whether a certain function
was instantiated with a certain type.

>From a pragmatic point-of-view, this is one of the things that I think is
more straightforward with macros and "generative programming". You can
construct your code in such a way that redundant code never reaches the
backend of the compiler. When you use combinator libraries, you can
(almost) never (easily) be sure that the compiler is doing what you think
it should be doing.

An interface to easily query the information from the compiler might prove
valuable. You could use the compiler to prove that certain optimizations
can be made to a (particular) program (and that the compiler actually performs
those optimizations). It could even be useful in other contexts (not just for
verifying reasoning about optimizations).

-Vesa Karvonen