Multimethods, generic functions


#1

This must have been discussed in the past, but I was not able to find anything using the search.

This message is about generic functions. I’ll be using terminology from CLOS (Common Lisp Object System), and in discussing this with people who are not familiar with CLOS, I have noticed that the terminology can be confusing, so please keep that in mind while reading this in order to avoid any confusion.

I would really like to see an implementation of CLOS-style generic functions in Kotlin. I’ll explain the behaviour using Kotlin-style syntax, so that I don’t need to explain the Lisp syntax to any readers not familiar with Lisp. In CLOS, methods do not belong to classes. Instead, we have generic functions. A generic function is a function with multiple implementations, which are chosen at runtime based some some set of criteria.

Let’s say we have a function collide that processes collisions between two objects in a game:

generic fun collide(obj1: Any, obj2: Any)

We can now implement multiple implementations of this function (CLOS refers to the concrete implementations of a generic function “method” but this terminology would be very confusing in Kotlin):

class GameObject
class Ship : GameObject
class Planet : GameObject

impl fun collide(obj1: GameObject, obj2: GameObject) {
    // this will process a collision between any objects unless they are handled by a
    // more specific implementation
}

impl fun collide(obj1: Ship, obj2: Ship) {
    // process ship-to-ship collisions
}

impl fun collide(obj1: Planet, obj2: GameObject) {
    // All planet collisions are handled here
}

impl fun collide(obj1: GameObject, obj2: Planet) {
    collide(obj2, obj1)
}

In CLOS, what would be a “normal” method in a language like Kotlin is simply implemented by convention as a generic function with a single discriminating argument. In other words, CharSequence.charAt() would be equivalent to a generic function with two arguments:

generic fun charAt(seq: CharSequence, index: Int)

impl fun charAt(seq: String, index: Int) {
    // implementation here
}

In CLOS, the method by which the implementation to be called is chosen can be configured using what is called “method combinators” which are fully customisable by the developer. The entire system is incredibly flexible, and if anyone is interested in learning how it works in Lisp there is some information on Wikipedia about it: https://en.wikipedia.org/wiki/Common_Lisp_Object_System. For some more in-depth discussion, here’s another article: http://cl-cookbook.sourceforge.net/clos-tutorial/

I believe that the first reason to not implement this will be the argument that method resolution for generic functions will be very slow in Kotlin. That is true. It will be significantly slower than normal method calls. This is actually an issue in Lisp too, and lots of effort has gone into making the implementations as fast as possible. Typically the compilers implement a method cache that caches the results of method lookups in order to avoid calling the method combinator for every call.

Of course, even with such optimisations it’s still slower than normal method calls, but in Lisp we still see very heavy use of generic functions, and in practice it works really well. You might want to avoid using them in very tight performance critical code, but that’s a very small portion of an application.

Note that ABCL, which is one popular implementation of Common Lisp runs on the JVM, and it seems to work pretty well.


#2

Can you narrow down your feature request? It’s not really clear what exactly you want given that your example can be already implemented in kotlin. Type and compile the following:

fun collide(x: Any, y: Any) { println("Generic collide for $x,$y") }
fun collide(x: Float, y: Any) { println("Float collide1 for $x,$y") }
fun collide(x: Any, y: Float) { println("Float collide2 for $x,$y") }
fun collide(x: Float, y: Float) { println("Float collide3 for $x,$y") }

fun main(args: Array<String>) {
	val a = 3
	val b = 4
	val c = 3.5f
	collide(a, b)
	collide(c, b)
	collide(b, c)
	collide(c, c)
}

The output for this code is:

Generic collide for 3,4
Float collide1 for 3.5,4
Float collide2 for 4,3.5
Float collide3 for 3.5,3.5

Performance is not a problem since methods are resolved as compile time, just like C++ or similar where the most specialised type is selected.


#3

The main difference is that the feature that I want is the ability to resolve this at runtime. That’s the whole point of generic functions.


#4

but what advantage does that have?


#5

What you are looking for is multiple dispatch which is the ability to choose a method at run time based on the type of more than one argument. Kotlin like most languages only supports single dispatch which lets you choose at runtime based only on a single argument (the receiver of the method call).

There are some ways to try to emulate multiple dispatch using multiple single dispatches (see double dispatch). An example of this is the classic Visitor pattern. Other alternatives are switch statements or map data structures.

Multiple dispatch would definitely provide more power but would be a lot of work to implement and probably very expensive at run time. Since the JVM does not support it, it is unlikely Kotlin will any time soon.

