Tag Archives: oop

A small benchmark util for Scala continued

Extending the benchmark

Note: This is a follow-up post of a previous post. You might want to read the first to get a simpler view of the extensions added here.

One improvement I wanted to add to the previous benchmark util was monitors which generate statistics for the task being benchmarked. I chose traits for implementing them. That way I’ll be able to adapt the monitor using inheritance. A Monitor is simply defined as having a begin() and end() method, where end() returns a sequence of statistical data. The type of data returned is defined by the type parameter of Monitor.

In addition to the Monitor trait the previous code get extended with a newMonitor() argument for instantiating them:

case class TaskDone[Id,Stats](id: Id, run: Int, stats: Seq[Stats])
case class TaskFail[Id,Stats](id: Id, run: Int, stats: Seq[Stats], error: Throwable)
case class BenchDone[Id,Stats](warmups: Seq[Task[Id,Stats]], runs: Seq[Task[Id,Stats]])
 
trait Monitor[Stats] {
  private[this] var step = 0
  def begin(): Unit = {
    assert(step == 0, "Improperly handled monitor.")
    step = 1
  }
  def end(): Seq[Stats] = {
    assert(step == 1, "Improperly handled monitor.")
    step = 2
    Nil
  }
}
 
type Report[Result]  = Result => Unit
type Make[Value]     = () => Value
type Task[Id,Stats]  = Either[TaskFail[Id,Stats],TaskDone[Id,Stats]]
type Bench[Id,Stats] = BenchDone[Id,Stats]
type Batch[Id,Stats] = Seq[Bench[Id,Stats]]
 
def task[Id,Stats]
    (id: Id, fn: () => Unit)
    (run: Int)
    (newMonitor: Make[Monitor[Stats]])
    (report: Report[Task[Id,Stats]]): Task[Id,Stats] = {
  val monitor = newMonitor()
  monitor.begin()
  val result = try {
    fn()
    Right(TaskDone(id=id,run=run,stats=monitor.end()))
  } catch {
    case exp: Throwable =>
      Left(TaskFail(id=id,run=run,stats=monitor.end(),error=exp))
  }
  report(result)
  result
}
 
def benchmark[Id,Stats]
    (task: Int => Make[Monitor[Stats]] => Report[Task[Id,Stats]] => Task[Id,Stats])
    (runs: Int, warmups: Int)
    (newMonitor: Make[Monitor[Stats]])
    (warmupReport: Report[Task[Id,Stats]], runReport: Report[Task[Id,Stats]])
    (benchReport: Report[Bench[Id,Stats]]): Bench[Id,Stats] = {
  assert(runs > 0, "Number of runs must be greater than zero.")
  assert(warmups >= 0, "Number of warmups must be zero or greater.")
 
  val (warmupsResults,runsResults) = (
    (1 to warmups) map (run => task(run)(newMonitor)(warmupReport)),
    (1 to runs) map (run => task(run)(newMonitor)(runReport))
  )
  val result = BenchDone(warmups=warmupsResults,runs=runsResults)
  benchReport(result)
  result
}
 
def batch[Id,Stats]
    (benchs: Seq[Report[Bench[Id,Stats]] => Bench[Id,Stats]])
    (benchReport: Report[Bench[Id,Stats]])
    (batchReport: Report[Batch[Id,Stats]]) {
  val result = benchs map (bench => bench(benchReport))
  batchReport(result)
}

The revised diagram sketch now visualizes how statistics generated by the monitor is fed back to reporters:

Example usage

In this revised example we need to define some statistical datatypes. These will be TaskTime and TaskMem which collect time and memory usage. They are case classes extended from the sealed trait TaskStats which will allow us to pattern match them.

type Id = String
 
case class MemStats(free: Long, total: Long, max: Long) {
  def used(): Long = total - free
}
 
sealed trait TaskStats
 
case class TaskTime(duration: Long) extends TaskStats
 
case class TaskMem(samples: Seq[MemStats]) extends TaskStats {
  def avgUsed(): Long = {
    val totals = samples map (mem => mem.used)
    if (totals.nonEmpty) totals.sum / totals.length else 0
  }
  def minUsed(): Long = {
    samples.collect{ case mem: MemStats => mem.used }.min
  }
  def maxUsed(): Long = {
    samples.collect{ case mem: MemStats => mem.used }.max
  }
}

For utility we add some more convenience methods for text conversion and calculating statistics of memory usage.

def timeToText(value: Long): String = {
  def pad(n: Int, value: Long): String =
    value.toString.reverse.padTo(n,"0").reverse.mkString
  // utility for turning nanoseconds into text
  val ms      = (value / 1000000L).toLong
  val msPart  = ms % 1000L
  val sec     = (ms - msPart) / 1000L
  val secPart = sec % 60L
  val min     = (sec - secPart) / 60L
  val minPart = min
  if (minPart > 0) minPart + "m" + pad(2,secPart) + "s" + pad(3,msPart) + "ms"
  else if (secPart > 0)  secPart + "s" + pad(3,msPart) + "ms"
  else msPart + "ms"
}
 
def memToText(value: Long): String = {
  def pad(n: Int, value: Long): String =
    value.toString.reverse.padTo(n,"0").reverse.mkString
  // utility for turning bytes into text
  val mb     = value / (1024L * 1024L)
  val mbPart = mb % 1024L
  val gb     = (mb - mbPart) / 1024L
  val gbPart = gb
  if (gbPart > 0) gbPart + "gb" + pad(3,mbPart) + "mb"
  else mbPart + "mb"
}
 
def taskId[Id](bench: Bench[Id,TaskStats]): Id = {
  // utility for extracting task id
  val firstDone = bench.runs find (result => result.isRight)
  val firstFail = bench.runs find (result => result.isLeft)
  if (firstDone.nonEmpty) firstDone.get.right.get.id
  else firstFail.get.left.get.id
}
 
