Protocol-Oriented Programming

When Apple announced Swift 2 at the WWDC in 2015, they also declared that Swift was the world’s fist protocol oriented programming language.  However protocols have been present in Java and  Objective-C since many years. So why is Swift different? And what does protocol-oriented really mean?

With object-oriented programming we usually begin our design by thinking about the objects and the class hierarchies. Protocol-oriented programming still thinks in objects but the main difference in modelling is that we will rather choose protocols instead of superclasses. And we implement common functionality with protocol extensions instead of virtual methods in abstract superclasses. And these protocol extensions are what make Swift unique.

The second real difference with the protocol-oriented design is the use of value types (struct, enumeration) rather than reference types (class) for our types. Apple has advised we should prefer value types over reference types where appropriate. Value types are safer and especially novice programmers can’t change instance properties by mistake. Using value types ensure that we always get a unique instance since we pass a copy of the original rather than a reference when calling functions.

Both object-oriented and protocol-oriented programming is using polymorphism to let us interact with different types using the same interface. With the object-oriented design, we use the interface by the superclass. In the protocol-oriented design we use the interface provided by the protocol and its extension. And last but not least protocols and generics work hand in hand and provide compile time type safety.

Linked List example

As an example I will show how to implement a linked list and implement the collectionType protocol.

Basic Operations

A linked list is a linear collection of data elements, called nodes. Each node contains a value and two references the next and previous node. This structure allows for efficient insertion or removal of elements from any position in the sequence.  Note: A node must be a class because it’s definition is recursive:

class LLNode<T> {
    var value: T
    var next: LLNode?
    var previous: LLNode?

    init(value: T, next: LLNode<T>?, previous: LLNode<T>?) {
        self.next = next
        self.previous = previous
        self.value = value
    }
}

Each linked list has a head property that references the first LLNode and an element counter. As the list can be empty the head is an optional. We implement our linked list as a struct like all other collection types.

struct LinkedList<T: Equatable>  {
    var head: LLNode<T>?
    public var count = 0
    ....
}

There are two operations our linked list must support: insert, remove and subscript . Let’s start with insert. A node is inserted at the head of our list by adjusting the previous and next properties.

public mutating func insert(value: T) {
     let newNode = LLNode(value: value, next: head, previous: nil)
     head?.previous = newNode
     head = newNode
     count++
}

Next we want to remove a value from our linked list. We implement this operation in two steps. First we find the node that contains the value and second we remove this node from the linked list.

func findNodeWithValue(value: T) -> (node: LLNode<T>?,index: Int?) {
        var idx = 0
        var current = head
        while let node = current  where node.value != value{
            current = node.next
            idx++
        }

        if let _ = current {
            return (current, idx)
        }
        return (nil, nil)
    }

And last but not least we can remove the node – circular linked lists would have been easier!

    mutating func remove(value: T) -> T? {

        if let node = findNodeWithValue(value).node {
            // node found
            if count == 1 {
                // list has only one entry
                head = nil
            } else {
                // list contains >2 items
                if let next = node.next {
                    if let previous = node.previous {
                        // node is in the middle of list
                        previous.next = node.next
                        next.previous = node.previous
                    } else {
                        // node is at begin of list
                        next.previous = nil
                        head = next
                    }
                } else {
                    // node is at tail of list
                    node.previous?.next = nil

                }
            }
            count--
            return node.value
        } else {
            // node not found
            return nil
        }
    }

How to become CollectionType compliant

This was quite a lot of work. However we are almost done and making our linked list CollectionType compliant just requires a few more lines of code. CollectionType is an aggregation of two protocols SequenceType and Indexable. So we must implement all methods of these protocols. Luckily this is not complicated at all because the protocols provide default implementations.

Implement SequenceType

The first two collection protocols are inextricably linked: a sequence – a type that conforms to SequenceType – represents a series of values, while a generator  – a type conforming to GeneratorType – provides a way to use the values in a sequence, one at a time, in sequential order. The SequenceType protocol only has one requirement: every sequence must provide a generator from its generate() method.

A generator works by providing a single method, namely, next(), which simply returns the next value from the underlying sequence. next() will continue returning values until there are none left, at which point it will return nil. Note that this may never comes to pass, since sequences aren’t necessarily finite.

