Protocol Programing, Part 1: 2D spaces.

Part 1

During the holidays I ended up having a lot of free time and no phone nor computer, I only had my iPad with me. From this experiment I learned two things:

1. I am physically unable to spend a couple days without programming on a computer
2. Using Apple’s Playground app to write and compile Swift is a delight

Since I haven’t been writting Swift for a long time I thought it would be a nice experiment to see how far I could take the language since they introduced conditional conformances.

The motivation spanned from an attempt to write a library for linear algebra. This took another direction midway through but the result is a useful set of protocols that encapsulate the behaviour of complex numbers (ℂ), 2d vectors (ℝ²) and other linear spaces.

This blog post has a Swift playground counterpart that you can download for your iPad here or for your Mac here. I strongly encourage you to give it a try since you will be able to run the code shown as example here and make your own little tweaks and changes.

Common operations

Vector spaces define a field, a field has a pretty big set of properties (commutativity, etc.). Unfortunately, Swift’s type system cannot check for those properties. Instead we are going to focus on a couple of properties that we need and that Swift allows us to implement and assume they will be sufficient.

The properties we will use are:

• Add two things together and have an identity value for addition.
• Multiply two things together and have an identity value for multiplication.
• Abstract over two-dimensional objects.
• Multiply two-dimensional objects with a scalar.
• Compute the magnitude of a two-dimensional object.

The goal is that once we have all this machinery weaved together, adding our functionalities to a type will be just as easy as.

Let’s get started.

Mutliplicative

The multiplicative protocol defines a function * between two values of the same type and returns the same type. It also has an identity value such that a * id = a. As we will see, for Int and Double the identity value will be 1 and 1.0 respectively but this isn't the case for more complex types.

“lhs” and “rhs” stand for “left hand side” and “right hand side” respectively.

Given this, we can implement Multiplicative for the Int type.

Since the Int type already has a * operator that fits the definition of the protocol we only need to define the multId value.

Additive

The additive protocol will be similar with a value for addition identity and an addition operator +.

And implement it for Int:

Those two protocols are monoids

TwoDimensions

In order to simplify our future work we will abstract over the fact that some types have two dimensions. As such, they will need to be able to return each component and create itself from two component values.

This protocol will allow us to define default implementation for types that have two dimensions.

We do not have any type to conform to this protocol but we can already implement Additive for it. Indeed, any type is Additive provided it has two dimensions and its components are Additive as well.

As for addId, since Additive is implemented by adding each component together we can define it by creating a 2D object with identity values for each component.

As we can see, we have an identity for addition that isn’t 1 but is a value which uses the identity value of it's component type.

Magnitude

The magnitude of a value is a way to have a representation of the “size” of it. Typically for 2D vectors the magnitude is the length of the vector. For Ints it is their absolute value. This value is useful to compare two different values even if there is not necessarily a total order between all values.

To describe a type that has a magnitude we need to say that it has a property that returns a value of some type and this value needs to be Comparable.

Since the magnitude usually requires a square root operation but isn’t a very general operation we are going to assume that magSquare returns the magnitude squared.

Since we know how to compute the magnitude of a value in the general sense (given a value v with projections x and y the magnitude squared is given by v.x * v.x + v.y * v.y), any type can have a magnitude provided:

• It has two dimensions.
• The components are multiplicative.
• The components are additive.
• The types of the components are the same as the result of computing the magnitude.

Scalar

The scalar protocol should allow to “scale” a value using another value. For this we are going to add a new operator to differentiate between regular multiplication and scalar multiplication. The ◊ operator can be found on Apple platforms with alt-shift-v.

This protocol can also be implemented automatically for any type provided:

• It has two dimensions.
• The components are multiplicative.
• The types of the components are the same as the scale factor’s type.

Now that we have all the protocols we wanted we can start to implement concrete types.

2D Vectors

The definition of 2D vectors is pretty simple. It’s a struct parameterized over the type of each of its components.

We implemented CustomStringConvertible because we are going to need it when printing more complex values.

Then, we can implement TwoDimensions and omit fst and snd since they are already implemented by the struct.

And finally, we can trivially (there is nothing to do) implement Additive, Magnitude and Scalar for Vector and add Equatable in the mix as well.

For those unfamiliar with Swift, typealias relates an associatedtype with a concrete type coming from the instance we are implementing. MagVal = A says, "For this instance the associated type MagVal is actually A"

There is no Multiplicative implementation since it isn't clear how to multiply two 2D Vectors. (Dot product? Cross product? Multiply the components?)

Now we can use +, magSquare and ◊

Computing the magnitude of a vector is a bit awkward let’s see how we can improve that.

Improving magnitude with square root

Let us add a new protocol for types that have a square root:

This definition of square root is incomplete since most values have multiple roots.

This protocol uses the prefix operator √ which can be found with alt-v on Apple platforms.

We can now extend Magnitude to provide a magnitude field whenever the MagVal has a square root.

We can now try that:

But we get an error.

“Type ‘Int’ does not conform to protocol SquareRoot"

Indeed, we haven’t added a SquareRoot extension for Int. But that is because there is no easy way to compute the square root of an integer number (Do we assume it's a double and round down? round up? truncate?)

Instead we are going to give Double all the necessary protocols in order to have vectors support the magnitude function when they are vectors of Doubles

We can now write

and get 1.414213… as expected. Now we can use magnitude when dealing with Vector of Double and magSquare when using Int.

Complex Numbers

Why stop here? We already have all those protocol so let us use them with a new type. Let us implement Complex Numbers.

As we can see, appart from Multiplicative there is no real work to do in order to implement those protocols.

This allows us to write the following without any extra work.

Linear functions

We can take this to another level and implement linear functions. A linear function is a function of the form f(x) = a * x + b

Like before, this allows us to write

As we can see, we left out magnitude since the semantics of magnitude for a linear function are unclear (at least to me). We also left out Multiplicative because multiplying two linear functions results in a quadratic one. And this is a problem because our definition of Multiplicative expects to return a value of the same type as its argument.

Fancy multiplication

We can fix the multiplication problem by introducing another protocol FancyMult which multiplies two values of the same type and returns a value of another type.

We can use this to implement the product between two linear functions:

Or even dot product of two vectors:

This allows us to write the identity (a²x² - b²) = (ax + b) * (ax - b)

Power interlude

For entertainment purposes here is an implementation of a power operator ^^ based on the implementation of Multiplicative

This allows us to write

Combining everything

Now we can combine everything and have it work as expected. For example we can have complex vectors:

And we can even have linear functions of complex vectors:

This really demonstrates the power of protocols and conditional conformance. They allow us to reuse our code and combine different structures in very flexible ways without us having to worry about the details of how future code will be implemented.

Conclusion

Our protocol-oriented approach perfectly encapsulates the concept of DRY. We only define the relevant implementation once and the rest follows from the structure of our program. This makes the code very easy to extend and makes every component of it relatively simple. Unfortunately, our example only allows for 2-dimensional types. In the next part we are going to see how to use protocols to emulate dependent types and have vectors of arbitrary size.