fabián cañas

Making a Numeric Type in Swift

2015-05-21

Programmers invariably work with numbers that represent values with intrinsic types, or units. Types can be conceptual representations of real world modeling such as distance, mass, time. Those conceptual types can be formalized into units, such as meters, grams, seconds.

Naturally we want to be able to manipulate these numbers with types. I want to take the distance from my apartment to my favorite coffee shop, and the distance from the coffee shop to my office, add them together and know the distance of my commute. I may want to add the time for each of those trips to find the total time. But if I were to add a distance to a time, the result is meaningless. We are going to explore how Swift can help us avoid committing such an error.

tl;dr here's the gist. But the journey really is worthwhile. Please read on.

If you've worked with Cocoa, you may have encountered types like NSTimeInterval and CLLocationDistance. Hopefully you've favored using them over naked numeric types for your properties. Not only do they allow for easier interoperation with system frameworks, they also provide a conventional basis for understanding what your values represent.

// according to convention, you know this is in seconds
@property (nonatomic, assign) NSTimeInterval elapsedTime;
// hours? minutes? jiffy?
@property (nonatomic, assign) double mysteryTime;

// according to convention, you know this is in meters
@property (nonatomic, assign) CLLocationDistance totalDistance;
// meters? fathoms? potrzebies?
@property (nonatomic, assign) double secretDistance;

Unfortunately, there's nothing preventing you from committing type atrocities:

unknowableWhatever = elapsedTime + totalDistance;

Swift can rescue us with types! Right? Unfortunately, it is perfectly valid to arbitrarily combine those various types in a Swift program.

var elapsedTime :NSTimeInterval = 12
var mysteryTime :Double = 24
var totalDistance :CLLocationDistance = 917
var secretDistance :Double = 1.726

let sadness = elapsedTime + totalDistance

But wait! I thought Swift was supposed to prevent this sort of thing! That's what types are all about!

In Swift, types such as NSTimeInterval and CLLocationDistance are "type aliases". That is, they say they are one thing but it is a new name for what they actually are. They are a Double in everything but name. Swift is designed to closely interoperate with C, and Apple's frameworks (and most any other non-trivial C code) makes extensive use of typedef. typedef is critically important in writing portable C code, as well as enabling language features like structs as types. Further, some of those types are truly intended to be mixed, such as CLLocationDistance and CLLocationAccuracy. And while we are exploring an avenue for a unit-safe numeric type, we will see later that strictly enforced boundaries between arithmetic types can be sometimes undesirable.

Swift's typealias seems to be, in part, a concession to C's typedef, though it is also used in the construction of complex type relationships with generics.

That said, it is entirely possible for the work contained in the entire rest of this article to be obviated by a simple new Swift language feature to strengthen the power of typealias

// This is not real Swift, nor do I have any reason to believe it ever will be.
// But I could imagine this meaning that Distance is to behave exactly like a Double,
// yet also remain a strictly different type.
strict typealias Distance = Double 

Structs for Type Safety

Structs, whether in C or Swift, can provide us with the type safety we need. We can define a Distance struct like so

/// Type used to represent distance in meters
struct Distance {
    var value :Double
}

Now we can't arbitrarily add distances and time intervals. But we can't add distances to distances either. We can create functions to do that (again, this works in C as well with appropriate syntactical changes)

func add(a: Distance, b: Distance) -> Distance {
    return Distance(value: a.value + b.value)
}

But where Swift really begins to shine is in overloading operators with our own functions. We can define + as a function that operates on a pair of Distance, and proceed to to freely add distances as though they were numbers. We could implement function after function until we have all the operators we might need, ==,<=,>=,!=,+,-,*,/,++,-- and so on. But we can save ourselves some work and integrate very closely with how Swift is built by taking a principled approach to our new numeric type.

More Principled with Protocols

Many of Swift's fundamental language features are expressible in Swift itself. Swift's collection protocols allow us to write first-class collections, a process that has been outlined in NSHipster. There are protocols that can help us on the way to creating first-class numbers.

Swift protocols are much like Objective-C protocols. They represent a sort of contract -- a class or struct can adopt the protocol if and only if it fulfills all the requirements of the protocol. The protocol's requirements look a lot like a struct or a class except they lack implementation of functions. By adopting protocols and fulfilling their requirements, we can leverage functionality built right into Swift that sits on top of those protocols.

Comparisons

Comparisons start with the Equatable protocol. Equatable only defines one required function, ==, and the documentation states

When adopting Equatable, only the == operator is required to be implemented. The standard library provides an implementation for !=.

We can grow our definition of Distance as follows with == implemented and != provided by the standard library. Note that if we implement == but do not conform to Equatable, != will not be available.

