March 4, 2015

A Sanatorium for Swift Generics

Marcin Krzyżanowski had a great post a few days ago about the challenges of working with integers in Swift, Madness of Generic Integer. The gist of the post is that since Swift’s disparate integer types don’t have a single common protocol in their hierarchy that encapsulates all their functionality, you need to jump too many hurdles to write generic functions that can apply to all the available integer types, from Int8 up to UInt64.

I’d like to explain here how I would go about solving this particular problem, and in the process hopefully make Swift generic functions a bit easier to understand and implement. Some of the frustration I’ve seen in the responses to Marcin’s post seem to stem from trying to look at Swift’s protocol system through Objective-C-tinged lenses.

While Swift and Objective-C both use protocols extensively, protocols in Swift are constructed and put to use in an entirely different way. In Objective-C, protocols are mostly used to loosely couple objects—for example, a UITableView doesn’t need to know the precise type of its data source, just that it conforms to UITableViewDataSource. In Swift, however, protocols hierarchically build functionality by adding capabilities to types bit by bit. The sprawling protocol hierarchy of Int isn’t a sign of addled language designers run amok, but of a deep and powerful type system.

I’d like to suggest a workflow for creating generic functions, whether for integer types, collection types, or anything else:

  1. Create a type-specific version of your function. Get it working and simplify as much as you can.

  2. Look at your function implementation and determine what functions and operations you’ll need. Are you simply adding two numbers? Are you using the length of an array or map, reduce, and filter?

  3. Enumerate the types that you want to use with a generic version of your function and look for their common protocol ancestors. For example, at what point do the protocol hierarchy graphs for Array and Dictionary merge?

  4. Find the lowest-level protocol that provides your needed functionality. Keep in mind that you use generic constraints to require that the type for your generic function conforms to multiple protocols.

  5. If you can’t find one or more protocols that provide all the functionality you need (as Marcin found), you may need to write your own, and extend your targeted types to conform to your new protocol. (Depending on what you’re doing in your function, this may require adding a new top-level function or two.)

  6. Genericize! You’re now ready to convert your type-specific function to a generic one and test it.

I’ll walk through each of these steps with the problem from Marcin’s post: converting an array of bytes (UInt8) to any particular integer type.

1. A type-specific function

Before trying to write a generic function that handles this, I’ll write a type specific one so I know what I’m working with, and try to reduce it to its simplest form. Particularly when using collections, favor top-level functions over instance methods: map(array) { ... } instead of array.map { ... }:

func integerWithBytes(bytes: [UInt8]) -> UInt32? {
    // check the size of the bytes array
    if bytes.count != sizeof(UInt32) {
        return nil
    }
    
    var result: UInt32 = 0
    for byte in bytes.reverse() {
        result = result << 8 | UInt32(byte)
    }
    return result
}

We’re going to step through the bytes array in reverse, shifting result upward by one byte-length at each step and using a bitwise or (|) to add each byte. Testing this out, we can see that it works properly:

let shouldBeNil = integerWithBytes([0])                         // nil
let shouldBeOne = integerWithBytes([0x01, 0x00, 0x00, 0x00])    // 1
let shouldBeMax = integerWithBytes([0xFF, 0xFF, 0xFF, 0xFF])    // 4294967295

2. Finding operations

Looking at my function, I can see that I’m doing four things with UInt32:

  1. var result: UInt32 = 0 is initializing a variable from an integer literal,
  2. result << 8 uses the << left bitshift operator,
  3. UInt32(byte) initializes a new UInt32 from an UInt8, and
  4. the bitwise or operator | merges those last two expressions.

3. Enumerate types

As said above, I’d like this to work with any signed or unsigned integer type. Let’s take a look at the Int and UInt8 protocol graphs, as examples of the types I want to use.

4. Find common protocol ancestors

