Aman King

MultimethodsAman King's BlikiControl PanelChange LogBrowse PagesSearch?

Multimethods

I first heard about Multimethods from fellow-ThoughtWorker Unmesh Joshi. I was complaining about why Java behaves a certain way to which his response was something like "It's related to multimethods". He kind of left it at that, and so did I.

Of late, I've started looking at Clojure and surprisingly I ran into the concept of multimethods again. This time around I dug deeper. The following is how I finally understood multimethods...

Let's start by looking at this Java code snippet:

public class MultimethodsDemo {
    static class Walk { }
    static class Dance { }
    static class Attack { }
 
    static class Robot {
        public String doThis(Walk walk) { return "I am walking..."; }
        public String doThis(Dance dance) { return "Let's boogie woogie..."; }
        public String doThis(Attack attack) { 
            throw new RuntimeException("I don't believe in violence!");
        }
    }
 
    public static void main(String[] args) {
        Robot robot = new Robot();
        System.out.println(  robot.doThis(  new Walk()   ));
        System.out.println(  robot.doThis(  new Dance()  ));
        System.out.println(  robot.doThis(  new Attack() ));
    }
}

As expected, its output is:

I am walking...
Let's boogie woogie...
Exception in thread "main" java.lang.RuntimeException: I don't believe in violence!
	at MultimethodsDemo$Robot.doThis(MultimethodsDemo.java:10)
	at MultimethodsDemo.main(MultimethodsDemo.java:18)


We know this is polymorphism at work, overloading to be precise.

Let's look at another snippet where we introduce a Command abstraction:

import java.util.*;
public class MultimethodsDemo {
    static interface Command {}
    static class Walk implements Command { }
    static class Dance implements Command { }
    static class Attack implements Command { }
 
    static class Robot {
        public String doThis(Walk walk) { return "I am walking..."; }
        public String doThis(Dance dance) { return "Let's boogie woogie..."; }
        public String doThis(Attack attack) { 
            throw new RuntimeException("I don't believe in violence!"); 
        }
    }
 
    public static void main(String[] args) {
        Robot robot = new Robot();
        List<Command> commands = Arrays.asList( new Walk(), new Dance(), new Attack() );
        for ( Command command :  commands ) {
            System.out.println(  robot.doThis(command)  );
        }
    }
}

Can we expect the same output as before?

MultimethodsDemo.java:20: cannot find symbol
symbol  : method doThis(MultimethodsDemo.Command)
location: class MultimethodsDemo.Robot
            System.out.println(  robot.doThis(command)  );
                                      ^
1 error


Oops, we get a compilation error! Java is looking for a doThis() with a Command parameter. On second thought, it seems reasonable. What if someone implemented a Jump that implements Command? We could easily put a Jump instance in the commands list: how would robot deal with it? So let's try the following:

import java.util.*;
public class MultimethodsDemo {
    static interface Command {}
    static class Walk implements Command {}
    static class Dance implements Command {}
    static class Attack implements Command {}
 
    static class Robot {
        public String doThis(Walk walk) { return "I am walking..."; }
        public String doThis(Dance dance) { return "Let's boogie woogie..."; }
        public String doThis(Attack attack) { 
            throw new RuntimeException("I don't believe in violence!"); 
        }
        public String doThis(Command command) { 
            throw new RuntimeException("Unknown command: " + command.getClass()); 
        }
    }
 
    public static void main(String[] args) {
        Robot robot = new Robot();
        List<Command> commands = Arrays.asList( new Walk(), new Dance(), new Attack() );
        for ( Command command :  commands ) {
            System.out.println(  robot.doThis(command)  );
        }
    }
}


Yep, this makes the compiler happy! And what about the output...

Exception in thread "main" java.lang.RuntimeException: Unknown command: class MultimethodsDemo$Walk
	at MultimethodsDemo$Robot.doThis(MultimethodsDemo.java:15)
	at MultimethodsDemo.main(MultimethodsDemo.java:23)


Hmm... the robot knows how to walk so why say it doesn't?

That's because of early binding that happens at compile-time. Java decides even before the program is run that if the line System.out.println(robot.doThis(command)) gets executed, it'll call the doThis(Command command) version of doThis() because the data type Java can guarantee at compile-time is Command, not the specific ones. Note we're iterating over a List<Command> after all.

To fix this, we can force correct compile-time overloading by doing this:

// ...
 
    static class Robot {
        public String doThis(Walk walk) { return "I am walking..."; }
        public String doThis(Dance dance) { return "Let's boogie woogie..."; }
        public String doThis(Attack attack) { 
            throw new RuntimeException("I don't believe in violence!"); 
        }
        public String doThis(Command command) { 
            if (command instanceof Walk) { return doThis(    (Walk) command   ); }
            if (command instanceof Dance) { return doThis(   (Dance) command  ); }
            if (command instanceof Attack) { return doThis(  (Attack) command ); }
            throw new RuntimeException("Unknown command: " + command.getClass()); 
        }
    }
 
// ...


Java now decides at compile-time that if the line return doThis((Walk) command) gets called during runtime, it'll invoke doThis(Walk walk) because of the explicit cast. Similarly for the rest.

