[MLton] Slightly more flexible _overload mechanism

[Matthew Fluet]

On Sat, 15 Dec 2007, Vesa Karvonen wrote:
> As some of you already know, MLton has a simple (non-standard) mechanism
> for introducing overloads.  I guess it has been designed for implementing
> the very simple overloads
> mandated by the Basis library spec (and the Definition).

Right; it is a very minimal mechanism that serves a very specific purpose.

> I don't fully understand the reasons behind the priority and haven't
> examined the issue carefully.  From what I saw while quickly browsing the
> code, it would seem that the priority is used as a priority for insertion
> into a kind of work queue (sequence that will be sorted later) for
> overload resolution.  Two overloads with different priority, unless they
> are otherwise forced to be resolved earlier, will be resolved in order
> that depends on the priority (one always before the other).  I briefly
> looked at the Basis library book and the Definition and saw no mention of
> such overload resolution priority.  AFAICT, it should mostly have an
> effect when the resolution of several overloads depend on each other.

The priority was introduced to support proper overload resolution of 
functions/expressions like:

   fun f x y z = (x + y) / z

We need to resolve the / overload to the type 'real * real -> real', 
because there is no / overload at the type 'int * int -> real', which is 
what would be required if we resolved the + overload first to the type 
'int * int -> int'.

It turns out that a simple priority mechanism suffices for the overloads 
proscribed by the Basis Library, since there aren't that many and there 
aren't complicated overload classes.  I'm doubtful that a simple priority 
mechanism would suffice if there are arbitrary additions to the set of 
overloaded functions and the (induced) overload classes.

> Now, while MLton's current overload mechanism is expressive enough for
> implementing the overloads mandated by the Basis library spec, it has a
> couple of limitations that make it somewhat cumbersome for more general
> use.

True, though, the overload mechanism has always been an implementation 
detail and never a documented feature.

> One limitation of the current mechanism is that an overload must be
> defined all at once.  IOW, while one can completely (re)define an
> overload, there is no way to extend an existing overload.
...
> To solve this problem, I
> changed the mechanism to allow the identifiers in the overload definition
> to include other overloaded identifiers as well as ordinary variables:
>
> _overload priority id : type as longid (and longid)*

That seems reasonable enough.  Though, as I mentioned above, I'm not sure 
how well the priority mechanism would scale to such ad hoc extensions.

> Another limitation with the current mechanism is that it only works for
> monotypes.  Consider, for example, defining an overloaded sub for
> accessing arbitrary sequences:
>
> _overload 2 sub : 'a * int -> 'b
> as        List.nth
> and      Array.sub
> and     Vector.sub
> and  CharArray.sub
> and CharVector.sub
>
> Also note the silly type, 'a * int -> 'b, given for the overload.

In the Haskell type class terminology, one really wants functional 
dependencies to (uniquely) relate the output element type of sub to the 
input sequence type.

Though, in the limited MLton overload mechanism, I don't see that there is 
anything inherently wrong with the type.  As you noted above, MLton will 
just look for an overload that unifies in the context; if all of the 
overloads are monotypes, then that will pin down all the type variables in 
the _overload declaration.

> At any rate,
> it turns out that MLton currently does not check (at all) whether the
> alternatives of an overload can actually be unified with the given type.
...
> I changed this by adding a check to the implementation that
> tries to unify each variant with the given type

That seems like a good check.

> In addition, I made the typing of overloads more flexible allowing
> polymorphic types for overload variants, so now the previous overload for
> sub also works. I'm not entirely sure whether my implementation is fully
> correct with respect to the rest of MLton's type checking infrastructure,
> but it seems to work (type checks and generates correct code) for the
> simple tests I've tried.

Given the way in which the overload mechanism works, I don't see that 
there would be any problems; but, I'm not an expert on the 
type-inference/check implementation.

> I think that MLton's current mechanism should at least be changed to check
> that the overload variants/alternatives match the type specified for the
> overload.  I also don't see major harm in integrating the rest of my
> improvements (with fixes if necessary).

I don't see any harm (or necessary fixes).  I'm impressed that the patch 
is so small.  But, it remains an ad hoc mechanism.  And, it certainly 
won't be as extensible as OO overloading or Haskell type classes, so I 
don't think you'll win any c.l.f. discussions with it.

> In particular, the possibility of
> extending overloads later could be useful in the Basis library
> implementation.

We actually went back the other way at one point, ensuring that no 
overloading was used in the Basis Library implementaiton:
    http://mlton.org/cgi-bin/viewsvn.cgi?rev=2476&view=rev

> Also, the additional complexity of allowing polymorphic
> types in overloads is relatively small, IMO, but it is neither required
> nor useful in the Basis library implementation.