It looks like IntegerType is probably the best match for what I need. It inherits from IntegerLiteralConvertible, solving #1 above, and from BitwiseOperationsType, solving #4. Unfortunately, I can’t find a protocol that satisfies #2 and #3—there’s no BitshiftOperationsType (although there should be), and no common protocol that provides a UInt8 intitializer.

5. Adding to the protocol hierarchy

To solve these missing items, we can think either big or small. Thinking big means we would implement the protocols that were left out of Swift’s standard library—in this case, BitshiftOperationsType and, perhaps, ByteConvertible.

protocol BitshiftOperationsType {
    func <<(lhs: Self, rhs: Self) -> Self
    func >>(lhs: Self, rhs: Self) -> Self
    func <<=(inout lhs: Self, rhs: Self)
    func >>=(inout lhs: Self, rhs: Self)
}

protocol ByteConvertible {
    init(_ value: UInt8)
}

Thinking small in this case would be adding a protocol that does exactly what our function needs and nothing more: a ByteArrayConvertibleType protocol with only the four operations listed in step 2:

// inheriting from IntegerType gets us bitwise operations and literal convertible
protocol ByteArrayConvertibleType : IntegerType {
    init(_ value: UInt8)
    func <<(lhs: Self, rhs: Self) -> Self
}

In either case, we need to add our new protocol(s) to all the integer types. It’s easy to do this, since they already implement the required initializer and operator functions—Apple calls this declaring protocol adoption. I’ll use the “thinking big” version here:

extension Int : BitshiftOperationsType, ByteConvertible {}
extension Int8 : BitshiftOperationsType, ByteConvertible {}
extension Int16 : BitshiftOperationsType, ByteConvertible {}
// yada yada yada...

6. Type-specific to generic

Now we’re ready for the generic implementation of our integerWithBytes function. Add the generic constraints to the earlier function and convert the specific type UInt32 to the generic T:

func integerWithBytes<T: IntegerType where T: ByteConvertible, T: BitshiftOperationsType>
    (bytes: [UInt8]) -> T?
{
    if bytes.count != sizeof(T) {
        return nil
    }
    
    var result: T = 0
    for byte in bytes.reverse() {
        result = result << 8 | T(byte)
    }
    return result
}

Now, before anyone gets angle-bracket-T blindness, here’s what that bracketed code is saying:

  • <T: IntegerType—you can call this function with any type that conforms to IntegerType
  • where T: ByteConvertibleand conforms to ByteConvertible
  • , T: BitshiftOperationsType>and conforms to BitshiftOperationsType

Testing out our newly generic function, we can check for any runtime issues:

// original examples:
let shouldBeNil: UInt32? = integerWithBytes([0])
let shouldBeOne: UInt32? = integerWithBytes([0x01, 0x00, 0x00, 0x00])
let shouldBeMax: UInt32? = integerWithBytes([0xFF, 0xFF, 0xFF, 0xFF])
// all still correct

// new types:
let uhOh: UInt8? = integerWithBytes([1])
> EXC_BAD_INSTRUCTION
let alsoBad: Int8? = integerWithBytes([0xFF])
> EXC_BAD_INSTRUCTION

So, what happened there? Shifting by eight bits is fine for UInt32, but with an eight-bit type it’s a runtime exception. Moreover, even trying to initialize a signed Int8 with a higher-range UInt8 will result in an overflow. These are a couple of the errors, like out-of-bounds exceptions, that Swift’s type-checking unfortunately can’t protect us from. To fix the problem, we’ll need to add a bit pattern-based initializer to our ByteConvertible protocol—init(truncatingBitPattern:) already exists for most integer types, with this description:

Construct a [specific integer type] having the same bitwise representation as the least significant bits of the provided bit pattern. No range or overflow checking occurs.

Sounds like what we need! Here’s the new declaration of ByteConvertible, and an implementation of the init for the two integer types without it:

protocol ByteConvertible {
    init(_ value: UInt8)
    init(truncatingBitPattern: UInt64)
}