struct Distance: Equatable {
    var value :Double
}

func ==(lhs: Distance, rhs: Distance) -> Bool {
    return lhs.value == rhs.value
}

Next up the protocol hierarchy is Comparable, which itself conforms to Equatable.

A type conforming to Comparable need only supply the < and == operators; default implementations of <=, >, >=, and != are supplied by the standard library::

We can implement <, drop Equatable in favor of Comparable and end up with

struct Distance: Comparable {
    var value :Double
}

func ==(lhs: Distance, rhs: Distance) -> Bool {
    return lhs.value == rhs.value
}

func <(lhs: Distance, rhs: Distance) -> Bool {
    return lhs.value < rhs.value
}

Literal Convertibles

A literal, in Swift and other languages, is a value that appears to be baked in to the source code. In the following code, the characters "1" and "2" together (and "1", "2", "." and "0") are a numeric literal representing the number 12.

let w         = 12
let x :Double = 12
let y :Int    = 12
let z         = 12.0

When compiled, type constraints are applied to determine what type literals should be. If they are not of a specific type, they end up as IntegerLiteralType or FloatLiteralType, which in turn are typealiases for Int and Double

Swift exposes the mechanisms underlying literals to developers. With Literal Convertibles, we can create constructs that feel first-class, much in the same way as collection protocols and operator overloading. NSHipster has a nice overview of the available literal convertibles and some of their uses. Here, we will examine the IntegerLiteralConvertible and FloatLiteralConvertible types which were not covered in their article but are critical to implementing our own numeric type.

With what we've built so far, to create a Distance, we must use an initializer:

let twelve = Distance(value: 12)
let eleven = Distance(value: 11)
let ten :Distance = 10     // This will not compile because '10'
                           // isn't a Distance, it's a literal

What we would like to do is the following:

let twelve :Distance = 12
let eleven :Distance = 11

To avoid overloading the default initializer in Comparable, we will implement IntegerLiteralConvertible in an extension as follows, and thereby gain the ability to assign integer literals directly into Distance typed containers.

extension Distance :IntegerLiteralConvertible {
    init(integerLiteral value: IntegerLiteralType) {
        self.init(value: Double(value))
    }
}

With integer literal convertibles, we still cannot assign floating point literals (e.g. 1.75) directly. That has its own protocol that is much the same as its integer counterpart. In our present case considering distances represented as a Double under the hood, we will implement FloatLiteralConvertible. It is not so difficult to imagine purely integral types for which the protocol should not be implemented.

extension Distance :FloatLiteralConvertible {
    init(floatLiteral value: FloatLiteralType) {
        self.init(value: Double(value))
    }
}

Unfortunately at this point, we begin to run out of runway with literal convertible types.

let one :Distance  = 1          // Ok
let two :Distance  = 2.0        // Ok

let six            = two + 4    // 'Int' is not convertible to 'Distance'
let five :Distance = 3 + 2      // 'Int' is not convertible to 'Distance'
let four           = 2.0 + two  // 'Double' is not convertible to 'Distance'

Arithmetic

We can start enabling arithmetic with the SignedNumberType protocol. SignedNumberType conforms to IntegerLiteralConvertible, so we can replace our integer literal extension's protocol and implement two new required functions: negation and subtraction

// Replace `Distance :IntegerLiteralConvertible` from before with a new extension signature
extension Distance :SignedNumberType {
    init(integerLiteral value: IntegerLiteralType) {
        self.init(value: Double(value))
    }
}

// Subtraction
func -(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value - rhs.value)
}

// Negation (notice the `prefix` keyword)
prefix func -(x: Distance) -> Distance {
    return Distance(value:-x.value)
}

We now gain the ability to create Distances from arithmetically combined integer literals -- as long as they're combined with subtraction. We also get abs for free at this point even though we don't implement AbsoluteValuable

let four :Distance = 5 - 1      // Ok
let five :Distance = 7 - two    // Ok
let negativeSix :Distance = -6
let six = abs(negativeSix)      // 6

To Integer or Not to Integer?

We now have a choice before us. There are four remaining basic operators to implement. +,*,/,%. For Double and other floating point types, Swift seems to declare these operations in a free-standing form with no associated protocol. However integers all conform to IntegerType, which includes an IntegerArithmeticType. The fundamental arithmetic operations are supported by a small family of functions, which if implemented would give us those operators:

static func addWithOverflow(lhs: Self, _ rhs: Self) -> (Self, overflow: Bool)
static func subtractWithOverflow(lhs: Self, _ rhs: Self) -> (Self, overflow: Bool)
static func multiplyWithOverflow(lhs: Self, _ rhs: Self) -> (Self, overflow: Bool)
static func divideWithOverflow(lhs: Self, _ rhs: Self) -> (Self, overflow: Bool)
static func remainderWithOverflow(lhs: Self, _ rhs: Self) -> (Self, overflow: Bool)