def isDone[Id](bench: Bench[Id,TaskStats]): Boolean = {
  // utility for detecting a bench without errors
  val warmupsFail = bench.warmups collect { case Left(task) => task }
  val runsFail    = bench.runs collect { case Left(task) => task }
  warmupsFail.isEmpty && runsFail.isEmpty
}
 
def avgTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating average time of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => value }.sum
    case Left(task)  => task.stats.collect{ case TaskTime(value) => value }.sum
  }
  if (totals.nonEmpty) totals.sum / totals.length else 0
}
 
def minTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating minimum time of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => value }.min
    case Left(task)  => task.stats.collect{ case TaskTime(value) => value }.min
  }
  totals.min
}
 
def noTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating number of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => 1 }.sum
    case Left(task)  => task.stats.collect{ case TaskTime(value) => 1 }.sum
  }
  totals.sum
}
 
def avgMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating average memory usage in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case mem: TaskMem => mem.avgUsed }.sum
    case Left(task)  => task.stats.collect{ case mem: TaskMem => mem.avgUsed }.sum
  }
  if (totals.nonEmpty) totals.sum / totals.length else 0
}
 
def maxMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating max memory usage in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case mem: TaskMem => mem.maxUsed }.max
    case Left(task)  => task.stats.collect{ case mem: TaskMem => mem.maxUsed }.max
  }
  totals.max
}
 
def noMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating number of memory samples taken in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskMem(samples) => samples.length }.sum
    case Left(task)  => task.stats.collect{ case TaskMem(samples) => samples.length }.sum
  }
  totals.sum
}

Next up, we need to refine the reporters to account for the new datatypes and output relevant statistics on memory usage.

def taskReport(title: String)(result: Task[Id,TaskStats]) {
  result match {
    case Right(task) =>
      val time = task.stats.collect{ case TaskTime(value) => value }.sum
      println(
        "%s %s %s completed in %s"
          .format(task.id.toString, title, task.run, timeToText(time))
      )
    case Left(task) =>
      val time = task.stats.collect{ case TaskTime(value) => value }.sum
      val error = task.error.getClass.getName
      println(
        "%s %s %s failed after %s from %s"
          .format(task.id.toString, title, task.run, timeToText(time), error)
      )
  }
}
 
val warmupReport = taskReport("warmup") _
 
val runReport = taskReport("run") _
 
def benchReport[Id](bench: Bench[Id,TaskStats]) {
  val id = taskId(bench)
  if (isDone(bench)) {
    val totalTime = bench.runs.collect{
      case Right(task) =>
        task.stats.collect{ case TaskTime(value) => value }.sum
    }.sum
    println(id + " finished in " + timeToText(totalTime) + "\n")
  }
  else
    println(id + " failed\n")
}
 
def batchReport(batch: Batch[Id,TaskStats]) {
  def propsToText(): String = {
    import scala.util.{Properties => Props}
    val os = java.lang.management.ManagementFactory.getOperatingSystemMXBean
    val props = scala.collection.immutable.SortedMap(
      "os" -> (os.getName + " (" + os.getVersion + ")"),
      "arch" -> os.getArch,
      "cpus" -> os.getAvailableProcessors.toString,
      "java" -> (Props.javaVmName + " " + Props.javaVersion),
      "scala" -> Props.versionString.replace("version","").trim
    )
    props.map{ case (k,v) => k + ":" + "\"" + v + "\"" }.mkString(" ")
  }
  def statsToText(status: String, benchs: Seq[Bench[Id,TaskStats]]): String = {
    benchs
      .map(bench => (
        avgTime(bench),noTime(bench),minTime(bench),
        avgMem(bench),noMem(bench),maxMem(bench),taskId(bench)
      ))
      .sortWith((a,b) => a._1 < b._1) // sort on durations
      .map(item =>
        "%2s %12s/%-6s %12s %10s/%-6s %10s %s"
         .format(
           status,timeToText(item._1),item._2,timeToText(item._3),
           memToText(item._4),item._5,memToText(item._6),item._7)
      )
      .mkString("\n")
  }
  val (doneBenchs,failedBenchs) = batch partition isDone
  println(
    "Batch of benchmarks finished with %s completed and %s failed.\n"
      .format(doneBenchs.length,failedBenchs.length)
  )
  println("Statistics for benchmarks:\n")
  println(
    "   %12s/%-6s %12s %10s/%-6s %10s %s"
      .format("avgtime","no","mintime","avgmem","no","maxmem","id")
  )
  println(statsToText("ok", doneBenchs))
  println(statsToText("na", failedBenchs))
  println("\nSystem properties:")
  println(propsToText)
}

For implementing the Monitor trait I use mixin inheritance for this example. One for TimeUsage and one for MemUsage. These traits can be stacked together and accumulate the statistics generated. TimeUsage is just an abstraction of the previous post’s task() code. MemUsage on the other hand is a little more involved. It will stay active during benchmarking and sample memory usage at regular intervals.

For multithreaded sampling I chose actors since they are fairly simple in use. A MemUsage object simply starts the sampler actor by sending a message with NextSample. This will trigger the sampler to start regular recordings of memory usage. When the benchmark is done the MemUsage object will send and wait for reply for a LastSample message. The sampler will reply with the sequence of MemStats samples collected and terminate. Last, the samples are stored in a TaskMem object and accumulated with the other TaskStats results.

trait TimeUsage extends Monitor[TaskStats] {
  var startTime: Long = 0L
 
  override def begin() {
    super.begin()
    startTime = System.nanoTime  
  }
 
  override def end(): Seq[TaskStats] = {
    List(TaskTime(duration=System.nanoTime - startTime)) ++ super.end()
  }
}
 
trait MemUsage extends Monitor[TaskStats] {
  import MemUsage.{NextSample,LastSample}
 