extension Int64  : BitshiftOperationsType, ByteConvertible {
    init(truncatingBitPattern value: UInt64) {
        self = Int64(bitPattern: value)
    }
}
extension UInt64 : BitshiftOperationsType, ByteConvertible {
    init(truncatingBitPattern value: UInt64) {
        self = value
    }
}

Now we can use that initializer to return early if T is a single-byte type:

func integerWithBytes<T: IntegerType where T: ByteConvertible, T: BitshiftOperationsType>
    (bytes: [UInt8]) -> T?
{
    if bytes.count != sizeof(T) {
        return nil
    }
    
    if sizeof(T) == 1 {
        return T(truncatingBitPattern: UInt64(bytes[0]))
    }
    
    var result: T = 0
    for byte in bytes.reverse() {
        result = result << 8 | T(byte)
    }
    return result
}

// new types:
let noProblem: UInt8? = integerWithBytes([1])
// 1
let allGood: Int8? = integerWithBytes([0xFF])
// -1

All set! You can get the final code as a gist.


I hope this post has provided some clarity into how generic functions can be constructed. Generics aren’t always intuitive or easy at first, particularly for those coming from an Objective-C background. However, they are a powerful feature in a strongly-typed language such as Swift and one that can’t be ignored.

by Nate Cook swift generics Comments


January 12, 2015

Links for January 12, 2015

Long Live Cocoa

Another first — my first article in a new role at NSHipster:

Swift is an exciting language for many of us, but it’s still brand new. The stability of Objective-C and the history and strength of Cocoa mean that Swift isn’t ready to be the driving force behind a major change, at least not quite yet. Cocoa’s depth and the power it affords, along with the way it and Swift go hand in hand, make Cocoa as relevant and as promising as ever.

by Nate Cook swift cocoa nshipster


November 25, 2014

A Look At Swift's Elusive ~> Operator

The Swift standard library begins with declarations of all the operators used throughout. All the familiar operators are there – arithmetic, logical, bitwise, bitshift, range, as well as the pattern matching and null coalescing operators. Later you find functions defined for each of these, so you can compare two Ints or append to an Array. But for one operator, there are no visible functions at all. To put it succinctly:

Swift’s internal header1 holds the answer—there are actually several functions defined for ~>, but only a few of them are accessible to us in a playground or compiled code. Now, the fact that these are available may be a fluke, and all indications are that these functions are solely meant for internal use. I wouldn’t advise anyone to use these in production code, since they could disappear or change at any time. With that said, in the spirit of exploration, let’s jump right in!

Visible declarations

func ~><T : _ForwardIndexType>(start: T, rest: (_Advance, T.Distance)) -> T
func ~><T : _ForwardIndexType>(start: T, rest: (_Advance, (T.Distance, T))) -> T
func ~><T : _BidirectionalIndexType>(start: T, rest: (_Advance, T.Distance)) -> T
func ~><T : _BidirectionalIndexType>(start: T, rest: (_Advance, (T.Distance, T))) -> T
func ~><T : _RandomAccessIndexType>(start: T, rest: (_Advance, (T.Distance))) -> T
func ~><T : _RandomAccessIndexType>(start: T, rest: (_Advance, (T.Distance, T))) -> T

func ~><T : _RandomAccessIndexType>(start: T, rest: (_Distance, (T))) -> T.Distance
func ~><T : _ForwardIndexType>(start: T, rest: (_Distance, T)) -> T.Distance

So what do we have there? Eight generic functions, each of which uses a *IndexType as the left-hand-side parameter. The eight functions really boil down to two (plus one variation): you can advance an index (with an optional limit) to get a new index, or you can get the distance from one index to another. But there’s a wrinkle—what goes on the right-hand side of this operator?

_Advance and _Distance

