## Swift Talk #11 Evaluating Expressions 29:36

We write an evaluator for a simple expression language. We write our code in a test-driven way, which saves us time and helps us verify the correctness the code.

### Source Code

0:06 Let's look at evaluating expressions in Ledger. When we display a Ledger file, we first parse the file. After that, we evaluate the contents of the parsed file. This episode is about the step that comes after parsing: computing everything. To illustrate, here are some sample expressions in a Ledger file:

```
2016/07/25 Lunch
Expenses:Food 10 USD
Assets:Checking
```

0:34 We're interested in the expressions on the right-hand side of a
posting. For example, the `Expenses:Food`

posting has the expression `10 USD`

.
This is the simplest possible expression: it's a number with a currency. In
Ledger, we can also have more complicated expressions. For example, we can
calculate on the right-hand side, and we could say `(10 USD * 5)`

. We can also
perform all kinds of different calculations: add, divide, multiply, and so on.
We can even use variables. For example, we could introduce a variable first and
then use it in an expression:

```
define numberOfPeople=5
2016/07/25 Lunch
Expenses:Food (10 USD * numberOfPeople)
Assets:Checking
```

1:35 We have to handle all these cases in our evaluator. The topic of
evaluating expressions might seem a bit obscure at first. However, many apps
have some form of expression evaluation. If you look at a spreadsheet, for
example, or at a compiler, it's the same thing: you get a parsed expression and
you need to do something with it — maybe interpret it or compile it. Even in
apps like Photoshop or Sketch, you can often type in the measurements as an
expression, so you could write: `100px/2`

, which evaluates to `50px`

.
Expression evaluation is an interesting problem to solve, and once you know how
to solve it, you can apply the techniques everywhere.

## Representing the Expressions

2:24 That said, let's look at how to do this in Ledger. The first step
is to represent the expressions. Currently, when we look at our Xcode project,
we already have an `Amount`

struct defined. It represents the combination of a
number and a commodity — for example, `10 USD`

:

```
struct Amount: Equatable {
var value: LedgerDouble
var commodity: Commodity?
init(value: LedgerDouble, commodity: Commodity? = nil) {
self.value = value
self.commodity = commodity
}
}
```

2:51 If Ledger only supported amounts for postings, we would already be
done. However, since we can write expressions, we need to wrap the above. We can
start by writing an `Expression`

enum for all the different cases in an
expression. The most straightforward case is the `amount`

case, which is what we
use whenever we have an expression that's just an amount. Later on, we'll add
cases for operators and identifiers:

```
enum Expression {
case amount(Amount)
// operator
// variable
}
```

3:49 Let's write a test for this. We want to evaluate an `Expression`

and compute the final amount we get out, so we'll start with a simple test. For
the `.amount`

case, it's easy — we test whether or not an `Expression.amount`

evaluates to the corresponding amount:

```
class ExpressionEvaluationTests: XCTestCase {
func testAmount() {
// 5 EUR
let expr = Expression.amount(Amount(value: 5, commodity: "EUR"))
XCTAssertEqual(expr.evaluate(), Amount(value: 5, commodity: "EUR"))
}
}
```

4:19 In our finished application, we get expressions out of the parser.
Here, however, we instantiate expressions in our test code. Let's write an
extension and implement the `evaluate`

method. The method returns an `Amount`

,
and the initial implementation is straightforward: we switch on `self`

, and
because we only have a single case, we just return the amount. Now the tests
pass:

```
extension Expression {
func evaluate() -> Amount {
switch self {
case .amount(let amount):
return amount
}
}
}
```

## Operators

5:54 In a second test case, we test an operator. We'd like to test an
expression like `5 + 2`

, so we write an expression representing the addition. We
need a second `Expression`

case for the operator, which we could call
`infixOperator`

. It will have three associated values: an operator name, and two
amounts. We'd like to test that it evaluates to `7`

:

