Multiple dispatch for multiple arguments

Question

Is there an elegant way to obtain multiple dispatch for methods with 2 parameters (or even more) in OO languages with (single) dynamic dispatch?

Example of a possible problem:

This is a Java-inspired example. (the problem is not language related!)

// Visitable elements
abstract class Operand {
}
class Integer extends Operand {
    int value;
    public int getValue() {
        return value;
    }
}
class Matrix extends Operand {
    int[][] value;
    public int[][] getValue() {
        return value;
    }
}

// Visitors
abstract class Operator {
    // Binary operator
    public Operand eval(Operand a, Operand b) {
        return null; // unknown operation
    }
}
class Addition extends Operator {
    public Operand eval(Integer a, Integer b) {
        return new Integer(a.getValue() + b.getValue());
    }
}
class Multiplication extends Operator {
    public Operand eval(Integer a, Integer b) {
        return new Integer(a.getValue() * b.getValue());
    }
    // you can multiply an integer with a matrix
    public Operand eval(Integer a, Matrix b) {
        return new Matrix();
    }
}

I have many Operator and Operand concrete types but only refer to them through their abstract types:

Operand a = new Integer()
Operand b = new Matrix();
Operand result;
Operator mul = new Multiplication();
result = mul.eval(a, b); // Here I want Multiplication::eval(Integer, Matrix) to be called

Answer 1

I decided to add to this since the above two answers are somewhat incomplete. I was myself curious about this issue but couldn't find an answer so had to do my own analysis. In general there are two approaches that can be used to implement multi-methods in languages like C++ or Java that support both single dynamic dispatch and something like typeof or runtime type identification.

For the double dispatch case the visitor pattern is most common (for Arg1->foo(Arg2) ) and I gather in most cases is preferred to using RTTI and switches or if statements. One can also generalize the visitor approach to the n case by i.e. Arg1->foo(Arg2,Arg3..ArgN) by chaining a series of single dispatches that call methods in a treelike structure that differentiate on the type of the arguments up to some k and split the number of ways of the k+1 argument. For example for a simple case of triple dispatch and only two instances of each type:

interface T1 {
    public void f(T2 arg2, T3 arg3);
}

interface T2 {
    public void gA(A a, T3 arg3)
    public void gB(B b, T3 arg3)
}

interface T3 {
    public void hAC(A a,C c);
    public void hAD(A a,D d);
    public void hBC(B b,C c);
    public void hBD(B b,D d);
}

class A implements T1 {
    public void f(T2 arg2, T3 arg3) {
        arg2->gA(this,arg3);
    }
}

class B implements T1 {
    public void f(T2 arg2, T3 arg3) {
        arg2->gB(this,arg3);
    }
}

class C implements T2 {
    public void gA(A a,T arg3) {
        arg3->hAC(a, this);
    }

    public void gB(B b,T arg3) {
        arg3->hBC(b, this);
    }
}

class D implements T2 {
    public void gA(A a,T arg3) {
        arg3->hAD(a, this);
    }

    public void gB(B b,T arg3) {
        arg3->hBD(b, this);
    }
}

class E implements T3 {
    public void  hAC(A a,C c) {
        System.out.println("ACE");
    }
    public void  hAD(A a,D d) {
        System.out.println("ADE");
    }
    public void  hBC(B b,C c) {
        System.out.println("BCE");
    }
    public void  hBD(B b,D d) {
        System.out.println("BDE");
    }

}

class F implements T3 {
    public void  hAC(A a,C c) {
        System.out.println("ACF");
    }
    public void  hAD(A a,D d) {
        System.out.println("ADF");
    }
    public void  hBC(B b,C c) {
        System.out.println("BCF");
    }
    public void  hBD(B b,D d) {
        System.out.println("BDF");
    }

}

public class Test {
    public static void main(String[] args) {
        A a = new A();
        C c = new C();
        E e = new E();

        a.f(c,e);
    }
}

Though the approach generalizes the problem are quite obvious. For each endpoint function in the worse case one has to write n-1 dispatch functions.

One can achieve something similar with runtime type identification via the instanceOf operator:

class Functions
{
    static void f(A a,C c,E e) {
        System.out.println("ACE");
    }
    static void f(A a,C c,F f) {
        System.out.println("ACF");
    }
    static void f(A a,D d,E e) {
        System.out.println("ADE");
    }
    static void f(A a,D d,F f) {
        System.out.println("ADF");
    }
    static void f(B b,C c,E e) {
        System.out.println("BCE");
    }
    static void f(B b,C c,F f) {
        System.out.println("BCF");
    }
    static void f(B b,D d,E e) {
        System.out.println("BDE");
    }
    static void F(B b,D d,F f) {
        System.out.println("BDF");
    }

