Functional Programming in Object-Oriented Programming in Functional Programming in Swift

The objects that I’ve been building up over the last few posts have arbitrarily broad behaviours. They can respond to any selector drawn from the set of all possible strings.

As with all art, beauty is produced by imposing constraints. An important class (pardon the pun) of objects only has a meaningful response to one selector (value or, if it takes an additional argument, value:) which causes the object to do the one thing it knows how and return a result.

In many object-oriented programming circles, including the Smalltalk world, these objects are called blocks. They’re useful because they enable multiple uses of the same algorithm to be extracted into a single place, with the block customising the significant activity that happens in the algorithm. As an example, iterating an array to square numbers and iterating an array to load images from paths both involve iterating an array. The algorithm that iterates an array can be expressed in a form that accepts a block that does the work: squaring some numbers or loading some images.

Without going in to the details of the implementation (which is a collection of classes in the Objective-Swift system), here’s how a block could be used:

let myArray = newObject(NSArray(Integer(1, proto: o), Integer(2, proto: o),
  Integer(3, proto: o), Integer(4, proto: o)))
let evens = (myArray,"filter:") ✍ OneArgBlock({ obj in
  return (ℹ︎(obj)! % 2) == 0 ? True : False
  }, proto: o)
ℹ︎(evens→"count") // 2
📓((evens,"objectAtIndex:") ✍ Integer(0, proto: o)) // "2"
📓((evens,"objectAtIndex:") ✍ Integer(1, proto: o)) // "4"

The NSArray→filter: selector takes a block, and for each element in the array it sends the value: message with the element as the argument. In fact, it passes another block to the result of this block. Both True and False respond to the ifTrue: message. True→ifTrue: executes its argument, False→ifTrue: doesn’t.

Now we already have a name for the concept of an object that does exactly one thing, returning some result based on its input parameters. That’s a function. Yes, we finally got there:

Swiftception

So just as Object-Oriented Programming was a restricted application of a subset of Functional Programming, we can see Functional Programming as a restricted application of a subset of Object-Oriented Programming.

And that’s pretty much the point of this series of posts. These two ways of thinking about computer programs get you to the same place, as long as you apply the thinking. Neither is a silver bullet, neither is subsumed nor obsoleted by the other.

Coda

Now imagine a block that takes a selector and returns another block…

Classes in objects in object-oriented programming in functional programming in Swift

So far, Objective-Swift objects have used prototypical inheritance, in which they supply some methods but also know about another object to which they can forward messages they don’t understand themselves. This pattern is used in languages like Self, JavaScript and Io but is not common to other languages that also call themselves object-oriented programming languages.

Most OO languages have the idea of a “class” that supplies the methods for each object. An object knows that it “is a” specific realisation of its class, so when it receives a message it can look up the corresponding method in that class’s method table.

Like this.

typealias Class = Dictionary

// define a "Non-Standalone" Object that relies on a class for its methods.

let NSObject : Class = [ "description": IMP.description({ _ in return "An NSObject" })]

func newObject(isa : Class) -> Object {
  return { aSelector in
    if let anImplementation = isa[aSelector] {
      return anImplementation
    } else {
      return IMP.methodMissing({ _ in
        print("Does not recognize selector \(aSelector)")
        return nil
     })
    }
  }
}

let anObject = newObject(NSObject)
📓(anObject) // "An NSObject"

Objects returned by the newObject() function look up their methods in their class dictionary, a table of method implementations for the corresponding selectors.

Not like that.

Mapping things to other things, that’s a function, isn’t it? And indeed there already is a type of function that takes selectors to methods, the object. A class should just be an object. Let’s try that again.

typealias Class = Object

let NSObject : Class = { aSelector in
  switch aSelector {
  case "description":
    return IMP.description({ _ in return "An NSObject" })
  default:
    return IMP.methodMissing({ _ in
      print("Instance does not recognize selector \(aSelector)")
      return nil
    })
  }
}

func newObject(isa : Class) -> Object {
  return { aSelector in
    return isa(aSelector)
  }
}

let anObject = newObject(NSObject)
📓(anObject) // "An NSObject"

Great. Classes are objects, just as we’re used to. And indeed, a class could get its own methods from another class: a metaclass.

Notice that class-based objects walk and quack like the earlier, prototypical objects, so interoperate completely. That’s the point of message passing. No object needs to know how any other object works, just that it will respond to messages.

That’s what makes all of the bridges that let other languages interoperate with Objective-C. As long as objc_msgSend() can find your code and run it, we’re all good. In Objective-Swift, as long as passing you a selector gives me an IMP, we’re all good.

Instance variables.

Methods defined by classes should be able to see the object’s instance variables. The instance variables should, per their definition, be unique to each instance. However the best place to define them is in the class, for three reasons:

  1. The class knows which instance variables its methods expect to be present.
  2. The class’s constructor function captured the values (or the initial values, if they’re mutable) of the instance variables.
  3. If I’m subclassing, I want to be able to add the subclass’s instance variables to the superclass’s, without having to redefine the whole shebang.

So a class should tell its objects what instance variables it needs, and the values. Now, how should an instance look up its instance variables? We need to go from the name of an instance variable to its value, and I’ll save us both some embarrassment by cutting straight to the conclusion that an object is a great way to do this.

Each object in the class-based system will therefore be composed of two others: the class encapsulates what the object is and the methods it responds to, while the instance variable store encapsulates what the object is made of and what variables it has. Both are accessed through selectors, in a design choice that follows Eiffel and its Uniform-Access Principle (and the later Self language).