Whenever you iterate over a sequence, Swift creates a generator and successively calls its next() method. The familiar code for element in myArray { ... } is in fact just a nice wrapper for this:

generator = myArray.generate()
while let element = generator.next() {
    // do something
}

The relationship between the two protocols is asymmetrical. That is, every sequence has a generator, but only some generators are themselves also sequences (which they can become by returning themselves from their generate() method). Swift includes a whole host of generators, including one that is perfect for our LinkeList case: the type-erasing AnyGenerator. AnyGenerator is initialized with the next method implemented as a closure.

extension LinkedList : SequenceType {

    public typealias Generator = AnyGenerator<T>;

    public func generate() -> AnyGenerator<T> {
       var currentNode = head
       return anyGenerator({
            let value = currentNode?.value
            currentNode = currentNode?.next
            return value
       })
    }

}

Ten lines of code later, we can now use SortedCollection with a dozen  top-level functions, including the bedrock of the functional approach in Swift—reduce, map, and filter.

• contains: Returns true if (1) a particular given element is found in the sequence or (2) an element satisfies the given predicate closure.
• enumerate: Converts a sequence into a sequence of tuples, where each tuple is made up of a zero-based index and the value at that index in the sequence.
• filter: Converts a sequence to an Array, keeping only the elements that match the given predicate closure.
• join: Creates a collection from the sequence, with a given initial collection interposed between each element of the sequence. The initial element must be an ExtensibleCollectionType, described below.
• lazy: Creates a “lazy sequence” from the given sequence. Subsequent calls to map, filter, and reverse on the sequence will be evaluated lazily—that is, until you access or iterate over the sequence, none of the transformations will be executed.
• map: Converts a sequence to an Array after mapping each element with the transforming closure given.
• maxElement: Returns the maximum value of a sequence of Comparableelements.
• minElement: Returns the minimum value of a sequence of Comparableelements.
• reduce: Given an initial value and a combining closure, this “reduces” a sequence to a single element through repeated calls to the closure.
• sorted: Returns a sorted Array of the sequence’s elements. Sorting is automatically ascending for sequences of Comparable elements, or it can be based on a comparison closure.
• startsWith: Returns true if one sequence starts with another sequence.
• underestimateCount: Returns an underestimate of the number of elements in a sequence (SequenceTypes give no hints about length, so this will be zero for a sequence). Returns the actual count for CollectionType instances.
• zip: Converts two sequences into a sequence of tuples, where each tuple is made up of one element from each sequence.

Implement CollectionType

A collection ( type implementing CollectionType) is a step beyond a sequence in that individual elements of a collection can be accessed multiple times via subscript. A type conforms by providing a subscripted getter for elements, then starting and ending index properties. No infinite collections here! A MutableCollectionType adds a setter for the same subscript.

Our SortedCollection can easily use Int for its index, so conforming to CollectionType is straightforward:

extension LinkedList: CollectionType {

    public var startIndex: Int {
        return 0
    }

    public var endIndex: Int {
        return count
    }

    public subscript (position: Int) -> T  {
        var idx = 0
        var current: LLNode<T>? = head
        while idx++ < position  {
          current = current?.next
        }
        return current!.value
    }
}

Like SequenceType, there are a host of global functions that can operate on CollectionType instances. Now that the start and end of the collection are known, count, sort, and other finite operations become available as top-level functions:

• count: Returns the number of elements in a collection.
• find: Returns the first index of a given element in the collection, or nil if not found.
• first: Returns the first element in the collection, or nil if the collection is empty.
• indices: Returns a Range of the collection’s indices. Equivalent to c.startIndex..<c.endIndex.
• isEmpty: Returns true if the collection has no elements.
• last: Returns the last element in the collection, or nil if the collection is empty.
• partition: The primary function used in a quick sort (a fast, memory-efficient sorting algorithm). partition reorders part of a collection and returns a pivot index, where everything below the pivot is equal to or ordered before the pivot, and everything above the pivot is equal to or ordered after. Partitioning can be based on a comparison closure if the collection’s elements themselves are not Comparable. Requires MutableCollectionType.
• reverse: Returns an Array with the elements of the collection in reverse order.
• sort: Sorts a collection in place, modifying the order of the existing collection. Requires MutableCollectionType.