But for IntegerType, things expand quickly aside from IntegerArithmeticType. There are seemingly unrelated protocols such as RandomAccessIndexType, which includes BidirectionalIndexType and _RandomAccessIndexType, which in turn pull in many, many protocols enabling the type to be used for things like indexing, ranges, incrementing. All this amounts to 11 separate protocols (or 19 if you count the _-prefixed protocols) that you must implement to fulfill the requirements of being an integer in Swift. This is not counting whether you decide to go down the SignedIntegerType or UnsignedIntegerType paths.

We are not implementing an integer. So we will not conform the the IntegerType in any form. There is no floating point corresponding protocol for arithmetic, so we will just implement a couple of arithmetic functions.

func +(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value + rhs.value)
}

func %(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value % rhs.value)
}

And now we can do basically what we want.

let one :Distance = 1
let two :Distance = 2.0
let three = two + 1

let negativeSeven :Distance = -7
let seven = abs(negativeSeven)

let six = three + three
let five = six - 1
let four = 5 - one

let eight = 4 + four
let nine = 10 - one

Multiplication

Be warned: if you are planning on creating your own numeric type for any kind of real-world application: the type of Distance * Distance is not Distance but Distance2 or Area. The combination of types as units is not something that the Swift type system can likely dynamically account for. For certain units, Area being a likely candidate, it may be worthwhile to implement a more elaborate system to account for common use cases:

func *(lhs: Distance, rhs: Distance) -> Area {
    return Area(value:lhs.value * rhs.value)
}

func /(lhs: Area, rhs: Distance) -> Distance {
    return Distance(value:lhs.value / rhs.value)
}

This approach will only take you so far. So be warned that due to the nature of multiplication, implementing * and / on a type that needs to behave like a unit is likely a bad idea. It would be better to implement your domain-specific elaborate operations directly on the underlying Double within a carefully constructed type-safe function.

Additionally, when constructing a numeric type to account for units, if an integer representation seems like a good way to go, consider that conforming to the various integer protocols forces you to implement potentially dangerous multiplication and division functions.

So multiplication and division will be left out of our Distance unit for now.

Bookkeeping

Among the protocols we skipped over when deciding to not implement an IntegerType are Printable and Hashable. These are good protocols to conform to whenever possible. Printable lets the object play nicely with string interpolation, can help with debugging, and makes the new type behave more like a built-in number. Hashable is another protocol implemented by the native numeric types. Implementing a hash value is a good idea for creating value types. It can act as a shortcut to determining the uniqueness of values without doing a direct comparison. It also enables the types use in hash-map based data structures such as Set and Dictionary.

extension Distance :Printable {
    var description: String { get {
            return value.description
        }
    }
}

extension Distance :Hashable {
    var hashValue: Int { get {
            return ~Int(value._toBitPattern())
        }
    }
}

Done!

Putting it all together we now have a Distance unit with some lovely arithmetic properties. But what if we want to make another unit, say, a TimeInterval? This is a lot of boilerplate to copy.

struct Distance: Comparable {
    var value :Double
}

extension Distance :FloatLiteralConvertible {
    init(floatLiteral value: FloatLiteralType) {
        self.init(value: Double(value))
    }
}

extension Distance :SignedNumberType {
    init(integerLiteral value: IntegerLiteralType) {
        self.init(value: Double(value))
    }
}

extension Distance :Printable {
    var description: String { get {
            return value.description
        }
    }
}

extension Distance :Hashable {
    var hashValue: Int { get {
            return ~Int(value._toBitPattern())
        }
    }
}

func ==(lhs: Distance, rhs: Distance) -> Bool {
    return lhs.value == rhs.value
}

func <(lhs: Distance, rhs: Distance) -> Bool {
    return lhs.value < rhs.value
}

func -(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value - rhs.value)
}

prefix func -(x: Distance) -> Distance {
    return Distance(value:-x.value)
}

func +(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value + rhs.value)
}

func %(lhs: Distance, rhs: Distance) -> Distance {
    return Distance(value:lhs.value % rhs.value)
}

Don't Repeat Yourself: Generics

This is programming. Once we get it working, we're just getting started. Time to refactor!

All of the arithmetic functions we provided an implementation for are dependent on two things: the Distance type, and the fact that the value property within that type contains a type that already has the desired operations defined on it. With Swift's generics, we can take advantage of this arrangement and create a protocol to reduce the amount of work we have to do to make a new type.

