00: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. 00:29 To illustrate, here are some sample
expressions in a Ledger file:
2016/07/25 Lunch
Expenses:Food 10 USD
Assets:Checking
00:34 We're interested in the expressions on the righthand 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.
00:53 In Ledger, we can also have more complicated expressions. For
example, we can calculate on the righthand side, and we could say `(10 USD

5)`. 01:08 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
01: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. 01:53 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
. 02:18 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
02:24 That said, let's look at how to do this in Ledger. 02:26
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
}
}
02: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)
}
03: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() {
let expr = Expression.amount(Amount(value: 5, commodity: "EUR"))
XCTAssertEqual(expr.evaluate(), Amount(value: 5, commodity: "EUR"))
}
}
04:19 In our finished application, we get expressions out of the parser.
Here, however, we instantiate expressions in our test code. 05:15 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.
05:43 Now the tests pass:
extension Expression {
func evaluate() > Amount {
switch self {
case .amount(let amount):
return amount
}
}
}
Operators
05: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() {
let expr = Expression.infixOperator("+", Amount(value: 5), Amount(value: 2))
XCTAssertEqual(expr.evaluate(), Amount(value: 7))
}
07: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
}
}
08:10 We can now simplify our tests:
func testOperator() {
let expr = Expression.infixOperator("+", 5, 2)
XCTAssertEqual(expr.evaluate(), 7)
}
08:35 In Expression
, we now add the infixOperator
case:
enum Expression {
case amount(Amount)
case infixOperator(String, Amount, Amount)
}
09: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 lefthand and righthand sides:
extension Expression {
func evaluate() > Amount {
switch self {
case .amount(let amount):
return amount
case let .infixOperator("+", lhs, rhs):
}
}
09: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. 11:26 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
. 11:54 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() {
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() {
let expr = Expression.infixOperator("*", 5, 2)
XCTAssertEqual(try! expr.evaluate(), 10)
}
13:19 The testdriven 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 copypasting 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 copypaste 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. 20:52 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)
}
22:27 In our evaluate
method, we can't simply call compute
on the
lefthand and righthand 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() {
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() {
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() {
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.