objc.io

00:06 Today we're going to do something a little bit different. We've done a lot of SwiftUI and UI stuff and practical things, but today we'll do something more functional. We've built many parsers and abstract syntax trees (ASTs) on Swift Talk already, and yet we're going to look at this kind of stuff again because it's a useful technique to know.

00:41 We start with a simple AST and write some functions on it. If we were to build a simple calculator or a spreadsheet, we'd typically have an expression enum with various cases for operators and one case for an integer. Because the enum is recursive — i.e. it has associated values of its own type — we need to mark it as indirect:

indirect enum Expr {
    case add(Expr, Expr)
    case minus(Expr, Expr)
    case times(Expr, Expr)
    case div(Expr, Expr)
    case int(Int)
}

01:27 To evaluate an expression of this type, we switch on self and we go through the cases:

extension Expr {
    func evaluate() -> Int {
        switch self {
        case .add(let expr1, let expr2):
            return expr1.evaluate() + expr2.evaluate()
        case .minus(let expr1, let expr2):
            return expr1.evaluate() - expr2.evaluate()
        case .times(let expr1, let expr2):
            return expr1.evaluate() * expr2.evaluate()
        case .div(let expr1, let expr2):
            return expr1.evaluate() / expr2.evaluate()
        case .int(let value):
            return value
        }
    }
}

02:00 Instead of #Preview, we use the #Playground macro to see the evaluation of our sample expression:

#Playground {
    let sample = Expr.times(Expr.add(.int(5), .int(7)), .int(2))
    print(sample.evaluate())
}

03:01 The result of adding 5 and 7 and then multiplying by 2 is, as we'd expect, 24.

03:05 If we want to pretty-print an expression, we do basically the same thing. To build up a String, we switch on self again and we recursively call pretty on the nested expressions:

func pretty() -> String {
    switch self {
    case .add(let expr1, let expr2):
        return "\(expr1.pretty()) + \(expr2.pretty())"
    case .minus(let expr1, let expr2):
        return "\(expr1.pretty()) - \(expr2.pretty())"
    case .times(let expr1, let expr2):
        return "(\(expr1.pretty())) * (\(expr2.pretty()))"
    case .div(let expr1, let expr2):
        return "(\(expr1.pretty())) / (\(expr2.pretty()))"
    case .int(let value):
        return "\(value)"
    }
}

03:52 There's one gotcha for the .times and .div cases, whose left-hand side or right-hand side expressions may contain an addition or subtraction operation, around which we need to add parentheses. We're just going to add them in any case, so we'll generate more parentheses than necessary, but that's okay.

04:20 Now we can pretty-print our expression, and it prints the string (5 + 7) * (2):

#Playground {
    let sample = Expr.times(.add(.int(5), .int(7)), .int(2))
    print(sample.evaluate())
    print(sample.pretty())
}

Creating a Generic Functor

04:39 Now, let's transform this concrete Expr type into something more generic. Instead of having each case like .add take two Expr values directly, we can replace every recursive position with a generic parameter.

05:25 This creates what's called a pattern functor or base functor — essentially we're abstracting away the recursive structure so that we can write a map function that handles recursion automatically. This gives us the flexibility to, for example, swap out simple values with annotated values.

05:57 Consider a spreadsheet or code editor that needs to track where each expression comes from — i.e. which spreadsheet cell or which source line and column. With our functor approach, we can change the generic parameter to something that holds not just a value, but also a source location or another kind of annotation.

06:23 To implement this, we first replace each recursive position with a generic parameter, R. The leaf case, .int, remains the same, because it doesn't contain any sub-expressions:

indirect enum ExprFunctor<R> {
    case add(R, R)
    case minus(R, R)
    case times(R, R)
    case div(R, R)
    case int(Int)
}

07:22 We write a specialized evaluation method of this functor for the case where R is Int. In this type of expression, all sub-expressions are basically already evaluated, so there's no recursion here:

extension ExprFunctor where R == Int {
    func evaluate() -> Int {
        switch self {
        case .add(let expr, let expr2):
            return expr + expr2
        case .minus(let expr, let expr2):
            return expr - expr2
        case .times(let expr, let expr2):
            return expr * expr2
        case .div(let expr, let expr2):
            return expr / expr2
        case .int(let value):
            return value
        }
    }
}

08:37 Next, we need a map function on the generic functor. This function transforms each recursive position using a provided function that transforms an R into an O (for output), changing ExprFunctor<R> to ExprFunctor<O>. We enable the map function to handle a throwing transformation function by adding throws and rethrows:

extension ExprFunctor {
    func map<O>(_ f: (R) throws -> O) rethrows -> ExprFunctor<O> {
        switch self {
        case .add(let r, let r2):
            try .add(f(r), f(r2))
        case .minus(let r, let r2):
            try .minus(f(r), f(r2))
        case .times(let r, let r2):
            try .times(f(r), f(r2))
        case .div(let r, let r2):
            try .div(f(r), f(r2))
        case .int(let int):
            .int(int)
        }
    }
}

10:31 The type system ensures we transform every recursive position, because forgetting to call f would cause a compilation error.

Reconstructing the Original Expression Type

11:15 We can now use ExprFunctor to define the original Expr, and let map handle the recursion for us. For this we need to create a specialized version of ExprFunctor that uses its own type for the R parameter. In the functional world, this recursive version is called the fixed version:

struct FixedExpr {
    let expr: ExprFunctor<FixExpr>
}

11:58 FixExpr holds an expression whose generic parameter R is FixExpr itself. This creates the recursive structure we need, because each FixExpr contains an ExprFunctor<FixExpr>, enabling unlimited nesting.

12:39 To evaluate FixedExpr, we can now use map on the functor wrapper, evaluating each nested expression. This creates an ExprFunctor<Int>, on which we can call our specialized, non-recursive evaluate method:

extension FixExpr {
    func evaluate() -> Int {
        return self.expr.map { $0.evaluate() }.evaluate()
    }
}

13:37 Constructing FixExpr values is verbose because we must explicitly wrap each sub-expression. A custom initializer that removes the label helps a little bit, but it's still hard to read:

struct FixedExpr {
    let expr: ExprFunctor<FixExpr>

    init(_ expr: ExprFunctor<FixExpr>) {
        self.expr = expr
    }
}

// ...

#Playground {
    let sample = Expr.times(.add(.int(5), .int(7)), .int(2))

    let sample2 = FixedExpr(.times(
        .init(.add(
            .init(.int(5)),
            .init(.int(7))
        )),
        .init(.int(2))
    ))

    print(sample.evaluate())
    print(sample.pretty())
    print(sample2.evaluate())
}

15:10 We can implement pretty printing for the ExprFunctor wrapper by writing another constrained extension, this time for the case where the R parameter is equal to String. We copy the original pretty from earlier and we remove the recursion:

extension ExprFunctor where R == String {
    func pretty() -> String {
        switch self {
        case .add(let expr, let expr2):
            "\(expr) + \(expr2)"
        case .minus(let expr, let expr2):
            "\(expr) - \(expr2)"
        case .times(let expr, let expr2):
            "(\(expr)) * (\(expr2))"
        case .division(let expr, let expr2):
            "(\(expr)) / (\(expr2))"
        case .int(let value):
            "\(value)"
        }
    }
}

16:07 Again, map handles the recursive traversal, converting each FixExpr to its string representation. The result is an ExprFunctor<String> that we can pretty-print without recursion:

extension FixedExpr {
    func evaluate() -> Int {
        expr.map { $0.evaluate() }.evaluate()
    }

    func pretty() -> String {
        expr.map { $0.pretty() }.pretty()
    }
}

17:00 While this seems like a lot of extra work for the same result as Expr, we've gained something valuable: a reusable recursive structure. The map function encapsulates the recursion, so adding new operations like evaluate and pretty requires no additional recursive code.

17:32 This relates to our structural programming episodes, but here we're programming over recursive patterns rather than data shapes.