With that in mind, we can create a new NumericType protocol that looks like just the parts of Distance that we want to abstract. We want a value property, and we want all the protocols we explored above.

public protocol NumericType : Comparable, FloatLiteralConvertible, IntegerLiteralConvertible, SignedNumberType {
    var value :Double { set get }
    init(_ value: Double)
}

Now we can write functions that operate on instances of that protocol. We may be tempted to write our first function to like so

public func + (lhs: NumericType, rhs: NumericType) -> NumericType {
    return NumericType(lhs.value + rhs.value)
}

This is going to present a few problems. The first of which is that we can't make an instance of NumericType. It's a protocol, and we can't instantiate a protocol. While this isn't an insurmountable problem, it's not quite worth fixing because we have a more serious problem:

The point of creating NumericType is so we can create instances such as Distance and TimeInterval. They will each conform to NumericType and therefore be perfectly valid arguments to +. So we would end up right back where we started:

public struct Distance :NumericType {
    ...
}

public struct TimeInterval :NumericType {
    ...
}

public func + (lhs: NumericType, rhs: NumericType) -> NumericType {
    return NumericType(lhs.value + rhs.value) // This won't even compile
}

let time :TimeInterval = 5
let Distance :Distance = 12
let untypedChaos = time + Distance

Generics provide a way to write flexible and reusable code that can operate on a variety of types. But most importantly, and much more powerfully than protocols, generics are a way to constrain code to operate on types that match certain conditions. This is easiest to see by example.

public func + <T :NumericType> (lhs: T, rhs: T) -> T {
    return T(lhs.value + rhs.value)
}

What this does is, between the < >, say that there is a type T that must be a NumericType. Then we go on to say that + accepts a pair of T, and returns a T. In the implementation we create a new T, which we can do because we've said we can in the protocol. Whenever this function is called, every T must correspond to just one type. So

public struct Distance :NumericType {
    ...
}

public struct TimeInterval :NumericType {
    ...
}

public func + <T :NumericType> (lhs: T, rhs: T) -> T {
    return T(lhs.value + rhs.value)
}

let time :TimeInterval = 5
let Distance :Distance = 12
let untypedChaos = time + Distance // This won't compile. Chaos averted!

Let's follow this pattern to create a new fully-fleshed NumericType we can reuse.

public protocol NumericType : Comparable, FloatLiteralConvertible, IntegerLiteralConvertible, SignedNumberType {
    var value :Double { set get }
    init(_ value: Double)
}

public func % <T :NumericType> (lhs: T, rhs: T) -> T {
    return T(lhs.value % rhs.value)
}

public func + <T :NumericType> (lhs: T, rhs: T) -> T {
    return T(lhs.value + rhs.value)
}

public func - <T :NumericType> (lhs: T, rhs: T) -> T {
    return T(lhs.value - rhs.value)
}

public func < <T :NumericType> (lhs: T, rhs: T) -> Bool {
    return lhs.value < rhs.value
}

public func == <T :NumericType> (lhs: T, rhs: T) -> Bool {
    return lhs.value == rhs.value
}

public prefix func - <T: NumericType> (number: T) -> T {
    return T(-number.value)
}

public func += <T :NumericType> (inout lhs: T, rhs: T) {
    lhs.value = lhs.value + rhs.value
}

public func -= <T :NumericType> (inout lhs: T, rhs: T) {
    lhs.value = lhs.value - rhs.value
}

And we can now trim down our specific implementation of types and keep repeated down to more reasonable levels. Repeat this for any numeric types you want to make sure don't mix with incompatible numbers.

public struct Distance :NumericType {
    public var value :Double
    public init(_ value: Double) {
        self.value = value
    }
}

extension Distance :IntegerLiteralConvertible {
    public init(integerLiteral: IntegerLiteralType) {
        self.init(Double(integerLiteral))
    }
}

extension Distance :FloatLiteralConvertible {
    public init(floatLiteral: FloatLiteralType) {
        self.init(Double(floatLiteral))
    }
}

It is through the protocols we adopted and generics on the implementations that the Swift standard library is able to provide !=, > and all the other functions we didn't have to write for types that didn't exist at the time of writing. Not only have we used these language features, we also followed the same pattern to create a powerful new protocol that save us and others time in the future.

By defining types (and protocols) around capabilities, and writing functions that target those capabilities, we end up with cleaner and remarkably reusable code when compared to implementing functionality targeting a specific type. The bulk of our final implementation has nothing to do with distances, time intervals, apples, oranges, or anything else. It reads more like a set of statements of fact that any future programmer could adopt if they so chose.

These kinds of patterns have always been possible. The only difference is that Swift very nicely lets us apply them in a way that using the resulting structures feels much more like writing native Swift.