```
func testOperator() {
// 5 + 2
let expr = Expression.infixOperator("+", Amount(value: 5), Amount(value: 2))
XCTAssertEqual(expr.evaluate(), Amount(value: 7))
}
```

7:06 Before we make our test pass, let's add a small convenience helper
to read and write these tests, because they get a little bit difficult to read
after a while. We can make our `Amount`

struct conform to the
`IntegerLiteralConvertible`

protocol so that we can initialize an `Amount`

from
an integer literal:

```
extension Amount: IntegerLiteralConvertible {
init(integerLiteral value: LedgerDouble) {
self.value = value
self.commodity = nil
}
}
```

8:10 We can now simplify our tests:

```
func testOperator() {
// 5 + 2
let expr = Expression.infixOperator("+", 5, 2)
XCTAssertEqual(expr.evaluate(), 7)
}
```

8:35 In `Expression`

, we now add the `infixOperator`

case:

```
enum Expression {
case amount(Amount)
case infixOperator(String, Amount, Amount)
// variable
}
```

9:09 The compiler helps us by warning that the `switch`

statement in
`evaluate`

is no longer exhaustive, so let's implement the `+`

operator. We'll
switch on `self`

and add a new case, `infixOperator`

. We match on the `+`

symbol
and define variables for the left-hand and right-hand sides:

```
extension Expression {
func evaluate() -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator("+", lhs, rhs):
// TODO
}
}
```

9:38 Here we want to return an amount. We could, for example, write ```
lhs
+ rhs
```

. However, there's not yet a definition of `+`

on `Amount`

. So before we
do that, let's add a default case to the `switch`

statement and make it crash
for now. This is something we'll fix later:

```
extension Expression {
func evaluate() -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator("+", lhs, rhs):
return lhs + rhs
default:
fatalError()
}
}
}
```

10:12 We now need a `+`

operation for amounts, and we can simply define
it as a function that takes two `Amount`

s and returns an `Amount`

. Because we
can't add amounts like `5 USD + 2 EUR`

, we add a `guard`

statement to ensure
that the commodities are equal. However, what do we do in the `else`

case? We
could crash or we could return `nil`

, but we choose to throw an error. This way,
we know what went wrong, and we can use the information during evaluation.

## Error Messages

11:16 Because there are a lot of different places where things could go
wrong, it would be nice to throw an error with more specific information than
just a `nil`

value. We made `String`

conform to the `Error`

protocol, and that
way we can `throw`

a simple `String`

value. We also need to mark our function as
`throws`

. Now that we're outside of the guard, we can create a new `Amount`

with the two values added together, along with their commodity:

```
func +(lhs: Amount, rhs: Amount) throws -> Amount {
guard lhs.commodity == rhs.commodity else {
throw "Commodities don't match"
}
return Amount(value: lhs.value+rhs.value, commodity: lhs.commodity)
}
```

12:15 Now we'll have to add `try`

everywhere. We need to mark the call
to `+`

with a `try`

keyword, mark `evaluate`

as `throws`

, and add `try`

keywords
in our tests:

```
extension Expression {
func evaluate() throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator("+", lhs, rhs):
return try lhs + rhs
default:
fatalError()
}
}
}
// ...
class ExpressionEvaluationTests: XCTestCase {
func testAmount() {
// 5 EUR
let expr = Expression.amount(Amount(value: 5, commodity: "EUR"))
XCTAssertEqual(try! expr.evaluate(), Amount(value: 5, commodity: "EUR"))
}
// ...
}
```

12:36 Now our tests pass.

12:48 The next step is to add another operator. We currently cover `+`

,
so let's add `*`

for multiplication. We'll start by copying and modifying our
test for addition:

```
func testMultiplication() {
// 5 * 2
let expr = Expression.infixOperator("*", 5, 2)
XCTAssertEqual(try! expr.evaluate(), 10)
}
```

