Friday 22 July 2016

Spark, a Worked Example: Speeding Up DNA Sequencing

Processing huge amounts of data takes time. To do it efficiently we can write code in a functional style and use the opportunities for parallelism that FP allows us. Still, if we want to spread the code over thousands of processors, there is extra work involved in distributing it and managing failure scenarios.

Fortunately things have got much easier in recent years with the emergence of helper software like Spark which will take your code and run it reliably in a cluster. This assumes that you follow certain conventions. Specifically, your program should be a pipeline of transformations between collections of elements, especially collections of key-value pairs. Such a collection in the Spark system is called an RDD (Resilient Distributed Dataset).

Spark is written in Scala. The API supports other languages too like Python and R, but let's stick with Scala, and illustrate how a sample problem can be solved by modelling the solution in this way and feeding the code to Spark. I will take a simplified task from the area of genomics.

DNA may be sequenced by fragmenting a chromosome into many small subsequences, then reassembling them by matching overlapping parts to get the right order and forming a single correct sequence.In the FASTA format, each sequence is composed of characters: one of T/C/G/A. Here are four sample sequence fragments:

>Frag_56
ATTAGACCTG
>Frag_57
CCTGCCGGAA
>Frag_58
AGACCTGCCG
>Frag_59
GCCGGAATAC

Can you see the overlapping parts? If you put the sequences together, the result is be ATTAGACCTGCCGGAATAC.

A naive solution would do it the same way you do it in your head: pick one sequence, look through all the others for a match, combine the match with what you already have, look though all the remaining ones for a match again... and so on, until all sequences have been handled or there are no more matches.

Let's try a better algorithm, one which divides the solution into a number of tasks, each of which can be parallelized. First, you may want to download Spark. You will also need Scala and sbt.

We need Spark because the number of sequence fragments in a real-life scenario would be many millions. (However, I will continue to illustrate the algorithm using the toy data above.)

The skeleton of a Spark program looks like this:

import org.apache.spark.{SparkContext, SparkConf}
import org.apache.spark.rdd.RDD
object MergeFasta {
  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setAppName("MergeFasta")
    val sc = new SparkContext(conf)
  
    // The algorithm's code will go here.
  }
}
main is the entry point. (The Scala extends App syntax also works, but the documentation recommends not using it.) The first thing any Spark program needs to do is get a reference to a SparkContext so it can send computations to the Spark execution environment.

Now, back to the algorithm. We start with a set of small sequences (see above). These would typically be read from a file and converted to an RDD. Throughout the program we try to keep all data wrapped in RDD data structures so Spark knows how to deal with and parallelize the processing. To get an RDD from a file, we can use Spark's own function, sc.textFile("data.txt"), or use regular Scala code to read the file, parse it into a collection, and call sc.parallelize(anyScalaCollection).

By the way if you want to play about with Spark functions like this, the Spark software includes a REPL which you can fire up as follows:

$ spark-shell

scala> val myRDD = sc.parallelize(List(1,2))
myRDD: org.apache.spark.rdd.RDD[Int] = ParallelCollectionRDD[1] at parallelize at <console>:27

scala> myRDD.collect()
res2: Array[Int] = Array(1, 2)

Notice how the collect() function is used to convert an RDD back into a Scala collection so we can view it.

Anyway, now that we have a starting RDD in the program, the first step of the algorithm is to compare each sequence with every other sequence to form a matrix. For each pair, calculate the number of characters at the end of the first sequence that match the characters at the beginning of the second (0 if there is no match). The matrix looks like this:


Key sequenceOther sequences
ATTAGACCTG(CCTGCCGGAA, 4), (AGACCTGCCG, 7), (GCCGGAATAC, 1)
CCTGCCGGAA(ATTAGACCTG, 0), (AGACCTGCCG, 0), (GCCGGAATAC, 7)
AGACCTGCCG(ATTAGACCTG, 0), (CCTGCCGGAA, 7), (GCCGGAATAC, 4)
GCCGGAATAC(ATTAGACCTG, 0), (CCTGCCGGAA, 1), (AGACCTGCCG, 0)

There are different ways you can build this matrix. Let's assume we have a function matchingLength that calculates the number of characters that overlap between two sequences. Then we can use this code:

val seqList = seqSet.collect().toList
val matrix = seqSet.map(seq => (seq, seqList.filterNot(_ == seq)))
matrix.map {
  case (keySeq, seqs) => (keySeq, seqs.map(seq => (seq, matchingLength(keySeq, seq))))
}

The nice thing is that if you are used to dealing with Scala collections, this will look very familiar. We are actually operating not on Scala collections but RDDs. More good news: RDDs are based on the FP technique of lazy evaluation, so no time is wasted on building intermediate collections. The work is postponed until you call collect() or something similar.

The next step in the algorithm is this: for each row in the matrix, eliminate all values except the one with the longest match. Also eliminate inadequate matches, i.e. where the common part is not more than half the length of a sequence. The reduced matrix looks like:


Key sequenceSequence with overlap length
ATTAGACCTG(AGACCTGCCG, 7)
CCTGCCGGAA(GCCGGAATAC, 7)
AGACCTGCCG(CCTGCCGGAA, 7)
GCCGGAATAC(CCTGCCGGAA, 1)

This transformation can be achieved using the mapValues function:

val matrixMaximums = matrix.mapValues(seq => seq.maxBy(_._2))

The last line of the matrix is not a good match, so we can lop it off by applying a filter:

matrixMaximums.filter { case (key, (seq, length)) => length > seq.length / 2 }

