# Structure and Interpretation of Computer Programmers

I make it easier and faster for you to write high-quality software.

## Friday, May 29, 2015

### 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 `Set`s that represent contiguous ranges of `Int`s.

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

Now it’s possible to create these `Set`s 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 `Int`s. They could be anything else, including other `Set`s.

``````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 `List`s:

``````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 `List`s? 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 `List`s. 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 let`s 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 `String`s. 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()
)
}
ListWithDescriptionSelectors<String>(count: nil,
at: nil,
describe: describe))
}

let awesomeGreeting =
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.

posted by Graham at 00:39

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

Comment by Baiss Eric Magnusson — 2015-05-30 @ 00:45

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

Pingback by Object-Oriented Programming in Functional Programming in Swift | Dinesh Ram Kali. — 2015-06-01 @ 21:34

3. 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.

Comment by Jeremy Gibbons — 2015-06-02 @ 10:04

4. 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.

Comment by Graham — 2015-06-02 @ 11:05

5. I think I’m with Bryan.

Comment by Jeremy Gibbons — 2015-06-02 @ 11:19