The same selector cannot refer both to a method and an ivar, because they’re both in the same namespace. One of them has to win, and in this case I’ve chosen the instance variable lookup to win.

Here’s a non-standalone version of Point, with its two instance variables. In the code shown here, o is a previously-defined object on which all methods are missing.

func NSPoint(x:Int, y:Int) -> Class {
  let superclass = NSObject
  let ivars:Object = { variableName in
    switch variableName {
    case "x":
      return .method({_ in return Integer(x, proto: o)})
    case "y":
      return .method({_ in return Integer(y, proto: o)})
    default:
      return (superclass→"instanceVariables")!(variableName)
    }
  }
  let thisClass:Class = { aSelector in
    switch aSelector {
    case "instanceVariables":
      return .method({_ in return ivars})
    case "distanceFromOrigin":
      return .method({(this, _cmd, args:Object...) in
        let thisX = ℹ︎(this→"x")!
        let thisY = ℹ︎(this→"y")!
        let distance = sqrt(Double(thisX*thisX + thisY*thisY))
        return Integer(Int(distance), proto: o)
      })
    default:
      return superclass(aSelector)
    }
  }
  return thisClass
}

let aPoint = newObject(NSPoint(3,y: 4))
📓(aPoint) // "An NSObject"
📓(aPoint→"x") // "3"
📓(aPoint→"distanceFromOrigin") // "5"

Super calls.

You can see that NSPoint is a subclass of NSObject, although this isn’t amazingly useful. NSPoint gets all zero of NSObject‘s instance variables, and the not-particularly-descriptive description method.

In what might be the worst design choice of this blog, I’ll say that a 3D point is a specialisation of a 2D point. I’ll need to override distanceFromOrigin to calculate the distance in three dimensions, but I can use the result from the superclass’s two-dimensional calculation to do this.

As with Objective-C, this will require a different method lookup system, one that says “ask your superclass” instead of “ask yourself”. To do this, the object must know what its superclass is: it can ask its class. Here is a new method on NS3DPoint:

    case "superclass":
      return .method({ _ in return superclass })

Now, because I’m really running out of ideas on how to name these operators, here are some doubly-long operators that call into the superclass for an object:

infix operator .... {}

func .... (receiver: Object?, _cmd:Selector) -> IMP? {
  guard let this = receiver else { return nil }
  let method = (this→"superclass")!(_cmd)
  switch(method) {
  case IMP.methodMissing(let f):
    return f(this, _cmd)...._cmd
  default:
    return method
  }
}

infix operator →→ {}

func →→ (receiver: Object?, _cmd:Selector) -> Object? {
  guard let imp = receiver...._cmd else { return nil }
  switch imp {
  case .method(let f):
    return f(receiver!, _cmd)
  default:
    return nil
  }
}

Now, with all of this notation in place, it’s possible to create a method NS3DPoint→distanceFromOrigin that both overrides its parent method, and uses that overridden method in its calculation. Here’s the method:

    case "distanceFromOrigin":
      return .method({(this, _cmd, args:Object...) in
        let twoDDistance = ℹ︎(this→→"distanceFromOrigin")!
        let thisZ = ℹ︎(this→"z")!
        let distance = sqrt(Double(twoDDistance*twoDDistance + thisZ*thisZ))
        return Integer(Int(distance), proto: o)
      })

Here it is in use:

let anotherPoint = newObject(NS3DPoint(10, y: 12, z: 14))
📓(anotherPoint→"distanceFromOrigin") // "20"

Conclusion

In many “classical” object-oriented programming systems, classes are just objects, which instances can use to find the methods they respond to. If you’ve already got objects that don’t use classes, it’s possible to make objects that do use classes by giving each object a class object. You need somewhere to hold the instance variables for an object, and it happens that objects are good for that too.

More useful to notice is that objects are really just a way to do late binding of functions to their names. It doesn’t really matter what rules you use, as long as the result is a map of names to functions you’ve got yourself an object that will work with other objects.

Mutable objects in immutable objects in object-oriented programming in functional programming in Swift

I didn’t realise this at the time, the previous entry wasn’t the last Objective-Swift post.

The inheritance mechanism in ObjS is prototypical, meaning that an object inherits from a single other object rather than getting its behaviour from a class. This is the same system that Self and languages that, um, inherit its approach use.

This form of inheritance gives us two capabilities: decorating an object by attaching new methods, or updating an object by shadowing existing methods. And that means that setting a variable can be mimicked by returning an object where the accessor for that variable has been overridden. So in fact the objects in this system won’t be mutable at all, but they will have mutators that return replacement values.

It sounds weird, but there are reasons to really do this. In Postscript, you can mimic variables by creating named functions that just push a value onto the stack. Rather than mutating the data, you “set” the variable by rebinding the name to a function that pushes the updated value.

Digression: updating the dispatch system

In rewriting setters to be immutable I also noticed it was possible to consolidate the “accessor” and “mutator” implementation types into a single type, using variadic arguments. I have genuinely no idea why I didn’t realise that before, when the type of an ObjC method is usually expected to be (id, SEL, id...) -> id.

enum IMP {
  case method((Selector->IMP, Selector, Selector->IMP...)->(Selector->IMP)?)
  case asInteger((Selector->IMP, Selector, Selector->IMP...)->Int?)
  case methodMissing((Selector->IMP, Selector, Selector->IMP...)->(Selector->IMP)?)
  case description((Selector->IMP, Selector, Selector->IMP...)->String?)
}

