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.