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.

Object-Oriented Programming in Functional Programming in Swift

The maths behind functional programming predates computers. Once people had some experience with both of these things, they stripped them down and created object-oriented programming. It’s still possible to jettison a lot of the features of functional programming and work with the object-oriented core, and in this post I’ll do so using a subset of the Swift programming language.

Step One: Useing you’re type’s good

I’ll use this particular definition of a type: it’s a set. I could define a type completely as a set of constants:

Boolean :: {True, False}

or using constructors:

Natural :: {Zero, Successor(N : Natural)}

An element drawn from the set is an instance of the type. So True is an instance of Boolean, and Successor(Successor(Zero)) is an instance of Natural.

A particular, um, type of type is the “product” type, which represents a combination of other types. A tuple is product type: a tuple of type (Boolean, Natural) represents an instance of Boolean and an instance of Natural. The set (Boolean, Natural) or Boolean x Natural is the set of all possible combinations of Boolean and Natural.

Crucially, for the following argument, a struct is also a product type. Has been since before C was created, will be forever.

A function is a map from an input type to an output type. Really there’s more nuance in the world than that, particularly around whether the function works for all instances of the input type and whether there’s a one-to-one mapping between input and output instances, but that’s not relevant right now. All we need to know is that given an instance of the input type, applying a function to it will always result in a particular instance of the output type.

f :: InputType -> OutputType

You may think that you’ve seen functions with more than one input argument: that’s the same (roughly) as a function that takes a single tuple argument.

Step Two: Know what an object is

Defining instance variables as the values “known” inside an object, and methods as functions attached to an object that have access to its instance variables, I could say this:

An object is a collection of instance variables and methods that act on those instance variables.

But I want to put this a different way.

Given a collection of values, an object gives you a collection of methods that yield particular results based on those values.

But I want to put this a different way.

Given the input of a product type drawn from possible instance variables, an object will return a particular member of the product type drawn from possible methods.

But I want to put this a different way.

An object is a function that maps from instance variables to methods.

Step Three: Build an object

As the output of an object is a collection of methods, you can define an object entirely by its methods. In object-oriented programming, this is called “data hiding” or “encapsulation” and means that you can’t see what went into making the objects work this way, only that they do.

Starting small, think about the set data type. You only ever want to do one thing with a set: discover whether a particular element is contained in the set. That means that, for example, the type of a set of integers is equivalent to this type of function (in Swift syntax):

typealias Set = (Int) -> Bool

Now it’s possible to build trivial sets. Here’s one that contains no integers, and one that contains all the integers:

let emptySet : Set = { (_) in return false }
let universe : Set = { (_) in return true }

It’s easy to use the one method that these objects define: just call the objects as functions.

emptySet(12) //false
universe(12) //true

Step Four: Add some instance variables

I want to keep my Set method signature, because I want the objects I create to all be compatible (I really want them to all be of the same class). But I also want to be able to store and use instance variables from within the Set‘s method, so I can build some more interesting sets.

I’ll build a Set constructor, a function that returns properly-configured instances of Set. That constructor can close over the instance variables, therefore making them available from within the method. Here’s a constructor for Sets that represent contiguous ranges of Ints.

func RangeSet(lowerBound:Int, upperBound:Int)->Set
{
  return { (x) in (x >= lowerBound) && (x <= upperBound) }
}

Now it’s possible to create these Sets and use their method:

RangeSet(3, 7)(2) //false

let mySet = RangeSet(0, 2) //(Function)
mySet(1) //true
mySet(3) //false

Of course, the instance variables don’t have to be Ints. They could be anything else, including other Sets.

func UnionSet(setOne:Set, setTwo:Set) -> Set
{
  return { (x) in (setOne(x) || setTwo(x)) }
}

UnionSet(RangeSet(0, 2), RangeSet(3, 5))(4) //true

func IntersectSet(setOne:Set, setTwo:Set) -> Set
{
  return { (x) in (setOne(x) && setTwo(x)) }
}

IntersectSet(RangeSet(0, 5), RangeSet(3, 7))(5) //true

Even when a Set has another Set as an instance variable, it cannot see how that Set was constructed or what instance variables it has. It can only see the Set‘s method, because the encapsulation is working.

Step Five: Add more methods

Not all things that we might want to use as objects can be expressed as one method. A list has two methods: a count of the number of items it holds and a method to get the item at a given index. A list object therefore needs to represent the product of (count method, at method) and to let clients select which method they want to use from that product. This product could be expressed as a tuple:

typealias ListSelectors = (count:() -> Int, at:Int->AnyObject?)

Or (perhaps more usefully because the compiler for Swift allows generics in this case) as a struct:

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

Now it’s possible to rely on the old trick of making constructor functions that return Lists:

func EmptyList<T>() -> List<T>
{
  return List(count: {return 0}, at: {(_) in return nil})
}

including the use of instance variables captured by closing over them:

func LinkedList<T>(head:T, tail:List<T>) -> List<T>
{
  return List(count: {return 1 + tail.count()},
    at: { index in return (index == 0) ? head : tail.at(index - 1)})
}

Step Six: Inherit from objects

The List is cool, but it’d be nice to be able to describe lists. I could create a function:

func describeList(list:List<SomeType>) -> String

but wouldn’t it be better to add description as a method on Lists? That would make the List type look like this:

struct ListWithDescription<T> {
  let count: () -> Int
  let at: (Int) -> T?
  let describe: () -> String
}

