Skip to content

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.

{ 4 } Comments

  1. Baiss Eric Magnusson | May 30, 2015 at 12:45 am | Permalink

    From the ACM proceedings:
    “An object is a programming entity with a lifespan of its own.”
    Swift still has a way to go.

  2. Jeremy Gibbons | June 2, 2015 at 10:04 am | Permalink

    Unless I’ve missed something, you’re describing only immutable objects here: your objects are mappings from the values of instance variables (r-values) to method sets, not from their addresses (l-values). Then indeed you have a kind of functional programming; but one may argue that it’s not really OO programming as usually practised. If you try to give a similarly clean and simple explanation of mutable objects, including constructor methods that may call other methods but are never supposed to reveal uninitialised objects, I predict that you’ll find it rather more difficult.

    Which is to say, “immutable OOP is a simple, easy-to-use subset of FP”. FP subsumes the well-behaved bits of OO.

  3. Graham | June 2, 2015 at 11:05 am | Permalink

    In this case, all of the objects are indeed immutable. Swift has the var keyword to introduce a variable (i.e. mutable) value, so if the constructor introduces a var which the returned object then closes over (or for the same reason, if there’s one in the global context) you end up with a mutable object. In fact, it’d be somewhat similar to objects in Self in that enclosed mutable variables represent data slots and selectable methods represent, well, method slots.

    I agree that this introduces a lot of difficulty in ensuring that you only ever “see” valid objects that satisfy their own invariants. That’s true in traditional, imperative OO systems too, indeed a lot of the design patterns from the 1990s can be seen as ways to force that an object is always in a well-defined state.

    I’m also with you on the distinction between “OO as practised” and “OO as intended” :). Gary Bernhardt has talked a lot about this distinction too, though I can’t find a single reference that would serve as a pithy example as it’s spread all over his Twitter timeline. The danger with that line of thinking, and a trap I’ve certainly fallen into, is constructing what Bryan O’Sullivan called a “pre-lapsarian” view of OOP in which Kay, Goldberg, Ingalls etc. “got it”, and everyone else either “didn’t get it” or is rediscovering it.

  4. Jeremy Gibbons | June 2, 2015 at 11:19 am | Permalink

    I think I’m with Bryan.

{ 1 } Trackback

  1. […] via Structure and Interpretation of Computer Programmers : Object-Oriented Programming in Functional Pro…. […]

Post a Comment

Your email is never published nor shared. Required fields are marked * Comments are moderated; please make sure that your post is civil and valuable before submitting it to improve the chance it will be accepted.