Now we have the sequences that we can put together to make the final sequence. We still need to get them in the right order though. Which is the first sequence? It will be any sequence that does not appear as a value anywhere.

val values: RDD[String] = matrix.values.map(_._1)
val startingSeqs: RDD[String] = matrix.keys.subtract(values)

subtract is one of the many useful transformations available on an RDD, and does what you would expect. If you want to see all the available RDD transformations check the Spark API. There are examples of using each one here.

We extract the starting sequence (signalling an error if there wasn't one and only one), and then "follow" that through the matrix: from ATTAGACCTG to AGACCTGCCG to CTGCCGGAA to GCCGGAATAC where the trail ends. To implement this, we may call lookup on the RDD repeatedly inside of a recursive function that builds the String. Each sequence found is appended using the given length (7 in all cases here) to get a final sequence of ATTAGACCTGCCGGAATAC.

To see the final result we can just use println . But how to run it? First compile it to a jar file. sbt is a good choice for building. The full code is available as an sbt project here. When you've cloned or downloaded that, call sbt package in the normal way and then issue the command:

spark-submit --class "MergeFasta" --master local[4] target/scala-2.11/mergefasta_2.11-0.1.jar

The local[4] means that for test purposes we will just be running the program locally rather than on a real cluster, but trying to distribute the work to all 4 processors of the local machine.

When you run spark-submit it will produce a lot of output about how it is parallelizing tasks. You might prefer to see this in the Web UI later. If you want to turn off excessive stdout logging in the meantime, go to Spark's conf directory, copy log4j.properties.template to log4j.properties and set log4j.rootCategory to WARN. Then you will just see the result at the end.

The next question is: how fast was it really? The Spark history server can look at the application logs stored on the filesystem and construct a UI.  There is more about configuration here. But the main thing is to run this from the Spark root:

./sbin/start-history-server.sh

Then navigate in your browser to http://localhost:18080/. You will see a list representing all the times you called spark-submit. Click on the latest run, the top one. Now there is a list of "jobs," the subtasks Spark parallelized and how long they took. The jobs run on RDDs will just be a few milliseconds each because of the strategy of deferring the bulk of the work to the end (lazy evaluation), where something like collect() is called.

When I first ran the code, by far the slowest thing in the list of jobs was the count() on line 78, taking 2 seconds. count() is not a transformation: it is an action and it is not lazy but eager, forcing all the previously queued operations to be performed. So it is necessary to dig a bit deeper to find out where the true bottleneck is. Clicking on the link reveals a graph of what Spark has been doing:



This suggests that the really slow thing is the subtract operation on line 76. Let's look at that code again:

val values: RDD[String] = matrix.values.map(_._1)
val startingSeqs: RDD[String] = matrix.keys.subtract(values)

You can see that the matrix RDD is used twice. The problem is that by default Spark is not keeping the matrix in memory, and it has to recompute it. To solve this, the cache function needs to be called just before the above code:

matrix.cache()

After running everything again, the statistics breakdown looks like this:



So, thanks to caching, the time has been nearly halved.

There are still many optimizations possible and perhaps you can think of a better algorithm entirely. However, hopefully this post has shown how Spark can be useful for parallelizing the solution to a simple problem. Again, the full code can be found here.

Wednesday 13 May 2015

Scala.js and React: Building an Application for the Web

Scala.js compiles Scala code to JavaScript. I noticed on the Reactive Programming course at Coursera that Scala.js has been integrated into it to implement a basic spreadsheet on a Web page, suggesting good support from the Scala establishment. The principal developer of Scala.js is a collaborator of Martin Odersky at EPFL, Sébastien Doeraene, and he will be speaking about it next month (June 2015) at Scala Days in Amsterdam.

Before getting into the sample application, let's talk about the motivation for Scala.js. Basically, the Web continues to be a powerful platform for application development. Despite its many problems, it has features that the desktop and mobile phone cannot match. For example, the install process for a web application is negligible from a user's perspective: just load the web page for the first time and it is already there. Also, web applications can connect with each other via hyperlinks and REST calls.

Unfortunately on the Web, JVM languages have traditionally been limited to the server-side. Functionality on the client-side is dominated by JavaScript. The trouble is, from a developer's perspective, two languages mean a lot of extra complexity. You can't share code between them, and to pass objects at runtime between client and server, you end up writing serialization and validation logic in both languages. It would be preferable to implement a web application in a single language.

How is this possible, given that browsers only understand JavaScript? One possibility is to run JavaScript on the server-side, which is the approach that Node.js takes. However, JavaScript meets with many complaints: it is essentially untyped, and you can't take advantage of the solidity and scalability that the JVM has been providing on the server-side for so long. It would be better to use a language on both sides that can take advantage of the performance of JVM, the safety of typing, and also the FP principles crossing over into the mainstream during the past ten years. This is made possible though the use of transpilers which convert one source language (Scala in the case of Scala.js) to JavaScript.

One of the big challenges in Web programming is coordinating events so that elements in the view (client-side) are updated when the model (server-side) changes. For desktop apps, the Observer design pattern is often used, but on the Web, it takes a bit more work, and we often employ the help of some MVC (Model-View-Controller) Web framework. The most general term for getting changes to propagate automatically like this (as opposed to manually making calls from the view all the time) is "Reactive Programming". A particular form of Reactive Programming is Functional Reactive Programming (FRP) which is about capturing relationships in a composable way between values that change over time ("signals"). A related approach is to use a message passing system like Akka that keeps components loosely coupled. In both cases the key goals are to avoid the inefficiency of blocking operations and the hazards of mutable data, so making the overall system scalable and resilient.

I would propose that the term FWP (Functional Web Programming) be used to cover systems that bring FP and Reactive Programming to the Web: including Elm, ClojureScript/Om, and Play Iteratees. The FWP implementation I have chosen is a combination of Scala.js and React: this article describes setting up a simple application without going into depth about FRP or being a full tutorial.

While Scala.js was being developed, back in the JavaScript world frameworks were being developed that tackled the issues of Reactive Programming. One of the most popular has been React, developed by Facebook and Instagram. When it was introduced in May 2013, it surprised seasoned developers as it seemed to violate establish best practices. In JavaScript updating the browser DOM is slow, so it was common to only update the necessary parts when the backing model changed. However, in React when any component's state is changed, a complete re-render is done from the application developer's perspective. It's almost like serving a whole new page, guaranteeing that every place data is displayed it will be up-to-date. This avoids the dangers of mutating state but it seems like it would be very slow: still, it actually outperforms other frameworks like AngularJS thanks to some a clever diffing algorithm involving a "virtual DOM" that is maintained independently of the browser's actual DOM.



Another advantage of React is that developers concentrate on re-using components rather than templates where messy logic tends to accumulate. Components are typically written in JSX, a JavaScript extension language, and then translated to actual JavaScript using a preprocessor. For instance, consider the score text at the top left in the Libanius app (see screenshot). In JSX this would be written:
















var ScoreText = React.createClass({
  render: function() {
    return (
      <span className="score-text">
        Score: {this.props.scoreText}
      </span>
    );
  }
});
React.render(
  <ScoreText />,
  document.getElementById('content')
);

This is JavaScript plus some syntactic sugar. Notice how the score variable is passed in using the props for the component.

The code above is converted to normal JavaScript by running the preprocessor. On the command-line you would typically run something like this to watch your source directory and translate code to raw JavaScript in the build directory whenever anything changes:


> jsx --watch src/ build/

This is using standard React so far. However this is not the way we do it with Scala.js.

Firstly, there exists a Scala library from Haoyi Li called Scalatags, that includes Scala equivalents for HTML tags and attributes. Let's assume we have a file QuizScreen.scala in which we are writing the view. The core code may start off looking a bit like this:

@JSExport
object QuizScreen {
  @JSExport
  def main(target: html.Div) = {
    val quizData = // … Ajax call
    target.appendChild(
      span(`class` := "alignleft", "Score: " + quizData.score)
      // ... more view code here
    )
  }
} 

Notice that span is a Scala method (the Scalatags library has to be imported). Assuming you've configured SBT to use Scala.js (see below), this is converted to JavaScript in SBT by calling:


> fastOptJS 

A good thing about the Scala.js compiler is that it keeps the target JavaScript small by eliminating any code from included libraries that is not used. To stop this from happening on the entry point itself in QuizScreen, it is necessary to use the @JSExport annotation both on the object and the main method. This guarantees that main() will be callable from JavaScript. 

So now we have seen the React way and the Scala.js way. How do we combine them? A good option is to use the scalajs-react library from David Barri. Now the ScoreText component looks like this:

  
val ScoreText = ReactComponentB[String]("ScoreText")
    .render(scoreText => <.span(^.className := "alignleft", "Score: " + scoreText))
    .build

Compare this with the JSX version. The Scala code is more concise. Notice that the render() method is present. It's also possible to use other React lifecycle methods if necessary, like componentDidMount() for initializing the component.

Notice also that it uses a Scala span. A specialized version of Scalatags is used here. At first the extra symbols look intimidating, but just remember that < is used for tags and ^ is used for attributes, and they are imported like this:

import japgolly.scalajs.react.vdom.prefix_<^._

In classic JavaScript React, a component can hold state, as seen in references to this.state and the getInitialState() method, which might look like this.

  getInitialState: function() {
    return {data: []};
  }

The Scala version lets us define the state more clearly because it is a strongly typed language. For example, the state for the QuizScreen looks like this:

case class State(userToken: String, currentQuizItem: Option[QuizItemReact] = None,
    prevQuizItem: Option[QuizItemReact] = None, scoreText: String = "",
    chosen: Option[String] = None, status: String = "")

It is best to centralize the state for the screen like this and pass it down to components, rather than having each sub-component have its own separate state object. That could get out of hand!

By the way, you can compose components just as you can in classic React. The central component of the QuizScreen object is the QuizScreen component, and it contains the ScoreText component along with the various other bits and pieces. The code below shows how this is all put together.

val QuizScreen = ReactComponentB[Unit]("QuizScreen")
  .initialState(State(generateUserToken))
  .backend(new Backend(_))
  .render((_, state, backend) => state.currentQuizItem match {
    // Only show the page if there is a quiz item
    case Some(currentQuizItem: QuizItemReact) =>
      <.div(
        <.span(^.id := "header-wrapper", ScoreText(state.scoreText),
          <.span(^.className := "alignright",
            <.button(^.id := "delete-button",
              ^.onClick --> backend.removeCurrentWordAndShowNextItem(currentQuizItem),
                  "DELETE WORD"))
        ),
        QuestionArea(Question(currentQuizItem.prompt,
            currentQuizItem.responseType,
            currentQuizItem.numCorrectResponsesInARow)),
        <.span(currentQuizItem.allChoices.map { choice =>
          <.div(
            <.p(<.button(
              ^.className := "response-choice-button",
              ^.className := cssClassForChosen(choice, state.chosen,
                  currentQuizItem.correctResponse),
              ^.onClick --> backend.submitResponse(choice, currentQuizItem), choice))
          )}),
        PreviousQuizItemArea(state.prevQuizItem),
        StatusText(state.status))
    case None =>
      if (!state.quizEnded)
        <.div("Loading...")
      else
        <.div("Congratulations! Quiz complete. Score: " + state.scoreText)
  })
  .buildU

The central component (QuizScreen) contains the other components (implementations not shown) and also has access to a State and a Backend. The backend contains logic that is a bit more extended. For example, in the code above, observe that submitResponse is called above on the backend when a button is clicked by the user. The code invoked is:

class Backend(scope: BackendScope[Unit, State]) {
    def submitResponse(choice: String, curQuizItem: QuizItemReact) {
      scope.modState(_.copy(chosen = Some(choice)))
      val url = "/processUserResponse"
      val response = QuizItemAnswer.construct(scope.state.userToken, curQuizItem, choice)
      val data = upickle.write(response)

      val sleepMillis: Double = if (response.isCorrect) 200 else 1000
      Ajax.post(url, data).foreach { xhr =>
        setTimeout(sleepMillis) { updateStateFromAjaxCall(xhr.responseText, scope) }
      }
    }

    def updateStateFromAjaxCall(responseText: String, scope: BackendScope[Unit, State]): Unit = {
      val curQuizItem = scope.state.currentQuizItem
      upickle.read[DataToClient](responseText) match {
        case quizItemData: DataToClient =>
          val newQuizItem = quizItemData.quizItemReact
          // Set new quiz item and switch curQuizItem into the prevQuizItem position
          scope.setState(State(scope.state.userToken, newQuizItem, curQuizItem,
              quizItemData.scoreText))
      }
    }
    // more backend methods...
  }

submitResponse makes an Ajax POST call to the server, collects the results and updates the State object. The React framework will take care of the rest, i.e. updating the DOM to reflect the changes to State.

In making the Ajax call, the upickle library (again from Haoyi Li) is used for serialization/deserialization. This is also used on the server side of our Scala.js application. The core of the server side is a Spray server. A simple router is defined which recognizes the call to processUserResponse made above:
 
object Server extends SimpleRoutingApp {
  def main(args: Array[String]): Unit = {
    implicit val system = ActorSystem()
    lazy val config = ConfigFactory.load()
    val port = config.getInt("libanius.port")

    startServer("0.0.0.0", port = port) {
      // .. get route not shown here
      post {
        path("processUserResponse") {
          extract(_.request.entity.asString) { e =>
            complete {
              val quizItemAnswer = upickle.read[QuizItemAnswer](e)
              upickle.write(QuizService.processUserResponse(quizItemAnswer))
            }
          }
        }
      } 
    }
  }
}

The "processUserResponse" path extracts the post data using upickle then passes the call on to the QuizService singleton which contains the mid-tier business logic, and relies on the core Libanius library to run the main back-end functionality on the Quiz. I won't go into detail about this logic, but note that both for historical reasons and future portability it relies on simple files to hold quiz data rather than a database system.

Back to the Spray server: when the QuizScreen page is initially loaded, this route is used:

     get {
        pathSingleSlash {
          complete{
            HttpEntity(
              MediaTypes.`text/html`,
              QuizScreen.skeleton.render
            )
          }
        } 

The QuizScreen mentioned here is not the QuizScreen on the client-side that is described above. In fact, it is a server-side QuizScreen that makes a call to the client-side QuizScreen. Like this:

object QuizScreen {

  val skeleton =
    html(
      head(
        link(
          rel:="stylesheet",
          href:="quiz.css"
        ),
        script(src:="/app-jsdeps.js")
      ),
      body(
        script(src:="/app-fastopt.js"),        
        div(cls:="center", id:="container"),
        script("com.oranda.libanius.scalajs.QuizScreen().main()")
      )
    )
} 

Again the tags are from Scalatags. The main call is in the last script tag. Recall that on the client-side we use @JSExport to make the QuizScreen().main() available:

  
  @JSExport
  def main(): Unit = {
    QuizScreen() render document.getElementById("container")  
  } 

Also notice in the skeleton above, there are two included JavaScript libraries:
  • app-fastopt.js: In a Scala.js application, the *-fastopt.js file is the final output of the fastOptJS task, containing the JavaScript code that has been generated from your Scala code.
  • app-jsdeps.js: In a Scala.js application, the *-jsdeps.js, contains all additional JavaScript libraries: in our case, the only thing it incorporates is react-with-addons.min.js
Here are the essentials of the SBT configuration, which can be used as a starting point for other Scala.js projects, as it just uses the most basic dependencies, including Scalatags, upickle for serialization, and utest for testing.

import sbt.Keys._

name := "Libanius Scala.js front-end"

// Set the JavaScript environment to Node.js, assuming that it is installed, rather than the default Rhino 
scalaJSStage in Global := FastOptStage  

// Causes a *-jsdeps.js file to be generated, including (here) React
skip in packageJSDependencies := false

val app = crossProject.settings(
  unmanagedSourceDirectories in Compile +=
    baseDirectory.value  / "shared" / "main" / "scala",

  libraryDependencies ++= Seq(
    "com.lihaoyi" %%% "scalatags" % "0.5.1",
    "com.lihaoyi" %%% "utest" % "0.3.0",
    "com.lihaoyi" %%% "upickle" % "0.2.8"
  ),
  scalaVersion := "2.11.6",
  testFrameworks += new TestFramework("utest.runner.Framework")
).jsSettings(
  libraryDependencies ++= Seq(
    "org.scala-js" %%% "scalajs-dom" % "0.8.0",
    "com.github.japgolly.scalajs-react" %%% "core" % "0.8.3",
    "com.github.japgolly.scalajs-react" %%% "extra" % "0.8.3",
    "com.lihaoyi" %%% "scalarx" % "0.2.8"
  ),
  // React itself (react-with-addons.js can be react.js, react.min.js, react-with-addons.min.js)
  jsDependencies += "org.webjars" % "react" % "0.13.1" / "react-with-addons.js" commonJSName "React"

).jvmSettings(
  libraryDependencies ++= Seq(
    "io.spray" %% "spray-can" % "1.3.2",
    "io.spray" %% "spray-routing" % "1.3.2",
    "com.typesafe.akka" %% "akka-actor" % "2.3.6",
    "org.scalaz" %% "scalaz-core" % "7.1.2"
  )
)

lazy val appJS = app.js.settings(

  // make the libanius core JAR available
  // ...
  unmanagedBase <<= baseDirectory(_ / "../shared/lib")
)

lazy val appJVM = app.jvm.settings(

  // make sure app-fastopt.js, app-jsdeps.js, quiz.css, the libanius core JAR, application.conf 
  // and shared source code is copied to the server
  // ...
)

As you can see, the special thing about a Scala.js client-server SBT configuration is that it is divided into three parts: js, jvm, and shared. The js folder contains code to be compiled by ScalaJS, the jvm folder contains regular Scala code used on the server-side, and the shared folder contains code and configuration that should be accessible to both js and jvm. This is achieved by using the crossProject builder from Scala.js, which constructs two separate projects, the js one and the jvm one.

So far we've been assuming that any generated JavaScript will run in a browser. However, Scala.js also works with "headless runtimes" like Node.js or PhantomJS to ensure you can run it from the command-line on the server-side too: this is important in testing. Notice the scalaJSStage in Global := FastOptStage line above.

Now for a grand overview of the web application, let's look at the directory structure. You can see how slim the application really is: there are only a few key source files.

libanius-scalajs-react/  
  build.sbt
  app/
    js/
      src/
        main/
          scala/
            com.oranda.libanius.scalajs/
              QuizScreen.scala
      target/
    jvm/
      src/
        main/
          resources/
            application.conf
          scala/
            com.oranda.libanius.sprayserver/
              QuizScreen.scala
              QuizService.scala
              Server.scala
      target/
    shared/
      lib/
        libanius-0.982.jar
      src/
        main/
          resources/
            quiz.css
          scala/
            com.oranda.libanius.scalajs/
              ClientServerObjects.scala
                QuizItemReact

Again notice there is a QuizScreen on both the server-side and client-side: the former calls the latter.

One thing that I didn't mention yet is the quiz.css file that is used in the client-side QuizScreen. This is just an old-fashioned CSS file, but of course it also possible to use LESS files. Furthermore, if you don't anticipate having a graphic designer want to change your styles, you could even go the whole way in making your application type safe, and write your styles in Scala with ScalaCSS.

The full code for this front-end to Libanius is on Github. As of writing there is a deployment on Heroku (may not be supported indefinitely). For a full tutorial on Scala.js, see Hands-on Scala.js from Haoyi Li. There is also a small official tutorial.

Monday 6 April 2015

Speaking Actors Living in the Phone

A Hollywood actor who couldn't speak wouldn't get far. How soon before we say the same of mobile apps?

This article is a bit off-topic for this blog, but it's a bit of fun and the subject deserves more attention. Over the past 18 months the Google Text-to-Speech API has come a long way on the Android platform. I decided to take advantage of it in the Libanius quiz app. For example, when the app presents a quiz item, it should speak the prompt ("Clairvoyance" in the picture).

Libanius uses the actor model from Akka to coordinate its subsystems. To see how Android can be set up to use Akka actors, see this from Typesafe, or this from me. Assuming the Akka infrastructure is in place, a speaking actor can be created like this:


class Voice(implicit ctx: Context) extends Actor with TextToSpeech.OnInitListener {

  val tts = new TextToSpeech(ctx, this)

  override def receive = {
    case Speak(text: String, quizGroupKeyType: String) => // see next code snippet
    case _ => logError("Voice received an unknown command")
  }
}

The Context of the Android activity is passed to the actor because the TextToSpeech class needs it for initialization. Speak is just a case class for the message that is sent to the actor. We have to implement what happens when that message is received.

The prompt could be in various different languages. The Google API supplies a different voice for each language, so we need to take advantage of this.

  case Speak(text: String, quizGroupKeyType: String) =>
    KnownQuizGroups.getLocale(quizGroupKeyType).foreach(speak(text, _))

KnownQuizGroups is a simple map of Libanius quiz group types (e.g. "Spanish") to locales
recognized by TextToSpeech.

The speak method finally uses the TextToSpeech API to set the voice according to the given locale, and actually speak the text. It works fine whether the text is a word or a full sentence.

def speak(text: String, locale: Locale) {
  setSpeechLanguage(locale)
  tts.speak(text, TextToSpeech.QUEUE_FLUSH, null)
}

private[this] def setSpeechLanguage(locale: Locale): Unit = {
  val result: Int = tts.setLanguage(locale)
  if (result == TextToSpeech.LANG_MISSING_DATA || result == TextToSpeech.LANG_NOT_SUPPORTED)
    logError("Language is not available.")
}

Also we must remember in the Speak code to reset the language after the message is spoken.

  setSpeechLanguage(DEFAULT_LOCALE)

While we're adding sound to the Libanius quiz, how about a ping sound for a correct answer, and a buzz sound for a wrong answer? This is a job for another actor: SoundPlayer. The guts of it look like this:

class SoundPlayer(implicit ctx: Context) extends Actor {

  val audioManager: AudioManager =
    ctx.getApplicationContext.getSystemService(Context.AUDIO_SERVICE).asInstanceOf[AudioManager]
  val soundPool: SoundPool = new SoundPool(10, AudioManager.STREAM_MUSIC, 0)
  var soundPoolMap = Map[SoundSample, Int]()

  override def receive = {
    case Load() => 
      loadSounds()
    case Play(soundSample: SoundSample) =>
      val curVolume = audioManager.getStreamVolume(AudioManager.STREAM_MUSIC)
      soundPool.play(soundPoolMap(soundSample), curVolume, curVolume, 1,  0, 1f)
    case _ =>
      logError("SoundPlayer received an unknown command")
  }
}

There is more complete code on Github. This is all for the Android platform, but of course you can also use Akka actors for sound on other platforms like the Mac: see Alvin Alexander's Wikipedia Reader page for some sample code. Have fun!

Tuesday 23 September 2014

The QuizItemSource Typeclass

When talking about scaling an application, people are usually referring to performance: how to design the software so that limited hardware can support millions of users? But it is also important to be able to scale the feature set of an application. If users say they want a new button, you don't want to have to make extensive refactorings of your core model classes as is all too often the case in industry. The key to both of these related demands is decoupling.

While writing the Libanius quiz application, I found typeclasses to be very useful in decoupling behaviour from the model classes. Typeclasses (formally spelt "type classes") originated in Haskell, but can be used in Scala too, being a language that supports FP well. I'll describe one use of typeclasses in Libanius, an example that should be less "theoretical" and more extended than the ones that are usually given.

To start with, the core model in Libanius is a simple containment hierarchy as shown in the diagram. The Quiz data structure contains all the information necessary to provide a stream of quiz items to a single user. It is split by topic into QuizGroups, which, for performance reasons, are further partitioned into "memory levels" according to how well the user has learned the items. The flow of a typical request then is Quiz.findQuizItem() followed by QuizGroup.findQuizItem() calls, followed by QuizGroupMemoryLevel.findQuizItem() calls.

In practice the findQuizItem() signatures and functionality were similar but not identical. Rather than have them scattered throughout the model classes, it was desirable to put them together in a single place where the similarites could be observed and moulded, avoiding any unnecessary repetition. The same was true of other operations in the model classes. Pulling them out would also solve the problem of too much bloat in the model.

Furthermore, although the Quiz data structures are optimized for finding quiz items, I wanted to be able to extend the same action to other entities. A wide range of scenarios can be imagined:

  1. A Twitter feed of quotes might be seen as a mapping from speakers to quotations, which could be turned into a Who-Said-What quiz.
  2. A set of web pages with recipes could be read as a "What ingredient goes with what dish?" quiz.
  3. In a chat forum context, a person might be thinking of quiz questions and feeding them through.
  4. A clever algorithm might not simply be "finding" quiz items in a store, but dynamically generating them based on previous answers. 
  5. The Quiz might not be a Scala data structure, but a database. This could be a NoSQL in-memory database like Redis or leveldb. It could also be a traditional RDBMS like Postgres accessed via Slick.

What links all these cases together is that a findQuizItem() function is necessary but with a new implementation. So the immediate priority is to decouple the findQuizItem() action from the simple Quiz data structure. Notice that this action might be applied to structures that didn't even know they were supposed to be quizzes. We don't want to have to retroactively modify classes like TwitterFeed and ChatParticipant to make them "quiz aware".

If you know a lot of Java, some design patterns might occur to you here, like Adapter, Composite, or Visitor. In the Visitor pattern, in particular, you can separate out arbitary operations from the data structures and form a parallel hierarchy to run those operations. But the original data structures still have to have an accept() method defined. In Scala a more convenient alternative, graced with all the polymorphism you could ever need, is the typeclass construct. Typeclasses excel at separating out orthogonal concerns.

Firstly a trait is defined for the typeclass with the behaviour we wish to separate out. Let's begin by calling the main function produceQuizItem() rather than findQuizItem(), to abstract it more from the implementation:

trait QuizItemSource[A] {
  def produceQuizItem(component: A): Option[QuizItem]}
}

The component could be a Quiz, a QuizGroup, a QuizGroupMemoryLevel or anything else. Instead of calling produceQuizItem() on the component, the component is passed as a parameter to the operation.

Next, define some sample implementations (aka typeclass instances) for the entities (aka model components) that we already have:

object modelComponentsAsQuizItemSources {

  implicit object quizAsSource extends QuizItemSource[Quiz] {
    def produceQuizItem(quiz: Quiz): Option[QuizItem]} = 
      … // implementation calls methods on quiz
  }

  implicit object quizGroupAsSource extends QuizItemSource[QuizGroup] {
    def produceQuizItem(quizGroup: QuizGroup): Option[QuizItem]} = 
      … // implementation calls methods on quizGroup
  }

  implicit object quizGroupMemoryLevelAsSource extends QuizItemSource[QuizGroupMemoryLevel] {
    def produceQuizItem(quizGroupMemoryLevel: QuizGroupMemoryLevel): Option[QuizItem]} = 
      … // implementation calls methods on quizGroupMemoryLevel
  }
}

