concrete protocols

I didn't know the term "concrete protocol" until fairly recently, but it was pretty easy to understand: a concrete protocol comes with default implementations for some of its methods. Foundation already flirts with the idea of concrete protocols with its collections' subclassing strategies—if you want to build your own array, you only have to implement -count and -objectAtIndex: in your NSArray subclass in order to support all of the other instance methods provided by the class. Written as a concrete protocol, it might look something like this:

@protocol NSArray <NSCopying, NSMutableCopying, NSSecureCoding, NSFastEnumeration>

@required
- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;

@provided
- (NSString *)componentsJoinedByString:(NSString *)separator;
- (BOOL)containsObject:(id)anObject;
- (NSString *)description;
- (NSString *)descriptionWithLocale:(id)locale;
- (NSString *)descriptionWithLocale:(id)locale indent:(NSUInteger)level;
- (id)firstObjectCommonWithArray:(NSArray *)otherArray;
- (void)getObjects:(id __unsafe_unretained [])objects range:(NSRange)range;
- (NSUInteger)indexOfObject:(id)anObject;
- (NSUInteger)indexOfObject:(id)anObject inRange:(NSRange)range;
- (NSUInteger)indexOfObjectIdenticalTo:(id)anObject;
- (NSUInteger)indexOfObjectIdenticalTo:(id)anObject inRange:(NSRange)range;
- (BOOL)isEqualToArray:(NSArray *)otherArray;
- (id)firstObject;
- (id)lastObject;
- (NSEnumerator *)objectEnumerator;
- (NSEnumerator *)reverseObjectEnumerator;
// two dozen more methods…

Compared to subclassing, a concrete protocol lacks state of its own, but allows for multiple inheritence. To make the effects of this more obvious, let's look at a class that would obviously benefit from multiple inheritence: NSOrderedSet.

Today's NSOrderedSet is (almost) API-compatible with both NSArray and NSSet. It supports the fast membership testing and single-instance-storage semantics of sets, while also providing array-like indexing and iteration. It's perfect for things like Switch's window list interface. Yet NSOrderedSet inherits from NSObject.

In a world with concrete protocols, the declaration of NSOrderedSet would look like this:

@interface NSOrderedSet : NSObject <NSArray, NSSet>
@end

Unfortunately, this example also reveals a flaw in concrete protocols as tools for composition: conflicts. Among other methods, both protocols provide -containsObject:. There are a number of solutions to this problem, including using the protocol ordering in the class declaration for precedence, or assigning efficiency factors to the implementation of each provided method to be resolved when the class is registered with the runtime.

Luckily, there's a better way.

traits

The paper on traits—which is super readable and not very long—was published in 2003; it provides a solution for conflict resolution and also explores how traits compare to multiple inheritance, single inheritence, and mixins. The conflict resolution is pretty simple: conflicting method implementations in inherited traits get aliased and the method becomes required. Classes resolve the conflicts by implementing the method and either forwarding the call to one of the aliased methods or providing their own implementation. The net of this for something like ordered sets is that an ordered set for Objective-C can be written in less than 150 lines, a third of which are conflict resolution.

Traits—like protocols—can inherit from other traits, so the NSArray and NSSet traits could inherit from NSFastEnumeration, which could inherit from NSEnumerable, which could provide map, reduce, and filter. This represents a case of the diamond problem that is trivially resolved with traits because of the absence of state; the methods are the same, so the conflicts that would arise from their need for state are managed at the level of the required state accessors.

This makes traits really powerful for building tools. Want a priority queue that supports all of the methods of an immutable array? 80 lines of code. Future possibilities for traits that aren't elucidated in the paper are also really exciting—what if you could write a category for the NSSet trait that returned a new set representing the union, minus, or intersection with another set¹? You'd be extending not only NSSet, but also any type that wants set-like behaviour.

learning by doing

In order to explore the effects of traits, I wrote Traitor. It is a basic implementation for Objective-C that performs all of the safety checks that traits support as early as possible in the execution of the application². This means that classes that are dynamically registered with the runtime can't use traits, but otherwise there should be no problems at runtime due to problems with traits. Reinventing arrays and sets was annoying, but the power of being able to leverage them both in new classes was eye-opening, especially when all the collection classes gained list comprehension methods just from adding a single trait to the hierarchy.