  val sampleRate: Long
  private val rt = java.lang.Runtime.getRuntime
  private val sampler = new actors.Actor {
    var samples = List.empty[MemStats]
    var running = true
    def act() {
      while(running) {
        try { receive {
          case NextSample =>
            samples ::=
              MemStats(free=rt.freeMemory, total=rt.totalMemory, max=rt.maxMemory)
            java.lang.Thread.sleep(sampleRate)
            this ! NextSample
          case LastSample =>
            running = false
            samples ::=
              MemStats(free=rt.freeMemory, total=rt.totalMemory, max=rt.maxMemory)
            reply(samples)
        } }
        catch {
          case error: java.lang.OutOfMemoryError =>
            // skip this sample then wait for LastSample
            java.lang.Thread.sleep(sampleRate)
        }
      }
    }
  }
 
  override def begin() {
    rt.gc()
    sampler.start()
    sampler ! NextSample
    super.begin()
  }
 
  override def end(): Seq[TaskStats] = {
    val stats = super.end()
    (sampler !? LastSample) match {
      case samples => List(TaskMem(samples.asInstanceOf[List[MemStats]])) ++ stats
    }
  }
}
 
object MemUsage {
  private case object NextSample
  private case object LastSample
}

In the new benchmark code we now need to make some adjustments to accommodate the extensions made. First we need to add a function for generating new monitors. Here we use inheritance to select which statistics we are interested in collecting and set relevant configuration. Finally, we also need to update task() calls. Since its a partially applied function where the Stats type parameter is specificed by a later argument, we now need to specify type parameters ahead of time.

val newMonitor = () => {
  new Monitor[TaskStats] with MemUsage with TimeUsage {
    val sampleRate = 50L
  }
}
val (warmups,runs) = (1,2)
val (start,end) = (1,5000000)
val sum = (a: Int, b: Int) => a + b
 
 
@scala.annotation.tailrec
def loopWithTailrec(start: Int, end: Int, sum: Int): Int = {
  if (start <= end) loopWithTailrec(start + 1, end, sum + start)
  else sum
}
 
