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 craze. Especially Java and C# always attempt to squeeze your solutions into an Object Oriented framework. Free functions are not supposed to exist. They are supposed to be part of some class.

Since then, the software development community as a whole 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 compose 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 we can build and evaluate a parse tree representing this expression.

So what we want to do is to create an abstract syntax tree as shown above representing our mathematical expression. Reza covers that quite well, so I will not repeat that. Instead I will look at how we can represent the individual nodes in the syntax tree and how they can be composed to form the tree as well as how we can evaluate this tree.

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

let expression = 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)
}
}

The he 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. So we define an expression as a function 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: Expression, rightOperand: 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:

(Expression, Expression) -> Expression

+, -, * and / are all binary operators. So we are combining two expression to create an new expression in each case.

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: BinaryOperator) -> ((Expression, Expression) -> Expression) {
return { leftOperand, rightOperand 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.