After a point, folks find such code hard to read and maintain since every sensible implementation of Command would need additional if's in doThis(Command command). To make this more manageable, some folks use the Visitor design pattern.

So that was the effect of early binding. But what about the other type of polymorphism: overriding?

Thankfully Java does late binding (runtime) for overriding polymorphism. This is well-known to Java developers but for completeness' sake, here's an example:

public class MultimethodsDemo {
 
    static class Robot {
        public String name() { return "normal robot"; }
    }
    static class AwesomeRobot extends Robot {
        public String name() { return "awesome robot!!!"; }
    }
 
    public static void main(String[] args) {
        Robot robot = new Robot();
        Robot awesomeRobot = new AwesomeRobot();
        System.out.println( robot.name() );         // "normal robot"
        System.out.println( awesomeRobot.name() );  // "awesome robot!!!"
    }
}


Now, please humour me by thinking of robot.doThis(command) as doThis(robot, command) for a while... the syntax is a bit awkward but interestingly it's not alien to languages like Javascript or C# even.

Javascript example:

var person = { 
    name: 'Aman', 
    greet: function(someName) { 
        return 'Hi ' + someName + ', I am ' + this.name + '!'; 
    }
};
person.greet('Dude'); // "Hi Dude, I am Aman!"
 
var anotherPerson = { name: 'King' };
 
var greetMethod = person.greet;
greetMethod.apply(anotherPerson, ['Dudette']);  // "Hi Dudette, I am King!"


C# 3.0 example:

namespace CustomExtensions
{
    public static class CustomExtensionsClass
    {
        public static string Times(this object input, int times)
        {
            return "don't care!";
        }
        public static string Times(this string input, int times)
        {
            string result = "";
            for(int i = 0; i < times; i++)
                result += input;
            return result;
        }
        public static int Times(this int input, int times)
        {
            return input * times;
        }
    }
}
// ...
using CustomExtensions;
var aStringObject = "aman";  aStringObject.Times(2); // "amanaman"
var anIntObject = 3; anIntObject.Times(2);           // 6
// ...

(By the way, in the above example, if we had object aStringObject instead of var aStringObject, we'd run into the same early binding issues as in Java: var does implicit typing, becoming equivalent to string aStringObject for a string assignment.)


In all these examples, if we consider the doThis(robot, command) kind of syntax, we can say that polymorphism was based on the runtime type of a single argument: the first one (implicitly passed).

In other words, Java and C# 3.0 support Single Dispatch, not Double Dispatch, not Multiple Dispatch.

So what is Multiple Dispatch?

My attempt at a definition: Multiple Dispatch is the selection aka dispatch of a method based on the runtime type of multiple arguments.


Here are some languages that support Multiple Dispatch / Multimethods:

  • Common Lisp
  • Clojure
  • Perl
  • Groovy
  • C# 4.0

Yep, notice C# at the end. Multiple Dispatch has been made possible by the introduction of Dynamic Language Runtime (DLR) in .NET Framework 4, with the use of the dynamic type in C# 4.0.

Here's an example:

using System;
namespace Multimethods
{
    public interface ICommand { }
    public class Walk : ICommand { }
    public class Dance : ICommand { }
    public class Attack : ICommand { }
 
    public class Robot
    {
        public string DoThis(Walk walk) { return "I am walking..."; }
        public string DoThis(Dance dance) { return "Let's boogie woogie..."; }
        public string DoThis(Attack attack) 
	    { throw new InvalidOperationException("I don't believe in violence!"); }
        public string DoThis(ICommand command) 
	    { throw new InvalidOperationException("Unknown command: " + 
			((object) command).GetType().Name); }
        public string DoThisCommand(ICommand command) 
        {
            dynamic cmd = command;
            return DoThis(cmd);
        }
    }
}
 
// ...
Robot robot = new Robot();
ICommand command = new Walk();
robot.DoThisCommand( command ); // "I am walking..."
robot.DoThis( command );        //  Exception: "Unknown command: Walk"
// ...


So what do I find interesting about Multiple Dispatch / Multimethods?

The fact that it makes me wonder about:

  • OO as syntactic sugar for method dispatch?
  • Design patterns as a way to overcome lack of language features? (Example: Visitor for Double Dispatch, Strategy for Closures/Lambdas)
  • Do we really need more than Single Dispatch or at best Double Dispatch anyways?

I won't jump to conclusions as yet, especially since I've not used multimethods for real purposes so far. But yeah, I would like to avoid using the Visitor pattern where Double Dispatch is all I need. In a dynamic language like Ruby, however, language features like duck typing seem to suffice.

Will keep you posted if I see interesting uses of multimethods in Clojure maybe.

In the meanwhile, you could read the following:


By the way, I did a lightning talk on Multimethods for a Techquilla session in ThoughtWorks Pune. Here's the presentation: http://www.slideshare.net/amanking/multimethods

Comments

Talk
Tags: technology:coding, technology:javascript, technology:java, technology:clojure, technology:language, technology:talks, personal Last modified 14:26 Mon, 9 Aug 2010 by AmanKing. Accessed 1,435 times Children What Links Here share Share Except where expressly noted, this work is licensed under a Creative Commons License.