    static void dispatch(T1 t1, T2 t2, T3 t3) {
        if( t1 instanceOf A)
        {
            if(t2 instance of C) {
                if(t3 instance of E) {
                    Function.F( (A)t1, (C)t2, (E)t3 );
                }
                else if(t3 instanceOf F) {
                    Function.F( (A)t1, (C)t2, (F)t3 );
                }
            }
            else if(t2 instance of D) {
                if(t3 instance of E) {
                    Function.F( (A)t1, (D)t2, (E)t3 );
                }
                else if(t3 instanceOf F) {
                    Function.F( (A)t1, (D)t2, (F)t3 );
                }
            }
        }
        else if(t1 instanceOf B) {
            if(t2 instance of C) {
                if(t3 instance of E) {
                    Function.F( (B)t1, (C)t2, (E)t3 );
                }
                else if(t3 instanceOf F) {
                    Function.F( (B)t1, (C)t2, (F)t3 );
                }
            }
            else if(t2 instance of D) {
                if(t3 instance of E) {
                    Function.F( (B)t1, (D)t2, (E)t3 );
                }
                else if(t3 instanceOf F) {
                    Function.F( (B)t1, (D)t2, (F)t3 );
                }
            }
        }
    }
}

The second solution can probably be further simplified using reflection.

Answer 2

I am not sure that I will answer your question, but I hope I can add a bit to the discussion. I will try to come back later with a more general answer, but in this one I will focus only on your example above.

The problem with the example given in the question is that it is based on arithmetical operations and that makes it inherently complex because the implementation of a given operator changes depending on the types of its operands.

I think that the problem obscures the question a little bit, e.g. we could spend time trying to make your example work instead of dealing with multiple dispatch issues.

One way to make your code work would be to think from a different point of view. Instead of defining an abstraction called Operator what we could do is to recognize the inherent nature of the operands, namely that they must provide an implementation of every possible operation that can affect them. In object-oriented terms, every operand packs a bunch of actions that can affect them.

And so, imagine I have an interface Operand like this, that defines every possible operation an operand supports. Notice that I not only defined one method variance per every possible known operand but also one method for a general case of another unknown operand:

interface Operand {
    Operand neg();
    Operand add(Int that);
    Operand add(Decimal that);
    Operand add(Operand that);
    Operand mult(Int that);
    Operand mult(Decimal that);
    Operand mult(Operand that);
    Operand sub(Int that);
    Operand sub(Decimal that);
    Operand sub(Operand that);
}

Then now consider that we had two implementations of this: Int and Decimal (I will use decimal instead of the matrix of your example for simplicity).

class Int implements Operand {
    final int value;
    Int(int value) { this.value = value; }
    public Int neg(){ return new Int(-this.value); }
    public Int add(Int that) { return new Int(this.value + that.value); }
    public Decimal add(Decimal that) { return new Decimal(this.value + that.value); }
    public Operand add(Operand that) { return that.add(this); } //!
    public Int mult(Int that) { return new Int(this.value * that.value); }
    public Decimal mult(Decimal that) { return new Decimal(this.value * that.value); }
    public Operand mult(Operand that) { return that.mult(this); } //!
    public Int sub(Int that) { return new Int(this.value - that.value); }
    public Decimal sub(Decimal that) { return new Decimal(this.value - that.value); }
    public Operand sub(Operand that) { return that.neg().add(this); } //!
    public String toString() { return String.valueOf(this.value); }
}

class Decimal implements Operand {
    final double value;
    Decimal(double value) { this.value = value; }
    public Decimal neg(){ return new Decimal(-this.value); }
    public Decimal add(Int that) { return new Decimal(this.value + that.value); }
    public Decimal add(Decimal that) { return new Decimal(this.value + that.value); }
    public Operand add(Operand that) { return that.add(this); } //!
    public Decimal mult(Int that) { return new Decimal(this.value * that.value); }
    public Decimal mult(Decimal that) { return new Decimal(this.value * that.value); }
    public Operand mult(Operand that) { return that.mult(this); } //!
    public Decimal sub(Int that) { return new Decimal(this.value - that.value); }
    public Decimal sub(Decimal that) { return new Decimal(this.value - that.value); }
    public Operand sub(Operand that) { return that.neg().add(this); } //!
    public String toString() { return String.valueOf(this.value); }
}

Then I can do this:

Operand a = new Int(10);
Operand b = new Int(10);
Operand c = new Decimal(10.0);
Operand d  = new Int(20);

Operand x = a.mult(b).mult(c).mult(d);
Operand y = b.mult(a);

System.out.println(x); //yields 20000.0
System.out.println(y); //yields 100

Operand m = new Int(1);
Operand n = new Int(9);

Operand q = m.sub(n); 
Operand t = n.sub(m); 

System.out.println(q); //yields -8
System.out.println(t); //yeilds 8

The key points here are:

• Every operand implementation works in a similar way to a visitor pattern, in the sense that every operand implementation contains a dispatch function for every possible combination that you can get.
• The tricky part is the method that acts on any Operand. This is the place where we exploit the visitor dispatch power, because we know the exact type of this, but not the exact type of that, so we force the dispatch by doing that.method(this) and problem solved!
• However, since we invert the order of the evaluation, this has a problem with arithmetic operations that are not commutative, like the subtraction. That's why I do subtraction using addition instead (i.e. 1-9 equates to 1 + -9). Since addition is commutative.

And there you have it. Now I kind of found a solution to the specific example, but I have not provided a good solution to the multiple dispatch problem you originally had. That's why I said the example was not good enough.

Perhaps you could provide a better example, like the one in the Wikipedia page for Multiple Dispatch.

However, I think the solution will probably always be, reduce the problem to a series of single dispatches solved with some sort of visitor pattern like the one I did. If I have time, I will try to give it a shot later to a more general answer and not just this specific example.

But hopefully this post helps to foster further discussion and with luck it is step in the direction of the actual answer.

Answer 3

uncle bob did this:

 // visitor with triple dispatch. from a post to comp.object by robert martin http://www.oma.com
    /*
    In this case, we are actually using a triple dispatch, because we have two
    types to resolve.  The first dispatch is the virtual Collides function which
    resolves the type of the object upon which Collides is called.  The second
    dispatch is the virtual Accept function which resolves the type of the
    object passed into Collides.  Now that we know the type of both objects, we
    can call the appropriate global function to calculate the collision.  This
    is done by the third and final dispatch to the Visit function.
    */
    interface AbstractShape
        {
        boolean Collides(final AbstractShape shape);
        void Accept(ShapeVisitor visitor);
        }
    interface ShapeVisitor
        {
        abstract public void Visit(Rectangle rectangle);
        abstract public void Visit(Triangle triangle);
        }
    class Rectangle implements AbstractShape
        {
        public boolean Collides(final AbstractShape shape)
            {
            RectangleVisitor visitor=new RectangleVisitor(this);
            shape.Accept(visitor);
            return visitor.result();
            }
        public void Accept(ShapeVisitor visitor)
            { visitor.Visit(this); } // visit Rectangle
        }
    class Triangle implements AbstractShape
        {
        public boolean Collides(final AbstractShape shape)
            {
            TriangleVisitor visitor=new TriangleVisitor(this);
            shape.Accept(visitor);
            return visitor.result();
            }
        public void Accept(ShapeVisitor visitor)
            { visitor.Visit(this); } // visit Triangle
        }

    class collision
        { // first dispatch
        static boolean Collides(final Triangle t,final Triangle t2) { return true; }
        static boolean Collides(final Rectangle r,final Triangle t) { return true; }
        static boolean Collides(final Rectangle r,final Rectangle r2) { return true; }
        }
    // visitors.
    class TriangleVisitor implements ShapeVisitor
        {
        TriangleVisitor(final Triangle triangle)
            { this.triangle=triangle; }
        public void Visit(Rectangle rectangle)
            { result=collision.Collides(rectangle,triangle); }
        public void Visit(Triangle triangle)
            { result=collision.Collides(triangle,this.triangle); }
        boolean result() {return result; }
        private boolean result=false;
        private final Triangle triangle;
        }
    class RectangleVisitor implements ShapeVisitor
        {
        RectangleVisitor(final Rectangle rectangle)
            { this.rectangle=rectangle; }
        public void Visit(Rectangle rectangle)
            { result=collision.Collides(rectangle,this.rectangle); }
        public void Visit(Triangle triangle)
            { result=collision.Collides(rectangle,triangle); }
        boolean result() {return result; }
        private boolean result=false;
        private final Rectangle rectangle;
        }
    public class MartinsVisitor
        {
        public static void main (String[] args)
            {
            Rectangle rectangle=new Rectangle();
            ShapeVisitor visitor=new RectangleVisitor(rectangle);
            AbstractShape shape=new Triangle();
            shape.Accept(visitor);
            }
        }