The asInteger and description types gain variadic arguments but still need to be present so you can exit the O-O type system and get back to Swift types. For the moment, methodMissing is still modelled as a separate case in the enumeration, even though it has the same type as a regular method.

Mutation as a function

Given an object, a selector to override, and the replacement value, return a new object that will return that value when messaged with that selector.

infix operator ☞ {}

func mutate(receiver: Object, selector: Selector, value:Object) -> Object {
  return { _cmd in
    switch (_cmd) {
    case selector:
      return .method({ _ in return value })
    default:
      return receiver(_cmd)
    }
  }
}

func ☞(message:(receiver: Object?, selector: Selector), value:Object) -> Object? {
  if let receiver = message.receiver {
    return mutate(receiver, message.selector, value)
  } else {
    return nil
  }
}

Taking the Point objects from the further advances post, but deleting their mutators, this can be used to make updated objects.

let p = Point(3, 4, o)
📓(p) // (3,4)
let p2 = (p,"x")☞(Integer(1,o))
📓(p2) // (1,4)

Mutation as a method

The same function can be used in the implementation of an Objective-Swift method. Here’s the setY: method on Points:

  return IMP.method({ (this, aSelector, args : Object...) in
    return (this, "y")☞args[0]
  })

Now a bit of notation to make calling mutator methods easier (I’m starting to run out of reasonable symbols):

infix operator ✍ {}

func ✍(message:(receiver:Object?, selector:Selector), value:Object) -> Object? {
  if let imp = message.receiver..message.selector {
    switch imp {
    case .method(let f):
      return f(message.receiver!, message.selector, value)
    default:
      return nil
    }
  } else {
    return nil
  }
}

Done.

let p3 = (p2, "setY:")✍(Integer(42, o))
📓(p3) // (1,42)

Fork me

I have put the current playground (which is written for the Swift 1.2 compiler, because I’m risk averseold fashioned) on GitHub.

Finishing the ObjS story

This gist shows the result of doing the self-threading talked about at the end of the last post. Each method implementation takes an object pointer and a selector name, just like in the real world.

That’s enough Objective-Swift for me. Yes, more could be done (mostly defining a preprocessor to make the syntax more regular) but my goal was to understand the definition of Smalltalk-style—or maybe Self-style—objects in a functional programming environment, and I think I’m there. For now.

Further Advances in Objective-Swift

Previously on SICPers, I defined objects as functions that return methods and built dynamic method dispatch in this object system. It’s time to tie up some loose ends.

Proper selectors

In languages like Smalltalk and Objective-C, an object’s range isn’t a small list of selectors like count and at:. It’s the whole of the String type.

typealias Selector = String

Now an object takes a Selector (i.e. a String) and returns a method implementation. Continuing with the type-safe theme from the previous posts, I’ll define a few different types of implementation that I might want to use.

enum IMP {
  case accessor(()->((Selector)->IMP)?)
  case asInteger(()->Int?)
  case methodMissing(()->((Selector)->IMP)?)
  case mutator(((Selector->IMP))->Void)
  case description(()->String?)
}

typealias Object = Selector -> IMP

Now I can create some proper objects.

func DoesNothing()->(_cmd:Selector)->IMP {
  var _self : Object! = nil
  func myself (selector: Selector)->IMP {
    return IMP.methodMissing({assertionFailure("method missing: \(selector)"); return nil;})
  }
  _self = myself
  return _self
}

let o : Object = DoesNothing()

func Integer(x: Int, proto: Object) -> Object {
  var _self : Object! = nil
  let _x = x
  func myself(selector:Selector) -> IMP {
    switch(selector) {
    case "asInteger":
      return IMP.asInteger({ return _x })
    case "description":
      return IMP.description({ return "\(_x)" })
    default:
      return proto(selector)
    }
  }
  _self = myself
  return _self
}

let theMeaning = Integer(42, o)

A better syntax

Usually you don’t think of method lookup as a function invocation, but rather as finding a member of an object (indeed in C++ they’re called member functions). A member-like syntax could look like this:

infix operator .. {}

func .. (receiver: Object?, _cmd:Selector) -> IMP? {
  if let this = receiver {
    let method = this(_cmd)
    switch(method) {
    case .methodMissing(let f):
      return f().._cmd
    default:
      return method
    }
  }
  else {
    return nil
  }
}

This system now has the same nil behaviour as Objective-C:

nil.."asInteger" // nil

And it also has a limited form of default message forwarding:

func Proxy(target:Object)->((_cmd:Selector)->IMP) {
  var _self : Object! = nil
  var _target = target
  func myself(selector:Selector) -> IMP {
    return IMP.methodMissing({ return _target })
  }
  _self = myself
  return _self
}

let proxyMeaning = Proxy(theMeaning)
let descriptionImp = proxyMeaning.."description"
descriptionImp!.describe() // (Enum Value)

But it’s going to be pretty tedious typing all of those switch statements to unbox the correct implementation of a method. There are two ways to go here, one is to add methods to the enumeration to make it all easier. These just unbox the union and call the underlying function, so for example:

extension IMP {
  func describe() -> String? {
    switch(self) {
    case .description(let f):
      return f()
    default:
      return nil
    }
  }
}

descriptionImp!.describe() // "42"

Or if you’re really going to town, why not define more operators?

infix operator → {}

func → (receiver: Object?, _cmd:Selector) -> Object? {
  if let imp = receiver.._cmd {
    switch (imp) {
    case .accessor(let f):
      return f()
    default:
      return nil
    }
  } else {
    return nil
  }
}

