Generics

In the previous lesson, the cubed we wrote for Int had to be written again for Double. Writing the same body once and applying it to many types is the job of generics. Generics let you write a function or a type for a type that is not yet known; the type becomes known at the point of use. In this lesson we measure two behaviors: how a generic body runs on every call, and when the lazy sequences of the standard library call the transformer.

A type parameter is a placeholder written inside angle brackets: <T>. A constraint says which protocol that placeholder has to carry: <T: Comparable> accepts only types that can be compared. Without a constraint the body knows nothing about T; it cannot even use the < operator.

The Measurement Setup

Probe is the first block in the same form in every lesson. In this lesson, a generic structure and a protocol with an associated type additionally sit in a separate helper file.

// Probe.swift — records when an expression is evaluated
final class Probe {
    let label: String
    private(set) var evaluations = 0
    private(set) var uses = 0
    private var evaluatedBeforeUse = false

    init(_ label: String) {
        self.label = label
    }

    func eval<T>(_ value: T) -> T {
        evaluations += 1
        if uses == 0 { evaluatedBeforeUse = true }
        return value
    }

    func use<T>(_ access: () -> T) -> T {
        uses += 1
        return access()
    }

    var moment: String {
        if evaluations == 0 { return "never" }
        if evaluations > 1 { return "on-every-use" }
        return evaluatedBeforeUse ? "immediately" : "on-first-use"
    }

    func report() {
        print("\(label): \(evaluations) evaluations, \(uses) uses -> \(moment)")
    }
}

func tally(_ probes: [Probe]) {
    for moment in ["immediately", "on-first-use", "on-every-use", "never"] {
        let count = probes.filter { $0.moment == moment }.count
        print("\(moment): \(count)")
    }
}

TS35. Every observation, apart from never, carries two uses; by binding the transformer to single-element arrays, we keep the number of elements from inflating the evaluation count.

// Stack.swift — a generic stack and a protocol with an associated type
protocol Container {
    associatedtype Item
    var count: Int { get }
    mutating func append(_ item: Item)
}

struct Stack<Element>: Container {
    private(set) var items: [Element] = []
    var count: Int { items.count }
    mutating func append(_ item: Element) { items.append(item) }
    mutating func pop() -> Element? { items.popLast() }
}

Container carries an associated type: Item. The protocol does not say which type will be stored, only that such a type will exist; the conforming type decides. Stack<Element>, on the other hand, is a generic structure: the Element placeholder turns into a real type when Stack<Int> or Stack<String> is written, and the Item type of Container is inferred as Element.

A Generic Body Runs on Every Call

The block below puts three things side by side. largest(_:tracking:) is a generic function with a Comparable constraint, and it is called with two different types. describe puts a constraint on the associated type with where. The last two observations are two forms of the same transformation: the eager map and lazy.map.

// main.swift — a generic function, a generic structure, an eager and a lazy map
func largest<T: Comparable>(_ values: [T], tracking tracker: Probe) -> T? {
    tracker.eval(values.max())
}

func describe<C: Container>(_ box: C) -> Int where C.Item: Comparable {
    box.count
}

let generic = Probe("generic-function")
let eager = Probe("eager-map")
let lazyMap = Probe("lazy-map")

_ = generic.use { largest([3, 9, 4], tracking: generic) }
_ = generic.use { largest(["b", "a"], tracking: generic) }

var stack = Stack<Int>()
stack.append(5)
stack.append(8)
print(describe(stack))
print(stack.pop() ?? -1)

let eagerDoubled = [4].map { eager.eval($0 * 2) }
_ = eager.use { eagerDoubled[0] }
_ = eager.use { eagerDoubled[0] }

let lazyDoubled = [4].lazy.map { lazyMap.eval($0 * 2) }
_ = lazyMap.use { lazyDoubled[0] }
_ = lazyMap.use { lazyDoubled[0] }

let all = [generic, eager, lazyMap]
for probe in all { probe.report() }
tally(all)

2
8
generic-function: 2 evaluations, 2 uses -> on-every-use
eager-map: 1 evaluations, 2 uses -> immediately
lazy-map: 2 evaluations, 2 uses -> on-every-use
immediately: 1
on-first-use: 0
on-every-use: 2
never: 0

The generic function ran on every call: largest was evaluated twice in two calls, and the calls were made with different types. A generic body is a single piece of writing but a separate call for each type; the moment of evaluation does not depend on the type parameter. describe and Stack worked only at the type level: the where C.Item: Comparable constraint was satisfied because the Item of Stack<Int> is Int, and the compiler checked this at the call.

