Type of multi methods in a static object-functional language

Question

I'm currently working on expanding the capabilities of my pet programming language project's type system, and have come across an interesting area where my research into other language's type systems hasn't taken me before.

As background, my language is an object-functional language with static types and partial type inference. The language will (but doesn't yet) support both of these features:

• functions whose behaviour depend on the runtime type of all of their arguments (ie multi-methods)
• union types, i.e. a value may have one of many types, all of which are transparently tracked at runtime (similar to a sum type but without needing explicit construction or declaration of which types can be used).

Given this combination, the type of a function is interesting. For example, if I have a value defined thus:

v : union (int, string) = randomInt & 1 == 0 ? 1 : "hello"

I can then apply this to any function that accepts either int or string for its first argument. This could mean a function that accepts a union type:

fn1 (p : union (int, string)) { p + 1; }

But it could also be a multi-method that is defined to accept either type:

fn2 (p : int) { "Integer: " + p; },
    (p : string) { p.length }

While I could describe the types of these functions by using a union of their parameters and result, i.e. (using an appropriately extended Haskell-like notation):

fn1 :: union (int, string) -> union (int, string)

(and the same type for fn2) this loses information, i.e. the fact that fn1 maintains the type of its argument while fn2 swaps between the two types.

Has anyone seen a language that tracks function types in this way? If so, what kind of notation does it use for the combination of different argument and result types and their interactions? Is there a name for the kind of function type we're talking about? And is it worth doing, or should I just allow the information to be lost?

Another interesting thought: the function fn2 can be seen as a combination of two functions, one of type int-> string and the other string-> int. My first thought was that the function's type is a union of these, but that's obviously wrong - my current thinking is that it's actually a dual of the union type, analogous to the way a product type relates to a sum type. Any other thoughts on this? Am I on the right track? Is there a standard name for such a type?

Answer 1

Some food for thought. Overloads are traditionally done at compile time. You're talking about doing runtime differentiation of overloads, or in other words, introducing a runtime dispatch to the selection of the overload.

There are several things of interest. First, most languages with static type systems that do runtime dispatch (e.g. for virtual or interface methods) have some way to ensure that the dispatch won't result in a method-not-found error. For example, in C# we declare that a class implements an interface, and then the class must provide an implementation for each of the methods of the interface or else it is a compile time error.

What I'm getting at is the mechanism by which your f2 is related to the union type. It isn't declared as satisfying the union but rather merely supporting the individual members. One question would be: if f2 declared only the int->string version, where and when would an error for the usage/invocation f2 ( union );. I could see that at compile-time you can issue an error at the point of the invocation of f2 citing that it doesn't provide sufficient methods to cover the union. (Another option would be to have f2 declare its intent to cover the union, then you could issue a compile time error at the definition of f2 rather than at such use off2.)

Another point to make is that the invocation of with a union expression, f2 ( union ), is in some sense cracking open the union in order to do the dispatch. Nominal vs. structural typing comes to mind here, though perhaps that is not totally the correct concept. It is almost as if there is a member selection of the value, as in something like f2 ( union.value );, or f2 ( valueOf ( union );. (Your language must have some way of obtaining (one of) the value(s) of the union.) This in contrast to some f2 that actually accepts the full union type, which is to say that perhaps cracking open of the union is only done when no f2 of the actual union type is available?

Note that an abstract base classes with two subclasses reflects the notion of (tagged) unions. A method (1) can accept the base class as a parameter, which is potentially either subclass. Two other methods could each accept specific subclasses. And method (1)'s implementation might choose between the other two methods based on the true type of the subclass (this, manually, is the dispatch you're speaking of doing internally and automatically).

On your last point I would see the type of f2 as being

    union ( int->string, string->int )

rather than union ( int, string ) -> union ( string, int ), which you had noted as problematic, as it introduces options that are not provided for such as string->string and int->int.

Perhaps the union of two functions was not as elegant as you were hoping for. Alternatives might use type parameters with complex qualifying expressions, as is in

    T -> S where (T=string and S=int) or (T=int and S=string);

Just some food for thought...

Answer 2

A very similar approach is common in object-oriented languages. There, it's called function overloading and it means that you have multiple distinct functions with the same name, but different signatures.

These languages don't assign type to the group of functions with the same name, but I think one way to look at it is that it's a tuple (or, more formally, product) of functions.