After toying a bit with Kotlin, it seems it doesn’t have a proper solution to the famous Expression Problem.
The problem
The original statement:
The goal is to define a datatype by cases, where one can add new cases
to the datatype and new functions over the datatype, without recompiling
existing code, and while retaining static type safety (e.g., no casts).
Also see this very didactic explanation.
In OO language like Java in Kotlin, you can easily add “new cases” via subclassing, but you can’t add new operations (this necessitates adding methods to existing classes). If the code uses the visitor pattern, then you can add new operations (new visitors), but you can’t add new classes, because they have not been included in the visitor class.
There exist “solutions” to that problem in Java, but they are deeply unsatisfactory. In particular, new classes or operations must be “linearized”, meaning that new operations/classes added by different people (e.g. in different libraries) do not compose.
It’s not an exotic problem either, and I encounter it shockingly often. For instance, when writing a parser combinator library, I want to give the users the ability to specify custom parsers (subclass the parser interface) but also define new operations over parsers, in order to implement grammar transformations by walking a tree of parsers.
Solutions
Perhaps the most famous (and in my opinion, elegant) solution to the problem are typeclasses. Let’s ignore them for a second, though.
I believe that the solution that would make the most sense in Kotlin would be to add retroactive interface implementation: making existing classes implement new interfaces. The advantage is that this solves the problem (we can now easily add new operations by retroactively implementing interfaces) while adding no new concepts: users already know what is means to implement an interface.
Note that this is close to what Cedric Beust proposed as Extension Types on this very forum.
Alas, I believe this to be impossible to implement on the JVM. I’m not an expert, so feel free to correct me, but I believe that to making a compiled class implement a new interface would at least require modifying the class file.
And so, we’re back to typeclasses. Except we don’t need to call them that. Here’s what they could look like:
plugin interface Addable<T, R> {
fun add(x: T): R
}
implement String: Addable<String, String> {
fun add(x: String): String = this + x
}
fun test(x: Addable<String, String>) = x + "bar"
test("foo")
We could implement all of this by desugaring to:
interface Addable<Self, T, R> {
fun add(self: Self, x: T): R
}
val addableStringStringString = object: Addable<String, String, String> {
override fun add(self: String, x: String): String = self + x
}
fun <T> test(typeclass: Addable<T, String, String>, x: T) = typeclass.add(x, "bar")
test(addableStringStringString, "foo")
Most of the transformation is straightforward. In the last line, we need to select the correct typeclass for “foo”. The simplest solution is to implement this as a lookup in Class -> Typeclass map. In cases where the static type of the argument is “final” (as is often the case in Kotlin) we can optimize this lookup away. Ditto when a method using a typeclass calls a method that requires the same typeclass. This is a form of caching, which minimizes the number of lookup required.
The trick from Haskell is that typeclasses are really an additional implicit argument to a function. By using this trick, we can preserve the illusion that a type implements a new interface.
Most of the transformation is straightforward. In the last line, we need to select the correct typeclass for “foo”. The simplest solution is to implement this as a lookup in Class -> Typeclass map. In cases where the static type of the argument is “final” (as is often the case in Kotlin) we can optimize this lookup away. Ditto when a method using a typeclass calls a method that requires the same typeclass. This is a form of caching, which minimizes the number of lookup required.
There are a few downsides: first, the underlying plumbing would have to be exposes to Java clients, no way around it. Second, a few additional precautions must be taken to maintain the illusion that String implements Addable. For instance, we need to transform expression like "foo" is Addable<String, String> to perform a lookup in our Class -> Typeclass map. Ditto for some typecasts.
Conclusion
I hope to have shown that Kotlin really needs a solution to the expression problem, and that such a solution isn’t too difficult to implement, in addition to being user-friendly. The downside is having to expose implement details to Java clients, even though these details aren’t terribly complex.