OK, but I don’t want to go back to all of my previous List implementations and add describe methods to them. What I really want to do is to add this method as an extension to Lists. I’ll define a type that includes a describe method and optionally implementations of the other methods too.

struct ListWithDescriptionSelectors<T> {
  let count: (() -> Int)?
  let at: ((Int) -> T?)?
  let describe: () -> String
}

Given a List and some ListWithDescriptionSelectors, it’s possible to build a ListWithDescription that knows how to describe itself and either inherits count and at from its List or overrides them itself.

func SubtypeListByAddingDescription<T>(prototype: List<T>,
  overrides: ListWithDescriptionSelectors<T>) ->
  ListWithDescription<T>
{
  let countImplementation : () -> Int
  if let count = overrides.count {
    countImplementation = count
  } else {
    countImplementation = prototype.count
  }
  let atImplementation : (Int)->T?
  if let at = overrides.at {
    atImplementation = at
  } else {
    atImplementation = prototype.at
  }
  return ListWithDescription<T>(count: countImplementation, at:     atImplementation, describe: overrides.describe)
}

(The slight complication with all the if lets is because the Swift compiler at time of writing wasn’t happy with using the ?? operator in their place.)

It’s now possible to put this into practice. In order to work with the elements in a List I need to know more about what type of thing they are, so here’s a specialisation of ListWithDescription that can describe a List of Strings. As ever, it has no special access to the instance variables of the List it extends and can only work with it through the published methods.

func ListOfStringsWithDescription(strings: List<String>) ->
  ListWithDescription<String>
{
  let describe: () -> String = {
    var output = ""
    for i in 0..<strings.count() {
      output = output.stringByAppendingString(strings.at(i)!)
      output = output.stringByAppendingString(" ")
    }
    return
      output.stringByTrimmingCharactersInSet(
        NSCharacterSet.whitespaceCharacterSet()
      )
  }
  return SubtypeListByAddingDescription(strings,
    ListWithDescriptionSelectors<String>(count: nil,
      at: nil,
      describe: describe))
}

let awesomeGreeting =
  ListOfStringsWithDescription(LinkedList("Hello,",
    LinkedList("World",
      EmptyList())))

awesomeGreeting.at(1) //"World"
awesomeGreeting.describe() //"Hello, World"

Next Step: Draw some conclusions

Object-Oriented Programming is a simple, easy to use subset of Functional Programming.

Open Step: Cite references

The objects in this article (like the objects in Microsoft COM or my earlier BlockObject) are Procedural Data Types, which I discovered in Object-Oriented Programming Versus Abstract Data Types and User-defined types and procedural data structures as complementary approaches to data abstraction. The idea of objects as closures first appeared, to my knowledge, in Objects as Closures: Abstract Semantics of Object Oriented Languages. The last two of these articles were brought to my attention by my colleague Peter O’Hearn after a discussion on the topic of functional/O-O duality. I am indebted to him for his help in drawing this article out of me.

After Step: Finish this idea

This journey, as we say at Facebook, is 1% complete. There’s plenty more to explore here, and I’m not sure the explanation is as clear as it could be. It is, however, written down, which is a start.

A subtle [mis]understanding of monads

As I said when talking about Learning Phases, one of the things that happens when I’m trying to learn a new thing is that I build an analogy in terms of something I do understand. This can be dangerous when the analogy is wrong. I’m currently hanging on to the analogy that follows, so I’m publishing it as a straw man argument in the hope that those with more experience than me can critique it and help improve my understanding.

Proposition: Monads are what objects are supposed to look like

Throw away everything you know about Object-Oriented programming, particularly if you know Objective-C, Java, C++ or C#. Now go and read the first edition (the straightforward one, not the detective-novel second edition) of Object-Oriented Software Construction by Bertrand Meyer. You’ll find the principle of Command-Query Separation, that an object’s interface should provide distinct facilities for manipulating and investigating that object. Consider an object as an enclosed module analogous to an electronic circuit[*], with switches you can flip and lights you can observe. Watching a light shouldn’t also have the effect of flipping a switch, and you shouldn’t have to flip a switch in order to watch a light.

How could a language support that principle? Clearly imperative programming is too general, as it lets me mix commands and queries in the same place. What I need is an operation that lets me bind sequential commands together, taking an object in state a and a function that turns state a into state b and creating an object in state b. I also need an operation that lets me run a query, taking an object in state a and returning a value corresponding to a. Given those, and assuming the single responsibility principle has driven me to the point where my object does one thing and can be represented by a single command and query, then the interface on my object is complete.

Interestingly and usefully, except in the (common-ish) special case where my object needs to talk to the world, objects defined in this way are completely understandable mechanistically. The same sequence of commands applied to the same constructor will always yield the same value on query.

But that is, I think, what Monads are supposed to be: things that bind commands into sequences and allow inspection at points in the sequence. As stated in this post’s preamble, I’m not fully confident of this, and may be over-applying an analogy to replace a thing I don’t understand with the comfort of the thing I do. I’d be interested in hearing informed critique on the argument.

Not the other monads

When Alan Kay said that objects are monads, he was talking about Leibniz monads as previously discussed on this blog.

[*] An analogy already present in the proceedings of _that_ 1968 NATO conference, and drawn to extremes by Brad Cox in Object-Oriented Programming: An Evolutionary Approach.

Update

The discussion among my monadically-inclined friends on Facebook indicates that this analogy is incomplete. Yes, monads can be used like that, but they need not be used like that. Counter-examples included the reverse state monad in which state flows backwards, and the TARDIS monad in which state can flow in both directions.