Swift

Design Patterns

Functional Programming

Functional Design Patterns in Swift: Interpreter

Swift is different from Java, C# and Objective-C. These are all languages which appeared at the height of the object-oriented programming (OOP) craze. Especially Java and C# attempt to squeeze you into an object-oriented solution. Free functions are an abomination. You are supposed to add all functionality as methods to classes.

Fortunately the software development community has become more pragmatic and accepted that sometimes it is useful to think in terms of functions rather than objects. Newer programming languages such as Scala, Clojure, Swift, Kotlin and Julia all put more emphasis on functional constructs at the expense of OOP.

Recently I read Reza Shirazian Blog on Design Patterns in Swift, specifically the Interpreter pattern. He shows how to implement design patterns in the classical OOP tradition found in Java and C#.

What I like to do here is to show that there are other ways available to you in Swift. This is a demonstration of functional rather than object-oriented thinking. The idea is that you try to destill your problem into a composition of functions rather than objects.

Reza’s example was creating a program which can parse a simple mathematical expressions such as:

l + p - 10.00

We are not going to look at how we create a parse tree from a text string. Instead we look at how to build and evaluate a parse tree representing this expression.

A parse tree representing the expression l + p — 10.00

We want to create an abstract syntax tree as shown above representing a mathematical expression. Reza covers that well, so it will not be repeated here. Instead we will look at different ways of representing the nodes in the syntax tree. Next we will look at how this tree can be used to evaluate the mathematical expression.

Below is an example of composing several nodes to form such a syntax tree.

let exp = substract(add(variable("l"), variable("p")), number(10.0))

We can then evaluate it with values bound to the variables l and p.

var result = exp(["l": 2.0, "p": 4.0])

In Reza’s object-oriented approach, a single node like the Add node is represented as an object:

class Add: Expression {
 
  var leftOperand: Expression
  var rightOperand: Expression
 
  init(_ leftOperand: Expression, _ rightOperand: Expression) {
    self.leftOperand = leftOperand
    self.rightOperand = rightOperand
  }
 
  func interpret(_ variables: [String : Expression]) -> Double {
    return leftOperand.interpret(variables) + rightOperand.interpret(variables)
  }
}

He then repeats this pattern for describing the other operators such as subtraction, division and multiplication.

An expression is represented as a protocol:

protocol Expression {
  func interpret(_ variables: [String:Expression]) -> Double
}

A Functional Approach

In our example we will use functions. We define an expression as a function, rather than an object, which takes a dictionary mapping strings to double values and returning a double.

typealias Expression = ([String: Double]) -> Double

First we want a representation of a number literal

func number(_ value: Double) -> Expression {
    return { _ in
        return value
    }
}

We are creating a function number which returns another function (or closure to be more specific). The function returned is of type Expression meaning we can evaluate it by passing a dictionary of variables and their bound values.

We can make our add node in a similar fashion:

func add(_ leftOperand:  @escaping Expression, 
         _ rightOperand: @escaping Expression) -> Expression 
{
    return { variables in
        return leftOperand(variables) + rightOperand(variables)
    }
}

But as we can see from Reza’s example that turns into a lot of boilerplate code which looks the same. For every node the only difference in the code is the operator being switched from + to -, * and / respectively.

So we will instead embrace functional thinking and make a function which will make our expression functions.

So we are making a function which returns a function with this signature:

(@escaping Expression, @escaping Expression) -> Expression

+, -, * and / are all binary operators. So we are combining two expression to create an new expression in each case. Just ignore the @escaping keyword, it is there to make the compiler happy. This story was originally written prior to Swift 3.x.

We also need a way to pass in the binary operator we are performing in each expression. This will be represented by another type alias:

typealias BinaryOperator = (Double, Double) -> Double

So +, -, * and / all fit this description. E.g.

3 + 4

Can be thought of as:

+(3, 4)

So here is out function which creates binary expressions:

func binaryExpression(_ op: @escaping BinaryOperator) 
   -> ((@escaping Expression, @escaping Expression) -> Expression) 
{
    return { (_ leftOperand @escaping Expression, _ rightOperand @escaping Expression) -> Expression in
        return { (variables: [String: Double]) -> Double in
            op(leftOperand(variables), rightOperand(variables))
        }
    }
}

Let us dissect what this means. We return a function which takes a left and right expression.

return { leftOperand, rightOperand in
}

This function uses those operands to create a new expression. And an expression happens to be a function performing a binary operator on its operands:

return { (_ variables: [String: Double]) -> Double in
   op(leftOperand(variables), rightOperand(variables))
}

If we wrote this in regular function syntax it would look like:

func binary(_ variables: [String: Double]) -> Double {
   op(leftOperand(variables), rightOperand(variables))
}

So now we have a quick way of making all of our binary operator nodes:

let add = binaryExpression(+)
let substract = binaryExpression(-)
let multiply = binaryExpression(*)
let divide = binaryExpression(/)

Finally we got to have a variable node:

func variable(_ name: String) -> Expression {
    return { variables in
        variables[name] ?? 0.0
    }
}

Now we can combine all this to create a syntax tree and evaluate it:

let variables = ["l": 2.0, "p": 4.0]

let exp = substract(add(variable("l"), variable("p")), number(10.0))
exp(variables)

It probably takes a bit to get used to combining functions which return functions, which return functions. But as you can see it is a very powerful way of constructing code, which makes it possible to create a lot of functionality in relatively few lines of code.

Remark on Swift 5.x Update

I wrote this story a long time ago, before Swift 3.x, but decided to update the content for Swift 5. Not having written Swift code in quite some time, gives me another perspective on looking at this code.

I am not sure I necessarily recommend writing code the way I have done here. The abundant usage of the @escaping keyword makes the code look a lot more cluttered than in the past.