by Channing Walton on Oct 18, 2013

technical

Lance Walton’s Treelog is the result of a real problem that arose in a trading system that we were working on:

How can everything that happens to a trade be audited?

The first (and tedious) answer is copius logging by writing to some kind of audit data type or simple logger.

There are a number of problems with this approach:

- writing logging around computations often complicates the code as values must be extracted, recorded and then applied
- separating logic from the computation can lead to a mismatch between the log and the computation
- linear logs are very difficult to follow
- its not easy to control how much of a linear log to show a user if you do not know what is detail and what isn’t

Treelog resolves these issues by making the log itself a tree, reflecting the computational tree it logs, and uses techniques described in the Typeclassopedia to bring logging closer to the computation: the `Writer`

Monad, a Monad Transformer, and a cunning Monoid.

Note that this post is a more technical description of how Treelog was written. For a quick introduction of use please refer to the [README]. I will also refer you to Eugene Yokota’s excellent Scalaz tutorial to study the details of Scalaz where appropriate.

Here is an example which illustrates how Treelog is used (more examples):

```
val simple: DescribedComputation[Int] =
"Calculating sum" ~< {
for {
x ← 11 ~> ("x = " + _)
y ← 2 ~> ("y = " + _)
sum ← (x + y) ~> ("Sum is " + _)
} yield sum
```

`DescribedComputation[Value]`

is just a type alias for `EitherT[LogTreeWriter, String, Value]`

. `EitherT`

, a Monad Transformer, enables success and failure to be represented and will be covered below.

The log and value can be retrieved with `result.run.written`

and `result.run.value`

respectively. The written tree will look like this:

```
Calculating sum
x = 11
y = 2
Sum is 13
```

and the value will be `\/-(13)`

, which is Scalaz’s version of `Right`

.

The nodes of the tree contain a `LogTreeLabel`

:

```
sealed trait LogTreeLabel[A] {
def success: Boolean
def annotations: Set[A]
// ...
}
case class DescribedLogTreeLabel[A](description: String, success: Boolean, annotations: Set[A]) extends LogTreeLabel[A]
case class UndescribedLogTreeLabel[A](success: Boolean, annotations: Set[A]) extends LogTreeLabel[A]
```

The node is able to represent success or failure, may have a description, and a set of annotations. Annotations allow extra information to be carried in a Node which may be useful when working with the audit later. For our trading system that was other trades that were affected by the process as a side effect of processing a trade.

Treelog distinguishes between tree nodes that describe a computation, a `DescribedLogTreeLabel`

, and an `UndescribedLogTreeLabel`

which is a Tree with no description in the root. In the example above, the root node is a `DescribedLogTreeLabel`

containing the text `Calculating sum`

. This is an important distinction that informs the way trees must be combined by our Treelog monoid, which the `Writer`

needs (see below).

Note that originally, `LogTreeLabel`

was a case class defined like this:

```
case class LogTreeLabel(description: Option[String], success: Boolean, annotations: Set[Annotation])
```

This meant that `DescribedLogTreeLabel`

and `UndescribedLogTreeLabel`

were not necessary because the optional `description`

carried the equivalent information. However, we found the formulation above easier to work with.

Treelog makes use of some syntactic sugar inspired by Tony Morris’s post on `Writer`

. In the example above, `~>`

is a method on an implicitly constructed class which takes any value `x: T`

and returns a `DescribedComputation[T]`

, representing the value `x`

and a leaf node containing the description.

There is special support for `Boolean`

s, `Option`

s, `Either`

s and `Traversable`

s which you can learn about from the Treelog [README].

`Writer`

and MonoidWriter allows us to do computations while making sure that all the log values are combined into one log value that then gets attached to the result. – LYAH

`Writer`

s allow us to write a log embedded within a computation.

Here is a simple example using Scalaz, see the references for more detailed examples.

```
val r: Writer[String, Int] =
for {
a ← 3.set("Got a 3.")
b ← 5.set("Got a 5.")
} yield a * b
println(r.written) // Got a 3.Got a 5.
println(r.value) // 15
```

The `Writer`

uses a monoid for the written value (a `String`

in this case) to combine the logs (concatenation for `String`

s). For `List`

s it is `:::`

and `Nil`

, etc.

Treelog uses a Scalaz Writer, Tree and a custom Monoid implementation to record logs.

The monoid has to provide two things: a `zero`

value, and a binary operation that combines two trees in a meaningful way. The `zero`

value for Treelog is just a constant used internally to the `Monoid´ implementation and never leaks out since there is always at least one value being logged.

Combining trees is done as follows:

- a
`zero`

tree with a tree is just the tree - two undescribed trees become a new undescribed tree with the children of the right tree appended to the children of the left tree
- an undescribed tree
`T1`

, and a described tree,`T2`

, becomes an undescribed tree with`T2`

appended to the children of`T1`

- a described tree,
`T1`

, and an undescribed tree,`T2`

, is an undescribed tree with`T1`

prepended to the children of`T2`

- two described trees are combined by creating an undescribed tree with the two trees as children

Note that the result is always an undescribed tree since there is no meaningful way to combine descriptions of child nodes. In the example above the tree contains two leaves: “Got a 3” and “Got a 5”. Concatenating those descriptions isn’t as meaningful as “Summing a and b”, which could be done like this:

```
val r: Writer[String, Int] =
"Summing a and b" ~< for {
a ← 3.set("Got a 3.")
b ← 5.set("Got a 5.")
} yield a * b
```

The quadratic roots example is a good one to see this.

`EitherT`

The purpose of Treelog is to audit a computation, return the log and result, and indicate whether the computation was successful or not. The Writer with the Monoid described above satisfies the first two requirements, but not the third. To add success and failure, the writer needs to be combined with `Either`

. What we need is a Monad Transformer.

Monad Transformers are special types that allow us to roll two monads into a single one that shares the behaviour of both. – Haskell Wikibook

`EitherT`

is a monad transformer that combines some monad with `Either`

, which is exactly what is needed. It is constructed with three types: `EitherT[M, A, B]`

where `M`

is the monad, `A`

is the failure type and `B`

is the success type. In Treelog, `M`

is a `Writer`

, `A`

is a `String`

and `B`

is the type of the result.

Logtree includes the methods `def failure[V](description: String): DescribedComputation[V]`

and `def success[V](value: V, description: String): DescribedComputation[V]`

to support failure and success. They ensure that the failure case is included in the tree and that the nodes in the tree now reflect that the computation has failed.

Here is an example from Treelog:

```
val foo: String \/ Int = 11.right[String]
val bar: String \/ Int = "fubar".left[Int]
val leftEithers: DescribedComputation[Int] =
"Calculating left either sum" ~< {
for {
x ← foo ~>? ("x = " + _)
y ← bar ~>? ("y = " + _)
sum ← (x + y) ~> (v ⇒ "Sum is " + v)
} yield sum
}
val leftEitherWriter: LogTreeWriter[String \/ Int] = leftEithers.run
println(leftEithers.run.written.shows)
```

To retrieve the underying value back from `EitherT`

, we call `run`

which returns the `Writer`

containing Scalaz’s version of `Either`

(which is more useful than Scala’s built-in `Either`

).

The written value is:

```
Failed: Calculating left either sum
x = 11
Failed: fubar
Failure: Calculating left either sum
```

So the written log indicates that the whole computation failed, and the result is `-\/`

, the `Left`

for a Scalaz `Either`

, containing “Failure: Calculating left either sum”.

Treelog is being used in earnest in a trading system, and the results have been a resounding success. And the level of accurate detail the system is able to show users has been invaluable in reducing support questions, which is always welcome.