These sample implementations can be accessed in client code once it is imported in this way:

import modelComponentsAsQuizItemSources._

However, we don't want to call implementations directly, like quizGroupAsSource.produceQuizItem(myQuizGroup). Instead we want to just call produceQuizItem(myQuizGroup) and let the correct implementation be selected automatically: this is what polymorphism is about. To facilitate this, let's define a function in the middle for accessing the implementations (and this is really the final piece of the puzzle for typeclasses!):

object QuizItemSource {

  def produceQuizItem[A](component: A)(implicit qis: QuizItemSource[A]): Option[QuizItem] =
    qis.produceQuizItem(component)
}

If you're coming from other languages, it's the use of the implicit that is at first difficult to grasp, but this is really the Scala feature that makes typeclasses convenient to use, where they are not in, say, Java. Let me explain what is happening here:

Suppose in client code, the modelComponentsAsQuizItemSources has been imported as above. Now the quizGroupAsSource is implicitly in scope, among other implementations. If there is now a call to QuizItemSource.produceQuizItem(quizGroup), the compiler, seeing that quizGroup is of type QuizGroup will match qis to an implicit of type QuizItemSource[QuizGroup]: this is quizGroupAsSource, the correct implementation.

The great thing is that the correct QuizItemSource implementation will always be selected based on the type of entity passed to produceQuizItem, and also the context of the client, specifically the imports it has chosen. Also, we have achieved our original goal that whenever we realize we want to turn an entity into a quiz (TwitterFeed, ChatParticipant, etc.) we don't have to modify that class: instead, we add an instance of the typeclass to modelComponentsAsQuizItemSources and import it.

