How KEEP-87 & Typeclasses will change the way we write Kotlin

What is KEEP-87

At QuickBird Studios, almost all of our projects are implemented in either Koltin or Swift. It’s only natural, that we compare these languages and find features in one of them, that we would also like to see in the other. While Swift’s protocols can sometimes be a little bit painful to work with, they also offer some features that our Kotlin team was always jealous of:

  • Being able to enforce static functions on implementations, as well as initializers (constructors)
  • Being able to add contract conformance to types outside of the definition of the type itself (implement a protocol as an extension of the type)
  • Conditional Conformance: Implementing a contract under given constraints for any type

Since Kotlin is a rapidly evolving language, there is a place for everyone to submit and discuss proposals for the language. This is called Kotlin Evolution and Enhancement Process (in short KEEP). In the following article, we want to shine a light on the current version of the proposal KEEP-87 and explain how it could, very elegantly, solve a lot of problems that we are currently facing. It has been coined “Typeclasses” in the initial proposal.

KEEP-87 was originally proposed by raulraja (Raúl Raja Martínez) · GitHub. Tomás Ruiz-López and Jorge Castillo already build a working proof of concept that we highly recommend checking out!

Typeclasses

The infamous Any.equals

In order to explain why we need KEEP-87, let me explain why I think a function like Any.equals is bad.

1. The Signature of the function: public open operator fun equals(other: Any?): Boolean

Literally Any type of object can be compared with any other type. The signature does not offer any meaningful information about whether or not this comparison actually makes any sense or is „supported“. It is entirely an implementation detail with absolutely no contract that can be enforced. It is the least „Type-Safe“ way of defining a comparison of two instances, relying only on the truthfulness of the documentation and we all know how well that works.

2. Subclassing and Symmetry

The equals function has to be symmetric.

Documentation:

But this becomes hard when maintaining multiple types in the type hierarchy. Let me give you a very simple example. Let’s say we have a model interface called Dog and two implementations for this model. One defined for the network API and the other representing our database entry:

We have the following requirements:

  1. We want all Dog implementations to be compared by their name (case insensitive)
  2. When working with a DatabaseDog, we also want to take the dog’s id into consideration to compare instances.
  3. DatabaseDog is required to subclass DatabaseObject from our database framework

Here is an example of how to implement this (omitting the hashCode part for the example)

This code has multiple problems!

  • Since DatabaseDog has to subclass DatabaseObject, we were unable to share the common code that compares the name of the dog. Maintaining symmetry here will become a mess later on when requirements change. Changing to a case sensitive comparison will require the developer to go through all implementations with no help by the type system/compiler.
  • DatabaseDog.equals is ambiguous: Let’s say you really want to change the comparison to be case sensitive. So you have to take out all the .toLowerCase() parts of the code above, right? Or not? Maybe the case insensitivity is required when comparing two DatabaseDog objects inside the database module? From that point, you are unable to differentiate the intention of the code duplication and it is almost impossible to see the original requirement.
  • It’s wrong. I do not know how many have immediately spotted the mistake in the implementation. AbstractDog.equals requires other to also subclass AbstractDog , instead of implementing Dog. This evaluates all comparisons of AbstractDog.equals(DatabaseDog) to be false while DatabaseDog.equals(AbstractDog) will still work. This is easy to fix, but would you have spotted this in a merge request where all those files are defined in a different package? That means, that they might not appear in order when looking at the diff. I do not know if I would have.

3. Only one intention

What if the database module has fundamentally different requirements when comparing two instances than the app module?

Maybe the app module just does not care about anything but the name of the dog, even ignoring the case, while it is mandatory for the database to compare the id and the case sensitive name like:

Covering those two intentions is not possible using one single symmetric .equals function!

Let’s fix Any.equals with a Typeclass in plain old Kotlin

All the problems we face when working with the current equals method arise because of one fact: It is defined on the object itself! Let’s pull this function out into another type: Equality<T>. Such an interface is called „extension interface“

Defining those functions as an extension to T might seem inconvenient here, but we will see the reason for it later!
It is easy now to define the two Equality implementations for our app and database module:

Now we can define extension functions by requiring an implementation of Equality. Here are two examples: One top-level comparison of two instances and one to create a distinct list out of any list. We will see both functions being used later to demonstrate the proposal.

Now, we can pass in the correct implementation of Equality depending on whether or not we are in the app or database module.

Working in our app module:

Working in our database module:

This approach solves all the problems that Any.equals brought to the table:

  1. The signatures are meaningful
  2. Maintaining symmetry is easy, since specific eq functions are just defined in one place
  3. We are able to represent multiple intentions (app and database in this example) with this approach without any interference or ambiguity