val rangeTasks = List(
  task[Id,TaskStats](id="range+sum",
    fn=() => (start to end).sum) _,
  task[Id,TaskStats](id="range+foldLeft",
    fn=() => (start to end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="range+foldRight",
    fn=() => (start to end).foldRight(0)(sum)) _
)
 
val listTasks = List(
  task[Id,TaskStats](id="list+sum",
    fn=() => List.range(start,end).sum) _,
  task[Id,TaskStats](id="list+foldLeft",
    fn=() => List.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="list+foldRight",
   fn=() => List.range(start,end).foldRight(0)(sum)) _
)
 
val vectorTasks = List(
  task[Id,TaskStats](id="vector+sum",
    fn=() => Vector.range(start,end).sum) _,
  task[Id,TaskStats](id="vector+foldLeft",
    fn=() => Vector.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="vector+foldRight",
    fn=() => Vector.range(start,end).foldRight(0)(sum)) _
)
 
val arrayTasks = List(
  task[Id,TaskStats](id="array+sum",
    fn=() => Array.range(start,end).sum) _,
  task[Id,TaskStats](id="array+foldLeft",
    fn=() => Array.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="array+foldRight",
    fn=() => Array.range(start,end).foldRight(0)(sum)) _
)
 
val streamTasks = List(
  task[Id,TaskStats](id="stream+sum",
    fn=() => Stream.range(start,end).sum) _,
  task[Id,TaskStats](id="stream+foldLeft",
    fn=() => Stream.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="stream+foldRight",
    fn=() => Stream.range(start,end).foldRight(0)(sum)) _
)
 
val itrTasks = List(
  task[Id,TaskStats](id="list+itr+foldRight",
    fn=() => List.range(start,end).iterator.foldRight(0)(sum)) _,
  task[Id,TaskStats](id="stream+itr+sum",
    fn=() => Stream.range(start,end).iterator.sum) _,
  task[Id,TaskStats](id="stream+itr+foldRight",
    fn=() => Stream.range(start,end).iterator.foldRight(0)(sum)) _
)
 
val loopTasks = List(
  task[Id,TaskStats](id="loop+for",
    fn=() => {
      var sum = 0
      for (i <- start to end) {
        sum = sum + i
      }
      sum
    }) _,
  task[Id,TaskStats](id="loop+while",
    fn=() => {
      var sum = 0
      var i = start
      while (i <= end) {
        sum = sum + i
        i = i + 1
      }
      sum
    }) _,
  task[Id,TaskStats](id="loop+tailrec",
    fn=() => {
      loopWithTailrec(start, end, 0)
    }) _
)
 
val benchs = (
  rangeTasks ++ listTasks ++ vectorTasks ++ arrayTasks ++
    streamTasks ++ itrTasks ++ loopTasks
).map(
  task => benchmark(task)(runs=runs,warmups=warmups)(newMonitor)(warmupReport,runReport) _
)
batch[Id,TaskStats](benchs)(benchReport)(batchReport)

Lets run the updated benchmark and see how memory usage plays into the equation. Now keep in mind that the memory related statistics isn’t necessarily accurate. Generated statistics accumulate memory. The JVM reserves memory for all kinds of optimizations so it might not reflect the actual memory usage of the data-structures. Runtime optimizations performed by the JVM might behave differently when code is used in an implementation. Different JVMs and hardware setups will also affect the result. Atleast you can get some idea of the time and memory usage involved and maybe get some insights into tradeoffs involved.

Batch of benchmarks finished with 16 completed and 5 failed.
 
Statistics for benchmarks:
 
        avgtime/no          mintime     avgmem/no         maxmem id
ok          5ms/2               5ms        3mb/4             3mb loop+while
ok          9ms/2               8ms        3mb/4             3mb loop+tailrec
ok         39ms/2              38ms        7mb/4            12mb loop+for
ok        152ms/2             150ms        3mb/8             7mb range+foldLeft
ok        181ms/2             178ms        4mb/9             8mb range+sum
ok        251ms/2             250ms       23mb/11           27mb array+foldRight
ok        254ms/2             253ms       21mb/10           25mb array+foldLeft
ok        294ms/2             291ms       34mb/12           58mb array+sum
ok      1s101ms/2           1s086ms       13mb/39           36mb stream+foldLeft
ok      1s366ms/2           1s361ms       78mb/45          139mb vector+foldLeft
ok      1s419ms/2           1s416ms       80mb/43          155mb vector+sum
ok      1s547ms/2           1s513ms      123mb/23          201mb range+foldRight
ok      2s002ms/2           1s989ms      112mb/36          199mb list+foldLeft
ok      2s062ms/2           2s061ms      116mb/38          212mb list+sum
ok      2s350ms/2           2s278ms      117mb/45          224mb vector+foldRight
ok      7s166ms/2           6s726ms      181mb/88          247mb list+itr+foldRight
na          2ms/2               2ms        1mb/4             1mb stream+foldRight
na      1s505ms/2           1s247ms       91mb/34          185mb list+foldRight
na     19s834ms/2          19s563ms      193mb/88          247mb stream+sum
na     26s811ms/2          26s255ms      193mb/101         247mb stream+itr+foldRight
na     26s869ms/2          26s692ms      186mb/114         247mb stream+itr+sum
 
System properties:
arch:"x86" cpus:"2" java:"Java HotSpot(TM) Client VM 1.6.0_27" os:"Windows 7 (6.1)" scala:"2.9.1.final"

Making objects queryable in Scala

Defining a Queryable trait

In a running program its often nice to have a way of querying and updating the various components of the application. In this example I’ll demonstrate one way you could do this in Scala by defining a Queryable trait. By inheriting this trait, an object can make available properties for reads and updates, and enable traversal to other objects. The data-format used for read results and updates is xml.

The query uses syntax similar to xpath. A few example usages could be:

  • Read a property by config.cache.dir
  • Filter on collection of objects by app.tasks[status='idle'].id
  • Write to a single-valued property by config.screen.width = <width>800</width>
  • Write to a structural-valued property by config.audio.format = <format chan="2" rate="48.0kHz" res="24bit"/>
  • Apply a method by app.playlist.queue = <file type="mp3" loc="http://tunes.com/tune.mp3"/>

Queryable objects can choose between the following kinds of properties:

  • QueryVal for read-only access
  • QueryVar for read-write access
  • QueryDef for an applicable property (similar to write)
  • QueryPath for traversal to named object(s)

The complete sourcecode for the trait is defined as follows.

import scala.util.matching.Regex
import scala.util.parsing.combinator._
 
/**
 * Query Syntax
 *   query         ::= {query-path `.`} query-leaf query-value?
 *   query-path    ::= name-path filters?
 *   query-leaf    ::= name-leaf
 *   query-value   ::= `=` <a xml element>
 *   name-path     ::= ([a-zA-Z][-a-zA-Z0-9]*)
 *   name-leaf     ::= ([a-zA-Z][-a-zA-Z0-9]*)|[?]
 *   filters       ::= `[` {filter `,`} `]`
 *   filter        ::= filter-key `=` `'` filter-value `'`
 *   filter-key    ::= [a-zA-Z][-a-zA-Z0-9]*
 *   filter-value  ::= `'` <an escaped string> `'`
 */
trait Queryable {
  import Queryable._
 
  private val queryKeys: () => Seq[xml.Elem] =
    () => {
      for (item <- queryMap.keys.toSeq) yield {
        <key name={item} doc={queryMap(item)._1} type={queryMap(item)._2.typeId}/>
      }
    }
 
  protected var queryMap = Map[String,(String,QueryNode)](
    "?" -> (
      "Lists all queryable keys." -> QueryVal(
        read = queryKeys
      )
    )
  )
 
  final def query(expr: String): Either[String,xml.Elem] = {
    try {
      val parser = new QueryParser
      parser.parseAll(parser.queryPath, expr) match {
        case parser.Success((path,value), remaining) =>
          Right(<query expr={expr}>{ query(path,value) }</query>)
        case parser.Error(msg, remaining) =>
          Left("error while parsing query: " + msg)
        case parser.Failure(msg, remaining) =>
          Left("failure while parsing query: " + msg)
        case err =>
          Left("unknown error while parsing query: " + err)
      }
    }
    catch {
      case exp: Exception => Left("exception caught during query: " + exp)
    }
  }
 
  private def query(path: Seq[Prop], value: Option[xml.Elem]): Seq[xml.Elem] = {
    path.toList match {
      case (key,filters) :: Nil if queryMap contains key =>
        (queryMap(key)._2,value) match {
          case (QueryVal(read),None)           => read()
          case (QueryVar(read,_),None)         => read()
          case (QueryVar(_,write),Some(value)) => write(value)
          case (QueryDef(apply),Some(value))   => apply(value)
          case _                               => Nil
        }
      case (key,filters) :: tail if queryMap contains key =>
        queryMap(key)._2 match {
          case QueryPath(next) =>
            next()
              .filter(node => filters.forall(item => contains(node,item)))
              .flatMap(node => node.query(tail,value))
          case _ => Nil
        }
      case _ => Nil
    }
  }
 
  private def contains(node: Queryable, check: (String,String)): Boolean = {
    if (node.queryMap.contains(check._1) == false) {
      false
    }
    else {
      val regex = new Regex(check._2)
      node.queryMap(check._1)._2 match {
        case QueryVal(read) =>
          read().headOption.exists(
            item => regex.findPrefixOf(item.text).isDefined
          )
        case QueryVar(read,_) =>
          read().headOption.exists(
            item => regex.findPrefixOf(item.text).isDefined
          )
        case _ => false
      }
    }
  }
}
 
 
object Queryable {
  import xml.XML.{loadString => toXml}
 
  private type Prop = (String,Map[String,String])
 
  sealed trait QueryNode {
    def typeId(): String
  }
  case class QueryVal(read: () => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "val"
  }
  case class QueryVar(read: () => Seq[xml.Elem],
                      write: xml.Elem => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "var"
  }
  case class QueryDef(apply: xml.Elem => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "def"
  }
  case class QueryPath(next: () => Seq[Queryable]) extends QueryNode {
    def typeId(): String = "path"
  }
 
  private class QueryParser extends JavaTokenParsers {
    def queryPath: Parser[(Seq[Prop],Option[xml.Elem])] =
      repsep(query, ".") ~ opt(white ~ "=" ~> white ~> queryValue) ^^ {
        case path ~ value => (path,value)
      }
 
    def query: Parser[Prop] =
      queryName ~ opt(queryFilters) ^^ {
        case name ~ Some(filters) => (name,filters)
        case name ~ None          => (name,Map())
      }
 
    def queryName: Parser[String] = """([a-zA-Z][-a-zA-Z]*)|[\?]""".r
 
    def queryFilters: Parser[Map[String,String]] =
      "[" ~ white ~> repsep(queryFilter, white ~> "," <~ white) <~ "]" ^^ {
        (Map() ++ _)
      }
 
    def queryFilter: Parser[(String,String)] =
      filterKey ~ "=" ~ filterValue ^^ {
        case key ~ "=" ~ value => (key,value)
      }
 
    def queryValue(): Parser[xml.Elem] =
      new Parser[xml.Elem] {
        def apply(in: Input): ParseResult[xml.Elem] = {
          // manually parse xml element from text
          val (begin,end) = (in.offset,in.source.length)
          if (begin >= end) {
            Error("Empty value", in)
          }
          else {
            val elem = toXml(in.source.subSequence(begin,end).toString)
            Success(elem, in.drop(end - begin))
          }
        }
      }
 
    def filterKey: Parser[String] = """[a-zA-Z][-a-zA-Z]*""".r
 
    def filterValue: Parser[String] =
      "'" ~> """[^']+""".r <~ "'" ^^ {
        (value: String) => value
      }
 
    def white: Parser[Option[String]] = opt("""[ \t]+""".r)
  }
}

An example usage

For the demonstration, lets define a few classes that implements the Queryable trait.

case class Song(title: String, composer: String, duration: String)
  extends Queryable {
  import Queryable._
 
  queryMap += (
    "title" -> ("The song's title." -> QueryVal(
      read = () => {<title>{title}</title> :: Nil}
    )),
    "composer" -> ("The song's composer." -> QueryVal(
      read = () => {<composer>{composer}</composer> :: Nil}
    )),
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<song title={title} composer={composer} duration={duration}/> :: Nil}
    ))
  )
}
 