_Advance and _Distance are two structs that, while missing from the visible standard library, are usable from our code. The ~> declarations we’ve seen so far take a tuple on the right side, with one of these in the first spot of the tuple. Let’s try creating an _Advance tuple first:

let advanceBy5 = (_Advance(), 5)
> error: '_Advance' cannot be constructed because it has no accessible initializers
// darn.

So the compiler knows about the type, but we can’t construct it directly. Happily enough, the internal header also contains a few methods that return the tuples we’re looking for:

func _advance<D>(n: D) -> (_Advance, (D))
func _advance<D, I>(n: D, end: I) -> (_Advance, (D, I))

func _distanceTo<I>(end: I) -> (_Distance, (I))

Putting it to use

So what does this look like in practice? Let’s try a couple things:

// create an (_Advance, Int) tuple
let advanceBy5 = _advance(5)

// try it out on the members of an array
let shifted = [1, 2, 3, 4, 5].map { $0 ~> advanceBy5 }
println(shifted)
> [6, 7, 8, 9, 10]

// create a bound advance for a string and iterate through every other character
let line = "Beware the jabberwock, my son / the jaws that bite, the claws that catch"
let everyOther = _advance(2, line.endIndex)

var index = line.startIndex
while index != line.endIndex {
    print(line[index])
    index = index ~> everyOther
}
> Bwr h abrok ysn/tejw htbt,tecasta ac

Alright! I can’t totally tell why this would be preferred over the advance() and distance() functions, but perhaps there’s more there than I’m seeing. In any case, that’s how ~> can work, for at least these simplest of cases.

More under the hood

The other ~> function declarations have a similar structure, and therefore give similar clues about their purpose. The functions to generate these tuples, however, don’t bubble up to a level that we can access, so we’re locked out of these particular uses for ~>. Most of these have to do with collections, with an absolute value function thrown in for good measure.

func ~><T : _CollectionType>(x: T, _: (_CountElements, ())) -> T.Index.Distance
func ~><T>(x: EmptyCollection<T>, _: (_CountElements, ())) -> Int
func ~><T>(x: CollectionOfOne<T>, _: (_CountElements, ())) -> Int

func ~><T : _CollectionType>(x: T, _: (_UnderestimateCount, ())) -> Int
func ~><T : _SequenceType>(s: T, _: (_UnderestimateCount, ())) -> Int

func ~><T : _CollectionType, R>(s: T, args: (_PreprocessingPass, ((T) -> R))) -> R?
func ~><T : _SequenceType, R>(s: T, _: (_PreprocessingPass, ((T) -> R))) -> R?

func ~><S : _Sequence_Type>(source: S, _: (_CopyToNativeArrayBuffer, ())) -> _ContiguousArrayBuffer<S.Generator.Element>
func ~><C : CollectionType where C._Element == C._Element>(source: C, _: (_CopyToNativeArrayBuffer, ())) -> _ContiguousArrayBuffer<C._Element>

func ~><T : _SignedNumberType>(x: T, _: (_Abs, ())) -> T
func ~><T : AbsoluteValuable>(x: T, _: (_Abs, ())) -> T

That’s a wrap on our look at ~> - let me know if you have other ideas for how it could be used.

  1. I don’t know exactly what to call this—you can get the Swift REPL to dump the headers for an entire module with the :print_module command; it’s a variation on the result of command-clicking import Swift in a playground, with more declarations and less documentation.

by Nate Cook swift operator Comments


November 17, 2014

Links for November 17, 2014

UIPrintInteractionController

My second article for NSHipster is up today, about UIPrintInteractionController, UIPrintPageRenderer, and the rest of the UIKit printing API:

With all the different means to comment, mark up, save, and share right at our fingertips, it’s easy to overlook the value of a printed sheet of paper. Through its printing API, UIKit makes it easy to print straight from a user’s device with custom designs that you can adapt to both your content and the paper size.

by Nate Cook swift uiprintinteractioncontroller nshipster


