Using multiple dispatch to add different types of numbers

This is part of a series on solving Paul Graham’s accumulator problem in Swift. You can find Part 1 here.

In the previous post, we solved the requirement that our accumulator accept any kind of numeric type, and to “upgrade” the type it returns from an integer to floating point only the first time it is called with a floating point number. The solution was to use the Swift Any type:

func foo(var n: Any) -> (Any) -> Any? {
    return { incf(&n, $0) }
}

There were lots of flaws with this approach, the worst of which was the loss of type-safety that comes with using Any. The user of foo can pass anything into the accumulator – a String, a Range, any user-defined Class. Our solution to this was to have incf return nil for types it didn’t understand. But it would be much better to rewrite foo so that it just wasn’t possible to call it with an unsuitable type in the first place.

One way would be to create a Number class and use that. But then users of the accumulator would have to explicitly convert their variables and literals to this class before using it (as Swift doesn’t support implicit conversion).

Intead, we can create a protocol Number, and extend both Int and Double to support it. Something like this:

protocol Number {
    func plus(rhs: Number) -> Number
}

extension Int : Number { ... }
extension Double : Number { ... }

Then rewrite the accumulator generator to use it instead of Any:

func foo(var n: Number) -> (Number) -> Number {
    return { n = n.plus($0); return n }
}

Now foo can be called with an Int or a Double, but can’t be called with any other type that doesn’t implement the Number protocol. The method plus would act polymorphically, adding either kind of number to an existing one, and upgrading from Int to Double when needed.

How do we implement the plus method? It needs to execute different code depending on both the type of the current value and the type of the value being added to it. That is, the behaviour of plus needs to be polymorphic with respect to two different objects, not just one. This requires something called “multiple dispatch” (in this case, specifically double dispatch).

Ordinarily, Swift (and most other OO languages) only alter their behaviour at runtime based on one object – the object who’s method is being called. This is known as single dispatch. But there is a technique that allows us to implement double dispatch. First, we need to add more methods to the Number protocol:

protocol Number {
    func plus(rhs: Number) -> Number
    func plus(rhs: Int) -> Number
    func plus(rhs: Double) -> Number
}

Then, we implement them for Int and Double like this:

extension Int : Number {
    func plus(rhs: Number) -> Number {
        // re-call plus with an Int parameter this time
        return rhs.plus(self)
    }

    func plus(rhs: Int) -> Number {
        // an Int plus an Int is an Int
        return self + rhs
    }

    func plus(rhs: Double) -> Number {
        // an Int plus a Double is a Double
        return Double(self) + rhs
    }
}

extension Double : Number {
    // re-call plus with a Double parameter this time
    func plus(rhs: Number) -> Number {
        return rhs.plus(self)
    }

    func plus(rhs: Double) -> Number {
        // a Double plus a Double is a Double
        return self + rhs
    }

    func plus(rhs: Int) -> Number {
        // a Double plus an Int is a Double
        return self + Double(rhs)
    }
}

How does this work? The interesting part is the implementation of plus that takes a Number. This calls plus again, but not recursively – instead it calls it on the right-hand side object, passing self in as a paramter. Because at this point, the code is inside a definitive type (either an Int or a Double), self will be one of those types rather than the abstract Number, and it will call one of the methods lower down.

We can easily test this works for all combinations:

let combos: Array<(Number,Number)> = [
    (1, 1),
    (1.1, 1.1),
    (1, 1.1),
    (1.1, 1),
]

for (a, b) in combos {
    println("\(a) + \(b) = \(a.plus(b))")
}

prints out:

    1 + 1 = 2
    1.1 + 1.1 = 2.2
    1 + 1.1 = 2.1
    1.1 + 1 = 2.1

Fun as this technique is, as Bjarne Stroupsrup says, “if you consider this elegant, you need to raise your standards, but it gets the task done”. Accumulators generated with this code can take either integers or floating point numbers, and ones that have only seen integers return integers, and you can’t call it with any other unsupported types.

It still suffers from similar problems to the incf solution – every time you add a new type of Number you need to alter the code quite extensively. And implementing additional operations like minus or multiply would require even more code. Looking at a solution to that will be the subject of the next in the series. Follow @AirSpeedSwift to catch it.

3 thoughts on “Using multiple dispatch to add different types of numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s