The real distinction is in the last two lines. The eager map transforms the elements of the array immediately and builds a new array; the transformer ran once while eagerDoubled was being built and the two reads did not compute again: immediately. lazy.map, on the other hand, returns a lazy wrapper that stores the transformer; the sequence is built without computing anything, and on every access the transformer is called again. Two accesses to the same element gave two evaluations: on every use. TS36. This result was measured for an array-based lazy collection; a lazy Sequence was not assumed to be traversable again.

A lazy map behaves like a computed property, not like a stored property: the result sits nowhere. If you want to do the calculation once and keep it, you derive an array from the wrapper, which is an eager step.

A where Constraint Ties Two Types

A constraint put on a single type parameter (T: Comparable) forces a protocol. A where clause can say more: it can ask for the associated types of two type parameters to be the same, or for an associated type to conform to a protocol. The function below takes two containers and compares them only if their element types are the same: A.Item == B.Item. This is a compile-time check; in the measurement we see that the moment of evaluation of the body does not change.

// main.swift — tying the element types of two containers with where
func sameCount<A: Container, B: Container>(_ left: A, _ right: B, tracking tracker: Probe) -> Bool
    where A.Item == B.Item {
    tracker.eval(left.count == right.count)
}

let whereProbe = Probe("where-constraint")

var first = Stack<Int>()
first.append(1)
var second = Stack<Int>()
second.append(2)
second.append(3)

_ = whereProbe.use { sameCount(first, second, tracking: whereProbe) }
_ = whereProbe.use { sameCount(first, first, tracking: whereProbe) }

whereProbe.report()

where-constraint: 2 evaluations, 2 uses -> on-every-use

The body ran twice in two calls: on every use. The where clause decides whether a call is valid; it takes no part in the cost or the timing of a valid call. That the element types of the two stacks are the same is the compiler’s inference here and leaves no trace in the measurement. We did not separately try giving this function two stacks with different element types; we understand what the constraint does from reading the signature, not from the behavior of the body. TS37. The rejection by the constraint was not measured in this lesson.

A Constrained Extension on a Generic Structure

In lesson 07 we added a constrained extension to Array. The same holds for our own generic type: Stack can be used with every element type, but a method that asks for comparison makes sense only on stacks where Element: Comparable. A constrained extension limits the method to that case. The extension below finds the largest element.

// main.swift — a constrained extension for Stack
extension Stack where Element: Comparable {
    func largest(tracking tracker: Probe) -> Element? {
        tracker.eval(items.max())
    }
}

let constrained = Probe("constrained-extension")

var numbers = Stack<Int>()
numbers.append(4)
numbers.append(9)

_ = constrained.use { numbers.largest(tracking: constrained) }
_ = constrained.use { numbers.largest(tracking: constrained) }

constrained.report()

constrained-extension: 2 evaluations, 2 uses -> on-every-use

largest scans the stack again on every call: on every use. There is no cache inside the stack; the extension is subject to the very same rule as in lesson 07 and cannot add a stored field. The advantage of generic types is this: largest exists for Stack<Int>, while for an element type that cannot be compared, such as Stack<Counter>, the method of the constrained extension is not offered. A generic structure is written once, and its set of methods changes with the element type. TS38. The measurement was made only on a stack of Int elements; that the method is not visible with a non-Comparable element was not verified separately.

An Opaque Return Type with some

A generic function can choose the return type itself instead of leaving the choice to the caller, and it can hide that. An opaque return type is written like some Sequence<Int>: the function returns a specific type, but the signature says only “something that conforms to this protocol”. The caller does not know the real type; the compiler does. The question here is whether an opaque return changes the moment of evaluation. Two functions make the same transformation; one returns a lazy sequence and the other an eager array, both as some Sequence<Int>.

// main.swift — an opaque return with some: lazy and eager
func lazySquares(of values: [Int], tracking tracker: Probe) -> some Sequence<Int> {
    values.lazy.map { tracker.eval($0 * $0) }
}

func eagerSquares(of values: [Int], tracking tracker: Probe) -> some Sequence<Int> {
    values.map { tracker.eval($0 * $0) }
}

let lazyOpaque = Probe("opaque-lazy")
let eagerOpaque = Probe("opaque-eager")

let lazyResult = lazySquares(of: [3], tracking: lazyOpaque)
let eagerResult = eagerSquares(of: [3], tracking: eagerOpaque)

_ = lazyOpaque.use { Array(lazyResult) }
_ = lazyOpaque.use { Array(lazyResult) }
_ = eagerOpaque.use { Array(eagerResult) }
_ = eagerOpaque.use { Array(eagerResult) }

let all = [lazyOpaque, eagerOpaque]
for probe in all { probe.report() }

opaque-lazy: 2 evaluations, 2 uses -> on-every-use
opaque-eager: 1 evaluations, 2 uses -> immediately

