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.

Swift’s for loops avoid an easy mistake with variable capture

This article from a while back points out “the biggest mistake everyone makes with closures” in Ruby, Python, Perl and Javascript.1

Try running this code in Ruby, which counts i up from 1 to 3 creating a closure each time which returns the value of i:

a = []
for i in 1..3
  a.push(lambda { i })
end

for f in a
  print "#{f.call()} "
end

and it prints out the possibly surprising value 3 3 3.

Using more “functional” constructs doesn’t always save you. This Python also prints all 3s:2

a = [lambda: i for i in xrange(1, 4)]
for a in f:
  print f()

The article goes on to suggest some workarounds.

Here is the equivalent in Swift:

var a: Array<()->Int> = []

for i in 1...3 {
  a.append( { i })
}

for f in a {
  println("\(f()) ")
}

and happily, this prints 1 2 3.

Note, this also works with references to objects, so if you subsituted a for over a sequence of objects instead of Ints in the code above, each closure would capture a reference to a different object.

Be careful though, this applies to for loops but not to other loops like while or the C-style for(;;), so:

var i: Int = 0
while(++i <= 3) {
    a.append( { i })
}

for f in a {
    print("\(f()) ")
}

prints out 3 3s.

Why is this? Is this a special hack to make for...in behave less surprisingly? To understand why it does this, you need to realize that this:

for i in 1...3 {
  a.append( { i })
}

is just a shorthand equivalent to writing this code using the source sequence’s generator:

var g = (1...3).generator()
while let i = g.next()
  a.append( { i })
}

The answer to our question lies in the let i =, which declares a fresh variable i for each iteration of the loop, hence if you capture i, it will retain its value at the end of the block. If you use this form of while loop, you’ll get the same results as with the for...in version.


  1. Go here for an epic list of how other languages handle this issue. 
  2. The Ruby each will do something similar in version 1.8, though it was altered in 1.9 to behave differently which is somehow more scary. 

Default Parameters in Swift – Dynamically or Statically Bound?

edit: after this post originally went up, the Swift dev team confirmed on the forums that default parameters should be dynamically bound. However, as of Swift 1.1, they’re still statically bound.

Quick quiz. What does the following code do?

class Shape {
  func draw(colour: String = "Red") { 
    println("\(colour) shape")
  }
}

let s1 = Shape()
s1.draw()

It prints Red shape, right? No argument supplied, so the default value of Red is used.

Ok what about this?

class Circle: Shape { 
  override func draw(colour: String = "Blue") { 
    println("\(colour) circle") 
  } 
}

let s2 = Circle()
s2.draw()

It should Blue circle. No surprises there. Again no argument, but the overridden function defaults to a different color and prints a different shape.

Ok finally, what about this?

let s3: Shape = Circle()
s3.draw()

Blue circle again, right? s3‘s static type is the base class, but it points to an inherited class. Polymorphism means the overridden function runs, so it should be just like the previous example.

If Swift bound default parameters dynamically, sure. But as of Swift 1.1, it behaves like C++,1 and you actually get Red circle. This is because parameters are bound statically not dynamically. Similarly, which overloaded function is chosen is also done statically – as seen in our series on Swift overload resolution

Why is C++ like this? Because default arguments are determined at compile time, not at run time. So while the correct function is applied, the default argument is looked up via the static type of s3, which is a Shape not a Circle. This could lead to some quite surprising behavior, which is why this is Item 37 of the Effective C++ book, which has more info on why it is this way (it’s related to run-time performance) and some workarounds to avoid it.


  1. I wrote the same code in C++ to double-check this and, holy cow, writing some simple C++ was painful after a week of Swift.