class Jukebox extends Queryable {
  import Queryable._
 
  private var status = "idle"
  private var songs  = List.empty[Song]
 
  def queue(song: Song) { songs = song :: songs }
 
  queryMap += (
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<jukebox status={status} size={songs.length.toString}/> :: Nil}
    )),
    "status" -> ("Status of jukebox." -> QueryVal(
      read = () => {<status>{status}</status> :: Nil}
    )),
    "songs" -> ("Traverse to songs." -> QueryPath(
      next = () => {songs}
    )),
    "queue" -> ("Queues a song from xml." -> QueryDef(
       apply = (elem: xml.Elem) => {
         val song = Song(
           title    = (elem \ "@title").text,
           composer = (elem \ "@composer").text,
           duration = (elem \ "@duration").text
         )
         songs = song :: songs
         <queue>done</queue> :: Nil
       }
    ))
  )
}
 
class App extends Queryable {
  import Queryable._
 
  var status = "ready"
  val jukebox = new Jukebox
 
  queryMap += (
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<app status={status}/> :: Nil}
    )),
    "jukebox" -> ("Traverse to jukebox." -> QueryPath(
      next = () => {jukebox :: Nil}
    ))
  )
}

Before demonstrating the Queryable trait using the App, Jukebox, and Song classes, lets also create an utility function for printing out the Either values that Queryable.query() returns.

def print(value: Either[String,xml.Elem]) {
  val printer = new xml.PrettyPrinter(width=80,step=2)
  value match {
    case Right(result) => println(printer format result)
    case Left(error)   => println(error)
  }
}

Lets start by creating the app and query which properties it and the jukebox has.

val app = new App
print(app query "?")
print(app query "jukebox.?")
<query expr="?">
  <key doc="Lists all queryable keys." type="val" name="?"></key>
  <key doc="Transform into xml." type="val" name="xml"></key>
  <key doc="Traverse to jukebox." type="path" name="jukebox"></key>
</query>
<query expr="jukebox.?">
  <key doc="Queues a song from xml." type="def" name="queue"></key>
  <key doc="Traverse to songs." type="path" name="songs"></key>
  <key doc="Transform into xml." type="val" name="xml"></key>
  <key doc="Status of jukebox." type="val" name="status"></key>
  <key doc="Lists all queryable keys." type="val" name="?"></key>
</query>

Now, lets add some songs programatically and query the jukebox for status and songs.

app.jukebox.queue(Song(title="Mars", composer="Gustav Holst", duration="7m05s"))
app.jukebox.queue(Song(title="Jupiter", composer="Gustav Holst", duration="7m51s"))
print(app query "jukebox.status")
print(app query "jukebox.songs.xml")
<query expr="jukebox.status">
  <status>idle</status>
</query>
<query expr="jukebox.songs.xml">
  <song composer="Gustav Holst" title="Jupiter" duration="7m51s"></song>
  <song composer="Gustav Holst" title="Mars" duration="7m05s"></song>
</query>

And a narrow search against specific songs using filtering (note that filter values are treated as regexes).