This approach is a break with OO, moving the emphasis from objects to actions. Instead of adding actions (operations) to objects, we are adding objects to an action generalization (typeclass). We can make that action as powerful as we like by continuing to add objects to it. Again, unlike in OO, those objects do not need to be custom-built to be aware of our action.

That is the main work done. There are two more advanced points to cover.

Firstly, it is possible to add some "syntactical sugar" to the definition of produceQuizItem() above. In this code

def produceQuizItem[A](component: A)(implicit qis: QuizItemSource[A]): Option[QuizItem] =
    qis.produceQuizItem(component)

… the qis variable may be viewed as clutter. We can push it into the background using context bound syntax:

def produceQuizItem(A : QuizItemSource](component: A): QuizItem =
  implicitly[QuizItemSource].produceQuizItem(component)

What happens is that the context bound A : QuizItemSource establishes an implicit parameter, which is then pulled out by implicitly. This syntax is a bit shorter, and looks shorter still if you do not need to call implicitly but are simply passing the implicit parameter down to another function.



Secondly, it is possible to have a typeclass with multiple type parameters. Context bound syntax is not convenient for this case, so, first, let's go back to the original syntax: 



def produceQuizItem[A](component: A)(implicit qis: QuizItemSource[A]): Option[QuizItem] =
    qis.produceQuizItem(component)