Array-Based Expression Representation

17:48 The functor pattern enables another common compiler technique: representing expression trees as flat arrays with index-based references instead of nested structures.

18:14 Our enum with simple calculus operations combined with a tree structure models the input of a traditional calculator, where we type an expression with the infix notation: 1 + 1 * 5. But there's also a different kind of calculator that uses postfix notation, where we enter 5 7 + 2 * — so first the operands, then the operators. Our functor can represent both approaches.

19:06 To demonstrate this, we can create an array-based representation where recursive positions become array indices. An add operation references indices 0 and 1, which might contain the values 5 and 7. The add itself sits at index 2, referencing its operands by position. This transforms our tree structure into a flat array where operations reference their operands by index rather than containing them directly.

20:08 To implement this, we need a type to represent array positions. It'd be confusing to work with ExprFunctor<Int>, because an Int could represent a value or an index. To avoid this, we write a new type to represent an index:

struct ArrayIndex {
    let idx: Int

    init(_ idx: Int) {
        self.idx = idx
    }
}

20:42 Now we can represent our sample expression as a flat array. Each element is either a value or an operation that references other elements by index:

let sample3: [ExprFunctor<ArrayIndex>] = [
    .int(5),
    .int(7),
    .add(ArrayIndex(0), ArrayIndex(1)),
    .int(2),
    .times(ArrayIndex(2), ArrayIndex(3))
]

23:07 We can evaluating this representation by writing an extension on this type of array. The evaluation method, which we'll call with a specific index, will need to resolve index references by looking up other values in the array. By looking up the element at the given index, we have an ExprFunctor<ArrayIndex>, on which we call map to transform it into an ExprFunctor<Int>:

extension Array where Element == ExprFunctor<ArrayIndex> {
    func evaluate(at index: Int) -> Int {
        self[index].map { self.evaluate(at: $0.idx) }.evaluate()
    }
}

25:33 The map operation resolves all index references, replacing them with evaluated results. An .add case of ExprFunctor<ArrayIndex> that previously referenced indices 0 and 1 has now become an .add case of ExprFunctor<Int>, containing the actual integers from those positions. We then evaluate this resolved expression using our standard method.

26:15 This demonstrates the power of our functor approach. If we'd add another case to ExprFunctor, we don't need to change anything to make it work for each specific representation. The same evaluation logic works whether we're dealing with trees or arrays.

26:26 Now we should be able to evaluate the last element (with index 4) of our sample array representation:

print(sample3.evaluate(at: 4)) // prints 24

Discussion

27:26 What's so nice about the functor wrapper is that we could add a new case to it, and everything else would keep working. Only the core evaluation logic needs updating.

27:43 The interaction between map and recursive evaluation can be confusing at first. Our recursive calls return Int values, but map packages these into a new ExprFunctor structure, maintaining the expression shape while changing the content type. Just like Array.map, this preserves the structure while transforming the contents. Having map at the center of it is why functional programmers call these types "functors."

28:05 Once we get the general idea, the functional patterns can be cool to work with, but it's also easy to get distract by all the generics. For simple cases, the direct approach might be better. But if we need to support multiple representations of the same structure, the functor pattern can really shine.

28:39 Our examples show the reusability: one expression type can be used for trees, arrays, annotated expressions, or any other variant we need. Instead of defining separate types for each use case, we parameterize a single type and get all variations for free.

Stack-Based Representation

28:56 As a final example — or an exercise for the viewers — we can consider a stack-based evaluation using ExprFunctor<Void>:

let sample4: [ExprFunctor<Void>] = [
    .int(5),        // Push 5
    .int(7),        // Push 7
    .add((), ()),   // Pop two, add, push result
    .int(2),        // Push 2
    .times((), ())  // Pop two, multiply, push result
]

29:15 Each Void value — i.e. () — replaces an index reference. Whenever a Void is encountered, we have to pop a value off the stack, compute the result, and push the result back onto the stack. It can be tricky but fun to get the implementation right.