print(app query "jukebox.songs[title='Ma',composer='Gustav'].xml")
<query expr="jukebox.songs[title='Ma',composer='Gustav'].xml">
  <song composer="Gustav Holst" title="Mars" duration="7m05s"></song>
</query>

Lets queue a new song on the jukebox by specifying its data in xml.

print(app query ("jukebox.queue = " + <song title="Nocturnes III" composer="Claude Debussy" duration="10m40s"/>))
<query
expr="jukebox.queue = &lt;song composer=&quot;Claude Debussy&quot; title=&quot;Nocturnes III&quot; duration=&quot;10m40s
&quot;&gt;&lt;/song&gt;">
  <queue>done</queue>
</query>

And finally, searching for the included song.

print(app query "jukebox.songs[composer='Claude'].xml")
<query expr="jukebox.songs[composer='Claude'].xml">
  <song composer="Claude Debussy" title="Nocturnes III" duration="10m40s"></song>
</query>

In summary

Fairly little code was necessary to integrate a querying mechanism into objects. Both the parser combinators and the collection library were of great help. Now, the parser combinators aren’t know to be high performance but that is hardly a problem with the small chunks of text being parsed. There are still some places where this solution is lacking though, like filtering being restricted to single-valued properties, lack of validation, and the dependence on a specific data-format like xml. Maybe the trait should be more asynchronous? This is still work in progress and might receive some updates later on.

If you have any suggestions please drop a comment!

A simple non-static logger for Scala

Overview

Here’s an idea for a logger that doesn’t rely on it being shared statically. Initialization is done using implicits, which results in less typing when using the actual classes that mixin the Loggable trait. Any object created within such classes will also get access to these implicits. This lets the implicit arguments propagate forward to other loggable objects when instanciated inside a Loggable class.

The Loggable trait

The trait defines several logging methods such as info(), warn(), error(), fail(), and debug(), where error() will return false and fail() will result in an AssertionError exception being thrown. Each method specify who triggered the logging method, where in the sourcecode it happend, the message that was sent, and a list of zero or more application-defined tags. The tags can be used for example to do filtering or add extra logging categories in the implementation of the logging methods.

Three members controls the behaviour of the Loggable trait. The getLogCompanion specify the companion object who contains the object’s debug tags, the logger.checker checks that debug logging is enabled using the companion’s debug tags, and the logger.writer outputs the logged messages.

The whole process is bootstrapped by constructing an object that implements the Logger trait and marking it as implicit. This could be done for example in an application object or in the main() method.

import java.io.{PrintWriter,StringWriter}
import java.util.regex.{Pattern,Matcher}
 
trait Loggable[+T <: Loggable[T]] {
  this: T => // type this trait with the subclass that uses it
 
  import Loggable._
 
  // attributes required by this trait
  protected val logger: Logger
 
  // methods required by this trait
  protected def getLogCompanion(): LogCompanion[T]
 
  // predefined methods
  protected final def error(msg: String, tags: String*): Boolean = {
    val trace = (new Exception).getStackTrace()(2)
    val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
    val where = trace.getFileName + ":" + trace.getLineNumber
    logger.writer.error(msg,who,where,tags:_*)
  }
 
  protected final def error(exp: Throwable, tags: String*): Boolean = {
    val trace = (new Exception).getStackTrace()(2)
    val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
    val where = trace.getFileName + ":" + trace.getLineNumber
    logger.writer.error(expToString(exp),who,where,tags:_*)
  }
 
  protected final def fail(msg: String, tags: String*): Nothing = {
    val trace = (new Exception).getStackTrace()(2)
    val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
    val where = trace.getFileName + ":" + trace.getLineNumber
    logger.writer.fail(msg,who,where,tags:_*)
  }
 
  protected final def debug(msg: String, tags: String*) {
    // the tag "all" controls all debug logging
    if (logger.checker("all") &&
        getLogCompanion.DebugTags.exists(tag => logger.checker(tag))) {
      val trace = (new Exception).getStackTrace()(2)
      val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
      val where = trace.getFileName + ":" + trace.getLineNumber
      logger.writer.debug(msg,who,where,tags:_*)
    }
  }
 
  protected final def info(msg: String, tags: String*) {
    val trace = (new Exception).getStackTrace()(2)
    val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
    val where = trace.getFileName + ":" + trace.getLineNumber
    logger.writer.info(msg,who,where,tags:_*)
  }
 
  protected final def warn(msg: String, tags: String*) {
    val trace = (new Exception).getStackTrace()(2)
    val who   = toDot(trace.getClassName) + "." + toDot(trace.getMethodName)
    val where = trace.getFileName + ":" + trace.getLineNumber
    logger.writer.warn(msg,who,where,tags:_*)
  }
}
 
object Loggable {
 
  // traits required by Loggable
  trait LogCompanion[+T <: Loggable[_]] {
    val DebugTags: Set[String]
  }
 
  trait Logger {
    val checker: LogChecker
    val writer: LogWriter
  }
 
  trait LogChecker {
    def update(tag: String, isEnabled: Boolean): Unit
    def apply(tag: String): Boolean
  }
 
  trait LogWriter {
      def debug(msg: String, who: String, where: String,tags: String*): Unit
      def error(msg: String, who: String, where: String, tags: String*): Boolean
      def fail(msg: String, who: String, where: String, tags: String*): Nothing
      def info(msg: String, who: String, where: String, tags: String*): Unit
      def warn(msg: String, who: String, where: String, tags: String*): Unit
  }
 
  // utility function
  private val SlashPattern = Pattern.compile("\\\\")
 
  private def toDot(str: String): String = {
    val matcher = SlashPattern.matcher(str)
    matcher.replaceAll(".")
  }
 
  private def expToString(exp: Throwable): String = {
    val writer = new StringWriter
    exp.printStackTrace(new PrintWriter(writer))
    writer.toString
  }
}

An example of how the trait could be used

import Loggable._
 
// common trait for tunes that Jukebox can use
trait Playable {
  this: Loggable[_] =>
 