October 29, 2014

Custom Ternary Operators in Swift

I ran across an interesting question on Stack Overflow today about how to implement custom ternary operators in Swift. Swift, like most languages, only has a single ternary operator built-in – the conditional ternary operator ?::

let result = booleanValue ? "true" : "false"

Even though Swift only supports unary and binary operators for operator overloading, it’s possible to implement our own ternary operators by declaring two separate operators that work together and using a curried function for one of the operators.

What’s your sign?

For our first example, let’s declare a ternary operator x +- y +|- z that will check the sign of the initial value x, and then return the second value y if the sign is zero or positive and the final value z if the sign is negative. This is similar to the existing ?: operator – we should be able to write:

let sign = -5 +- "non-negative" +|- "negative"
// sign is now "negative"

We’ll start by declaring the two operators. The important part is to have higher precedence on the second operator - we want to evaluate that part first.

infix operator +- { precedence 60 }
infix operator +|- { precedence 70 }

Now we define the functions - we’ll begin by defining the second operator (+|-) as a curried function that takes two autoclosures and a Bool. There’s a lot going on there – first, a couple definitions:

Autoclosures

An autoclosure parameter is a way of wrapping an expression in a closure so that it doesn’t immediately get executed. We want to make sure we only evaluate one side of the second operator after we’ve looked at the sign of the initial value. Using an autoclosure means that instead of receiving two values of type T in our function, we receive two closures that, when called, return a value of type T.

Curried functions

A curried function is one that, instead of being called one time with multiple parameters, can instead be called multiple times, adding a parameter each time. The first time a curried function is called, it returns another function that can take the remaining arguments, which can be called in the same way until no arguments remain. Apple gives an example of using a curried function two add integers.

Back to our second operator - the first time we call it will be with the two sides of that operator, and we’ll call the result of that with a Bool to select which autoclosure we’ll evaluate:1

func +|-<T>(lhs: @autoclosure () -> T, rhs: @autoclosure () -> T)(left: Bool) -> T {
    return left ? lhs() : rhs()
}

The remaining part of that function becomes the second parameter of the function for our first operator, and we can use our new “ternary” operator.

func +-<I: SignedIntegerType, T>(lhs: I, rhs: (left: Bool) -> T) -> T {
    return rhs(left: lhs >= 0)
}

println( -5 +- "non-negative" +|- "negative" )
> > negative

Here’s how it gets executed:

  1. Due to the precedence of +|- being higher than +-, this subexpression is evaluated first: "non-negative" +|- "negative"
  2. Each of the two sides of that subexpression (each of the two strings) is wrapped in a closure, waiting to be called
  3. Those two closures are returned from the +|- function captured inside another function which only takes a Bool
  4. That new function is passed as the right-hand side to the +- operator function, which evaluates the sign of lhs and passes it into that new function.
  5. Lastly, the boolean value determines which of the autoclosures created in step 2 gets executed - the result of the chosen closure is the result of the whole expression.

Modular exponentiation

This same technique can be used for other ternary operations, like calculating modular exponentiation. Modular exponentiation calculates the modulus m of a number b raised to the e power – a ternary operation. Here are the declarations, following the same structure:

// declare operators
infix operator *%* { precedence 50 }
infix operator %*% { precedence 60 }

// second operator first - no need for autoclosures here
func %*%(e: Int, m: Int)(b: Int) -> Int {
    var c = 1
    for _ in 0..<e {
        c = (b * c) % m
    }
    return c
}

// here we simply call the new function with the lhs
func *%*(lhs: Int, rhs: (b: Int) -> Int) -> Int {
    return rhs(b: lhs)
}

And now we have a ternary modpow operator:

let modexp = 4 *%* 13 %*% 497
println(modexp)
> > 445 

Thanks for reading!

  1. Bonus points for using the ternary operator when declaring a ternary operator?

by Nate Cook swift operators curried Comments