Sunday 20 May 2012

Multimethods

Multiple Dispatch (aka Multimethods) is one of those advanced programming features very rarely supported by Programming languages. Long in short, the idea is that the dispatch mechanism for overloaded methods should take into account the runtime type of the arguments (so, extending the normal polymorphism where the runtime type of the object on which the method is invoked is used to dispatch to the correct method via the corresponding vTable entry).

We can have dynamic dispatch, both in static and dynamic languages, by adding ourselves the dispatching mechanism to each method. So in every method for which we wanted multiple dispatch we would have to write some type checking code using instanceof (Java), is (C#), or whatever mechanism the language provides, and then we would have some kind of switch from which we would invoke the needed code

If we move to the JavaScript terrain, where we're so used to closures, functions that generate functions and so on, I thought sure it would be easy to come up with some way to automate this

Before implementing my own solution, I searched the web to see what others had come up with, and found 2 different projects:

  • le Func It's fine, but different from what I had in mind, it only takes into account primitive types
  • Multimethod.js Wow, this is sheer beauty, much more advanced that what I had in mind, cause it lets you dispatch not just based on "types", but just on values. In fact, it's been an eye opener, as I'd never thought of multiple dispatch in terms of values

Let me clarify that I'm very fond of the dynamic nature of JavaScript and I think coding in it should normally be based on duck typing, and in fact I think it's hard to apply the concept of types to a language where an object can be modified (augmented, expanded) so much that it can end up having quite little to do with what we initially obtained from the constructor function used for its creation. Though, let's say I'm a bit old fashioned when it comes to dynamic dispatching and wanted to implement a classic model, one based on the type of the object, and understanding as its type, the constructor function used for its creation. So I decided to roll out my own implementation, coming up with this:

var multimethod = function(){
 var me = function _multimethodImpl(){
  var found = false,
   i = 0;
  while(!found && i < me.keys.length){
   var j = 0,
    misMatch = false;
   while(!misMatch && j < arguments.length){
    var curArgument = arguments[j];
    if(typeof(curArgument) != "undefined" && curArgument != null){
     if(curArgument["constructor"] != me.keys[i][j]){
      misMatch = true;
     }
    }
    j++;
   }
   found = !misMatch;
   i++;
  }
  if (found){
   return me.methods[--i].apply(this, arguments);
  }
  else{
   throw new Error("function not found"); 
  }
 };
 
 me.keys = []; //each entry is an array of constructor functions
 me.methods = [];
 me.add = function(method, paramTypes){
  this.keys.push(paramTypes);
  this.methods.push(method);
  return this; //let's do it fluent
 };
 return me;
};

So the multimethod function returns a function (a closure holding the different functions to be invoked based on the different parameters) that exposes an add method intended for adding the real functions (and types) to which each call should be dispatched. It can be used like this:

var sayHi = multimethod()
 .add(function(){
  console.log("Person is saying Hi");
 }, [Person])
 .add(function(){
  console.log("Employer is saying Hi");
 }, [Employer])
 .add(function(){
  console.log("Employee is saying Hi");
 }, [Employee])
 .add(function(){
  console.log("received Employee and Number");
 }, [Employee, Number])
 .add(function(){
  console.log("received Employee and String");
 }, [Employee, String])
  .add(function(){
  console.log("received Employer and Number");
 }, [Employer, Number])
 .add(function(){
  console.log("received Employer and String");
 }, [Employer, String])
 .add(function(){
  console.log("received Employer and Function");
 }, [Employer, Function]);

Notice that I'm doing the type matching based on the constructor property of the parameters, not on the instanceof operator

.

You can find the code with some samples here

Update 2012/05/29. I'd like to complete this entry by saying that the crazy dispatch mechanism in Groovy presents us with out of the box multimethods. It's amazing to see how clean it makes patterns like Visitor

No comments:

Post a Comment