  def play(): Unit = info("Started playing " + this)
  def stop(): Unit = info("Stopped playing " + this)
}
 
// the secondary implicit list of arguments are resolved at compile-time by
// the compiler, which will replace these arguments with any available implicitly
// defined objects that satisfy the type. Multiple objects are resolved by using
// the most specific one. There are also rules for how the compiler does search.
class Jukebox()(implicit protected val logger: Logger)
  extends Loggable[Jukebox] {
 
  import scala.collection.immutable.Queue
 
  protected var tunes = Queue[Playable]()
 
  debug("Created " + this)
 
  override def toString(): String = "(Jukebox tunes: " + tunes.mkString("[",",","]") + ")"
 
  protected def getLogCompanion(): LogCompanion[Jukebox] = Jukebox
 
  def queue(tune: Playable) {
    tunes = tunes.enqueue(tune)
    debug("Queued " + tune + " on " + this)
  }
 
  def kick(): Unit = fail("Crashed " + this)
 
  def play() {
    if (tunes.isEmpty)
      return warn("No more tunes to play on " + this)
 
    val (tune,rest) = tunes.dequeue
    tunes = rest
    tune.play()
    tune.stop()
  }
}
 
object Jukebox extends LogCompanion[Jukebox] {
  val DebugTags = Set("jukebox")
}
 
class Song(val name: String)(implicit protected val logger: Logger)
  extends Playable with Loggable[Song] {
 
  debug("Created " + this)
  override def toString(): String = "(Song name: \"" + name + "\")"
  protected def getLogCompanion(): LogCompanion[Song] = Song
}
 
object Song extends LogCompanion[Song] {
  val DebugTags = Set("song")
}
 
// override the logCompanion of Song
class Jingle(name0: String)(implicit logger: Logger)
  extends Song(name0) {
  debug("Created " + this)
  override def toString(): String = "(Jingle name: \"" + name + "\")"
  override protected def getLogCompanion(): LogCompanion[Song] = Jingle
}
 
object Jingle extends LogCompanion[Jingle] {
  val DebugTags = Set("jingle") ++ Song.DebugTags
}

Running the example code with some objects

// instantiating the logging  checker and writer
implicit val logger = new Logger {
  var enabledTags = Set("all","song","jukebox","jingle")
  var disabledTags = Set()
 
  val checker = new LogChecker {
    def update(tag: String, isEnabled: Boolean) {
      enabledTags = if (isEnabled) enabledTags + tag else enabledTags - tag
    }
    def apply(tag: String): Boolean = enabledTags contains tag
  }
 
  val writer = new LogWriter {
    def debug(msg: String, who: String, where: String, tags: String*) {
      println("\n--debug " + who + " " + where + "\n" + msg)
    }
    def error(msg: String, who: String, where: String, tags: String*): Boolean = {
      println("--error " + who + " " + where + "\n" + msg)
      false
    }
    def fail(msg: String, who: String, where: String, tags: String*): Nothing = {
      println("\n--fail " + who + " " + where + "\n" + msg)
      throw new java.lang.AssertionError(
        "msg: " + msg + " who: " + who + " where: " + where
      )
    }
    def info(msg: String, who: String, where: String, tags: String*) {
      println("\n--info " + who + " " + where + "\n" + msg)
    }
    def warn(msg: String, who: String, where: String, tags: String*) {
      println("\n--warn " + who + " " + where + "\n" + msg)
    }
  }
}
 
// creating some test objects
val jukebox = new Jukebox
jukebox.queue(new Song("that ol' tune"))
jukebox.queue(new Song("dum di dum"))
jukebox.queue(new Jingle("snap! snap!"))
jukebox.play()
jukebox.play()
jukebox.play()
jukebox.play()
jukebox.kick()

The resulting output in the console

--debug Main$$anon$4$Jukebox.<init> Debug.scala:123
Created (Jukebox tunes: [])
 
--debug Main$$anon$4$Song.<init> Debug.scala:153
Created (Song name: "that ol' tune")
 
--debug Main$$anon$4$Jukebox.queue Debug.scala:129
Queued (Song name: "that ol' tune") on (Jukebox tunes: [(Song name: "that ol' tune")])
 
--debug Main$$anon$4$Song.<init> Debug.scala:153
Created (Song name: "dum di dum")
 
--debug Main$$anon$4$Jukebox.queue Debug.scala:129
Queued (Song name: "dum di dum") on (Jukebox tunes: [(Song name: "that ol' tune"),(Song name: "dum di dum")])
 
--debug Main$$anon$4$Song.<init> Debug.scala:153
Created (Jingle name: "snap! snap!")
 
--debug Main$$anon$4$Jingle.<init> Debug.scala:166
Created (Jingle name: "snap! snap!")
 
--debug Main$$anon$4$Jukebox.queue Debug.scala:129
Queued (Jingle name: "snap! snap!") on (Jukebox tunes: [(Song name: "that ol' tune"),(Song name: "dum di dum"),(Jingle name: "snap! snap!")])
 
--info Main$$anon$4$Playable$class.play Debug.scala:107
Started playing (Song name: "that ol' tune")
 
--info Main$$anon$4$Playable$class.stop Debug.scala:108
Stopped playing (Song name: "that ol' tune")
 
--info Main$$anon$4$Playable$class.play Debug.scala:107
Started playing (Song name: "dum di dum")
 
--info Main$$anon$4$Playable$class.stop Debug.scala:108
Stopped playing (Song name: "dum di dum")
 
--info Main$$anon$4$Playable$class.play Debug.scala:107
Started playing (Jingle name: "snap! snap!")
 
--info Main$$anon$4$Playable$class.stop Debug.scala:108
Stopped playing (Jingle name: "snap! snap!")
 
--warn Main$$anon$4$Jukebox.play Debug.scala:136
No more tunes to play on (Jukebox tunes: [])
 
