Hi, this is a guest post from Crusty. I’ve been doing a tour of the blogosphere, discussing Protocol-Oriented Programming. This time, Graham was kind enough to hand over the keyboard for SICPers and let me write a post here.
Back when Graham was talking about Object-Oriented Programming in Functional Programming in Swift, he mentioned that the number of methods you need to define on an object (or “procedural data type”) is actually surprisingly low. A set, Graham argued, is a single method that reports whether an object is a member of the set or not. An array has two methods: the count of objects it contains and the object at a particular index. We’re only talking about immutable objects here, but mutability can be modelled in immutable objects anyway.
Looking at the header or documentation for your favourite collections library, you probably think at this point that we’re missing something. Quite a few things, in fact. Your array data type probably has a few more than two methods, so how can those be the only ones you need?
Everything you might want to do to an array can be done in terms of those two methods that return the count and the object at an index. Any other operation can be built on those two operations (well, those two operations and a way to create some new objects). What’s more, any other array operation can be built using those operations without knowing how they’re implemented. That means we’re free to define them in a completely abstract way, using a protocol:
@protocol AnArray <NSObject>
- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;
@end
Now, without telling you anything about how that object works, I can create another object that “decorates” this array by using its methods. It can only call methods that are in the protocol, i.e. count and objectAtIndex:, but that’s sufficient. Hey, we’re doing protocol-oriented programming! As I said, we also need a way to create a new array sometimes, so for arguments’ sake let’s say that there’s a concrete version of AnArray called MyArray that the decorator knows how to create.
@interface ArrayDecorator : NSObject <AnArray>
- (instancetype)initWithArray:(id <AnArray>)anArray;
- (id)firstObject;
- (id <AnArray>)map:(SEL)aSelector;
@end
@implementation ArrayDecorator
{
id <AnArray> _array;
}
- (instancetype)initWithArray:(id <AnArray>)anArray
{
self = [super init];
if (!self) return nil;
_array = anArray;
return self;
}
- (NSUInteger)count { return [_array count]; }
- (id)objectAtIndex:(NSUInteger)index { return [_array objectAtIndex:index]; }
- (id)firstObject
{
return [self count] ? [self objectAtIndex:0] : nil;
}
- (id <AnArray>)map:(SEL)aSelector
{
void **buffer = malloc([self count] * sizeof(id));
for (int i = 0; i < [self count]; i++) {
buffer[i] = (__bridge void *)[[self objectAtIndex:i] performSelector:aSelector];
}
id <AnArray> result = [[ArrayDecorator alloc] initWithArray:
[[MyArray alloc] initWithObjects:(id *)buffer count:[self count]]];
free(buffer);
return result;
}
@end
We’ve managed to create useful additional methods like firstObject and map:, that are only implemented in terms of the underlying array’s count and objectAtIndex:. It doesn’t matter how those methods are implemented, as long as they are.
Now, I know what you’re thinking. This protocol-oriented programming is fine and all, but now I have to remember to decorate every array I might create in order to get all of these useful additional methods. Wouldn’t it be great if there were some way to give all implementors of the AnArray protocol default implementations of map: and firstObject?
There is indeed a way to do that. This is what OOP’s inheritance feature is for. It’s been kindof abused, in that it’s overloaded to mean subtyping, which gets people into horrible knots over whether squares are rectangles or rectangles are squares (the answer, by the way, is yes). All inheritance really means is “if you send me a message I don’t have a method for, I’ll check to see if my parent class has that method”. In that case, this array decoration can be rewritten like this:
@interface SomeArray : NSObject
- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;
- (id)firstObject;
- (SomeArray *)map:(SEL)aSelector;
@end
@implementation SomeArray
- (NSUInteger)count { [self doesNotRecognizeSelector:_cmd]; return 0; }
- (id)objectAtIndex:(NSUInteger)index { [self doesNotRecognizeSelector:_cmd]; return nil; }
- (id)firstObject
{
return [self count] ? [self objectAtIndex:0] : nil;
}
- (SomeArray *)map:(SEL)aSelector
{
void **buffer = malloc([self count] * sizeof(id));
for (int i = 0; i < [self count]; i++) {
buffer[i] = (__bridge void *)[[self objectAtIndex:i] performSelector:aSelector];
}
SomeArray *result = [[MyArray alloc] initWithObjects:(id *)buffer count:[self count]];
free(buffer);
return result;
}
@end
What’s changed? The methods that were previously defined on the AnArray protocol have been subsumed into the interface for SomeArray (which is what the word “protocol” used to mean in Smalltalk programming: the list of messages you could rely on an object responding to). Array implementations that are subclasses of SomeArray need merely implement count and objectAtIndex: (as before) and they automatically get all of the other methods, which are all implemented in terms of those two.
This looks familiar. Let me check the documentation for NSArray (this is from the Foundation 1.0 documentation on NeXTSTEP 3, by the way. They don’t call me Crusty for nothing.):
The NSArray class declares the programmatic interface to an object that manages an immutable array of objects. NSArray’s two primitive methods–count and objectAtIndex:–provide the basis for all the other methods in its interface. The count method returns the number of elements in the array. objectAtIndex: gives you access to the array elements by index, with index values starting at 0.
Interesting: all of its methods are implemented in terms of two “primitive” methods, called count and objectAtIndex:. The documentation also mentions that NSArray is a “class cluster”, and has this to say on class clusters:
Your subclass must override inherited primitives, but having done so can be sure that all derived methods that it inherits will operate properly.
Yes, that’s correct, protocol-oriented programming is a Crusty concept. We cornered it in the haunted fairground, removed its mask, and discovered that it was just abstract methods in object-oriented programming all along.