There once was a project to support multiple dispatch on Java but that is dead now for over 11 years and only worked up through JDK1.4.


#6

Yes, you are right. It’s a kind of multiple dispatch. CLOS generic functions are more powerful than the typical multiple dispatch implementation, but even a simple implementation would be a great step forward.

As I mentioned in the original post, runtime performance would obviously be slower than plain method calls. At least when targeting the JVM. What I am saying, however, is that it likely will not prohibitively slow. After all ABCL manages to implement it on the JVM with acceptable performance for pretty much all actual uses.

Kotlin does provide a lot of very nice syntactic sugar on top of Java, but it would be nice if it could also provide some features that helps with more than just reducing keystrokes. Multiple dispatch allows you to model certain problems in a much more efficient way.

Since Kotlin targets more than just the JVM, should the language be held back by limitations in Java? I’m not even sure it can be called a true limitation, since it’s certainly possible to implement this feature, but with a slightly lower performance.

The visitor pattern isn’t really an alternative to multiple dispatch. At least I don’t think I ever saw a good use of it.


#7

As I said it is more powerful, but not likely to happen. I have discussed it before in these forums. A common case I wanted it for on the JVM is with dependency injection. The way that Dagger 2 was written made dependency injection on Android extremely difficult to actually achieve. I created an annotation processor to wrap Dagger 2 components with a multiple dispatch mechanism (generated for you at compile time, not at run time).

And I wasn’t saying that the visitor pattern was equivalent to multiple dispatch. Double dispatch is a way that can sometimes be used to emulate multiple dispatch and the visitor pattern is an example of double dispatch that gives you something like it at the cost of boilerplate in your classes and is certainly only a substitute in a limited set of cases. For one thing the visitor pattern is only viable if you have access to modify the classes in question.


#8

You are right, of course.

It seems highly unlikely that this would be implemented based on the design decisions they have made in the past. My opinions and priorities are different from those of the Kotlin designers.

I think a Lisp-style macro system would be very nice and would allow a developer to build these kinds of abstractions without dedicated language support. I know full well that that is very unlikely to happen, but one can at least wish.


#9

I’m interested, can you provide a link to examples or documentation explaining this?


#10

Well, I could try to explain without delving too deep into Lisp specifics. There is a risk that that devolves into a discussion about alternative ways of implementing the same thing, which of course is always possible. So I’d need to find cases that would be particularly elegant using multimethods.

Let’s take CLIM as an example. CLIM is a GUI framework for Common Lisp which heavily uses CLOS for extensibility. With CLIM, you can create visualiation functions for custom objects. In other words, you tell the system how an object should be displayed and all you have to do is to write this object to the output stream, and it will be displayed at the current cursor position.

The display function is a generic function, and you write methods on this function to customise how they are displayed. Here are the arguments to this function:

  • The object to be printed
  • The type of the object
  • The stream that the object should be written to
  • The view type the container belongs to

To implement a display method that is used every time an instance of a given class is to be displayed, all you have to do is to specialise on the object type.

The benefit to this approach, however, is that I can create extra methods that specialise on the stream type or the view. For example, I might to create a method that specialises on all integers when they are displayed in a certain panel. I would do this by specialising on object type integer as well as the specific view type for that panel.

I used integer as an example specifially to point out that these methods are not tied to a class. If I had to add these methods to the class itself, I couldn’t specialise on a Kotlin integer instance, since that class is not available to be modified. And even if I could, I’d have to put the code together with the integer implementation which is not really where it belongs.

If anyone is interested to see some of my code that actually uses this, and if you’re willing to read Lisp code, you can have a look at my Mastodon client: https://github.com/lokedhs/mastodon/blob/master/src/format.lisp. Look at uses of define-presentation-method which is a macro that expands to the specific method definition.

The book Practical Common Lisp gives a pretty good introduction to generic functions: http://www.gigamonkeys.com/book/object-reorientation-generic-functions.html


#11

What if you have one method specialized for stream type and another for the view — how the most specific of them is selected?

How all the available specializations are discovered (at run-time/compile-time)?


#12

All the candidate methods are collected (i.e. all the methods whose argument types matches the supplied arguments), the chosen method (or methods) is selected by some criteria.

The criteria can be configured, but the default behaviour is to choose the method by picking the one whose leftmost argument is the most specific. If there is a conflict, the second argument is chosen, etc.

Since Lisp is a dynamic language, it has to be prepared to handle redefinitions at runtime. It’s not too disimilar from the way Kotlin would have to handle this.