func ℹ︎(receiver:Object?)->Int? {
  if let imp = receiver.."asInteger" {
    switch(imp) {
    case .asInteger(let f):
      return f()
    default:
      return nil
    }
  } else {
    return nil
  }
}

ℹ︎(theMeaning)! // 42

Mutable Objects

There’s no reason why an object couldn’t close over a var and therefore have mutable instance variables. You can’t access the variables from outside the object in any way other than through its methods[*], even from objects that inherit from it. They’re all private.

[*] Unless you were to build a trap door, e.g. declaring the var in a scope where some other function also has access to it.

Firstly, some similar notation:

infix operator ☞ {}

func ☞ (mutator:IMP?, value: Object) -> Void {
  if let mut = mutator {
    switch(mut) {
    case .mutator(let f):
      f(value)
    default:
      return
    }
  }
}

Here is, somewhat weirdly, a class of Point objects where you can redefine both the x and y coordinates after creation.

func Point(x: Int, y: Int, proto: Object)->((_cmd:Selector)->IMP) {
  var _self : Object! = nil
  var _x = Integer(x,o), _y = Integer(y,o)
  func myself (selector:Selector) -> IMP {
    switch (selector) {
    case "x":
      return IMP.accessor({
        return _x
      })
    case "y":
      return IMP.accessor({
        return _y
      })
    case "setX:":
      return IMP.mutator({ newX in
        _x = newX
      })
    case "setY:":
      return IMP.mutator({ newY in
        _y = newY
      })
    case "description":
      return IMP.description({
        let xii = ℹ︎(_self→"x")!
        let yii = ℹ︎(_self→"y")!
        return "(\(xii),\(yii))"
      })
    default:
      return proto(selector)
    }
  }
  _self = myself
  return _self
}

In use it’s much as you’d expect.

let p = Point(3, 4, o)
(p.."description")!.describe() // "(3,4)"
ℹ︎(p→"x") // 3
(p.."setX:")☞(Integer(1,o))
ℹ︎(p→"x") // 1
(p.."description")!.describe() // "(1,4)"

But there’s no need to bother

It’s possible to build mutable objects out of immutable objects. Given a Point(3,4,o), you can make an object that looks exactly like a Point at (1,4) by building an object that has replacement implementations for x and description, but otherwise forwards all methods to the original.

In this way, mutation would look a lot like the Command pattern. You have your original state, you have a linked list (via the prototype chain) of modifications to that state, and the external view is as if you only had the final state.

Further further advances

It’d be good to be able to tell a method what its self is, to make inheritance work properly. For example, if a Point‘s description knew what object was self, then replacing x on a subtype would automatically get the description right. Ben Lings shows how this might work on the previous post’s List objects.

Further thanks

Jeremy Gibbons initiated the discussion on mutable objects that led to the implementation shown above. Thanks to Lawrence Lomax for lots of feedback and discussion about how this should all work, including an alternate implementation.

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.

Object-Oriented Programming in Objective-C

UIKonf 1995 Keynote : Object-Oriented Programming in Objective-C

Introduction

Welcome to the keynote for UIKonf 1995. I’m really excited for what 1995 will bring. Customers are upgrading to last year’s OpenStep release, which means that we get to use the new APIs and the best platform around. And really, there are no competitors. OS/2 Warp doesn’t seem to be getting any more traction than previous versions, and indeed Microsoft seems to be competing against its own products with Windows. Their biggest release this year, the delayed Windows 93, looks like being a warmed-over version of MS-DOS and Windows 3, which certainly can’t be compared with a full Unix system like OpenStep. 1995 will go down in history as the year of NeXT on the desktop.

I want to talk about a crisis in software design, and that is the object-oriented crisis. Well, I suppose it isn’t really, it’s the procedural crisis again. But now we pretend that our procedural code is object-oriented, and Objective-C is the weapon that enacts this travesty.

What’s the main benefit of Objective-C over Smalltalk? It’s C. Rather than attempt to graft some foreign function interface onto Smalltalk and make us write adaptors for all of our C code, Brad Cox had the insight that he could write a simple message-sending library and a syntax preprocessor on the C language, and let us add all of the object-oriented programming we’d get from Smalltalk on top of our existing C code.

What’s the main drawback of Objective-C over Smalltalk? It’s C. Rather than being able to rely on the object-oriented properties of programs to help us understand them, we can just write a load of C code that we wrap up in methods and call it “object-oriented”. This is the source of our crisis. In 1992, Brad Cox claimed that Object-Oriented Programming (or Message/Object Programming as he also called it) was “the silver bullet” that Fred Brooks claimed didn’t exist. That it would help us componentise software into isolated units that can be plugged together, like integrated circuits bought from a catalogue and assembled into a useful product on a circuit board.

This idea of encapsulated software components is not new, and was presented at the NATO conference on software engineering in 1968. At that conference, Doug McIlroy presented an invited paper called “Mass-Produced Software Components” in which he suggested that the software industry would not be “industrialised” until it supported a subindustry of comprehensible, interchangeable, well-specified components. Here’s the relevant quote, the gendered pronouns are from the original.

The most important characteristic of a software components industry is that it will offer families of routines for any given job. No user of a particular member of a family should pay a penalty, in unwanted generality, for the fact that he is employing a standard model routine. In other words, the purchaser of a component from a family will choose one tailored to his exact needs. He will consult a catalogue offering routines in varying degrees of precision, robust- ness, time-space performance, and generality. He will be confident that each routine in the family is of high quality — reliable and efficient. He will expect the routine to be intelligible, doubtless expressed in a higher level language appropriate to the purpose of the component, though not necessarily instantly compilable in any processor he has for his machine. He will expect families of routines to be constructed on rational principles so that families fit together as building blocks. In short, he should be able safely to regard components as black boxes.