Suppose a Quiz were passed in, the quizAsSource instance will be selected. You will remember this looked like this:

implicit object quizAsSource extends QuizItemSource[Quiz] {
  def produceQuizItem(quiz: Quiz): Option[QuizItem]} = 
    … // implementation calls methods on quiz
}

However, I simplified a bit here. The original implementation did not in fact return simple quiz items in the case of a Quiz. Whenever the Quiz retrieved a quiz item from a QuizGroup, it would add some information. Specifically it would generate some "wrong choices" for the question and return that to the user to allow a multiple-choice presentation of the quiz item. So the QuizItem would be wrapped in a QuizItemViewWithChoices object. The signature had to be:

  def produceQuizItem(quiz: Quiz): Option[QuizItemViewWithChoices]} = … 

Now the problem is this does not conform to the typeclass definition. So let's massage the typeclass definition a bit by turning the return type into a new parameter, C:

trait QuizItemSource[A, C] {
  def produceQuizItem(component: A): Option[C]
}

Then the typeclass instance for Quiz will look as desired:

implicit object quizAsSource extends QuizItemSource[Quiz, QuizItemViewWithChoices] {
  def produceQuizItem(quiz: Quiz): Option[QuizItemViewWithChoices]} = 
    … // implementation calls methods on quiz
}

