Is it possible to have Ad-Hoc polymorphism with runtime dispatch

dispatchhaskellpolymorphismscalatypeclass

As I did understand, and as it's described here, ad-hoc polymorphism is limited to compile-time dispatch. That is, if we have a function that expects an argument that belongs to a typeclass, we must know the concrete type of the argument at compile time to be able to use this function.

So the following (in Haskell-like pseudocode) will be invalid:

// C-style comments

typeclass Num(X) where:
    add :: X -> X -> X
    one :: X

implementation Num for Int:
    add x y = x + y
    one = 1

implementation Num for Rational:
    // analogous thing…

veryCleverFunction :: Num a -> a -> a
veryCleverFunction x = add x one

tooCleverFunction :: Int -> Num(?)
tooCleverFunction x = {
    y =
        if (x > 0)
            x
        else
            Rational(x, 2) // `y` has a value of unknown type,
                           // but we know it's under `Num` typeclass
    veryCleverFunction y // can work with any `Num`s, but here the concrete type is unknown…
}

(I hope it's clear what I want to depict in this snippet)

At least in Scala I'm almost sure there's no way to express this. Or I'm wrong?
And is it possible in theory? Are there any languages which allow this?

Best Answer

There are different mechanisms of polymorphism. Except for parametric polymorphism, these dispatch control flow depending on the type of function arguments. In other words: they are some kind of function overloading. The arguments can either be considered for their static type or for their dynamic type. If we dispatch a call on a static type, we call this ad-hoc polymorphism. If we dispatch on the dynamic type, this is either single dispatch if we only consider the dynamic type of one argument (typically an object on which a method is called), or multiple dispatch if we consider the dynamic type of all arguments.

All OOP languages must at least offer single dispatch. The Visitor Pattern can be used to fake multiple dispatch by using additional levels of indirection, but is impractical for more than two arguments. Multi-dispatch in general solves the same kind of problems that ad-hoc polymorphism does, except that it happens at runtime and can therefore be more expressive. Noteworthy examples of languages with multi-dispatch (sometimes called multi-methods) are the Common Lisp Object System (CLOS) and the Julia language.

The blog post you linked to does demonstrate ad-hoc polymorphism, but in an overly complicated fashion. The simplest example might be:

abstract class Pet
class Cat extends Pet
class Dog extends Pet

object Owner {
    def pet(cat: Cat) = "You can haz cuddles!"
    def pet(dog: Dog) = "Who's a good boy?"
}

val cat: Cat = new Cat()
val dog: Dog = new Dog()
val pet: Pet = new Cat()

Owner pet cat // works
Owner pet dog // works
Owner pet pet // fails, because implementation is chosen *statically*

It's the same story in Java and C++. The blog post then goes on a tangent on how using implicit parameters can be used to implement extension methods, and how they can be used to hide the visitor pattern. None of this is really relevant to ad-hoc polymorphism.

Your code example runs into problems because the return types of tooCleverFunction but more importantly of the conditional assigned to the variable y are not well defined. As y can either be Int or Rational, the type checker must reject your code. To safely allow this ambiguity, we could introduce a Union type. But if we have y :: Union Int Rational, then veryCleverFunction can't be applied to y (except of course if Union is a functor so we can do fmap veryCleverFunction y, which returns another Union for you to deal with). If we use such an Union, no static type information is lost. Instead, you have to deal with the mess you created throughout the remaining program.

You would like y to have the type Num a instead. But Num a is not a type, but a type class, i.e. a restriction on the type a.

Related Topic