Is Object-Oriented Programming actually that silver bullet? Does it give us the black-box component catalogue McIlroy hoped for? Most of us will never know, because most of us aren’t writing Object-Oriented software.

I think this gulf between Object-Oriented design and principles as described during its first wave by people like Alan Kay, Brad Cox, and Bertrand Meyer is only going to broaden, as we dilute the ideas so that we can carry on programming in C. When I heard that a team inside Sun had hired a load of NeXT programmers and were working on a post-Objective-C OO programming environment, I was excited. We know about the problems in Objective-C, the difficulties with working with both objects and primitive types, and the complexity of allowing arbitrary procedural code in methods. When the beta of Oak came out this year I rushed to request a copy to try.

Java, as they’ve now renamed it, is just an easier Objective-C. It has garbage collection, which is very welcome, but otherwise is no more OO than our existing tools. You can still write C functions (called static methods). You can still write long, imperative procedures. There are still primitive types, and Java has a different set of problems associated with matching those up to its object types. Crucially, Java makes it a lot harder to do any higher-order messaging, which means that if it becomes adopted we’ll see a lot more C and a lot less OO.

The meat

I thought I’d write an object-oriented program in modern, OPENSTEP Objective-C, just to see whether it can even be done. I won’t show you all the code, but I will show you the highlights where the application looks strongly OO, and the depths where it looks a lot like C. I don’t imagine that you’ll instantly go away and rewrite all of your code, indeed many of you won’t like my style because it’s so different from usual Objective-C. My hope is that it gives you a taste of what OOP can be about, inspires you to reflect on your own approach, and encourages you to take more from other ideas about programming than some sugar that superficially wraps C.

Despite a suggestion from Marvin, the paranoid android, I’m going to talk to you about Life.

Life

Always be returning

Every method in this application returns a value, preferably an object, except where that isn’t allowed due to assumptions made by the OpenStep frameworks. Where the returned object is of the same type, the client code should use the returned object, even if the implementation is to return self. Even things that look like mutators follow this pattern: with the effect that it doesn’t matter to a client whether an object is mutable or immutable because it’ll use it the same way. Compare a mutable object:

-setFoo:aFoo
{
  foo = aFoo;
  return self;
}

with an immutable one:

-setFoo:aFoo
{
  return [self copyWithReplacementFoo:aFoo];
}

and the client doesn’t know which it’s using:

[[myThing setFoo:aDifferentFoo] doSomeStuff];

That means it’s easy to change the implementation between these two choices, without affecting the client code (which doesn’t need to assume it can keep messaging the same object). In Life, I built a mutable Grid class, but observed that it could be swapped for an immutable one. I didn’t need to change the app or the tests to make it happen.

This obviously has its limitations, but within those limitations is a great approach. If multiple objects in a system share a collaborator, then you need to choose whether that collaborator is mutable (in which case all correlated objects see all updates, even those made elsewhere in the system) or immutable (in which case collaborating objects will only see their own updates, unless some extra synchronisation is in place). Using the same interface for both lets you defer this decision, or even try both to understand the implications.

Always be messaging

In this Life application there are no C control statements: no if, no for, no while. Everything is done by sending messages to objects. Two examples are relevant, and both come from the main logic of the “game”. If you’ve seen the rules of Life, you’ve probably seen them expressed in a form like this:

If a cell is dead and has X neighbours, it becomes living otherwise it remains dead. If a cell is living and has Y neighbours, it remains living otherwise it becomes dead.

It seems that there are three if statements to be written: one to find out whether a cell is living or dead, and another in each branch to decide what the next state should be.

The first can be dealt with using the class hierarchy. A class (at some theoretical level what I mean here is “a constructor”, but that term is not really used in Objective-C so I’m going to say “class” which is the closest term) can often be a substitute for an if statement, by replacing the condition with polymorphism.

In this case, the question “is a cell living or dead” can be answered by sending a message to either a DeadCell or a LivingCell. The question disappears, because it was sent to an object that pre-emptively knew the answer.

@interface LivingCell : Cell
@end

@interface DeadCell : Cell
@end

Now each can answer the question “what is my next state?” without needing to test what its current state is. But how to do that without that other if statement? There’s a finite number of possible outcomes, keyed on an integer (the number of living neighbours the cell has), which means it’s a question that can be answered by sending a message to an array. Here’s how the Cell does it.

-tickOnGrid:grid atX:(NSInteger)x y:(NSInteger)y;
{
  return [[self potentialStates]
         objectAtIndex:
         [self neighboursOnGrid:grid atX:x y:y]];
}

Each of the two subclasses of Cell knows what its potential states are:

static id nextStatesFromLiving;

+(void)load
{
  nextStatesFromLiving = [[NSArray alloc] initWithObjects:
                        deadCell,
                      deadCell,
                      livingCell,
                      livingCell,
                      deadCell,
                      deadCell,
                      deadCell,
                      deadCell,
                      deadCell,
                      nil];
}

-potentialStates { return nextStatesFromLiving; }

Why write the program like this? To make it easier to understand. There’s an idea in the procedural programming world that the cyclomatic complexity – the number of conditions and loops in a function – should be minimised. If all a method is doing is messaging other objects, the complexity is minimal: there are no conditional paths, and no loops.