13:19 The test-driven approach works really well for the problem we're now solving, but it would be hard to test all of this manually, as we don't have an easy way to construct expressions without a parser and a UI. We don't often write tests for large parts of our projects because it's just the two of us, and the tradeoff isn't worth it. But here, it's perfect.

14:10 When we run our test, we now crash in our `default`

case, and
we'll implement multiplication by again copy-pasting the code for addition.
We'll copy the `case`

in the `switch`

statement:

```
// ...
case let .infixOperator("*", lhs, rhs):
return try lhs * rhs
// ...
```

14:41 For the `*`

operator, we can copy-paste the `+`

operator and
modify it accordingly:

```
func *(lhs: Amount, rhs: Amount) throws -> Amount {
guard lhs.commodity == rhs.commodity else {
throw "Commodities don't match"
}
return Amount(value: lhs.value*rhs.value, commodity: lhs.commodity)
}
```

15:04 Now all the tests pass, but our code isn't nice — and it's repetitive. We need to refactor, and we have the tests in place, so it should be possible.

## Refactoring

15:23 First, we could remove the duplication in the operator
definitions, and we could write them as an extension on `Amount`

. The method
takes an amount and an operator function with type ```
(LedgerDouble,LedgerDouble)
-> LedgerDouble
```

. It returns an `Amount`

as well. And just like the original
operator definitions, this method can throw:

```
extension Amount {
func compute(operatorFunction: (LedgerDouble,LedgerDouble) -> LedgerDouble, other: Amount) throws -> Amount {
guard commodity == other.commodity else {
throw "Commodities don't match"
}
return Amount(value: operatorFunction(value,other.value), commodity: commodity)
}
}
```

We can now delete our operator definitions and use our `compute`

method inside
`evaluate`

:

```
extension Expression {
func evaluate() throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator("+", lhs, rhs):
return try lhs.compute(operatorFunction: +, other: rhs)
case let .infixOperator("*", lhs, rhs):
return try lhs.compute(operatorFunction: *, other: rhs)
default:
fatalError()
}
}
}
```

17:49 The tests still pass.

17:57 Next, we should improve our `switch`

statement. Having the
`default`

case is dangerous, as we might forget to implement a case on
`Expression`

, so let's restructure the `switch`

statement. We add an
`infixOperator`

case, and we match on the operator symbol in a nested switch.
This allows us to move the `default`

case inside the nested switch. This is an
improvement, because the `default`

isn't at the outermost switch anymore. If we
were to add another case to `Expression`

, we'd get a warning again:

```
extension Expression {
func evaluate() throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator(op, lhs, rhs):
switch op {
case "+":
return try lhs.compute(operatorFunction: +, other: rhs)
case "*":
return try lhs.compute(operatorFunction: *, other: rhs)
default:
fatalError()
}
}
}
}
```

## Removing Duplication

19:18 We can do even better, because the cases for addition and
multiplication are almost identical — only the operator is different. Instead of
the switch, we can put the operators in a dictionary with the symbols as the
keys. In case we can't look up an operator, we can throw an error instead of
crashing. We can also get rid of the `switch`

statement, and our code becomes a
lot simpler. Our tests still run:

```
extension Expression {
func evaluate() throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator(op, lhs, rhs):
let dict: [String: (LedgerDouble, LedgerDouble) -> LedgerDouble] = [
"+": (+),
"*": (*)
]
guard let operatorFunction = dict[op] else { throw "Undefined operator: \(op)" }
return try lhs.compute(operatorFunction: operatorFunction, other: rhs)
}
}
}
```

21:40 The name `dict`

isn't very descriptive, so let's change it to
`operators`

.

21:52 Also, we're cheating a bit. We can represent expressions like
`2+7`

, but we can't represent expressions like `2+7+8`

. We defined our
`infixOperator`

with `Amount`

s, and we'd like the operands to be `Expression`

s
instead, so we change the associated value to `Expression`

:

```
enum Expression {
case amount(Amount)
case infixOperator(String, Expression, Expression)
// variable
}
```

22:27 In our `evaluate`

method, we can't simply call `compute`

on the
left-hand and right-hand sides. Instead, we first need to recursively evaluate
the operands:

```
extension Expression {
func evaluate() throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator(op, lhs, rhs):
let operators: [String: (LedgerDouble, LedgerDouble) -> LedgerDouble] = [
"+": (+),
"*": (*)
]
guard let operatorFunction = operators[op] else { throw "Undefined operator: \(op)" }
let left = try lhs.evaluate()
let right = try rhs.evaluate()
return try left.compute(operatorFunction: operatorFunction, other: right)
}
}
}
```

23:02 We also need to change our tests:

```
func testOperator() {
// 5 + 2
let expr = Expression.infixOperator("+", .amount(5), .amount(2))
XCTAssertEqual(try! expr.evaluate(), 7)
}
```

23:18 The code doesn't work yet. The compiler tells us that the
`Expression`

enum needs to be marked as `indirect`

because we defined it
recursively. After doing that, the tests pass, and we can have complicated
nested expressions.

## Adding Variables

23:56 There's a final element missing: we want to use variables within
our expressions. Let's write a test for that. More specifically, we'd like to
test that an identifier lookup works. When we evaluate the expression
`numberOfPeople`

, we expect the result to be five. This means that we also need
some way to specify that the `numberOfPeople`

variable currently has a value of
five. Of course, we don't really know up front where it will be defined. Just
like in a programming language, a variable could be defined as a local variable,
or maybe it's defined one scope up, or somewhere else. To represent this, we'll
add a `context`

dictionary with the current variables and their values, and
we'll pass the `context`

dictionary to our `evaluate`

method:

```
func testIdentifier() {
// numberOfPeople
let expr = Expression.identifier("numberOfPeople")
let context: [String: Amount] = ["numberOfPeople": 5]
XCTAssertEqual(try! expr.evaluate(context: context), 5)
}
```

26:16 We'll need to change our `evaluate`

method and add a parameter
for the context. We'll also need to pass it on recursively:

```
extension Expression {
func evaluate(context: [String:Amount]) throws -> Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator(op, lhs, rhs):
let operators: [String: (LedgerDouble, LedgerDouble) -> LedgerDouble] = [
"+": (+),
"*": (*)
]
guard let operatorFunction = operators[op] else { throw "Undefined operator: \(op)" }
let left = try lhs.evaluate(context: context)
let right = try rhs.evaluate(context: context)
return try left.compute(operatorFunction: operatorFunction, other: right)
}
}
}
```

26:48 Additionally, we'll add a third case to our `Expression`

enum:

```
indirect enum Expression {
case amount(Amount)
case infixOperator(String, Expression, Expression)
case identifier(String)
}
```

26:52 In the `evaluate`

method, we look up the identifier in the
`context`

dictionary. In the `nil`

case, we simply throw an error:

```
case .identifier(let name):
guard let value = context[name] else {
throw "Unknown variable \(name)"
}
return value
```

27:46 We update all our tests and add an empty context. Rather than
adding a default value to the `evaluate`

method, we require callers to specify
the value explicitly. This way, we can't accidentally forget to pass it on.

28:12 Our tests now pass. Let's add a final test for recursive expressions, where we combine multiplication and an identifier into a single expression:

```
func testMultiplicationWithIdentifier() {
// 10 * numberOfPeople
let expr = Expression.infixOperator("*", .amount(10), .identifier("numberOfPeople"))
XCTAssertEqual(try! expr.evaluate(context: ["numberOfPeople": 5]), 50)
}
```

28:54 Because we already implemented this, the test passes straight away.

29:06 It almost feels like we're implementing a little scripting language, which makes sense because the techniques you'd use for evaluating an interpreted language are exactly the same. In the next episode, we'll look into evaluating entire transactions and postings.