Lambda the Ultimate

Kitten has ad-hoc static polymorphism in the form of traits. You can declare a trait with a polymorphic type signature, then define instances with specialisations of that signature:

// Semigroup operation
trait + <T> (T, T -> T)

instance + (Int32, Int32 -> Int32) {
  _::kitten::add_int32
}

instance + (Int64, Int64 -> Int64) {
  …
}
…

This is checked with the standard “generic instance” subtyping relation, in which <T> (T, T -> T) ≤ Int32, Int32 -> Int32. But the current compiler assumes that specialisations are fully saturated: if it infers that a particular call to + has type Int32, Int32 -> Int32, then it emits a direct call to the (mangled) name of the instance. I’d like to remove that assumption and allow instances to be generic, that is, partially specialised:

// List concatenation
instance + <T> (List<T>, List<T> -> List<T>) {
  _::kitten::cat
}

// #1: Map union
instance + <K, V> (Map<K, V>, Map<K, V> -> Map<K, V>) {
  …
}

// #2: A more efficient implementation when the keys are strings
instance + <V> (Map<Text, V>, Map<Text, V> -> Map<Text, V>) {
  …
}

But this raises a problem: I want to select the most specific instance that matches a given inferred type. How exactly do you determine that?

That is, for Map<Text, Int32>, #1 and #2 are both valid, but #2 should be preferred because it’s more specific. There are also circumstances in which neither of two types is more specific: if we added an instance #3 for <K> (Map<K, Int32>, Map<K, Int32> -> Map<K, Int32>), then #2 and #3 would be equally good matches, so the programmer would have to resolve the ambiguity with a type signature.