My second example is how a loop gets removed from a method: with recursion, and appropriate choice of target object. One of the big bones of contention early on in NeXT’s use of Objective-C was changing the behaviour of nil. In Smalltalk, this happens:

nil open.
MessageNotUnderstood: receiver of "open" is nil

In Objective-C, nothing happens (by default, anyway). But this turns out to be useful. Just as the class of an object can stand in for conditional statements, the nil-ness of an object can stand in for loop termination. A method does its thing, and sends itself to the receiver of the next iteration. When that receiver becomes nil, the message is swallowed and the loop stops.

All loops in Life that are based on doing something a certain number of times are based on a category method on NSNumber.

@implementation NSNumber (times)

-times:target perform:(SEL)action
{
  return [self times:target perform:action withObject:nil];
}

-times:target perform:(SEL)action withObject:object
{
  return [[self nonZero] realTimes:target
               perform:action
            withObject:object];
}

-realTimes:target perform:(SEL)action withObject:object
{
  [target performSelector:action withObject:object];
  return [[NSNumber numberWithInteger:[self integerValue] - 1]
       times:target perform:action withObject:object];
}

-nonZero
{
  return ([self integerValue] != 0)?self:nil;
}

@end

Notice that the conditional expression doesn’t violate the “no if statements” rule, because it’s an expression not a statement. There’s one thing that happens, that yields one of two values. The academic functional programming community recently rallied around the Haskell language, which provides the same distinction: no conditional statements, easy conditional expressions.

Never be sequencing

Related to the idea of keeping methods straightforward to understand is ensuring that they don’t grow too long. Ideally a method is one line long: it returns the result of messaging another object. Then there are a couple of slightly larger cases:

  • a fluent paragraph, in which the result of one message is the receiver for another message. If this gets too deep, though, your method probably has too many coupled concerns associated with a Law of Demeter violation.
  • something that would be a fluent paragraph, but you’ve introduced a local variable to make it easier to read (or debug; Objective-C debuggers are not good with nested messages).
  • a method sends a message, then returns another more relevant object. Common examples replace some collection object then return self.

Finally, there are times when you just can’t do this because you depend on some API that won’t let you. A common case when working with AppKit is methods that return void; you’re forced to sequence them because you can’t compose them. The worst offender in Life is the drawing code which uses AppKit’s supposedly object-oriented API, but which is really just a sequence of procedures wrapped in message-sending sugar (that internally use some hidden context that was set up on the way into the drawRect: method).

  float beginningHorizontal = (float)x/(float)n;
  float beginningVertical = (float)y/(float)n;
  float horizontalExtent = 1.0/(float)n;
  float verticalExtent = 1.0/(float)n;
  NSSize boundsSize = [view bounds].size;
  NSRect cellRectangle = 
    NSMakeRect(
           beginningHorizontal * boundsSize.width,
           beginningVertical * boundsSize.height,
           horizontalExtent * boundsSize.width,
           verticalExtent * boundsSize.height
           );
  NSBezierPath *path =  [NSBezierPath bezierPathWithRect:cellRectangle];
  [[NSColor colorWithCalibratedWhite:[denizen population] alpha:1.0] set];
  [path stroke];
  [[NSColor colorWithCalibratedWhite:(1.0 - [denizen population])   alpha:1.0] set];
  [path fill];

The underlying principle here is “don’t make a load of different assignments in one place”, whether those are explicit with the = operator, or implicitly hidden behind message-sends. And definitely, as suggested by Bertrand Meyer, don’t combine assignment with answering questions.

Higher-order messages

You’ve already seen that Life’s loop implementation uses the target-action pattern common to AppKit views, and so do the views in the app. This is a great way to write an algorithm once, but leave it open to configuration for use in new situations.

It’s also a useful tool for reducing boilerplate code and breaking up complex conditional statements: if you can’t represent each condition by a different object, represent them each by a different selector. An example of that is the menu item validation in Life, which is all implemented on the App delegate.

-(BOOL)validateMenuItem:menuItem
{
  id action = NSStringFromSelector([menuItem action]);
  SEL validateSelector = NSSelectorFromString([@"validate"
                          stringByAppendingString:action]);
  return [[self performSelector:validateSelector withObject:menuItem]
       boolValue];
}

-validaterunTimer:menuItem
{
  return @(timer == nil);
}

-validatestopTimer:menuItem
{
  return @(timer != nil);
}

-validatetick:menuItem
{
  return @(timer == nil);
}

-validatequit:menuItem
{
  return @(YES);
}

We have four simple methods that document what menu item they’re validating, and one pretty simple method (a literate paragraph that’s been expanded with local variables) for choosing one of those to run.

There’s no message-forwarding needed in the Life app, and indeed you can do some good higher-order messaging without ever needing to use it. You could imagine a catch-all for unhandled -validate<menuitem>: messages in the above code, which might be useful.

Objective-C’s type checks are wrong for Objective-C

Notice that all of the examples I’ve shown here have used the NeXTSTEP <=3.3 style of method declaration, with (implicit) id return and parameter types. That’s not because I’m opposed to type systems, although I am opposed to using one that introduces problems instead of solving them.

What do I want to do with objects? I want to send messages to receivers. Therefore, if I have a method that sends a message to an object, what I care about is whether the recipient can handle that message (I don’t even care whether the handling is organised upfront, or at runtime). The OPENSTEP compiler’s type checks let me know whether an object is of a particular class, or conforms to a particular protocol, but both of these are more restrictive than the tests that I actually need. Putting the types in leads to warnings in correct code more than it leads to detection of incorrect code, so I leave them out.