The intermediate function for accessing the typeclass becomes a bit more complex. Recall this was previously:

  def produceQuizItem[A](component: A)
      (implicit qis: QuizItemSource[A]): Option[QuizItem] =
    qis.produceQuizItem(component)

The second type parameter for the return type is added as C:

  def produceQuizItem[A, C](component: A)
      (implicit qis: QuizItemSourceBase[A, C], c: C => QuizItem): Option[C] =
    qis.produceQuizItem(component)

C is constrained so that the return value must be compatible with QuizItem. To make QuizItemViewWithChoices compatible with QuizItem, it is not necessary to make it a subclass with lots of boilerplate as in Java. Instead an implicit conversion is defined next to the QuizItemViewWithChoices class like this:

object QuizItemViewWithChoices {
  // Allow QuizItemViewWithChoices to stand in for QuizItem whenever necessary
  implicit def qiView2qi(quizItemView: QuizItemViewWithChoices): QuizItem =
    quizItemView.quizItem
}

Now it all works!

That ends the description of the QuizItemSource typeclass. For more examples, see the other typeclasses in the Libanius source code such as CustomFormat and ConstructWrongChoices, which cover other concerns orthogonal to the model, or view this excellent video tutorial by Dan Rosen.

Monday 3 March 2014

The Akka Event Bus on Android

