Protocol Programing, Part 1: 2D spaces.
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:
- I am physically unable to spend a couple days without programming on a computer
- 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.
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
:
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 Int
s 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.
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.
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 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.