Of course, as with Objective-C’s successes, Objective-C’s mistakes also have predecessors in the Smalltalk world. As of last year (1994) the Self language used runtime type-feedback to inline message-sending operations (something that Objective-C isn’t doing…yet, though I note that in Java all “message sends” are inline function calls instead) and there’s an ongoing project to rewrite the “Blue Book” library to allow the same in a Smalltalk environment.

What is really needed is a form of “structural type system”, where the shape of a parameter is considered rather than the name of the parameter. I don’t know of any currently-available object-oriented languages that have something similar to this, but I’ve heard INRIA are working on an OO variant of Caml that has structural typing.

But what about performance?

It’s important to separate object-oriented design, which is what I’ve advocated here, from object-oriented implementation, which is the code I ended up with as a result. What the design gave me was:

  • freedom to change implementations of various algorithms (there are about twice as many commits to production code in Life as there are to test code)
  • hyper-cohesive and decoupled objects or categories
  • very short and easy to understand methods

The implementation ends up in a particular corner of the phase space:

  • greater stack depths
  • lots of method resolutions
  • lots of objects
  • lots of object replacements

but if any of this becomes a problem, it should be uninvasive to replace an object or a cluster of objects with a different implementation because of the design choices made. This is where Objective-C’s C becomes useful: you can rip out all of that weird nested message stuff and just write a for loop if that’s better. Just because you shouldn’t start there, doesn’t mean you can’t end up there.

An example of this in Life was that pretty early in development, I realised the Cell class didn’t actually need any state. A Grid could tell a Cell what the surrounding population was, and the Cell was just the algorithm that encapsulated the game’s rules. That meant I could turn a Grid of individual Cells into a Flyweight pattern, so there are only two instances of Cell in the whole app.

Conclusions

I’m not so much worried for OOP itself, which is just one way of thinking about programs without turning them into imperative procedures. I’m worried for our ability to continue writing quality software.

Compare my list of OO properties with a list of functional programming properties, and you’ll see the same features: immutable values, composed functions, higher-order functions, effectless reasoning over effectful sequencing. The crisis of 1995 shows that we took our existing procedural code, observed these benefits of OOP, then carried on writing procedural code while calling it OOP. That, unsurprisingly, isn’t working, and I wouldn’t be surprised if people blame it on OOP with its mutable values, side-effecting functions, and imperative code.

But imagine what’ll happen when we’ve all had enough of OOP. We’ll look to the benefits some other paradigm, maybe those of functional programming (which are, after all, the same as the benefits of OOP), and declare how it’s the silver bullet just as Brad Cox did. Then we’ll add procedural features to functional programming languages, or the other way around, to reduce the “learning curve” and make the new paradigm accessible. Then we’ll all carry on writing C programs, calling them the new paradigm. Then that won’t work, and we’ll declare functional programming (or whatever comes next) as much of a failure as object-oriented programming. As we will with whatever comes after that.

Remember, there is no silver bullet. There is just complexity to be governed.

Did that work? Maybe.

A limitation with yesterday’s error-preserving approach is that it leaves you on your own to recover from problems. Assuming your error definitions are sufficiently granular, this should be straightforward but tedious. Find out what went wrong, recover from it, then replay everything that happened afterwards.

Recovering from failures automatically is difficult in general, after all, if we could do that there wouldn’t have been a failure in the first place. But there’s no reason to then have a bunch of code that replays the rest of the workflow from the point of recovery, you’ve already written that code on the happy path.

Why can’t we just do that? On an error, why don’t we recover from the immediate error then go back in time to the point where it occurred and start again with our recovered value? Seems straightforward enough, let’s do it. In doing so, let’s borrow (at least in a superficial fashion) the idea of the optional object.

A Maybe object represents the possibility that a value exists, and the ability to find out whether it does. Should it not contain a value, you should be able to find out why not.

@interface Maybe : NSObject

@property (nonatomic, strong, readonly) NSError *error;

- (BOOL)hasValue;
- recoverWithStartingValue:value;

+ just:value;
+ none:aClass error:(NSError *)anError;

@end

I have a value

OK, let’s say that what you wanted to do succeeded, and you want to use the result object. It’d be kindof sucky if you had to test whether the Maybe contained a value at every step of a long operation, and unwrap it to get the object out that you care about. So let’s not make you do that.

@interface Just : Maybe
-initWithValue:value;
@end

@implementation Just
{
    id _value;
}

-initWithValue:value {
    self = [super init];
    if (self) {
        _value = value;
    }
    return self;
}

-(NSError *)error {
    NSAssert(NO, @"No error in success case");
    return nil;
}
-(BOOL)hasValue { return YES; }
-recoverWithStartingValue:value {
    NSAssert(NO, @"Cannot recover from success");
    return nil;
}
-forwardingTargetForSelector:(SEL)aSelector { return _value; }

@end

OK, if everything succeeds you can use the Maybe result (which will be Just the value) as if it is the value itself.

I don’t have a value

The other case is that your operation failed, so we need to represent that. We need to know what type of object you don’t have(!), which will be useful because we can then treat the lack of value as if it is an instance of the value. How will this work? In None, the no-value version of a Maybe, we’ll just absorb every message you send.

@interface None : Maybe
-initWithClass:aClass error:(NSError *)anError;
@end

@implementation None
{
    Class _class;
    NSError *_error;
    NSMutableArray *_invocations;
}