Event buses are useful for keeping components in a system loosely coupled, and we generally see them in two areas: distributed systems, and UIs. This post is about the use of an event bus in a UI, specifically Android.

There exist event bus libraries for Android like Otto and greenrobot. There also exists an Event Bus API for Akka. What I haven't seen yet is the Akka Event Bus set up on Android. So, here it is!

First a word on the motivation. In the Libanius Android application, I recently separated part of a screen (in Android's parlance, an Activity) into its own separate class. A problem was that, in response to certain events, the new class needed to add data back to the data structure in the main class for the Activity. My initial approach was to define a closure that could do the work of adding the data, and pass the closure as an argument to the new class (the sub-Activity). However, this felt a bit ad hoc, so I decided it was time to introduce a general event-handling mechanism into Libanius Android. Having helped create an event bus for the GWT UI framework before, I thought it would be interesting to see if the same idea could be applied in Android.

The Libanius Event Bus just extends Akka's ActorEventBus. It is nearly as simple as this:

class LibaniusActorEventBus extends ActorEventBus with LookupClassification
    with AppDependencyAccess {

  type Event = EventBusMessageEvent
  type Classifier = String

  protected def classify(event: Event): Classifier = event.channel

  protected def publish(event: Event, subscriber: Subscriber) {
    subscriber ! event
  }
}

The diagram below shows what use we are actually making of the event bus:



The Android parts are OptionsScreen and DictionarySearch. In the UI, DictionarySearch is actually part of the OptionsScreen activity, but they communicate through the event bus. When the user clicks on a button from DictionarySearch to add a new word to the quiz, a NewQuizItemMessage is constructed. This event is just a wrapper for the quiz item and an identifying header:

case class NewQuizItemMessage(header: QuizGroupHeader, quizItem: QuizItem)
  extends EventBusMessage

The NewQuizItemMessage is published to the QUIZ_ITEM_CHANNEL by calling sendQuizItem() in LibaniusActorSystem. LibaniusActorSystem is a facade to LibaniusActorEventBus and other actors in the system not discussed here.

object LibaniusActorSystem extends AppDependencyAccess {
  val system: ActorSystem = ActorSystem("LibaniusActorSystem")

  val appActorEventBus = new LibaniusActorEventBus
  val QUIZ_ITEM_CHANNEL = "/data_objects/quiz_item"

  def sendQuizItem(qgh: QuizGroupHeader, quizItem: QuizItem) {    
    val newQuizItemMessage = NewQuizItemMessage(qgh, quizItem)
    appActorEventBus.publish(EventBusMessageEvent(QUIZ_ITEM_CHANNEL, newQuizItemMessage))
  }
}

That's the guts of it. There is some more code in OptionsScreen to create an actor to subscribe to the QUIZ_ITEM_CHANNEL, and actually add the QuizItem when it sees the event. For more detail, see the code in the Libanius Android project.

Friday 3 January 2014

Extending Play with AngularJS: Nested MVCs in a Webapp

I finally got a bit of spare time to tighten up the JavaScript in Libanius-Play, the web interface to my quiz application. For a long time, I was dissatisfied with the way data was being passed around from server to client and then back from client to server: there was too much repetition. The JavaScript library jQuery was of use to create AJAX callbacks, but still, any time there was a new parameter, it had to be added in too many places.

AngularJS is another JavaScript library. Like jQuery it is geared towards asynchronous communication, but it provides an MVC framework. The Play Framework is also MVC, so the result is an MVC-within-MVC architecture (see diagram). It seems to work quite well.



The AngularJS controller has a services layer to fetch data from the Scala back-end. Then it updates the page. The nice thing about it is that I don't have to update variables in the web page one by one: I can just bind variables in the web page to attributes in the model. This is achieved in the HTML using AngularJS tags like ng-model and the use of curly braces like this: 

    
    {{ quizData.prompt }}

There are a number of variables like this scattered through the HTML, but they can all be updated at once in a single line of JavaScript if the Play backend returns a JSON structure. (The data structure can be defined as a case class in Scala on the server, and will be dynamically mirrored as a JavaScript structure on the client-side without the need to map attributes manually.) Here is a simplified version of what happens in the JavaScript controller after the server has processed a user response: basically it returns a new quiz item. 

    
    services.processUserResponse($scope.quizData, response).then(function(freshQuizData) {
       $scope.quizData = freshQuizData.data // updates values in the web page automagically
       labels.setColors($scope.quizData)    // extra UI work using a custom JavaScript module called labels
    }

In the first line, services.processUserResponse is a function in the services.js file which sends user input to the server, and immediately returns a promise of new data. The promise has a handy then function which takes a callback argument, describing what happens when the data actually comes through, i.e. updating the view.

All in all, a good experience with AngularJS.

Wednesday 18 December 2013

Private Constructors

Private constructors: mostly you won't need them. Commonly in Scala we just define a class and let the constructor and parameters be exposed to the world:
case class SocialFeedCache(tweets: List[Tweet]) { ... }
But suppose the tweets need to be organized for efficiency, and we don't want the cache to be constructed in an invalid state? Then we might have a factory method that performs the necessary initialization. In Java this would be a static method. In Scala we put it in a companion object:
object SocialFeedCache {
  def apply(tweets: List[Tweet]): SocialFeedCache = {
    // ... organize the tweets ...
    SocialFeedCache(organizedTweets) // call the primary constructor
  }
}
So now we must always call the factory method rather than the primary constructor. How can we enforce this? How can we block anyone from calling the constructor directly? A first attempt might look like this:
private case class SocialFeedCache(tweets: List[Tweet]) { ... }
But this doesn't just hide the constructor; it hides the whole class! In fact there will be a compile-time error, because the factory method in object SocialFeedCache is trying to expose a class that is now hidden.

The correct syntax is actually:
case class SocialFeedCache private(tweets: List[Tweet]) { ... }

And that's all there is to it. This is a useful technique whenever you have special initialization taking place in factory methods.