Treelog

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.

Logging with Treelog

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.

Tree Nodes

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.

Syntactic Sugar

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 Booleans, Options, Eithers and Traversables which you can learn about from the Treelog [README].

Writer and Monoid

Writer 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

Writers 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 Strings). For Lists it is ::: and Nil, etc.

Treelog’s Monoid

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.

Success and Failure – 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”.

In Practice

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.

Further Reading

• Monad Transformers in Scala
• Monad Transformers in the Wild