-initWithClass:aClass error:(NSError *)anError {
    self = [super init];
    if (self) {
        _class = aClass;
        _error = anError;
        _invocations = [NSMutableArray array];
    }
    return self;
}

-(NSError *)error { return _error; }
-(BOOL)hasValue { return NO; }

-methodSignatureForSelector:(SEL)aSelector {
    return [_class instanceMethodSignatureForSelector:aSelector];
}

-(void)forwardInvocation:(NSInvocation *)anInvocation {
    id returnValue = self;
    [_invocations addObject:anInvocation];
    [anInvocation setReturnValue:&returnValue];
}

-recoverWithStartingValue:value {
    id nextObject = value;
    while([_invocations count]) {
        id invocation = [_invocations firstObject];
        [_invocations removeObjectAtIndex:0];
        [invocation invokeWithTarget:nextObject];
        [invocation getReturnValue:&nextObject];
    }
    return nextObject;
}

@end

Again, there’s no need to unwrap a None (and that makes no sense, because it doesn’t contain anything). You just use it as if it is the thing that it represents (a lack of).

Recovering

You go through your complex process, and somewhere along the way it failed. At this point your Maybe answer turned into None, because you didn’t get a value at some step. But it carried on paying attention to what you wanted to do.

Now it’s time to turn back the clock. Looking at the error I get from the None, I can see what step failed and what I need to do to be in a position to try again. When I make that happen, I’ll get some object which would’ve been valid at that intermediate point in my operation.

Because the None was paying attention to what I tried to do to it, I can replay the whole process from the point where it failed, using the result from my recovery path.

Worked Example

Here’s an object that requires two steps to use. Either step could fail, and one of them does unless you take action to fix it up.

@interface AnObject : NSObject

@property (nonatomic, assign, getter=isRecovered) BOOL recovered;

-this;
-that;

@end

@implementation AnObject

-this
{
    return [self isRecovered] ? [Maybe just:self] :
        [Maybe none:[self class] error:[NSError errorWithDomain:@"Nope"
                                                           code:23
                                                       userInfo:@{}]];
}

-that
{
    return [Maybe just:@"Winning"];
}

@end

In using this object, I want to compose the two steps. If it goes wrong, I know what to do to recover, but I don’t want to have to explicitly write out the workflow twice if I got it right the first time.

int main(int argc, char *argv[]) {
    @autoreleasepool {
        id anObject = [AnObject new];
        id result = [[anObject this] that];
        if ([result hasValue]) {
            NSLog(@"success: %@", [result lowercaseString]);
        } else {
            NSLog(@"failed with error %@, recovering...", [result error]);
            [anObject setRecovered:YES];
            result = [result recoverWithStartingValue:anObject];
            NSLog(@"ended up with %@", [result uppercaseString]);
        }
    }
}

Conclusion

The NSError-star-star convention lets you compose possibly-failing messages and find out either that it succeeded, or where it went wrong. But it doesn’t encapsulate what would have happened had it gone right, so you can’t just rewind time to where things failed and try again. It is possible to do so, simply by encapsulating the idea that something might work…maybe.

Getting better at doing it wrong

For around a month at the end of last year, I kept a long text note called “doing doing it wrong right”. I was trying to understand error handling in programming, look at some common designs and work out a plan for cleaning up some error-handling code I was working with myself (mercifully someone else, with less analysis paralysis, has taken on that task now).

Deliciously the canonical writing in this field is by an author with the completely apt name Goodenough. His Structured Exception Handling and Exception Handling: Issues and a Proposed Notation describe the problem pretty completely and introduce the idea of exceptions that can be thrown on an interesting condition and caught at the appropriate level of abstraction in the caller.

As an aside, his articles show that exception handling can be used for general control flow. Your long-running download task can throw the “I’m 5% complete now” exception, which is caught to update the UI before asking the download to continue. Programming taste moved away from doing that.

In the Cocoa world, exceptions have never been in favour, probably because they’re too succinct. In their place, multi-if statement complex handling code is introduced:

NSError *error = nil;
id thing = [anObject giveMeAThing:&error];
if (!thing) {
  [self handleError:error];
  return;
}
id otherThing = [thing doYourThing:&error];
if (!otherThing) {
  [self handleError:error];
  return;
}
id anotherThing = [otherThing someSortOfThing:&error];

…and so it goes.

Yesterday in his NSMeetup talk on Swift, Saul Mora reminded me of the nil sink pattern in Objective-C. Removing all the error-handling from the above, a fluent (give or take the names) interface would look like this:

id anotherThing = [[[anObject giveMeAThing] doYourThing] someSortOfThing];

The first method in that chain to fail would return nil, which due to the message-sink behaviour means that everything subsequent to it preserves the nil and that’s what you get out. Saul had built an equivalent thing with option types, and a function Maybe a -> (a -> Maybe b) -> Maybe b to hide all of the option-unwrapping conditionals.

Remembering this pattern, I think it’s possible to go back and tidy up my error cases:

NSError *error = nil;
id anotherThing = [[[anObject giveMeAThing:&error]
                               doYourThing:&error]
                           someSortOfThing:&error];
if (!anotherThing) {
  [self handleError:error];
}

Done. Whichever method goes wrong sets the error and returns nil. Everything after that is sunk, which crucially means that it can’t affect the error. As long as the errors generated are specific enough to indicate what went wrong, whether it’s possible to recover (and if so, how) and whether anything needs cleaning up (and if so, what) then this approach is…good enough.