The KEEP-87 proposal

But if this is so easy to fix, why was it built this way?

Well… it’s actually not that simple. While the approach above might fix the problem of the equals function for one model in a particular project, it would not scale well for big projects or deep call chains.

Would you like to search for the correct Equality<T> implementation for every type in a big project and then pass it through with every method you call? Just think how much this would bloat Kotlin’s standard library if we would have to pass through extension interfaces like this every time? But what if we could somehow associate this extension interfaces with the type itself?

Let’s imagine how this could look like by modifying our eq extension function. The original version of the eq function:

Here is the first naive idea of something that we would like to write. Instead of passing the equality parameter in, we would like to change the signature to only allow a T which supports the given Equality<T> extensions like

Now the function only allows types of for T that also implement Equality<T>.

Wait. Now we ended up where we started, except that a type now has to implement Equality<T> which is exactly what we wanted to avoid. We want to have a separate own object that defines our extension functionality and the signature should just require proof if this objects existence!

Okay. So let’s change the signature further. Maybe we can add proof for the existence of this extension object by adding a constraint at the end of the function signature like:

So this function signature would tell us, that it wants some T, where a Equality<T> is given. Okay, but how can we now access the extensions defined by Equality<T>? The Equality<T> needs to be a receiver in the function body! Just like we did before by starting the function with with(equality { … }! So let’s iterate over the function signature one more time. Let’s consider the Equality to be a dependency of the eq extension function. What about requesting this dependency as a parameter to the function, but with two modifications:

  1. The parameter to this function shall also become receiver in the function body
  2. The dependency shall be resolved by the compiler for you

So here is the current state of the proposal:

A new with modifier is introduced to require a compile-time dependency which will become the receiver of the function. Let’s look at our app module where we are able to find two instances of Dog by its id. Since we have a Equality<Dog> implementation, we can freely use the eq extension function.

But the newly gained type-safety will prevent us from comparing dogs with other, unsupported types:

Also, we cannot use this eq function for types where no Equality is implemented!

Okay! So the function signature now allows us to have a typeclass implementation for a given type as a constraint to the function signature. That’s great! This solves the problem of finding and passing the implementations manually!

But how will the compiler look for these implementations? If we allow them to be placed anywhere, then we will end up in anarchy! We would have no idea of which implementation is actually used? Of course, there is a solution for this which will ensure compiler coherence.

So where does the compiler look for these implementations of the extension interface?

1. Arguments of the caller function

When using the eq function you are free to pass in any equality as a parameter. The compiler lookup can more be seen as something like a default argument to the function. Let’s go back to the non-compiling comparison between two cats. It did not compile, because we did not specify any equality as a parameter and the compiler does not know of any Equality<Cat> that it can use. Just passing in an implementation yourself will be perfectly fine and has a lot of power!

2. Companion object of the target type

If the implementation of the extension interface is not provided as a parameter at the function call site, the compiler will look into the companion object of the target type (e.g. Dog ). Here we can see another keyword proposed by KEEP-87: To mark any implementation of an extension interface as such, the extension keyword is necessary to support automatic compiler lookup.

3. Companion object of the contract interface

If no implementation was found in the companion of the target type, the companion object of the contract will be looked at:

This way, the implementer of such a contract interface can add implementations for types that he might not own, like types defined in the StdLib: Int, String, …

4 & 5.: Subpackes

If both, the companion of the target type (Dog) as well as the companion of the contract interface (Equality ) do not contain the implementation for the given contract for the specified type, then the compiler will first look into sub packages of the target type and then into sub packages of the contract type to resolve these extensions. But such extensions have to be marked as internal and cannot be used outside of the current gradle module.

Conclusion

Hopefully the simple example of the problematic Any.equals function was able to show the impact that this proposal would have to the way we currently write Kotlin code. We could think of a bunch of other fundamental Typeclasses that could be implemented nicely with this proposal like:

  • a hash code for a given instance
  • Order: Defining which instance is considered greater ( >)
  • Monoid: Being able to combine two instances

We think KEEP-87 is great and would definitely enable us to write Kotlin code in a way that would have been just not feasible right now. The prototype is nice and I had a good time playing around with it! I was already able to re-model some code that I use in private projects with the new language feature. KEEP-87 covered all of the things I was jealous about when looking at Swift’s protocols. This article presented the basic features of the proposal and, for sure, there is a lot more we could write about.

Let us know if you have any feedback or are interested in a more in-depth look in the proposal and more sophisticated use case examples.

Get notified when the next article is born 🐣
(no spam, just one app-development-related article per month)