--fail Main$$anon$4$Jukebox.kick Debug.scala:133
Crashed (Jukebox tunes: [])
java.lang.AssertionError: msg: Crashed (Jukebox tunes: []) who: Main$$anon$4$Jukebox.kick where: Debug.scala:133
        at Main$$anon$4$$anon$1$$anon$3.fail(Debug.scala:197)
        at Main$$anon$4$Loggable$class.fail(Debug.scala:33)
        at Main$$anon$4$Jukebox.fail(Debug.scala:116)
        at Main$$anon$4$Jukebox.kick(Debug.scala:133)
        at Main$$anon$4.<init>(Debug.scala:219)
        at Main$.main(Debug.scala:1)
        at Main.main(Debug.scala)
        ...

Some notes on the logger solution

I didn’t find any good solution on handling inherited DebugTags in the LogCompanion objects. These must instead be copied manually in the code of the companion object.

I considered using call-by-name on the debug argument but it wasn’t worth it. Per info from scala mailing list, it would result in an anonymous inner class and object instantiation at each place a debug call would be done, which clearly defeats the purpose of using call-by-name to only calculate the message when needed.

References

Multiple Inheritance in Javascript

Notice

Javascript does not support multiple inheritance, so the given method will break the instanceof operator! Javascript checks inheritance by traversing the linked list prototype.__proto__ for occurences of the requested prototype. This means that one prototype can only contain one reference to another prototype and in effect only inherit from one prototype. By discarding support for the instanceof operator, multiple inheritance can be simulated.

A support function is available that provide similar functionality as the instanceof operator.

Description and implementation details

The function responsible for applying inheritance between classes works by copying all missing attributes/methods from parent class(es) to the inheritance class. In addition, metadata in the class constructors allows for isInstanceOf() comparisons to to made on objects.

/**
 * Check if object is instance of given class.
 *
 * @param {Object} object Object to check inheritance of.
 * @param {Function} classConstructor Constructor function to check inheritance against.
 * @return Boolean indicating success of comparison.
 * @type {Boolean}
 */
function isInstanceOf(object, classConstructor) {
  // Check for class metadata
  if (object.constructor.meta === undefined || classConstructor.meta === undefined) {
    return object instanceof classConstructor; // Use standard inheritance test
  }
 
  // Use inheritance metadata to perform instanceof comparison
  return object.constructor.meta.fromClasses[classConstructor.meta.index] !== undefined;
}
 
/**
 * Applies inheritance to a class (first argument) from classes (second, third, and
 * so on, arguments).
 *
 * Notes:
 *  - This WILL BREAK the instanceof operator! Use the isInstanceOf() function instead.
 *  - Parent classes must be fully declared before calling this function.
 *  - Multiple classes will be copied in sequence.
 *  - Properties that already exists in class will not be copied.
 */
function applyInheritance() {
  // Validate arguments
  if (arguments.length < 2) {
    throw new Error("No inheritance classes given");
  }
 
  var toClass = arguments[0];
  var fromClasses = Array.prototype.slice.call(arguments, 1, arguments.length);
 
  // Check if class referencer has been created
  if (applyInheritance.allClasses === undefined) {
    applyInheritance.allClasses = [];
  }
 
  // Check for inheritance metadata in toClass
  if (toClass.meta === undefined) {
    toClass.meta = {
      index: applyInheritance.allClasses.length,
      fromClasses : [],
      toClasses: []
    };
    toClass.meta.fromClasses[toClass.meta.index] = true; // class links to itself
    applyInheritance.allClasses.push(toClass);
  }
 
  // Apply inheritance fromClasses
  var fromClass = null;
  for (var i = 0; i < fromClasses.length; i++) {
    fromClass = fromClasses[i];
 
    // Check for inheritance metadata in fromClass
    if (fromClass.meta === undefined) {
      fromClass.meta = {
        index: applyInheritance.allClasses.length,
        fromClasses: [],
        toClasses: []
      };
      fromClasses[i].meta.fromClasses[fromClass.meta.index] = true; // class links to itself
      applyInheritance.allClasses.push(fromClass);
    }
 
    // Link toClass and fromClass
    toClass.meta.fromClasses[fromClass.meta.index] = true;
    fromClass.meta.toClasses[toClass.meta.index] = true;
 
    // Copy prototype fromClass toClass
    for (var property in fromClass.prototype) {
      if (toClass.prototype.hasOwnProperty(property) === false) {
        // Copy missing property from the parent class to the inheritance class
        toClass.prototype[property] = fromClass.prototype[property];
      }
    }
  }
}

Multiple inheritance example:

function Animal(name) {
   // Attributes
   this.name = name;
}
 
Animal.prototype.makeSound = function (soundOutput) {
   soundOutput.playSound("Unknown");
};
 
Animal.prototype.getHierarchy = function () {
   return "Animal";
};
 
function Petable(personality) {
   // Attributes
   this.personality = personality;
}
 
Petable.prototype.isCompatible = function (personality) {
   return this.personality == personality;
};
 
function Dog(name, personality, breed) {
   // Call parent constructors
   Animal.call(this, name);
   Petable.call(this, personality);
 
   // Attributes
   this.breed = breed;
}
// Apply inheritance to Dog from Animal and Petable
applyInheritance(Dog, Animal, Petable);

An example of how to override a method of a parent class:

Dog.prototype.makeSound = function (soundOutput) {
   soundOutput.playSound("Bark");
};

An example of how an overidden method can delegate to it’s parent method:

Dog.prototype.getHierarchy = function () {
   // returns "Animal.Dog"
   return Animal.prototype.getHierarchy.apply(this, arguments) + ".Dog";
};

An example of how to call a parent method:

Dog.prototype.isOwner = function (name, personality) {
   if (this.name != name) {
      return false;
   }
 
   return Petable.prototype.isCompatible.call(this, personality);
};

Notes on calling function objects

References