Two functions with the same signature gave different moments. The lazy one computed again on every consumption: on every use. The eager one computed once during the call, and the two consumptions did not repeat it: immediately. some hides the real type but does not hide the behavior; whether what comes back is lazy or eager is not written in the signature, but it is visible in the measurement. This is why, in an API that carries an opaque return type, it is useful to state the cost of consumption separately in the documentation. TS39. The two functions were measured with a single-element input; the evaluation count with a multi-element input was deliberately left out here.

A Generic Function with an @autoclosure Parameter

The ?? operator of the standard library evaluates the right-hand side only if the left-hand side is nil. This is done with @autoclosure: the parameter is wrapped in a closure, but the caller writes an ordinary expression. In our own generic function we set up the same pattern: the orElse parameter is called only when needed.

// main.swift — a generic default value with @autoclosure
func unwrap<T>(_ value: T?, orElse backup: @autoclosure () -> T) -> T {
    if let value { return value }
    return backup()
}

let present = Probe("value-present")
let absent = Probe("value-absent")

let known: Int? = 7
let missing: Int? = nil

_ = present.use { unwrap(known, orElse: present.eval(0)) }
_ = present.use { unwrap(known, orElse: present.eval(0)) }
_ = absent.use { unwrap(missing, orElse: absent.eval(0)) }
_ = absent.use { unwrap(missing, orElse: absent.eval(0)) }

let all = [present, absent]
for probe in all { probe.report() }
tally(all)

value-present: 0 evaluations, 2 uses -> never
value-absent: 2 evaluations, 2 uses -> on-every-use
immediately: 0
on-first-use: 0
on-every-use: 1
never: 1

When there was a value, the backup expression was never evaluated: never. When there was no value, it was evaluated on every call: on every use. The generic function knows nothing about T, but its own body decides whether the closure will be called; what is deferred is independent of the type. This agrees with the main theme of the lesson: a generic body runs on every call, and even an expression inside the body may not run. TS40. The measurement was made with Int; it was not assumed that the result stays the same for types where the deferred expression has a side effect.

A Generic Structure Stores Its Elements

A value you put inside a generic structure is evaluated at the moment of insertion, whatever the type parameter is, and the structure holds that value. The expression given to Stack<Int> with append is computed on the caller’s side before append is called; the stack stores only the result. We measure this because it is important to see that a generic container does not behave as “lazy” or “computed”, it only carries.

// main.swift — a generic structure stores the value added to it
let element = Probe("stack-element")

var holder = Stack<Int>()
holder.append(element.eval(5))

_ = element.use { holder.count }
_ = element.use { holder.count }
_ = element.use { holder.pop() }

element.report()

stack-element: 1 evaluations, 3 uses -> immediately

The expression was evaluated once, on the line of insertion; reading the stack or pulling the element did not compute it again: immediately. In this respect a generic structure behaves like a stored property. If you want computed behavior, you give the structure a closure instead of a value, and in this case what is stored is the closure. TS41. It was measured with a single insertion and with Int; cases where the stack fills up and is resized are outside this measurement.

The Bounding Measurement

A lazy sequence has one transformer call per element, and the call is made only for the element that is read. The array below has two elements. The transformer uses one Probe for the first element and the other for the second. The sequence is read only with first.

// main.swift — the same lazy sequence, both on every use and never
let hot = Probe("read-element")
let cold = Probe("unread-element")

let pipeline = [10, 20].lazy.map { value -> Int in
    value == 10 ? hot.eval(value + 1) : cold.eval(value + 1)
}

_ = hot.use { pipeline.first }
_ = hot.use { pipeline.first }
_ = cold.use { pipeline.first }
_ = cold.use { pipeline.first }

hot.report()
cold.report()

read-element: 4 evaluations, 2 uses -> on-every-use
unread-element: 0 evaluations, 2 uses -> never

A single lazy sequence carried two separate moments. The first element was transformed again on every first call. There are four first calls in the block and all four read the first element; hot counted only its own two uses, but it saw all four evaluations: on every use. Nobody reached for the second element, and the transformer never ran on it: never, even with two uses. A lazy sequence does the opposite of the eager map: the eager array computes all elements immediately, the lazy sequence computes none of them beforehand. TS42. first evaluated only the first element; this is a result that depends on the first implementation of the collection and was measured on Swift 6.4.

Summary

• Generics let you write a body once with a type parameter and use it with many types; a constraint says which protocol the type has to carry.
• An associated type states that a protocol needs a type but that the conforming type will decide it; a constraint is put on this type with where.
• The eager map calls the transformer immediately; lazy.map calls it again on every access.
• For a never-read element of a lazy sequence, the transformer does not run; the same sequence can carry both on every use and never.
• This lesson’s moment: on every use (the lazy.map transformer, two accesses to the same element).

Next Step

So far every body ran to its end. But if something goes wrong in the middle of a body, what happens to the remaining lines? The next lesson measures throwing an error, and that the statements after a throw are not evaluated.