Dynamic Method Dispatch in Object-Oriented Programming in Functional Programming in Swift

In the previous episode, I said that objects are functions that map their ivars onto methods. However, the objects that I demonstrated in the post were tables, structures of functions that closed over the ivars, like this:

struct List<T> {
  let count: () -> Int
  let at: (Int) -> T?
}

Functions and tables are actually interchangeable, so this is not a problem and there’s no sleight of hand.

Here’s a simple example: imagine a function that maps Booleans (instances drawn from the set Boolean) to integers (instances drawn from the set Int):

enum Boolean {
 case False
 case True
}

func intValue(b : Boolean) -> Int
{
  switch b
  case .False:
    return 0
  case .True:
    return 1
}

This is, notation aside, identical to encoding the map in a table:

struct BooleanIntMap {
  let False = 0
  let True = 1
}

That’s the state that my objects were in at the end of the previous post. So let’s complete the story, and turn these objects from tables into functions.

Three Minute Hero

Along the way, I’ll fix a deficiency in the previous version of these objects. When you got an object, it was in the form of a table of all of its methods, but typically you only want to call one at a time. In Objective-C, you pass an object a selector and it returns the appropriate method which you then call (well, that’s how the GNU runtime works. The NeXT and Apple runtimes jump right into the returned function). See? An object really is a function that maps its variables onto the methods you want.

There are a limited (for now) number of legitimate selectors to send to an object, so they can easily be represented with an enumeration.

enum DynamicListSelectors {
  case count
  case at
}

Now it gets a bit complicated (Objective-C and Smalltalk are also this complicated, but use a different notation that hides it from you). My list object will be a function that maps these selectors onto methods, but the two methods have different signatures. I therefore need a type which can represent (function with the .count signature) OR (function with the .at signature).

In addition to representing enumerated constants, Swift’s enums can also sum types. Remember that a type is just a set of that type’s instances: a sum type is the union of two (or more) type sets. So the list function can return something of this type:

enum DynamicList<T> {
  case count (() -> Int)
  case at ((Int) -> T?)
}

There are two things to do now. One is to define the function that maps from a selector onto an instance of this sum type: this is our message dispatch function, or more succinctly, our object.

func EmptyDynamicList<T>()(_cmd: DynamicListSelectors) -> DynamicList<T>
{
  switch _cmd {
  case .count:
    return DynamicList<T>.count({ return 0 })
  case .at:
    return DynamicList<T>.at({ (_) in return nil})
  }
}

But now we need to pull apart the enumeration in the client code to find the message implementation and invoke it. In principle, Smalltalk, Objective-C and other dynamic O-O languages have to do this too (in ObjC it works by knowing how to use function pointers of different types, and treating all the methods as function pointers), but the notation or loose type system hides it from you.

let emptyCountIMP : DynamicList<Int> = EmptyDynamicList()(_cmd: .count)
switch emptyCountIMP {
case .count(let f):
  f() // returns 0
default:
  assertionFailure("Implementation does not match selector")
}

Doing that every time you call a method would get boring quickly, averted by defining a couple of convenience functions.

func countOfList<T>(list: (DynamicListSelectors) -> DynamicList<T>) -> Int
{
  switch list(.count) {
  case .count(let f):
    return f()
  case .at(let f):
    assertionFailure("Implementation does not match selector")
    return 0 //unreached
  }
}

func elementInListAtIndex<T>(list: (DynamicListSelectors) -> DynamicList<T>, index: Int) -> T?
{
  switch list(.at) {
  case .at(let f):
    return f(index)
  case .count(let f):
    assertionFailure("Implementation does not match selector")
    return nil //unreached
  }
}

Now it should be easy enough to use a more complex implementation of the list class. Here’s a linked list, as before the tail is itself a linked list (which is now a function mapping a selector to an implemetation).

func DynamicLinkedList<T>(head: T,
                          tail: (DynamicListSelectors) -> DynamicList<T>)
                         (_cmd: DynamicListSelectors) -> DynamicList<T>
{
  switch _cmd {
  case .count:
    return DynamicList<T>.count({
      return 1 + countOfList(tail)
    })
  case .at:
    return DynamicList<T>.at({ (i) in
      if i < 0 {
        return nil
      }
      if i == 0 {
        return head
      }
      else {
        return elementInListAtIndex(tail, i - 1)
      }
    })
  }
}

let unitList = DynamicLinkedList("Wow", EmptyDynamicList()) //(Function)
countOfList(unitList) // 1
elementInListAtIndex(unitList, 0) // "Wow"
elementInListAtIndex(unitList, 1) // nil

Draw the rest of the owl

Going from here to Smalltalk is a small matter of types. The object defined above is a total function of a small number of list message selectors to a small number list method implementations: every selector resolves to a method.

A Smalltalk object is also a function from selectors to methods, but from the range of all possible selectors (which are strings) to the domain of all possible function types. [Aside: as C doesn’t have closures, Objective-C’s message lookup domain is all possible function types that receive an object and selector as the first two arguments.] You probably didn’t write implementations for every possible selector, so most of these messages will be resolved to the doesNotRecognize: implementation which is where Smalltalk does its forwarding and dynamic method resolution, similar to Objective-C’s forwardInvocation: and Ruby’s method_missing.

The awesome power of the runtime. Now available in Swift.

About Graham

I make it faster and easier for you to create high-quality code.
This entry was posted in FP, OOP. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.