4

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?

  • 1
    In general, they're "just" overloaded functions and you the language designer need to choose what happens with the dispatch when you have an overload of int, string, and int|string. – Telastyn Jun 8 '16 at 11:29
  • Rather than run-time map/dispatch of the appropriate function based on the runtime type of the union, a common approach is to use pattern matching. What's your reasoning behind wanting to do it the way you are? – David Arno Jun 8 '16 at 11:37
  • The approach you are taking though is a form of duck-typing. It might be worth reading up on that topic therefore. – David Arno Jun 8 '16 at 11:38
  • @DavidArno - the reason for the design is actually twofold, and your comments hit both points... I want to attempt to unify pattern matching and type-based dynamic dispatch into a single mechanism, and one of the main aims of the language is to allow designs that are more common in dynamic languages in a language with static types... gradual typing coming from the static side rather than the dynamic side as is more common. – Jules Jun 8 '16 at 19:29
2

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...

  • "I would see the type of f2 as being union ( int->string, string->int )" This is where I started out, but it doesn't seem right to me. The issue I see with this is that semantically, this should mean that either f2 can contain a function int->string or a function string->int, but not both at the same time, which is what it actually is. I think this means it needs to have its own type constructor, perhaps product as suggested by @svick. The use of type variables is an interesting idea I hadn't thought of though. I suspect it will be more complex, but definitely worth considering. – Jules Jun 8 '16 at 19:41
  • Interesting. Perhaps f2 the conjunction of those signatures, rather than the disjunction of them? – Erik Eidt Jun 8 '16 at 20:17
1

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.

  • Indeed. My goal here is to provide a single mechanism that can support both functional-style pattern matching and OO-style overloading. Assigning a type for the collection seems to be necessary for the simple reason that as I'm deferring selection of the version to invoke until runtime, a reference to a method needs to carry all of the possibilities with it. That the result is essentially a product of functions is basically the conclusion I'm coming to, as well. – Jules Jun 8 '16 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.