Jim McBeath

Levels of Expertise

2011-12-08T21:36:00.001-08:00

An attempt to improve the objectivity of skill self-ratings.

Discussion
Scale
References

Discussion

We are often asked to rate things on a scale, typically 1 to 5 or 1 to 10. Rarely is there an attempt to define what those different numbers mean. From a statistician's point of view, this makes the values useful for the sole purpose of comparing a single individual's ratings against other ratings of that individual. In particular, without a good definition of what the various levels mean, I don't see how there can be any effective communication from one person to another of the meaning of such a rating.

When my doctor asks me to tell him how much something hurts on a scale of 1 to 10, I have no idea what information he expects to get when I say "3" or "7".

I once asked an acquaintance to rate, on a scale of 1 (bad) to 10 (good), a movie he had just seen. He said it was a 9. I was suspicious of this answer, so I asked him how he would rate Star Wars, which I knew to be his all-time favorite movie, on the same 1-to-10 scale. He said 12.

I personally consider it an aspect of innumeracy, but people often try to emphasize something by using numbers that are outside of the valid range. We may chuckle when Nigel says he likes his amp better because it goes to 11, but how often have you heard someone talking in all seriousness about putting in a "110% effort"? What does that actually mean? How would you know if someone were putting in 110% versus 100%? If 110% is a valid number, then presumably so is 120%, so anyone suggesting a mere 110% is clearly not asking for enough effort.

People tend to overestimate how good they are at all sorts of things, including cognitive, social and physical skills. If we all overrate ourselves by the same amount, I suppose that could all cancel out and you could still compare people's ratings - but without knowing a priori what their ratings should be, we don't know how much they might be overrating themselves.

When people consider their own expertise, it is common for those with less expertise to overvalue themselves more than people with more expertise. With more expertise comes more awareness of what one could do better. Einstein said, "As our circle of knowledge expands, so does the circumference of darkness surrounding it." Relative beginners easily fall into the Sophomore Illusion of thinking they know a lot because the circumference of their knowledge is not yet large enough for them to recognize the size of the surrounding darkness.

In 1989, psychologist John Hayes at Carnegie Mellon University identified what is now called the "ten-year rule" (although there are earlier commenters, including Herbert Simon, who was also at CMU). As Leonard Mlodinow says in "The Drunkard's Walk", "Experts often speak of the 'ten-year rule,' meaning that it takes at least a decade of hard work, patience and striving to become highly successful in most endeavors." (links mine) The ten-year rule is related to the idea that it takes about 10,000 hours of practice at something to become an expert; with 5 hours of practice per business day and 200 business days per year, it would take ten years to rack up that many hours. If you find yourself thinking how wonderfully expert you are in something that you have practiced for only a few years, perhaps you should consider the ten-year rule and temper your evaluation.

Given that people are so bad at these ratings, it seems to me that the only way to get any useful information from someone when asking this kind of self-rating question is to have an objective definition of what each level means.

One way to think about a scale is by how many people fall into each level. There are currently 7 billion people in the world, or almost 10 to the 10th power. This conveniently maps to a logarithmic scale from 0 to 10, allowing us to define eleven levels starting with level 0 containing all approximately 10 billion people in the world and with each higher level having one tenth the number of people as the level just below it. If the descriptions of a level are hard to interpret, perhaps the size of that level will help give an indication of whether a person should be rated there.

Years ago, during a job interview, I was asked to rate my level of expertise in various subjects, such as programming languages and development tools. This was not an unusual question, I had been asked this question before and have been asked it since. What was different that time was that the interviewer included a scale with some relatively objective descriptions for determining level of expertise. I rather liked the scale, so although I don't recall the exact definition of his levels, I have tried to reproduce that concept here, using descriptions somewhat similar to those given by that interviewer. Unfortunately, I don't remember who introduced that scale to me, so I am unable to give credit.

There are many reasons one might want a scale of expertise, including rating potential employees or creating a summary of the amount of expertise within a company. The scale I present here is intended to be very general; given its logarithmic nature that can include the entire world population, it is capable of allowing comparison of expertise across everyone in the world. You might think that would make it suboptimal for rating (potential) employee expertise, but I think there are enough levels to make it useful for that purpose.

Scale

The scale below includes the following columns:

Level: a number for the level, from 0 to 10, with 10 being the highest level of expertise.
Name: a name for the level. These are taken from a set of expertise level names proposed by the Traveling School of Life. My use of them probably doesn't quite match their intent, but I liked the names and thought the ten words matched my levels pretty well, so I applied them to my levels and added "ignorant" for level 0.
Description: a brief description of the level. The descriptions are worded as if for a technical tool; for application to other areas or concepts, modify accordingly. Comments referring to companies assume a large company (10,000+ people) with large divisions (1000+ people); being a company-wide guru in a company with 100 people might not get you past level 6.
Size: the approximate number of people expected to be at that level worldwide. As mentioned above, this is a simple logarithmic scale. The number of people in a level is 10^10-L where L is the level number.
Practice: the approximate amount of practice that could be required to reach that level of expertise. Putting in that many hours does not guarantee reaching that level, and reaching that level does not necessarily require putting in that many hours. The conversion factors are 1,000 hours per year or 5 hours per day.

All of these different factors are rough estimates, not intended as absolutes but merely as guidelines to help people rank themselves in a way that allows for more meaningful results. I don't have any research to show how well my guesses about Description, Size and Practice correlate; if anyone knows of something along those lines, that would be interesting.

Level	Name	Description	Size	Practice
0	ignorant	I have never heard of it.	10,000,000,000	none
1	interested	I have heard a little about it, but don't know much.	1,000,000,000	1 hour
2	pursuing	I have read an article or two about it and understand the basics of what it is, but nothing in depth.	100,000,000	1 day (5 hours)
3	beginner	I have read an in-depth article, primer, or how-to book, and/or have played with it a bit.	10,000,000	1 week (25 hours)
4	apprentice	I have used it for at least a few months and have successfully completed a small project using it.	1,000,000	3 months (250 hours)
5	intermediate	I have used it for a year or more on a daily or regular basis, and am comfortable using it in moderately complex projects.	100,000	1 year (1,000 hours)
6	advanced	I have been using it for many years, know all of the basic aspects, and am comfortable using it as a key element in complex projects. People in my group come to me with their questions.	10,000	5 years (5,000 hours)
7	accomplished	I am a local expert, with ten or more years of solid experience. People in my division come to me with their questions.	1,000	10 years (10,000 hours)
8	master	I am a company-wide guru with twenty or more years of experience; people from other divisions come to me with their questions.	100	20 years (20,000 hours)
9	grandmaster	I am a recognized international authority on it.	10	30 years (30,000 hours)
10	great-grandmaster	I created it, and am the number 1 expert in the world.	1	50 years (50,000 hours)

References

Other scales of expertise:

Ted Neward describes four levels in his post of August 16: Apprentice, Journeyman, Master, Adept.
The Dreyfus model of skill acquisition: Novice, (Advanced) Beginner, Competent, Proficient, Expert.
Paul Schempp's take on Dreyfus's five levels, with "Capable" rather than "Advanced Beginner".
The Four Stages of Competence of Thomas Gordon: Unconscious Incompetence, Conscious Incompetence, Conscious Competence, Unconscious Competence. And how they might apply to programming.

Debugging Scala Parser Combinators

2011-07-28T15:36:00.000-07:00

Two simple mechanisms for debugging parsers written using Scala's parser combinators.

Introduction
Example Parser
Calling Individual Parsers
Tracing
Updated Example

Introduction

In a recent comment on my 2008 blog post about Scala's parser combinators, a reader asked how one might go about debugging such a parser. As one post says, "Debugging a parser implemented with the help of a combinator library has its special challenges." You may have trouble setting breakpoints, and stack traces can be difficult to interpret.

The two techniques I show here may not provide you with the kind of visibility you might be used to when single-stepping through problem code, but I hope they provide at least a little more visibility than you might otherwise have.

Example Parser

As an example parser I will use an integer-only version of the four-function arithmetic parser I built for my 2008 parser combinator post. The code consists of a set of case classes to represent the parsed results and a parser class that contains the parsing rules and a few helper methods. You can copy this code into a file and either compile it or load it into the Scala REPL.

import scala.util.parsing.combinator.syntactical.StandardTokenParsers

sealed abstract class Expr {
    def eval():Int
}

case class EConst(value:Int) extends Expr {
    def eval():Int = value
}

case class EAdd(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval + right.eval
}

case class ESub(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval - right.eval
}

case class EMul(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval * right.eval
}

case class EDiv(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval / right.eval
}

case class EUMinus(e:Expr) extends Expr {
    def eval():Int = -e.eval
}

object ExprParser extends StandardTokenParsers {
    lexical.delimiters ++= List("+","-","*","/","(",")")

    def value = numericLit ^^ { s => EConst(s.toInt) }

    def parens:Parser[Expr] = "(" ~> expr <~ ")"

    def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) }

    def term = ( value |  parens | unaryMinus )

    def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
        level match {
            case 1 =>
                "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
                "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
            case 2 =>
                "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
                "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
            case _ => throw new RuntimeException("bad precedence level "+level)
        }
    }
    val minPrec = 1
    val maxPrec = 2

    def binary(level:Int):Parser[Expr] =
        if (level>maxPrec) term
        else binary(level+1) * binaryOp(level)

    def expr = ( binary(minPrec) | term )

    def parse(s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(expr)(tokens)
    }

    def apply(s:String):Expr = {
        parse(s) match {
            case Success(tree, _) => tree
            case e: NoSuccess =>
                   throw new IllegalArgumentException("Bad syntax: "+s)
        }
    }

    def test(exprstr: String) = {
        parse(exprstr) match {
            case Success(tree, _) =>
                println("Tree: "+tree)
                val v = tree.eval()
                println("Eval: "+v)
            case e: NoSuccess => Console.err.println(e)
        }
    }
    
    //A main method for testing
    def main(args: Array[String]) = test(args(0))
}

In the ExprParser class, the lines up to and including the definition of the expr method define the parsing rules, whereas the methods from parse onwards are helper methods.

Calling Individual Parsers

In our example parser we can easily ask it to parse a string by calling our ExprParser.test method, which parses the string using our parse method, prints the resulting parse, and (if the parse was successful) evaluates the parse tree and prints that value.

The last line of parse parses a string using our expression parser:

phrase(expr)(tokens)

phrase is a method in StandardTokenParsers that parses an input stream using the specified parser. The only thing special about our expr method is that we happen to have selected it as our top-level parser - but we could just as easily have picked one of our other parsers as our top-level parser.

Let's add another version of the test method that lets us specify which parser to use as the top-level parser. We want to print out the results in the same way as for the existing test method, so we first refactor that existing method:

def test(exprstr: String) =
        printParseResult(parse(exprstr))

    def printParseResult(pr:ParseResult[Expr]) = {
        pr match {
            case Success(tree, _) =>
                println("Tree: "+tree)
                val v = tree.eval()
                println("Eval: "+v)
            case e: NoSuccess => Console.err.println(e)
        }
    }

Now we add a new parse method that accepts a parser as an argument, and we call that from our new test method:

def parse(p:Parser[Expr], s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(p)(tokens)
    }

    def test(p:Parser[Expr], exprstr: String) =
        printParseResult(parse(p,exprstr))

We can run the Scala REPL, load our modified file using the ":load" command, then manually call the top-level parser by calling our test method. To reduce typing, we import everything from ExprParser. In the examples below, text in bold is what we type, the rest is printed by the REPL.

scala> import ExprParser._
import ExprParser._

scala> test("1+2")
Tree: EAdd(EConst(1),EConst(2))
Eval: 3

scala> test("1+2*3")
Tree: EAdd(EConst(1),EMul(EConst(2),EConst(3)))
Eval: 7

scala> test("(1+2)*3")
Tree: EMul(EAdd(EConst(1),EConst(2)),EConst(3))
Eval: 9

We can also call the test method that takes a parser as an argument, allowing us to specifically test one particular parsing rule at a time. If we pass in expr as the parser, we will get the same results as above; but if we pass in a different parser, we may get different results.

scala> test(expr,"1+2*3")
Tree: EAdd(EConst(1),EMul(EConst(2),EConst(3)))
Eval: 7

scala> test(binary(1),"1+2*3")
Tree: EAdd(EConst(1),EMul(EConst(2),EConst(3)))
Eval: 7

scala> test(binary(2),"1+2*3")
[1.2] failure: ``/'' expected but `+' found

1+2*3
 ^

scala> test(parens,"1+2")
[1.1] failure: ``('' expected but 1 found

1+2
^

scala> test(parens,"(1+2)")
Tree: EAdd(EConst(1),EConst(2))
Eval: 3

scala> test(parens,"(1+2)*3")
[1.6] failure: end of input expected

(1+2)*3
     ^

Tracing

If you have a larger parser that is not behaving and you are not quite sure where the problem lies, it can be tedious to directly call individual parsers until you find which one is misbehaving. Being able to trace the progress of the whole parser running on an input known to cause the problem might be helpful, but sprinkling println statements throughout your parser can be tricky. This section provides an approach that allows you to do some tracing with minimal changes to your code. The output can get pretty verbose, but at least this will give you a starting point from which you may be able to devise your own improved debugging.

The idea behind this approach is to wrap some or all of the individual parsers in a debugging parser that delegates its apply action to the wrapper parser, but that prints out some debugging information. The apply action is called during the act of parsing.

Note: this code relies on the fact that the code for the various combinators in the Parser class in Scala's StandardTokenParsers (which is implemented as an inner class in scala.util.parsing.combinator.Parsers) does not override any Parser method other than apply.

This code could be added directly to the ExprParser class, but it is presented here as a separate class to make it easier to reuse. Add this DebugStandardTokenParsers class to the file containing ExprParsers.

trait DebugStandardTokenParsers extends StandardTokenParsers {
    class Wrap[+T](name:String,parser:Parser[T]) extends Parser[T] {
        def apply(in: Input): ParseResult[T] = {
            val first = in.first
            val pos = in.pos
            val offset = in.offset
            val t = parser.apply(in)
            println(name+".apply for token "+first+
                    " at position "+pos+" offset "+offset+" returns "+t)
            t
        }
    }
}

The Wrap class provides the hook into the apply method that we need in order to print out our trace information as the parser runs. Once this class is in place, we modify ExprParser to inherit from it rather than from StandardTokenParsers:

object ExprParser extends DebugStandardTokenParsers { ... }

So far we have not changed the behavior of the parser, since we have not yet wired in the Wrap class. To do so, we can take any of the existing parsers and wrap it in a new Wrap. For example, with the top-level expr parser we could do this, with the added code highlighted in bold:

def expr = new Wrap("expr", ( binary(minPrec) | term ) )

We can make this a bit easier to edit and read by using implicits. In DebugStandardTokenParsers we add this method:

implicit def toWrapped(name:String) = new {
        def !!![T](p:Parser[T]) = new Wrap(name,p)
    }

Now we can wrap our expr method like this:

def expr = "expr" !!! ( binary(minPrec) | term )

If you don't like using !!! as an operator, you are free to pick something more to your taste, or you can leave out the implicit and just use the new Wrap approach.

At this point you must modify your source code by adding the above syntax to each parsing rule that you want to trace. You can go through and do them all, or you can just pick out the ones you think are the most likely culprits and wrap those. Note that you can wrap any parser this way, including those that appear as pieces in the middle of other parsers. The following example shows how some of the parsers in the term and binaryOp methods can be wrapped:

    def term = "term" !!! ( value |  "term-parens" !!! parens | unaryMinus )

    def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
        level match {
            case 1 =>
                "add" !!! "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
                "sub" !!! "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
            case 2 =>
                "mul" !!! "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
                "div" !!! "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
            case _ => throw new RuntimeException("bad precedence level "+level)
        }
    }

Assuming we have wrapped the expr, term and binaryOp methods as in the above examples, here is what the output looks like for a few tests. As in the previous REPL example, user input is in bold. If you are using the REPL and reload the file, remember to run import ExprParser._ again to pick up the newer definitions.

scala> test("1")
term.apply for token 1 at position 1.1 offset 0 returns [1.2] parsed: EConst(1)
plus.apply for token EOF at position 1.2 offset 1 returns [1.2] failure: ``+'' expected but EOF found

1
 ^
minus.apply for token EOF at position 1.2 offset 1 returns [1.2] failure: ``-'' expected but EOF found

1
 ^
expr.apply for token 1 at position 1.1 offset 0 returns [1.2] parsed: EConst(1)
Tree: EConst(1)
Eval: 1

scala> test("(1+2)*3")
term.apply for token 1 at position 1.2 offset 1 returns [1.3] parsed: EConst(1)
plus.apply for token `+' at position 1.3 offset 2 returns [1.4] parsed: +
term.apply for token 2 at position 1.4 offset 3 returns [1.5] parsed: EConst(2)
plus.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``+'' expected but `)' found

(1+2)*3
    ^
minus.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``-'' expected but `)' found

(1+2)*3
    ^
expr.apply for token 1 at position 1.2 offset 1 returns [1.5] parsed: EAdd(EConst(1),EConst(2))
term-parens.apply for token `(' at position 1.1 offset 0 returns [1.6] parsed: EAdd(EConst(1),EConst(2))
term.apply for token `(' at position 1.1 offset 0 returns [1.6] parsed: EAdd(EConst(1),EConst(2))
term.apply for token 3 at position 1.7 offset 6 returns [1.8] parsed: EConst(3)
plus.apply for token EOF at position 1.8 offset 7 returns [1.8] failure: ``+'' expected but EOF found

(1+2)*3
       ^
minus.apply for token EOF at position 1.8 offset 7 returns [1.8] failure: ``-'' expected but EOF found

(1+2)*3
       ^
expr.apply for token `(' at position 1.1 offset 0 returns [1.8] parsed: EMul(EAdd(EConst(1),EConst(2)),EConst(3))
Tree: EMul(EAdd(EConst(1),EConst(2)),EConst(3))
Eval: 9

scala> test(parens,"(1+2)")
term.apply for token 1 at position 1.2 offset 1 returns [1.3] parsed: EConst(1)
mul.apply for token `+' at position 1.3 offset 2 returns [1.3] failure: ``*'' expected but `+' found

(1+2)
  ^
div.apply for token `+' at position 1.3 offset 2 returns [1.3] failure: ``/'' expected but `+' found

(1+2)
  ^
add.apply for token `+' at position 1.3 offset 2 returns [1.4] parsed: +
term.apply for token 2 at position 1.4 offset 3 returns [1.5] parsed: EConst(2)
mul.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``*'' expected but `)' found

(1+2)
    ^
div.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``/'' expected but `)' found

(1+2)
    ^
add.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``+'' expected but `)' found

(1+2)
    ^
sub.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``-'' expected but `)' found

(1+2)
    ^
expr.apply for token 1 at position 1.2 offset 1 returns [1.5] parsed: EAdd(EConst(1),EConst(2))
Tree: EAdd(EConst(1),EConst(2))
Eval: 3

As you can see, even for these very short input strings the output is pretty verbose. It does, however, show you what token it is trying to parse and where in the input stream that token is, so by paying attention to the position and offset numbers you can see where it is backtracking.

When you have found the problem and are done debugging, you can remove the DebugStandardTokenParsers class and take out all of the !!! wrapping operations, or you can leave everything in place and disable the wrapper output by changing the definition of the implicit !!! operator to this:

def !!![T](p:Parser[T]) = p

Or, if you want to make it possible to enable debugging output later, change !!! to return either p or new Wrap(p) depending on some debugging configuration value.

Updated Example

Below is the complete program with all of the above changes.

import scala.util.parsing.combinator.syntactical.StandardTokenParsers

sealed abstract class Expr {
    def eval():Int
}

case class EConst(value:Int) extends Expr {
    def eval():Int = value
}

case class EAdd(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval + right.eval
}

case class ESub(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval - right.eval
}

case class EMul(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval * right.eval
}

case class EDiv(left:Expr, right:Expr) extends Expr {
    def eval():Int = left.eval / right.eval
}

case class EUMinus(e:Expr) extends Expr {
    def eval():Int = -e.eval
}

trait DebugStandardTokenParsers extends StandardTokenParsers {
    class Wrap[+T](name:String,parser:Parser[T]) extends Parser[T] {
        def apply(in: Input): ParseResult[T] = {
            val first = in.first
            val pos = in.pos
            val offset = in.offset
            val t = parser.apply(in)
            println(name+".apply for token "+first+
                    " at position "+pos+" offset "+offset+" returns "+t)
            t
        }
    }

    implicit def toWrapped(name:String) = new {
        def !!![T](p:Parser[T]) = new Wrap(name,p) //for debugging
        //def !!![T](p:Parser[T]) = p              //for production
    }
}

object ExprParser extends DebugStandardTokenParsers {
    lexical.delimiters ++= List("+","-","*","/","(",")")

    def value = numericLit ^^ { s => EConst(s.toInt) }

    def parens:Parser[Expr] = "(" ~> expr <~ ")"

    def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) }

    def term = "term" !!! ( value |  "term-parens" !!! parens | unaryMinus )

    def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
        level match {
            case 1 =>
                "add" !!! "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
                "sub" !!! "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
            case 2 =>
                "mul" !!! "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
                "div" !!! "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
            case _ => throw new RuntimeException("bad precedence level "+level)
        }
    }
    val minPrec = 1
    val maxPrec = 2

    def binary(level:Int):Parser[Expr] =
        if (level>maxPrec) term
        else binary(level+1) * binaryOp(level)

    def expr = "expr" !!! ( binary(minPrec) | term )

    def parse(s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(expr)(tokens)
    }

    def parse(p:Parser[Expr], s:String) = {
        val tokens = new lexical.Scanner(s)
        phrase(p)(tokens)
    }

    def apply(s:String):Expr = {
        parse(s) match {
            case Success(tree, _) => tree
            case e: NoSuccess =>
                   throw new IllegalArgumentException("Bad syntax: "+s)
        }
    }

    def test(exprstr: String) =
        printParseResult(parse(exprstr))

    def test(p:Parser[Expr], exprstr: String) =
        printParseResult(parse(p,exprstr))

    def printParseResult(pr:ParseResult[Expr]) = {
        pr match {
            case Success(tree, _) =>
                println("Tree: "+tree)
                val v = tree.eval()
                println("Eval: "+v)
            case e: NoSuccess => Console.err.println(e)
        }
    }
    
    //A main method for testing
    def main(args: Array[String]) = test(args(0))
}

Multithread Coroutine Scheduler

2011-07-19T16:49:00.000-07:00

Multithread Coroutine Scheduler

A scheduler that uses multiple worker threads for continuations-based Scala coroutines.

In my recent series of posts that ended with a complete Scala server that uses continuations-based coroutines to store per-client state, I asserted that the single-threaded scheduler implementation in that example could relatively easily be replaced by a scheduler that uses multiple threads. In this post I provide a simple working example of such a multithread scheduler.

Overview
Managing Tasks
Scheduler
Synchronization

Overview

We can use the standard thread-pool approach in which we have a pool of worker threads that independently pull from a common task queue. Java 1.5 introduced a set of classes and interfaces in the java.util.concurrent package to support various kinds of thread pools or potentially other task scheduling mechanisms. Rather than writing our own, we will use an Executor from that package.

We have an additional requirement that makes our situation a little bit more complex than the typical thread-pool: our collection of tasks includes both tasks that are ready to run and tasks that are currently blocked but will become ready to run at some point in the future.

We will implement a new scheduler class JavaExecutorCoScheduler that maintains a list of blocked tasks and uses a Java Executor to manage runnable tasks.

The updated complete source code for this post is available on github in my nioserver project under the tag blog-executor.

Managing Tasks

As mentioned above, we need to deal with two kinds of tasks: tasks that are ready to run and tasks that are blocked. The standard Executor class allows us to submit a task for execution, but does not handle blocked tasks. Since we don't want to submit blocked tasks to the Executor, we have to queue them up ourselves. We have two issues to attend to:

When our scheduler is passed a task, we must put it into our own queue of blocked tasks if it is not currently ready to run.
When a previously blocked task becomes ready to run, we must remove it from our queue of blocked tasks and pass it to the Executor.

The first issue is straightforward, as our framework already allows us to test the blocker for a task and see if the task is ready to run. In order to properly take care of the second issue, we will make a small change to our framework to allow us to notice when a blocker has probably stopped blocking so that we can run the corresponding task. We do this by modifying our CoScheduler class to add a method to notify it that a blocker has probably become unblocked:

    def unblocked(b:Blocker):Unit

We call this method from CoQueue in the two places where we previously called scheduler.coNotify: in the blockingEnqueue method after we have enqueued an item to notify the scheduler that the dequeue side is probably unblocked, and in the blockingDequeue method after we have dequeued an item to notify the scheduler that the enqueue side is probably unblocked. Those two methods in CoQueue now look like this:

    def blockingEnqueue(x:A):Unit @suspendable = {
        enqueueBlocker.waitUntilNotBlocked
        enqueue(x)
        scheduler.unblocked(dequeueBlocker)
    }

    def blockingDequeue():A @suspendable = {
        dequeueBlocker.waitUntilNotBlocked
        val x = dequeue
        scheduler.unblocked(enqueueBlocker)
        x
    }

The implementation of unblocked in our default scheduler DefaultCoScheduler is just a call to coNotify, so the behavior of that system will remain the same as it was before we added the calls to unblocked.

Because we need to ensure that all of our NIO read and write operations are handled sequentially, we continue to manage those tasks separately with our NioSelector class, where all of the reads are executed on one thread and all of the writes are executed on another thread.

Scheduler

We already have a scheduler framework that defines a CoScheduler class as the parent class for our scheduler implementations, which requires that we implement the methods setRoutineContinuation, runNextUnblockedRoutine and the newly added unblocked.

In our JavaExecutorCoSchduler, our setRoutineContinuation method is responsible for storing or executing the task. It checks to see if the task is currently blocked, storing it in our list of blocked tasks if so. Otherwise, it passes it to the thread pool (which is managed by an ExecutorService), which takes care of managing the threads and running the task. We define a simple case class, RunnableCont, to turn our task into a Runnable that is usable by the pool.

Our unblocked method gets passed a blocker which is probably now unblocked. We test that, and if in fact it is still blocked we do nothing. If it is unblocked, then we remove it from our list of blocked tasks and pass it to the pool.

The runNextUnblockedRoutine method in this scheduler doesn't actually do anything, since the pool is taking care of running everything. We just return SomeRoutinesBlocked so that the caller goes into a wait state.

In addition to the above three methods, we will have our thread pool, a lock that we use when managing our blocked and runnable tasks, and a set of blocked tasks waiting to become unblocked. For this implementation we choose to use a thread pool of a fixed size, thus the call to Executors.newFixedThreadPool.

Here is our complete JavaExecutorCoScheduler class:

package net.jimmc.scoroutine

import java.lang.Runnable
import java.util.concurrent.Executors
import java.util.concurrent.ExecutorService

import scala.collection.mutable.LinkedHashMap
import scala.collection.mutable.SynchronizedMap

class JavaExecutorCoScheduler(numWorkers:Int) extends CoScheduler {
    type Task = Option[Unit=>Unit]
    case class RunnableCont(task:Task) extends Runnable {
        def run() = task foreach { _() }
    }

    private val pool = Executors.newFixedThreadPool(numWorkers)
    private val lock = new java.lang.Object
    private val blockedTasks = new LinkedHashMap[Blocker,Task] with
            SynchronizedMap[Blocker,Task]

    private[scoroutine] def setRoutineContinuation(b:Blocker,task:Task) {
        lock.synchronized {
            if (b.isBlocked) {
                blockedTasks(b) = task
            } else {
                pool.execute(RunnableCont(task))
                coNotify
            }
        }
    }

    def unblocked(b:Blocker):Unit = {
        lock.synchronized {
            if (!b.isBlocked)
                blockedTasks.remove(b) foreach { task =>
                    pool.execute(RunnableCont(task)) }
        }
        coNotify
    }

    def runNextUnblockedRoutine():RunStatus = SomeRoutinesBlocked
}

Synchronization

Although not necessitated by the above changes, I added one more change to CoScheduler to improve its synchronization behavior.

While exploring various multi-threading mechanisms as alternatives to using Executor, I wrote a scheduler called MultiThreadCoScheduler in which I implemented my own thread pool and in which the master thread directly allocated tasks to the worker threads in the pool. Although that scheduler was quite a bit larger than the one presented above, it provided much more control over the threads, allowing me to change the number of worker threads on the fly and to be able to tell in my master thread whether there were any running worker threads.

In MultiThreadCoScheduler, the main thread would call coWait to wait until it needed to wake up and hand out another task, and the worker threads would call coNotify when they were done processing a task and were ready to be assigned the next task. Similarly, a call to coNotify would be issued whenever a new task was placed into the task queue.

Unfortunately, Java's wait and notify methods, which are the calls underlying our coWait and coNotify methods, do not quite behave the way we would like. If we compare those calls to the Java NIO select and wakeup calls, we note that if a call is made to wakeup before a call to select, the select call will return immediately. The wait/notify calls do not behave this way; if a call is made to notify when there is no thread waiting in a wait call on that monitor, the notify call does nothing, and the following call to wait will wait until the next call to notify.

This small difference in semantics actually makes a pretty big difference in behavior, because it means when using wait and notify you must be concerned with which happens first. Let's see how that works.

In a typical scenario we have a resource with a boolean state that indicates when a thread can access that resource, for example, a queue with a boolean state of "has some data" that indicates when a reader thread can pull an item from the queue (and perhaps another boolean state of "queue is full" that indicates when a writer thread can put an item into the queue). In the case of MultiThreadCoScheduler we have a task with a "ready" flag that tells us when we can assign that task to a worker, and a worker with an "idle" flag that tells us when we can assign a task to that worker. When a task becomes ready to run, we want a thread (other than the master, since it may be waiting) to add the task to our queue of tasks and then notify the master that a task is available. Meanwhile, when the master is looking for an available task to assign to an idle worker, it will query to see if a task is available, and if not it will then wait until one becomes available. The problem sequence would be if the master checks for available tasks, finds none, then before the master executes its wait, the non-master puts a ready task into the queue and issues a notify to the master. The result of this sequence would be a ready task in the queue, but a master waiting for a notify.

When all of the synchronization is done within a single class, you can ensure that the above problem sequencing of operations does not happen by arranging that the code that places a ready task into the queue and notifies the master happens within one synchronized block, and the code used by the master to query the queue for a ready task and then to wait happens within one synchronized block on the same monitor. But when dealing with subclasses, we run into the "inheritance anomaly" (or "inheritance-synchronization anomaly"). The essence of this problem is that the base class provides a method that is synchronized, but the subclass would like to include more functionality within that synchronized block. If, as is often the case, the subclass does not have access to the monitor being used by the base class to control its synchronization, there is no way for it to do this.

In our case, we can implement something that is sufficient for our current needs by making a small change to our coWait and coNotify methods in CoScheduler so that they behave in the same manner as select and wakeup: if a call to coNotify is made before a call to coWait, the call to coWait will return immediately. We do this by changing the implementation of coWait and coNotify in CoScheduler from this:

    def coWait():Unit = {
        defaultLock.synchronized {
            defaultLock.wait()
        }
    }

    def coNotify():Unit = {
        defaultLock.synchronized {
            defaultLock.notify
        }
    }

to this:

    private var notified = false
    def coWait():Unit = {
        defaultLock.synchronized {
            if (!notified)
                defaultLock.wait()
            notified = false
        }
    }

    def coNotify():Unit = {
        defaultLock.synchronized {
            notified = true
            defaultLock.notify
        }
    }

With the above change to our base class, our subclass no longer needs to be concerned about the problem sequence described above, because the call to coWait will return immediately if there was a call to coNotify since the most recent previous call to coWait.

Sledgehammer Words

2011-06-25T07:46:00.000-07:00

Words are tools that we use to clarify our concepts, express our emotions and persuade others to our positions. We use those tools to craft mental models which we deliver to our listener. The better the job we do with those tools, the more effectively we can communicate our message.

The words we use every day are our basic tools. Like screwdrivers and pliers, these words are simple but versatile, performing adequately for most tasks. Occasionally we might want to use a more esoteric word for a specific task, as we might pull out a pair of bent needle nose pliers when that tool is just right for the job.

The better your selection of tools, the better job you can do at making a beautiful and effective work. In a pinch you can use a slot-head screwdriver to set a Phillips screw, but you stand a higher chance of damaging the screw head and it is more difficult to set it just right. Similarly but more subtly, you may be able to use a Phillips screwdriver to set a Frearson screw, but you will be able to do a better job if you have a Frearson driver. Most of us will probably not need this level of distinction and can get by with just a Phillips, or indeed perhaps with just a slot-head driver, but if you want to be able to craft the best results over the widest range of projects, having that Frearson screwdriver in your toolbox will provide one more area in which you can do things better.

Swear words are the sledgehammers of our verbal toolbox. Like a sledgehammer, a swear word can pack a lot of punch, and like a sledgehammer it lacks precision. Sometimes a sledgehammer is the right tool for the job: when you need to smash a hole in something, one good whack with a sledgehammer can be far more effective than trying to use pliers and screwdrivers to do the same thing.

But for most of us, most of the time, that's not the job we are trying to do. Most of the time we are more interested in making a neat hole, and we should pull out the electric drill, or the hole saw, or even the Sawzall to do the job; or we just need to tap in a small nail, where a standard hammer would work nicely. If we smash it with a sledgehammer, it's likely that we will then need to spend a lot of time cleaning things up afterwards, which would probably be more work than using one of the other tools in the first place.

Some people seem to have a very small toolbox and are constantly swinging around that sledgehammer. They use it for almost everything; rather than pulling out a screwdriver to set a screw, they whack it with their sledgehammer. To me, everything these people say seems like a pile of smashed rubble. I doubt that's really the message they want to deliver.

Even a single use of a sledgehammer word can derail any kind of nuance or subtlety, and casual use will likely overwhelm everything else in the message.

So go ahead and use a sledgehammer when it is appropriate, but do so deliberately and fully conscious of your intended result. Make an effort to add a good assortment of tools to your toolbox, understand what you are trying to accomplish, learn to use the best tool for the job and use it well.

Java Nio Complete Scala Server

2011-04-15T11:08:00.000-07:00

The capstone to this series of posts: a complete multi-client stateful application server in Scala using Java NIO non-blocking IO for both reading and writing, and delimited continuations as coroutines for both IO and application processing.

Background
NioApplication
NioServer
NioListener
NioConnection
EchoServer
ThreeQuestionsServer
Limitations

Background

In the initial post of this series on Java NIO in Scala I mentioned a set of Limitations of the first example server. In the next three posts after that initial post I addressed some of those limitations. In this post I address the remaining limitation in that original list: the application code (an echo loop in the example) is buried in the NioConnection class, which makes that application code more difficult to maintain and makes the server code not directly reusable as a library.

With the changes described in the next section, all of the application-specific behavior will be encapsulated in an instance of an application-specific subclass of a new class, NioApplication. Since the remainder of the classes presented so far will now be independent of the application and reusable without any modifications for multiple applications, they will be moved into a separate package, net.jimmc.nio.

Other than adding package net.jimmc.nio, there were no changes to LineDecoder and NioSelector, and there were no changes to the coroutine package net.jimmc.scoroutine for this latest set of changes. For the files that were changed, listed below, the listings show the complete new version of the file, with changes from the previous version highlighted in bold.

The complete source for this series of posts is available on github in my nioserver project, with the specific version after the changes specified in this post tagged as blog-complete.

NioApplication

Extracting the application-specific code out of NioConnection is pretty simple: in NioConnection.startApp, rather than starting up a built-in echo loop, we add a hook that allows us to call back to an application-specific method that implements whatever behavior the application wants for dealing with a connection. To do this, we define a new abstract class NioApplication that includes a runConnection method that we can call from NioConnection.startApp.

We will also use the NioApplication class as a convenience class where we can bundle up some of the arguments that get passed around a lot, in particular the coroutine scheduler and the read and write selectors. This gives us the opportunity to override the coroutine scheduler with one more appropriate for the application, although we will not do so in this example.

package net.jimmc.nio

import net.jimmc.scoroutine.DefaultCoScheduler

import scala.util.continuations._

abstract class NioApplication {
    val readSelector = new NioSelector()
    val writeSelector = new NioSelector()
    val sched = new DefaultCoScheduler

    def runConnection(conn:NioConnection):Unit @suspendable
}

NioServer

We simplify the NioServer class by removing object NioServer, which will instead be in the application main object. We replace three parameters in the constructor with the single app parameter and likewise replace three arguments in the call to NioListener with the single app argument.

package net.jimmc.nio

import net.jimmc.scoroutine.DefaultCoScheduler

import java.net.InetAddress

class NioServer(app:NioApplication, hostAddr:InetAddress, port:Int) {
    val listener = new NioListener(app, hostAddr, port)

    def start() {
        listener.start(true)
        //run the NIO read and write selectors each on its own thread
        (new Thread(app.writeSelector,"WriteSelector")).start
        (new Thread(app.readSelector,"ReadSelector")).start
        Thread.currentThread.setName("CoScheduler")
        app.sched.run    //run the coroutine scheduler on our thread, renamed
    }
}

NioListener

Three parameters in the constructor have been replaced by the single app parameter.

package net.jimmc.nio

import net.jimmc.scoroutine.CoScheduler

import java.net.{InetAddress,InetSocketAddress}
import java.nio.channels.{ServerSocketChannel,SocketChannel}
import java.nio.channels.SelectionKey
import scala.util.continuations._

class NioListener(app:NioApplication, hostAddr:InetAddress, port:Int) {

    val serverChannel = ServerSocketChannel.open()
    serverChannel.configureBlocking(false);
    val isa = new InetSocketAddress(hostAddr,port)
    serverChannel.socket.bind(isa)

    def start(continueListening: =>Boolean):Unit = {
        reset {
            while (continueListening) {
                val socket = accept()
                NioConnection.newConnection(app, socket)
            }
        }
    }

    private def accept():SocketChannel @suspendable = {
        shift { k =>
            app.readSelector.register(serverChannel,SelectionKey.OP_ACCEPT, {
                val conn = serverChannel.accept()
                conn.configureBlocking(false)
                k(conn)
            })
        }
    }
}

NioConnection

We modify the constructor and the companion to replace three parameters with the single app parameter, and we replace our echo loop in startApp with a call to the application runConnection method, followed by a call to our close method to make sure we close the socket when the application is done with it.

package net.jimmc.nio

import net.jimmc.scoroutine.{CoQueue,CoScheduler}

import java.nio.ByteBuffer
import java.nio.channels.SelectionKey
import java.nio.channels.SocketChannel
import scala.util.continuations._

object NioConnection {
    def newConnection(app:NioApplication, socket:SocketChannel) {
        val conn = new NioConnection(app, socket)
        conn.start()
    }
}

class NioConnection(app:NioApplication, socket:SocketChannel) {

    private val buffer = ByteBuffer.allocateDirect(2000)
    private val lineDecoder = new LineDecoder
    private val inQ = new CoQueue[String](app.sched, 10)
    private val outQ = new CoQueue[String](app.sched, 10)

    def start():Unit = {
        startReader
        startWriter
        startApp
    }

    private def startApp() {
        reset {
            app.runConnection(this)
            close()
        }
    }

    private def startReader() {
        reset {
            while (socket.isOpen)
                readWait
        }
    }

    private def readWait:Unit @suspendable = {
        buffer.clear()
        val count = read(buffer)
        if (count<1) {
            socket.close()
            shiftUnit[Unit,Unit,Unit]()
        } else {
            buffer.flip()
            lineDecoder.processBytes(buffer, inQ.blockingEnqueue(_))
        }
    }

    private def read(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            app.readSelector.register(socket, SelectionKey.OP_READ, {
                val n = socket.read(b)
                k(n)
            })
        }
    }

    def readLine():String @suspendable = inQ.blockingDequeue

    private def startWriter() {
        reset {
            while (socket.isOpen)
                writeWait
        }
    }

    private def write(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            app.writeSelector.register(socket, SelectionKey.OP_WRITE, {
                val n = socket.write(b)
                k(n)
            })
        }
    }

    private def writeBuffer(b:ByteBuffer):Unit @suspendable = {
        write(b)
        if (b.remaining>0 && socket.isOpen)
            writeBuffer(b)
        else
            shiftUnit[Unit,Unit,Unit]()
    }

    private def writeWait():Unit @suspendable = {
        val str = outQ.blockingDequeue
        if (str eq closeMarker) {
            socket.close
            shiftUnit[Unit,Unit,Unit]()
        } else
            writeBuffer(ByteBuffer.wrap(str.getBytes("UTF-8")))
    }

    def writeLine(s:String) = write(s+"\n")
    def write(s:String) = outQ.blockingEnqueue(s)

    def isOpen = socket.isOpen
    private val closeMarker = new String("")
    def close():Unit @suspendable = write(closeMarker)
}

EchoServer

We move the application-specific main object out of NioServer and place it into our sample application class, which we call EchoServer, along with a subclassed NioApplication that provides our application behavior.

Highlighted differences are as compared to the previous version of NioServer.

import net.jimmc.nio.{NioApplication,NioConnection,NioServer}
import net.jimmc.scoroutine.DefaultCoScheduler

import java.net.InetAddress
import scala.util.continuations._

object EchoServer {
    def main(args:Array[String]) {
        val app = new EchoApplication
        val hostAddr:InetAddress = null //listen on local connection
        val port = 1234
        val server = new NioServer(app,hostAddr,port)
        server.start()
    }
}

class EchoApplication extends NioApplication {
    def runConnection(conn:NioConnection):Unit @suspendable = {
        while (conn.isOpen) {
            conn.writeLine(conn.readLine)
        }
    }
}

The above class is the complete application definition for our echo server when built on top of our generic nio package. After compiling, run with this command:

$ scala EchoServer

With all the above changes, we have once again internally transformed our application, but besides starting it up with a different name it's external behavior is still the same. However, we have reached the point where defining a new server-based application is easy.

ThreeQuestionsServer

The example in this section shows a slightly more complex application that maintains some local per-client state as it progresses through a short series of steps interacting with the client. In this simple application, the server asks up to three questions of the client and collects responses, with each next question sometimes depending on the previous answers. The per-client state is contained both in local variables and in the location of execution within the application. Each time the processing for a client is suspended the state for that client is captured in a continuation to be restored when the next piece of input is available. The continuation includes all of the above per-client state information, so we don't have to write any application-specific code to save and restore that data.

By defining the ReaderWriter interface trait, the application is written so as to be able to run either in server mode using an instance of ConnReader, in which case it accepts connections from clients, or in standalone mode using an instance of SysReader, in which case it only interacts with the console.

When our application running in server mode finishes handling a client and exits from the run method, control returns to NioConnection, which closes the connection.

import net.jimmc.nio.{NioApplication,NioServer,NioConnection}

import java.io.{BufferedReader,InputStreamReader,PrintWriter}
import java.net.InetAddress

import scala.util.continuations._

object ThreeQuestionsConsole {
    def main(args:Array[String]) {
        val in = new BufferedReader(new InputStreamReader(System.in))
        val out = new PrintWriter(System.out)
        val io = new SysReader(in,out)
        reset {
            (new ThreeQuestions(io)).run
        }
    }
}

object ThreeQuestionsServer {
    def main(args:Array[String]) {
        val app = new ThreeQuestionsApp
        val hostAddr:InetAddress = null //localhost
        val port = 1234
        val server = new NioServer(app,hostAddr,port)
        server.start()
    }
}

class ThreeQuestionsApp extends NioApplication {
    def runConnection(conn:NioConnection):Unit @suspendable = {
        val io = new ConnReader(conn)
        (new ThreeQuestions(io)).run
    }
}

trait ReaderWriter {
    def readLine():String @suspendable
    def writeLine(s:String):Unit @suspendable
}

class SysReader(in:BufferedReader,out:PrintWriter) extends ReaderWriter {
    def readLine() = in.readLine
    def writeLine(s:String) = { out.println(s); out.flush() }
}

class ConnReader(conn:NioConnection) extends ReaderWriter {
    def readLine():String @suspendable = conn.readLine
    def writeLine(s:String):Unit @suspendable = conn.writeLine(s)
}

class ThreeQuestions(io:ReaderWriter) {
    def run():Unit @suspendable = {
        val RxArthur = ".*arthur.*".r
        val RxGalahad = ".*galahad.*".r
        val RxLauncelot = ".*(launcelot|lancelot).*".r
        val RxRobin = ".*robin.*".r
        val RxHolyGrail = ".*seek the holy grail.*".r
        val RxSwallow = ".*african or european.*".r
        val RxAssyriaCapital =
            ".*(assur|shubat.enlil|kalhu|calah|nineveh|dur.sharrukin).*".r
        val name = ask("What is your name?").toLowerCase
        val quest = ask("What is your quest?").toLowerCase
        val holy = quest match {
            case RxHolyGrail() => true
            case _ => false
        }
        if (holy) {
            val q3Type = name match {
                case RxRobin() => 'capital
                case RxArthur() => 'swallow
                case _ => 'color
            }
            val a3 = (q3Type match {
                case 'capital => ask("What is the capital of Assyria?")
                case 'swallow => ask("What is the air-speed velocity of an unladen swallow?")
                case 'color => ask("What is your favorite color?")
            }).toLowerCase
            (q3Type,a3,name) match {
                //Need to use an underscore in regex patterns with alternates
                case ('capital,RxAssyriaCapital(_),_) => accept
                case ('capital,_,_) => reject
                case ('swallow,RxSwallow(),_) => rejectMe
                case ('swallow,_,_) => reject
                case ('color,"blue",RxLauncelot(_)) => accept
                case ('color,_,RxLauncelot(_)) => reject
                case ('color,"yellow",RxGalahad()) => accept
                case ('color,_,RxGalahad()) => reject
                case ('color,_,_) => accept
            }
        } else {
            reject
        }
    }

    def ask(s:String):String @suspendable = { io.writeLine(s); io.readLine }
    def accept:Unit @suspendable = io.writeLine("You may pass")
    def reject:Unit @suspendable = io.writeLine("you: Auuuuuuuugh!")
    def rejectMe:Unit @suspendable = io.writeLine("me: Auuuuuuuugh!")
}

To run in console or server mode, use one of the following two commands:

$ scala ThreeQuestionsConsole
$ scala ThreeQuestionsServer

Limitations

I am calling this version complete because it addresses all of the issues in the Limitations section of my original post, but it is far from production-ready. Before putting this code into production I would address the following issues.

Although the application now uses more than one thread, it still runs all of the application code on a single thread. The scheduler should be replaced by one that can choose how many threads to use and distribute the execution of the coroutines among those threads.
This version still has not addressed all of the issues raised in the Limitations section of the second post in this series, on character decoding. In particular:
- Error handling should be improved.
- It only supports UTF-8 encoding.
For an example of this problem, type a Control-C into your telnet window when connected to the EchoServer application.
The application should parse its command line arguments so that it has the flexibility to, for example, use a different port number without requiring a code change.
The application should read a configuration file.
Error handling in general needs to be improved.
Logging should be added.

Java NIO for Writing

2011-04-08T08:58:00.000-07:00

Using Java NIO non-blocking IO for writing as well as reading is almost - but not quite - straightforward.

Background
Implementation
Two Selectors
Close
Summary

Background

One of the limitations pointed out in the Limitations section of the original post in this series was that we were still directly writing our output data to the socket rather than using non-blocking IO and continuations as we were doing when reading our input data. If a client stops reading its input (or if there is sufficient network congestion that it looks that way from our end) then our socket output buffer may fill up. If that happens, then one of two things will happen when we try to write our data to that socket: either the call will block, or the data will not all be written. If the call blocks, then we have a blocked thread that we can not use for processing other clients until it is unblocked. If there are many clients who are not reading their input, we could have many blocked threads. Since one of the goals of this exercise is to be able to run many clients on a relatively small number of threads, having blocked threads is bad. To avoid this problem, we use non-blocking output and continuations for writing to the output, just as we did for reading the input.

The complete source for this series of posts is available on github in my nioserver project, with the specific version after the changes specified in this post tagged as blog-write.

Implementation

We model the output code on the input code by making these changes:

We write a suspending write method that registers our interest in writing to the output socket connection.
We add an output queue to receive data from the application.
We modify the writeLine method to add a line to the output queue rather than writing directly to the output socket.
We run a separate control loop that reads from the output queue and writes to the output socket.

//In class NioConnection
    private val outQ = new CoQueue[String](sched, 10)

    def start():Unit = {
        startReader
        startWriter
        startApp
    }

    private def startWriter() {
        reset {
            while (socket.isOpen)
                writeWait
        }
    }

    private def write(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            selector.register(socket, SelectionKey.OP_WRITE, {
                val n = socket.write(b)
                k(n)
            })
        }
    }

    private def writeBuffer(b:ByteBuffer):Unit @suspendable = {
        write(b)
        if (b.remaining>0 && socket.isOpen)
            writeBuffer(b)
        else
            shiftUnit[Unit,Unit,Unit]()
    }

    private def writeWait:Unit @suspendable = {
        val str = outQ.blockingDequeue
        writeBuffer(ByteBuffer.wrap(str.getBytes("UTF-8")))
    }

    def writeLine(s:String):Unit @suspendable = write(s+"\n")
    def write(s:String):Unit @suspendable = outQ.blockingEnqueue(s)

This seems pretty straightforward, but unfortunately it doesn't work. The problem is that we have attempted to register our channel twice (once for read and once for write) with the same selector. The documentation for SelectableChannel says, "A channel may be registered at most once with any particular selector." If we call register for our channel for write when it is already registered for read, the read registration is overwritten by the write registration and is lost.

In his Rox Java NIO Tutorial James Greenfield explicitly recommends that you "Use a single selecting thread" and "Modify the selector from the selecting thread only." We could take this approach, adding some code to combine the read and write interest flags when we are in that position, but unlike in James' case we would also need to add some code to demultiplex the separate callbacks for read and write. Instead, we use a different approach: we use separate selectors for reading and writing, and we give each of them its own thread.

Two Selectors

Depending on the implementation, using two selectors and two threads this way could cause problems. However, based on my understanding of the documentation, the code in the Sun implementation and the operation of the POSIX select operation, I believe this approach should work (at least on POSIX systems). This would need to be tested on all supported platforms for a production system.

To use separate read and write selectors, we replace the current selector parameter in NioConnection with two parameters readSelector and writeSelector of the same type.

//In object NioConnection:
    def newConnection(sched:CoScheduler, readSelector:NioSelector,
            writeSelector:NioSelector, socket:SocketChannel) {
        val conn = new NioConnection(sched,readSelector,
            writeSelector,socket)
        conn.start()
    }

class NioConnection(sched:CoScheduler, readSelector:NioSelector, 
        writeSelector:NioSelector, socket:SocketChannel) {
    ...
    private def read(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            readSelector.register(socket, SelectionKey.OP_READ, {
                val n = socket.read(b)
                k(n)
            })
        }
    }

    private def write(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            writeSelector.register(socket, SelectionKey.OP_WRITE, {
                val n = socket.write(b)
                k(n)
            })
        }
    }

    ...
}

We also change NioListener to pass through those two arguments, and we choose to use the readSelector to handle our accept calls.

//In NioListener
class NioListener(sched:CoScheduler, readSelector:NioSelector,
        writeSelector:NioSelector, hostAddr:InetAddress, port:Int) {
    ...
    def start(continueListening: =>Boolean):Unit = {
        reset {
            while (continueListening) {
                val socket = accept()
                NioConnection.newConnection(sched,
                    readSelector,writeSelector,socket)
            }
        }
    }

    private def accept():SocketChannel @suspendable = {
        shift { k =>
            readSelector.register(serverChannel,SelectionKey.OP_ACCEPT, {
                val conn = serverChannel.accept()
                conn.configureBlocking(false)
                k(conn)
            })
        }
    }
}

Finally, we instantiate the new write selector in NioServer, pass it in to NioListener, and start it running in a new thread.

//In NioServer
class NioServer(hostAddr:InetAddress, port:Int) {
    val readSelector = new NioSelector()
    val writeSelector = new NioSelector()
    val sched = new DefaultCoScheduler
    val listener = new NioListener(sched, 
        readSelector, writeSelector, hostAddr, port)

    def start() {
        listener.start(true)
        //run the NIO read and write selectors each on its own thread
        (new Thread(writeSelector,"WriteSelector")).start
        (new Thread(readSelector,"ReadSelector")).start
        Thread.currentThread.setName("CoScheduler")
        sched.run    //run the coroutine scheduler on our thread, renamed
    }
}

Close

Our current example has no terminating condition, so never attempts to close the connection. Looking ahead, we expect to have applications that will want to do that, so we add a close method to NioConnection, and an isOpen method that allows us to see when it is closed.

We can't just add a close method that directly closes the socket, because there may still be output data waiting to be written. Thus we need an implementation that somehow waits until all of the queued output data has been written to the output before closing the socket.

One easy way to do this is to have a special marker string that we put into the output queue when the application requests to close the socket. When our socket output code sees that marker, we know it has already written out all of the data that came before that marker in the output queue, so we can close the socket. By doing the socket close in the same method that does the writes to the socket, and by ensuring that that method is called on the (write) selection thread, we also ensure that the close happens on the selection thread.

The compiler shares constant strings, so to make sure we have a unique string for our marker that can't be passed in by any code outside of our close method, we use new String(). In writeWait, where we check for that marker, we use the identity comparison eq when checking for the marker, and we add a call to shiftUnit to make both sides of the if statement be CPS.

A call to our close method will return right away, but the socket will not get closed until after all of the data in the output queue has been written to the output socket. The application can tell when the socket has actually been closed by calling the isOpen method.

//In NioConnection
    private def writeWait():Unit @suspendable = {
        val str = outQ.blockingDequeue
        if (str eq closeMarker) {
            socket.close
            shiftUnit[Unit,Unit,Unit]()
        } else
            writeBuffer(ByteBuffer.wrap(str.getBytes("UTF-8")))
    }

    def isOpen = socket.isOpen
    private val closeMarker = new String("")
    def close():Unit @suspendable = write(closeMarker)

Summary

As in the previous two posts, we have modified the program to make an internal improvement that has not changed its basic external behavior. We have, however, changed its behavior for one of the corner cases - in this case what happens when an output socket fills up, such as might happen when there is excessive network latency - which is a necessary improvement for a production application, particularly if one expects the kind of high volume that would make those corner cases more likely.

Java NIO and Scala Coroutines

2011-04-02T18:33:00.000-07:00

I present a multi-client server in Scala that uses coroutines to allow modularization of stateful client processing in a way that is independent of threads.

Background
Coroutines
Architecture
NioSelector
CoScheduler
CoQueue
NioConnection
LineDecoder
NioListener
NioServer
Summary
Caveats

Background

In my previous two posts I presented a server in Scala that uses Java NIO non-blocking IO and continuations to allow scaling to a large number of clients. As I pointed out in the Limitations section of that first post, that example used one thread for all execution. On a multi-core machine, as is common today, we would prefer to have multiple threads running to allow us to take advantage of all of the processing power available to us, yet we don't want to allocate a thread to every client.

It would be nice if we could add our own SelectableChannel types to the set of NIO channel types that we can use with the select call so that we could have one place where we do all our scheduling, but that feature is not available. We thus have to come up with another mechanism for handling all of the other potentially blocking tasks we will want to do. Fortunately, we already have such a mechanism: coroutines.

Coroutines

Coroutines provide a separation of the maintenance of task state from the execution of code for that task, allowing us to bind execution of the task to different threads as we desire. When one of our task coroutines becomes blocked waiting for an unavailable resource, we suspend it by storing its continuation, allowing us to use that thread for another purpose, such as to restore and run a different previously stored continuation that is now runnable.

In my earlier post on coroutines I presented an implementation of a coroutine package that included a scheduler (CoScheduler) and a blocking queue (CoQueue). We will modify the server implementation of my previous two "Java NIO" posts to make use of those classes.

As pointed out in that earlier coroutines post, the default scheduler implementation in the example can easily be replaced by another implementation with no other changes to the code. In particular, that new implementation could use a thread pool or a group of actors to execute the coroutines that are ready to run, assuming the coroutine code itself is multi-thread safe. We will not write that multi-thread scheduler for this post, but will assume that it can be written later.

Architecture

At a high level, we want to modify our server so that we have a queue between our socket reader and the application that will eventually consume the data. We can then set up a small processing loop that reads the socket data, converts it to a string and writes it to that queue. The application will read the contents of the queue, process it, and write back its results to the connection. We will let the socket reader continue to run on the select thread, but we will run the application on a separate thread (or threads), ensuring that the select loop can quickly get to all connections and preventing the application processing of any one connection from delaying the IO of other connections.

With this architecture we have two processing loops:

Read data from socket, write to queue.
Read data from queue, process it, write data (to socket, for now).

Given that for now we are writing directly to the connection socket on output (and ignoring the possibility that the output socket might be blocked), the second loop only has one potential blocking point: if there is no data in the queue, it will block when trying to read from the queue. The first loop has two potential blocking points: when it reads data from the socket (if there is no data available), and when it writes data to the queue (if the queue is full). The difficulty here is that the potentially blocking socket read must be handled by the NIO select call, but the potentially blocking write to the queue can't be handled by the NIO select call and thus must be handled by our own scheduler.

Having one processing loop that when blocked is sometimes managed by one scheduler (NIO select) and sometimes by another (our coroutine scheduler) is not necessarily a problem. Each scheduler just sees a blocking resource that has a continuation associated with it; when the blocking resource becomes available, the continuation is called and the process continues. The new issue that arises when trying to combine two schedulers like this is that an action by one scheduler can potentially unblock a task that is currently controlled by (i.e. in a wait state on) the other scheduler. Every time we perform an action that might unblock a task we need to ensure that the appropriate scheduler is not stuck waiting on the other tasks. In other words, we need to wake up or notify the schedulers at appropriate points in our code.

In this post, code which has changed is highlighed in bold (when not using Syntax Highlighting). Changes for CoScheduler and CoQueue are as compared to the code in my post on coroutines; changes to NioSelector, NioConnection, LineDecoder, NioListener and NioServer are as compared to the code in my previous two posts.

The complete source for this post is available on github in my nioserver project, with the specific version used in this post tagged as blog-coroutines. There are also tags for the previous two posts, so you can compare using those tags to see the changes between the versions as used in each post.

NioSelector

As mentioned above, we have to cooperate with the coroutine scheduler. In particular, we have to be able to deal with the situation that we have no active connections, so we are in a select call, then another thread registers interest in an operation. The documentation for the select call states:

Changes made to the interest sets of a selector's keys while a selection operation is in progress have no effect upon that operation; they will be seen by the next selection operation.

To terminate the select operation early so that it retries with the newly registered channel, we add a call to wakeup just after registering our interest.

Unfortunately, this is not enough. The documentation for the select call is not very precise about whether it is actually possible to call the register call from another thread while the select call is blocked waiting for a previously registered channel to become active. The documentation for SelectableChannel does explicitly say "Selectable channels are safe for use by multiple concurrent threads", but the documentation for the register method says "This method will then synchronize on the selector's key set and therefore may block if invoked concurrently with another registration or selection operation involving the same selector." In fact, the standard Sun implementation does quite a bit of synchronization, so quite easily gets deadlocked when used by multiple threads. In particular, the OS-level select call in the Java select method is inside a pair of synchronized blocks that lock the set of SelectionKeys associated with that selector. If, while the first thread is blocked on the select, a second thread calls SelectableChannel.register, it locks the channel, then attempts to lock on the key set to which that channel is being added, so it blocks. If a third thread then tries to register that channel with a second selector, which the documentation implies is allowed, the third thread will attempt to lock the channel, which will block until the second thread unblocks and releases its lock on the channel.

In his Rox Java NIO Tutorial James Greenfield explicitly recommends that you "Use a single selecting thread" and "Modify the selector from the selecting thread only." From the description of how register works above, you can see why.

To get around this problem and ensure that all changes to the selection keys happen on the thread that is calling select, we modify NioSelect.register so that, rather than calling SelectableChannel.register directly, it packages the arguments up and puts them into a queue which is processed by the selection thread in order to make all of the calls to SelectableChannel.register just before it calls select.

Fortunately, the semantics of the wakeup call ensure that we won't get ourselves into a position where we have put our registration request into the queue but the select call doesn't see it and blocks on all the other channels. This is because wakeup is defined such that a call to it that happens while the selector is not currently in a select operation will cause the next select to wake up immediately.

With this change, all of the key set operations happen on the selection thread and, since the socket read operation is in a callback that gets executed by the selection thread in NioSelector.executeCallbacks, all socket reads (and likewise accepts) will happen on the selection thread.

//In class NioSelector
import scala.collection.mutable.SynchronizedQueue

    private case class RegistrationRequest(
        channel:SelectableChannel,op:Int,callback:Function0[Unit])
    private val regQ = new SynchronizedQueue[RegistrationRequest]

    def register(channel:SelectableChannel, op:Int, body: => Unit) {
        val callback:Function0[Unit] = { () => { body }}
        regQ.enqueue(RegistrationRequest(channel,op,callback))
        selector.wakeup()
    }

    def selectOnce(timeout:Long) {
        while (regQ.size>0) {
            val req = regQ.dequeue()
            req.channel.register(selector,req.op,req.callback)
        }
        ...
    }
}

CoScheduler

For our coroutine scheduler, we have to be able to deal with the situation that we have no coroutines that are currently runnable, then at some point one of those coroutines becomes runnable by the actions of another thread. In the architecture described above, this can happen when new data that has been read from a connection is placed into the input queue. To allow us to wait for this kind of event and to be awakened when it happens, we use Java's wait/notify model. We can't override those methods, since notify is final, so we define our own versions, which we call coWait and coNotify. Given those methods, we also extend Runnable and replace the old run method with one that runs coroutines until none are available to run, then waits until we are notified and continues the loop.

trait CoScheduler extends Runnable { cosched =>
    //we add the following items
    private val defaultLock = new java.lang.Object
    def coWait():Unit = { defaultLock.synchronized { defaultLock.wait() } }
    def coNotify():Unit = { defaultLock.synchronized { defaultLock.notify } }

    def run {
        while (true) {
            runUntilBlockedOrDone
            coWait
        }
    }
}

A coNotify method that accepts as an argument the coroutine or blocker that has potentially changed state would allow for a more efficient implementation, but for now we choose the simple implementation given above that does not attempt that optimization.

CoQueue

We use an instance of CoQueue as the queue between the socket read loop and the application processing loop. The socket read loop calls blockingEnqueue to place an item into the queue, and the application processing loop calls blockingDequeue to take an element out of the queue. The result of either of these actions could be to unblock another coroutine, so we modify those methods to add a call to coNotify in case they are being called from a coroutine that is not currently being managed by our coroutine scheduler. Since we are calling the enqueue and dequeue methods from different threads, we use a SynchronizedQueue rather than a plain Queue. Those two methods now look like this:

import scala.collection.mutable.SynchronizedQueue

class CoQueue ... extends SynchronizedQueue[A] { ...

    def blockingEnqueue(x:A):Unit @suspendable = {
        enqueueResource.waitUntilNotBlocked
        enqueue(x)
        dequeueResource.coNotify
    }

    def blockingDequeue():A @suspendable = {
        dequeueResource.waitUntilNotBlocked
        val x = dequeue
        enqueueResource.coNotify
        x
    }

NioConnection

We add a CoQueue which we use as our input queue between the socket reader loop and the application loop. For this example, we pick an arbitrary limit of 10; if our application gets behind by more than 10 items, the socket reader code will suspend when attempting to write to the queue. If more data arrives while that code is thus suspended, it will back up in the system's input buffer for that connection, and eventually the client will get an error when trying to write to its output connection.

In order to initialize the CoQueue we need to pass in a CoScheduler, so we add that parameter to our constructor and to the convenience method in our companion object.

import net.jimmc.scoroutine.{CoQueue,CoScheduler}

//In object NioConnection
    def newConnection(sched:CoScheduler, selector:NioSelector, socket:SocketChannel) {
        val conn = new NioConnection(sched,selector,socket)
    }

class NioConnection(sched:CoScheduler, selector:NioSelector, socket:SocketChannel) {
    //Add CoQueue
    private val inQ = new CoQueue[String](sched, 10)
}

Now that we have a queue, we modify our socket reader code to place our input data (after conversion to a Java string) into our queue rather than writing it straight to the output socket. We want to block when the queue is full, so we call the blockingEnqueue method. Since we now know that's the only action we will be taking, we fold the readAction method back into readWhile. Because blockingEnqueue is suspendable, the else branch of the if (count<1) code block is suspendable, so we need to make the if branch suspendable as well. We do this by adding a shiftUnit call as the final value in the if branch. The readWhile method now looks like this:

    private def readWait = {
        buffer.clear()
        val count = read(buffer)
        if (count<1) {
            socket.close()
            shiftUnit[Unit,Unit,Unit]()
        } else {
            //Moved here from readAction
            buffer.flip()
            lineDecoder.processBytes(buffer, inQ.blockingEnqueue(_))
        }
    }

We now have input data going into our queue, but nobody is reading it. For this example, we implement a simple echo loop that reads from the input queue using a new readLine method and writes to the output using our existing writeLine method. We do this inside a reset block so that it becomes another coroutine that can be managed by our coroutine scheduler. Our previous start method started up the socket reader loop. We rename that one to startReader, add a startApp method that starts up our echo loop, and call both of those from a new start method. Our start method now looks like this:

//In class NioConnection
    def start():Unit = {
        startReader
        startApp
    }   
            
    private def startApp() {
        reset {
            while (socket.isOpen)
                writeLine(readLine())
        }
    }

    private def startReader() {
        reset {
            while (socket.isOpen)
                readWait
        }
    }

    def readLine():String @suspendable = inQ.blockingDequeue

LineDecoder

Our processBytes method is now getting passed a callback that is suspendable, so we need to modify the signature of our method to accept that. It passes that callback to processChars, so that signature needs to be changed in the same way. Since processChars is now calling a suspendable method, it too is suspendable, so its return signature needs to be modified to note that, and since processBytes calls processChars, it too needs to be modified to have a suspendable return signature.

//In class LineDecoder
import scala.util.continuations._

    def processBytes(b:ByteBuffer,
        lineHandler:(String)=>Unit @suspendable):Unit @suspendable = ...

    private def processChars(cb:CharBuffer,
        lineHandler:(String)=>Unit @suspendable):Unit @suspendable = { ... }

NioListener

NioListener calls NioConnection.newConnection, and that call now requires a CoScheduler argument, so we add that to our constructor and pass it through when we call newConnection.

import net.jimmc.scoroutine.CoScheduler

class NioListener(sched:CoScheduler, selector:NioSelector, hostAddr:InetAddress, port:Int) {

    def start(continueListening: =>Boolean):Unit = {
        reset {
            while (continueListening) {
                val socket = accept()
                NioConnection.newConnection(sched,selector,socket)
            }
        }
    }
}

NioServer

NioServer instantiates the NioListener, so we need to pass it an instance of CoScheduler. We create an instance of DefaultCoScheduler and pass that in. We now need two threads, one for our coroutine scheduler and one for the NIO scheduler. In our start method, we create and start a second Thread for the NIO scheduler, then rename our own thread and run the coroutine scheduler on it.

import net.jimmc.scoroutine.DefaultCoScheduler

class NioServer(hostAddr:InetAddress, port:Int) {
    val selector = new NioSelector()
    val sched = new DefaultCoScheduler
    val listener = new NioListener(sched, selector, hostAddr, port)

    def start() {
        listener.start(true)
        //run the NIO selector on its own thread
        (new Thread(selector,"NioSelector")).start
        Thread.currentThread.setName("CoScheduler")
        sched.run    //run the coroutine scheduler on our thread, renamed
    }
}

Summary

As in the previous post, we have once again transformed our example application in a way which provides an internal improvement - in this case the ability to use multiple threads - but which has not changed its basic external behavior: we still have a simple echo server. We also have not yet addressed all of the Limitations from the first post in this series. Stay tuned for more.

Caveats

Although I have asserted that it is possible to write a multi-threading scheduler to the CoScheduler API, I have not yet actually done this. It is possible that this may be more difficult than I expect.
Multi-threaded code is generally tricky stuff. I have not spent a lot of time running this example code, so it is certainly possible that there are race conditions or other concurrency problems.

Java NIO for Character Decoding in Scala

2011-03-28T15:01:00.000-07:00

The Java NIO package includes some handy character encoding and decoding methods that can be used from Scala.

Background
Java NIO Character Coders
LineDecoder
NioConnection
Limitations

Background

In my previous post I described a simple Scala server using NIO and continuations, and mentioned in the Limitations section that the example did not convert the data bytes to characters. In this post I show how that can easily be added by using another feature of the Java NIO package: character-set encoders and decoders.

Java NIO Character Coders

The java.nio.charset package includes a Charset class that represents a mapping between the 16-bit Unicode code-units that Java uses for its internal representation for characters and strings, and a sequence of bytes as are stored in a file or transmitted through a socket connection. Each such mapping is represented by a separate instance of the Charset class. Standard character mappings such as "UTF-8" and "ISO-8859-1" can be retrieved using the static forName method.

Given an instance of Charset, a CharsetEncoder for that character mapping can be retrieved by calling the newEncoder method on that instance. That encoder can then be used to convert a Java string into a sequence of bytes suitable for writing to a file or connection.

Similarly, the newDecoder method on Charset retrieves a CharsetDecoder that can be used for the complementary task of converting bytes from a file or connection into a Java string.

The encoding and decoding methods convert data between a CharBuffer and a ByteBuffer. Since the java.nio socket I/O calls we are using read and write their data to and from ByteBuffers, it is convenient for the encoding and decoding to use those objects.

LineDecoder

Using the java.nio.charset classes described above, we write a LineDecoder class containing a processBytes method that takes as input a ByteBuffer (which is what we have to read into when using a SocketChannel) and converts that byte data to Java characters. For this example, we also break up that character data into separate lines when we see line break characters, converting each line of characters to a Java String. One buffer of data might contain multiple lines of character data, so rather than returning a set of lines, our method accepts a callback to which we pass each line as we decode it.

import java.nio.{ByteBuffer,CharBuffer}
import java.nio.charset.{Charset,CharsetDecoder,CharsetEncoder,CoderResult}
import scala.annotation.tailrec

class LineDecoder {

    //Encoders and decoders are not multi-thread safe, so create one
    //for each connection in case we are using multiple threads.
    val utf8Charset = Charset.forName("UTF-8")
    val utf8Encoder = utf8Charset.newEncoder
    val utf8Decoder = utf8Charset.newDecoder

    def processBytes(b:ByteBuffer, lineHandler:(String)=>Unit):Unit =
        processChars(utf8Decoder.decode(b),lineHandler)

    @tailrec
    private def processChars(cb:CharBuffer, lineHandler:(String)=>Unit) {
        val len = lengthOfFirstLine(cb)
        if (len>=0) {
            val ca = new Array[Char](len)
            cb.get(ca,0,len)
            eatLineEnding(cb)
            val line = new String(ca)
            lineHandler(line)
            processChars(cb, lineHandler)       //handle multiple lines
        }
    }

    //Assuming the first character in the buffer is an eol char,
    //consume it and a possible matching CR or LF in case the EOL is 2 chars.
    private def eatLineEnding(cb:CharBuffer) {
        //Eat the first character and see what it is
        cb.get match {
            case '\n' => if (cb.remaining>0 && cb.charAt(0)=='\r') cb.get
            case '\r' => if (cb.remaining>0 && cb.charAt(0)=='\n') cb.get
            case _ => //ignore everything else
        }
    }

    private def lengthOfFirstLine(cb:CharBuffer):Int = {
        (0 until cb.remaining) find { i =>
            List('\n','\r').indexOf(cb.charAt(i))>=0 } getOrElse -1
    }
}

Here is an imperative version of lengthOfFirstLine that does the same thing as the functional version above.

    private def lengthOfFirstLine(cb:CharBuffer):Int = {
        var cbLen = cb.remaining
        for (i <- 0 until cbLen) {
            val ch = cb.charAt(i)
            if (ch == '\n' || ch == '\r')
                return i
        }
        return -1
    }

NioConnection

One of the classes shown in my previous post was the NioConnection class, whose responsibilities include processing input data from the client. It does this in the method readAction, which initially looks like this:

//The old version
    private def readAction(b:ByteBuffer) {
        b.flip()
        socket.write(b)
        b.clear()
    }

We replace the direct call to socket.write with a call to LineDecoder.processBytes, which is responsible for decoding the input data, and we pass it our new writeLine method that accepts a line of characters and writes it back to the client. Also, we don't actually need the call to b.clear here, which is effectively at the bottom of our readWhile loop, since we call that method at the top of the loop.

    private val lineDecoder = new LineDecoder

    private def readAction(b:ByteBuffer) {
        b.flip()
        lineDecoder.processBytes(b, writeLine)
    }

    def writeLine(line:String) {
        socket.write(ByteBuffer.wrap((line+"\n").getBytes("UTF-8")))
    }

Now when we receive some input data, it gets passed to LineDecoder.processBytes, which converts it to characters, breaks it up into separate lines, and calls our writeLine method for each line. The writeLine method uses String.getBytes to convert the characters in the line back to bytes, wraps those bytes into a ByteBuffer and writes them directly to the output channel.

As compared to the example in the previous post, this example should behave the same externally, but we are now passing around Java strings rather than NIO buffers, which, assuming we want to deal with string data rather than binary data, will make it simpler to write the rest of the real application.

Limitations

As with the example in the previous post, the current example only shows how to use the NIO calls on the read side of the connection. We could use a CharsetEncoder on the write side rather than using String.getBytes and ByteBuffer.wrap.
Partial input lines (characters not terminated by an EOL character) are ignored by this implementation.
The example uses the convenience method version of decode, which assumes that the input ByteBuffer contains complete character sequences. It is possible that a multi-byte character sequence will be split such that only the first part of that sequence appears at the end of the input buffer, with the remainder of the sequence appearing at the start of the next buffer of input data. The above implementation will not properly handle this situation. The underlying decode method does handle this situation properly, but the remaining code in this example is not set up for this situation.
The decode convenience method throws exceptions rather than returning a status code as the full decode method does. Since these exceptions are nowhere caught in the code, such an exception would cause that task to abort. A more robust solution would have a mechanism to catch exceptions or restart an aborted task.
The example assumes UTF-8 encoding.

Java NIO and Scala Continuations

2011-03-22T13:30:00.000-07:00

Combining Java's NIO non-blocking input/output with Scala's delimited continuations allows making a multi-client stateful server that does not require a a dedicated thread for every active client.

Motivation
Java Nonblocking IO
NioSelector
NioListener
NioConnection
NioServer
Limitations
Resources

Motivation

When writing a high-volume server, you want it to be able to handle a large number of clients in a timely manner. You want the server to be able to respond quickly to each request even when there are a lot of clients. In particular, when you have a large number of clients for whom you are storing state but are not at this moment making a request, you want those clients to have a negligible effect on your response time, and when you have other clients currently making requests that may take some time to execute, you don't want those requests significantly increasing your response time to other requests.

From the above, we thus have these requirements:

The size of the state stored for each active client should be minimized.
The time to notice that a client has made a request should not depend significantly on the number of active clients not making a request.
A client request should never wait on a request from another client.

A simple Java implementation of a server might store its per-client state in a thread for each active client, and block waiting for a request on each thread. Java's thread scheduler then takes care of noticing when input is is available from one of those blocking reads and continuing execution on the associated thread. However, threads are relatively expensive and consume more memory than necessary.

An implementation that stores the state for each client manually could store that state much more compactly and thus handle many more clients, but in addition to being more complicated to implement, the application must now include a mechanism to multiplex multiple clients onto fewer threads than there are active clients without having any clients blocked by other clients.

Scala's delimited continuations give us a another option for storing the state of a client that is simpler to implement than manual state storage and that uses far less memory than using a thread for each client (see slide 19 of Phillip Haller's presentation on Actors, where he says an app can handle up to 5,000 threads, but up to 1,200,000 actors using closures).

That leaves us to solve the issue of how to multiplex many clients without having them block each other. If using the standard java.io package, the only option for reading from multiple streams without blocking is to poll using the available method. Besides the wasted CPU time, as the number of active clients grows the polling loop takes longer to run, meaning additional latency before the application notices that any particular stream is ready for reading and thus increased response time. The Java NIO package provides an efficient solution for this problem.

In the "Nio*" sections below I present a few Scala classes that break up the NIO work into chunks that I hope are easy to understand. The last piece is a simple main class to test it all.

Java Nonblocking IO

Starting with version 1.4, Java has a package called NIO (new input/output) that includes the ability to do non-blocking input and output.

The non-blocking IO model in Java NIO is based on Channels and Selectors, similar to file descriptors and the select call in POSIX operating systems. A Channel represents a connection to a file, socket, or some other data source or sink. A Selector allows collecting a set of Channels together and waiting until any of them are ready for input or output.

In order to use a Channel with a Selector, you must register the Channel with the Selector (and the Channel must be a SelectableChannel). When you register a channel you also specify which operations are of interest, such as READ or WRITE. These operations are represented by bits that can be combined by ORing them together to create a value that indicates interest in multiple operations.

Registering a channel with a selector creates a SelectionKey. When you later execute the select method on the selector, it returns a set of SelectionKeys, from which you can extract the information passed to the register call when the SelectionKey was created.

NioSelector

The register call to java.nio.channels.SelectableChannel includes an "attachment" parameter that allows the application to attach an arbitrary object to that registration and retrieve it later when the associated channel becomes selected. In our server, we attach a callback function to be executed when the channel becomes selected. We package this up in our own register method in our NioSelector class.

import java.nio.channels.SelectableChannel
import java.nio.channels.spi.SelectorProvider

/** Handle nio channel selection. */
class NioSelector {

    val selector = SelectorProvider.provider.openSelector()

    def register(channel:SelectableChannel, op:Int, body: => Unit) {
        val callback:Function0[Unit] = { () => { body }}
        channel.register(selector, op, callback)
    }
}

We add a selectOnce method that waits for one or more of the registered channels to be selected, or until the specified time has elapsed if no channels are selected during that time. The underlying call to selectedKeys in java.nio.channels.Selector returns to us a java.util.Set containing the information about which channels are selected. Before we process each channel, we need to clear the current state so that we are able to re-register interest in that channel during that processing. We make a copy of the state for all selected channels and then clear that state before processing any channels.

import scala.collection.JavaConversions
import java.nio.channels.SelectionKey

//In class NioSelector

    def selectOnce(timeout:Long) {
        selector.select(timeout)
        val jKeys:java.util.Set[SelectionKey] = selector.selectedKeys
        val keys = JavaConversions.asScalaSet(jKeys).toList
        selector.selectedKeys.clear()
        keys foreach { _.interestOps(0) }
        val callbacks = keys map { _.attachment.asInstanceOf[()=>Unit] }
        executeCallbacks(callbacks) //Execute callbacks for all selected keys
    }

The executeCallbacks method is responsible for executing the callbacks for the selected channels. If we assume that at least some of these callbacks may take a relatively long time to complete, then in a real server we might want to throw all of these callbacks into a thread pool or farm them out to actors so that we can avoid having one long-running callback block out the rest of the channels. For now, though, we will ignore that issue and use the simple implementation of just executing each callback sequentially in the same thread.

//In class NioSelector

    def executeCallbacks(callbacks:List[()=>Unit]) {
        callbacks foreach { _() }
    }

For convenience, we add a selectLoop method that will continue to call selectOnce until we are ready to stop processing, and we make our class implement the Runnable interface.

//In NioSelector class

    def run() {
        selectLoop(true)
    }

    def selectLoop(continueProcessing: => Boolean) {
        while (continueProcessing) {
            selectOnce(0)
        }
    }

Here is the complete NioSelector class:

import scala.collection.JavaConversions
import java.nio.channels.SelectableChannel
import java.nio.channels.SelectionKey
import java.nio.channels.spi.SelectorProvider

/** Handle nio channel selection. */
class NioSelector extends Runnable {

    val selector = SelectorProvider.provider.openSelector()

    def register(channel:SelectableChannel, op:Int, body: => Unit) {
        val callback:Function0[Unit] = { () => { body }}
        channel.register(selector, op, callback)
    }

    def run() {
        selectLoop(true)
    }

    def selectLoop(continueProcessing: => Boolean) {
        while (continueProcessing) {
            selectOnce(0)
        }
    }

    def selectOnce(timeout:Long) {
        selector.select(timeout)
        val jKeys:java.util.Set[SelectionKey] = selector.selectedKeys
        val keys = JavaConversions.asScalaSet(jKeys).toList
        selector.selectedKeys.clear()
        keys foreach { _.interestOps(0) }
        val callbacks = keys map { _.attachment.asInstanceOf[()=>Unit] }
        executeCallbacks(callbacks) //Execute callbacks for all selected keys
    }

    def executeCallbacks(callbacks:List[()=>Unit]) {
        callbacks foreach { _() }
    }
}

Our main method will create an instance of NioSelector, do some other initialization, and eventually call NioSelector.run.

NioListener

The above NioSelector class gives us our main event loop, but how do we get things hooked up to start generating events? The basic socket flow on the server side for reading data follows these steps:

Listen for new connections on a socket.
When a new connection is made, initialize that connection and wait for input data on that connection.
When input data is received, process that input data.
Eventually, close the connection.

Our NioListener class takes care of creating the socket on which we listen, accepting new connections, and passing them off to another class for per-connection initialization.

We start with the code that creates the listener socket. Since we will be passing this socket to our selector, we must create a ServerSocketChannel rather than a regular socket. We don't want to block waiting for this socket, so we call configureBlocking(false).

import java.net.{InetAddress,InetSocketAddress}
import java.nio.channels.ServerSocketChannel

class NioListener(selector:NioSelector, hostAddr:InetAddress, port:Int) {

    val serverChannel = ServerSocketChannel.open()
    serverChannel.configureBlocking(false);
    val isa = new InetSocketAddress(hostAddr,port)
    serverChannel.socket.bind(isa)
}

Now that we have created our socket, we must register it with our selector. In that call, we will tell the selector that we are interested in the ACCEPT operation on our socket channel. The third argument to our register method is the callback; this is where continuations come in.

Blocking code is generally simpler and thus easier to write and understand than asynchronous (non-blocking) code. By using continuations we can capture the current state of the code, explicitly save it for later execution, and continue running the thread at a different point. The code within our delimited continuation is blocked, but the thread does not get blocked.

Rather than explicitly creating and passing in a callback with application state, we arrange things such that the callback passed to our register method includes a call to our continuation, so that when that callback is called, it executes our continuation and makes our code continue from where we left off.

We implement our own accept method that looks to the calling code like the blocking ServerSocket.accept method, but that uses continuations as described above to do the blocking. We then call our accept method from within a reset block that delimits the continuation and determines how much code is saved in the continuation (everything within the reset) and the point at which execution continues (just past the reset) in the thread when the accept call blocks.

import java.nio.channels.SelectionKey
import java.nio.channels.SocketChannel
import scala.util.continuations._

//In NioListener class
    def start(continueListening: =>Boolean):Unit = {
        reset {
            while (continueListening) {
                val socket = accept()
                NioConnection.newConnection(selector,socket)
            }
        }
    }

    private def accept():SocketChannel @suspendable = {
        shift { k =>
            selector.register(serverChannel,SelectionKey.OP_ACCEPT, {
                val conn = serverChannel.accept()
                conn.configureBlocking(false)
                k(conn)
            })
        }
    }

When we call our start method, it enters the reset block and calls accept, which registers our interest in the ACCEPT operation, saves the continuation as part of our callback in the register method and immediately returns control to the end of the reset block, thus the start method returns quickly. When a new connection arrives, the select code in NioSelector calls our callback from its executeCallbacks method. Our callback accepts the new connection and sets it to non-blocking, then executes our continuation, which will "return" from our blocked accept method into the loop in our start method. The code processes the new connection, then loops and calls accept again, which reregisters interest in an ACCEPT operation on our socket and returns execution to the caller of the continuation, which returns control to the executeCallbacks method in NioSelector.

NioConnection

Our NioConnection class is responsible for creating our connection object, registering it with the selector, reading input data when available and processing that data. The processing that we do in this example is to echo the data back to the client. In order to keep this example simple, we are not using NIO and continuations on the writing side, rather we use a simple write call to write our data directly to the socket.

As with NioListener, we create our own read call that uses continuations to block, but otherwise looks similar to the standard Java InputStream.read(byte[]) call, except that we read into a ByteBuffer rather than a byte array. As with NioListener, our start method that calls our read method (via our intermediate method readWait) contains a reset block that delimits the continuation.

import java.nio.ByteBuffer
import java.nio.channels.SelectionKey
import java.nio.channels.SocketChannel
import scala.util.continuations._

object NioConnection {
    def newConnection(selector:NioSelector, socket:SocketChannel) {
        val conn = new NioConnection(selector,socket)
        conn.start()
    }
}

class NioConnection(selector:NioSelector, socket:SocketChannel) {

    private val buffer = ByteBuffer.allocateDirect(2000)

    def start():Unit = {
        reset {
            while (socket.isOpen)
                readWait
        }
    }

    private def readWait = {
        buffer.clear()
        val count = read(buffer)
        if (count<1)
            socket.close()
        else
            readAction(buffer)
    }

    private def read(b:ByteBuffer):Int @suspendable = {
        if (!socket.isOpen)
            -1  //indicate EOF
        else shift { k =>
            selector.register(socket, SelectionKey.OP_READ, {
                val n = socket.read(b)
                k(n)
            })
        }
    }

    private def readAction(b:ByteBuffer) {
        b.flip()
        socket.write(b)
        b.clear()
    }
}

The program flow is similar to the flow in NioListener When we call our start method, it enters the reset block and (through the call to readWait) calls read, which registers our interest in the READ operation, saves the continuation as part of our callback in the register method and immediately returns control to the end of the reset block, thus the start method returns quickly. When data is available to be read from the socket, the select code in NioSelector calls our callback from its executeCallbacks method. Our callback reads the data from the connection then executes our continuation, which will "return" from our blocked read method into the readWait method. The code processes the input data in readAction (which just echos the data back to the client), then (if the socket is still open) loops and ends up calling read again, which reregisters interest in a READ operation on our socket and returns execution to the caller of the continuation, which returns control to the executeCallbacks method in NioSelector.

NioServer

Here is a short main program to test the above modules.

import java.net.InetAddress

object NioServer {
    def main(args:Array[String]) {
        val hostAddr:InetAddress = null //listen on local connection
        val port = 1234
        val server = new NioServer(hostAddr,port)
        server.start()
    }
}

class NioServer(hostAddr:InetAddress, port:Int) {
    val selector = new NioSelector()
    val listener = new NioListener(selector, hostAddr, port)

    def start() {
        listener.start(true)
        selector.run()
    }
}

Create a directory and place into that directory the above four files (NioSelector.scala, NioListener.scala, NioConnection.scala and NioServer.scala), cd into that directory, then execute the following commands to compile the files and execute the test program:

scalac -P:continuations:enable *.scala
scala NioServer

If you get an "Address already in use" error and traceback, edit NioServer.scala and pick another port number.

After starting the server, connect to it using telnet:

telnet localhost 1234

In the telnet client, each time you enter a line of text the server should echo that line of text back to you.

Limitations

The above example demonstrates a very basic echo server in a bit over 100 lines of code that uses NIO and continuations for reading data, but it has some limitations:

The processing of the input data is buried in the code that reads the data. A well-factored architecture would allow that processing code to be separately maintained.
We are using one thread for all execution. In the above example we are just echoing clients' input back to them, but if we want to do some heavier processing we will need to move that work off of the select thread onto one or more worker threads so as not to block everyone while handling a request for one client.
Communication between the select thread and the worker threads will require some kind of buffering, which introduces more points at which execution can be blocked, thus more opportunities to use continuations.
If we wish to treat the data as characters rather than bytes then we need to do that conversion.
We are not using IO and continuations when writing data to the client, so if for some reason our socket is not ready for writing the application will not work properly (either it will block waiting for output, or we will lose some output data).
We are not storing any significant amount of state in our continuations. If all we are doing is a simple echo server, we don't really need continuations. A more sophisticated example would better illustrate the convenience of using continuations to store program state.

I hope to address these points in future posts.

Resources

My explanation of delimited continuations.
Wikipedia article on Java NIO.
Rox Java NIO Tutorial, in which James Greenfield builds a server in Java using NIO and gives a number of tips and warnings.
Jenkov's Java NIO Tutorial goes over each part of the entire NIO package in detail.
MINA, Apache's network application framework that uses NIO.
Loft, a single-threaded web server in Scala using NIO and continuations (under development).
A post from July 2009 on the Scala mailing list with an (uncompiled) example of a simple single-threaded server using NIO. The post demonstrates the approach of creating versions of the standard calls (accept, read, write) that block using continuations.

Scala Pros and Cons

2010-12-22T06:27:00.000-08:00

Some pros and cons of the Scala programming language as compared to Java from a business management perspective.

Introduction
Pros

Higher Productivity
Higher Quality
Better Developers
Rapidly Improving Ecosystem

Cons

Learning Curve
Limited Developer Pool
Better Developers
Limited Commercial Support
Tool Immaturity

Former Cons

Risk of Breaking Changes
Risk of Abandonment
Limited Documentation

References

Web Sites Using Scala
Other Posts

Introduction

I have been promoting Scala for quite some time now, and I have encouraged all of the developers in my office to try it out, hoping that at some point we can start using it for new projects.

It was suggested to me that I put together a list of the pros and cons of Scala to help other people in the company evaluate whether they should consider using it for their projects. After pondering this I realized that this would likely be of interest to a wider audience than just at my company, and that it would make a good topic for my blog. Thus this post in which I list what I believe to be the most important factors that a company that wants to stay on the JVM platform should consider when deciding whether or not to move from Java to Scala.

Because this comparison is specifically Scala versus Java, I do not include the fact that Scala runs on the JVM, has performance on par with Java, interoperates easily with Java and after compiling is essentially indistinguihsable from Java. While these might be benefits for some companies when comparing Scala against other language such as Ruby or Python or other JVM languages, they do not distinguish Scala from Java.

The intended audience for this post is not the developers who might be using Scala, but the technical managers who are involved in the decision about what technology to use. I don't discuss Scala's cool features such as closures and continuations, easy interoperation with legacy Java code, traits with code, or a sophisticated type system with type inference, but focus instead on the business-level questions of how using Scala rather than Java might affect the success of a project, a team, or the company.

My company has not yet produced a product using Scala, so my experience is limited to some prototypes at the office and some personal work at home. The points below are based on that experience plus my interpretation of comments from others that I have read in the last couple of years. Everyone's viewpoint differs, so you may disagree with my statements or my evaluation of their importance. Similarly, the specifics of your situation may make your experience with Scala significantly different than mine. It is easy to find both praise and dismissal of Scala on the 'net. As they say, YMMV.

Pros

Higher Productivity

Studies and anecdotal evidence indicate that Scala programs are from 1/2 to 1/10 the number of lines of code as compared to a functionally equivalent Java program The larger the application, the more apparent this difference becomes. If you believe, as I do, that a given programmer can produce roughly the same number of lines of code per day independent of the language used, you can see how this reduction of lines of code can translate into a substantial increase in productivity and a faster time-to-market.

Higher Quality

Scala encourages a functional programming style, which in turn leads to code with fewer bugs. Also, fewer lines of code means fewer bugs. Fewer bugs means higher productivity and a higher quality product.

Scala's Actor library and its encouragement of immutable variables help to avoid race conditions among multiple threads and thus improve reliability in concurrent applications.

Better Developers

Programmers who learn Scala pick up programming practices such as functional programming that they can (at least to some extent) apply to other languages, such as Java. This makes them better Java programmers. Providing an environment in which developers can learn something new should also make for a more positive environment for those developers, so they will be happier with their jobs and less likely to leave the company. Likewise, a shop that uses a new and advanced language such as Scala is more likely to attract top-notch developers (which Paul Graham has named as "The Python Paradox").

Rapidly Improving Ecosystem

The early adopters of Scala such as Twitter are well down that road. Here at the end of 2010 it is tempting to say that the early adopter window is closed and anyone who starts with Scala in 2011 or later is no longer in that category.

Some of the cons listed below may never change, or change very slowly, but at least the tools issue will certainly improve. The rate of improvement of the Scala ecosystem is much faster than most other languages at the moment. The IDE tools are improving, the testing tools are improving, the documentation is improving, and the functionality of available libraries is improving. All of these improvements will continue to make the Scala ecosystem more attractive over time. If you evaluate the current situation and find it close to satisfactory, and the problem areas are the ones that will improve with time, then you probably won't have to wait very long for that to happen.

Cons

Learning Curve

Scala incorporates features and concepts that are not familiar to many programmers, such as functional programming and continuations. It can take some time to learn these concepts. Some people say the Scala syntax is more complicated than Java, but in fact the language spec for Scala is significantly smaller (191 pages) than the language spec for Java (684 pages). The difference is that Scala is much more regular and allows things to be combined in ways that can't be done in Java, which provides more power and expressiveness but also can take some time to learn.

I have seen comments to the effect that it could take about two months for a Java developer to come up to speed on Scala, although a developer who already has experience using other languages with functional constructs such as Python or Ruby should be able to pick it up faster.

Limited Developer Pool

There are far fewer developers who already know Scala than who already know Java, which means it will be more difficult if you need to staff up quickly and don't want to spend any time training.

Because of the more advanced concepts embodied in Scala, or at least concepts which are different from the concepts that many Java developers have internalized, it may be possible that some Java developers will have a difficult time coming up to speed on Scala. This would effectively decrease the overall pool of available developers even if you are willing to spend the time to train someone on Scala.

Until a much larger number of current Java developers try to learn Scala it will be difficult to know how much of a problem this will be. One possibility is that many current Java developers will not want to put the effort into learning the new concepts required to use Scala effectively, and that a large chunk of the growth in the pool of Scala developers will come from new developers who were educated with those concepts from the start.

Better Developers

Wait, wasn't this listed as a pro for Scala? Yes, this one is a two-edged sword. Even after accepting the Learning Curve and the current Limited Developer Pool, there is a possibility that not every Java developer has what it takes to become an effective Scala developer. Scala provides tools that allow highly competent developers to write very concise code, and if you give them those tools they will use them. Developers who are less competent may then have trouble understanding that code. Java suffers less from this particular problem because it doesn't provide the kinds of high-level constructs (such as higher-order functions and continuations) that can cause difficulty for less capable developers. If you take the Scala road and hire highly capable developers, you may be making a commitment to continue to hire only highly capable developers for some time.

You should ask yourself this question: would your company culture allow you to hire and keep a developer who is twice as expensive and ten times as productive? If your answer is "probably not", then you should stick with Java where you can hire those developers who are half as expensive and one-tenth as productive.

Limited Commercial Support

If you have a large Java project and you find you quickly need some additional developers, you can call a consulting company such as Accenture or Cognizant and they can throw an army of Java developers your way. If your project is written in Scala, I suspect they will happily tell you they can provide you with those resources, but they might have more difficulty doing that due to the above-mentioned Limited Developer Pool.

You could probably post a request to the Scala or Lift mailing lists and find some contractors with Scala experience to help you out, but there is not yet much in the way of explicit commercial support for Scala.

The recently founded company Scala Solutions is the first I am aware of that is advertising support for Scala in mission-critical applications. Large companies considering Scala may not be comfortable without having more choice here.

Tool Immaturity

The development tools for Scala are not as advanced as for Java. In particular, the IDE plugins are not yet as sophisticated, so developers who use IDEs may encounter some frustration. On the other hand, this issue should be addressed by Scala's Rapidly Improving Ecosystem.

Former Cons

While browsing the web you may run across people complaining about the items listed in this section. As I note for each item, as of this posting at the end of 2010 I believe these issues have been resolved.

Risk of Breaking Changes

As a new and evolving language, Scala has gone through some breaking changes a few times as new versions have been released. This has caused a lot of pain for some people, a number of whom have declared in their blog posts that this demonstrates that Scala is just an academic language and not ready for the real world. I believe that, while there still may be some changes to be made, with the release of version 2.8 the language has reached a level of stability that makes it suitable for production use.

Risk of Abandonment

Scala is a relatively new language, and some people feel that it may not "make it" and survive as an ongoing language, in which case any code written in Scala would become hard to maintain. I believe this risk is now relatively small, given how it has been growing over the last few years and the number of big names who have adopted Scala (see the list below).

Limited Documentation

While this may still be an issue for non-English teams, I believe there are now enough Scala books in English that this is no longer an issue for anyone who reads English. The Books on Scala page lists 19 books about Scala and Lift, including five Scala books in English and five in other languages (some of which are translations of the English versions) that are currently available.

References

Web Sites using Scala

The Scala web site has a page on Scala in the Enterprise, last updated a couple of months ago (as of this posting), listing quite a few companies that are using Scala.

Here are a few well-known web sites using Scala or Scala/Lift and some tech articles about them:

Nondeterministic Evaluation in Scala

2010-11-30T06:46:00.000-08:00

Scala continuations can be used to implement nondeterministic evaluation.

Background
Goal
Implementation
Examples
Other Implementations

Background

Nondeterministic evaluation is an approach in which choices among multiple alternatives are factored out of an application so as to allow writing the application as if all alternatives were simultaneously being considered. Factoring the application in this way allows using different strategies for searching the space of available choices with no or only small changes to the application code.

A truly nondeterministic evaluation would potentially give different results (possibly the same set of results in a different order) each time it is run. In the simplest implementations, the evaluation is actually deterministic and does give the same results every time it is run. A different way of interpreting the phrase "nondeterministic evaluation" is to think of it from the point of view of the application built on top of such an evaluator: the application is written as if the evaluation were nondeterministic, and the decision as to whether the implementation is deterministic or not is entirely within the evaluation package. In other words, the application is not determining the order of evaluation among alternatives, therefore from its perspective the evaluation is nondeterministic. If at some later time the evaluator is replaced by one with the same API but which is truly nondeterministic, the correctly-written application will continue to deliver valid results.

One of the benefits of a nondeterministic evaluation environment is that an application using that environment can (with some assumptions about the application's avoidance of side-effects) transparently be run in a multi-thread, multi-processor or multi-host version of that environment so as to parallelize the computation. Development of such an application can be done on a single-processor workstation using a small dataset, then moved to a more powerful environment for use on the real problem with a much larger dataset.

One simple model of nondeterministic evaluation is the amb evaluator discussed in the MIT "Wizard Book", Structure and Interpretation of Computer Programs (SICP) in Section 4.3. The amb operator was introduced by John McCarthy in his 1963 paper A Basis For a Mathematical Theory of Computation.

Goal

Before getting into the implementation, let's take a look at an example to show where we want to go. SICP starts its section on Logic Puzzles with this example:

The following puzzle (taken from Dinesman 1968) is typical of a large class of simple logic puzzles:
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
We can determine who lives on each floor in a straightforward way by enumerating all the possibilities and imposing the given restrictions:
(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))
Evaluating the expression (multiple-dwelling) produces the result
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))

Here is what the above looks like in my Scala implementation (see the Examples section below for boilerplate):

MultipleDwelling.scala

class MultipleDwelling extends AmbEval[List[(String,Int)]] {
    def distinct(vals:List[Int]):Boolean = {
        vals.distinct.length == vals.length
    }
    generate {
        val baker = amb(List(1,2,3,4,5))
        val cooper = amb(List(1,2,3,4,5))
        val fletcher = amb(List(1,2,3,4,5))
        val miller = amb(List(1,2,3,4,5))
        val smith = amb(List(1,2,3,4,5))
        require(distinct(List(baker,cooper,fletcher,miller,smith)))
        require(baker!=5)
        require(cooper!=1)
        require(fletcher!=5)
        require(fletcher!=1)
        require(miller>cooper)
        require(scala.math.abs(smith-fletcher)!=1)
        require(scala.math.abs(fletcher-cooper)!=1)
        yld(List(
            ("baker",baker),
            ("cooper",cooper),
            ("fletcher",fletcher),
            ("miller",miller),
            ("smith",smith)))
    }
}

As you can see, it is quite similar to the lisp implementation. In particular, the code that solves this specific problem includes very little other than the statement of the problem: a set of possible values, a set of requirements, and a yielding of the solution. The implementation choices about how to make choices among the alternatives listed in the amb expressions and how to evaluate those alternatives are all handled in the code for the AmbEval class.

Of course, you could write something very similar to the above using for-comprehensions with guard statements, and that would likely be more practical for most situations, but besides the fact that you can't currently use a for-comprehension in suspendable (CPS) code and thus can't use that construct in a generator without modifications such as introduced in this post, that's just not as interesting as the amb evaluator.

The authors of SICP note that the evaluation of their straightforward implementation of multiple-dwelling is "very slow". When I execute my version on my desktop machine, it runs in less than 1/100th of a second. If that line was written in the original version of 1980, that same program could have taken 10,000 times as long to run, a couple of minutes - a long time for what seems like a small and simple program.

Implementation

In this post I implement a simple nondeterministic evaluator modeled on the amb evaluator introduced above that allows specific problems to be stated as in the above example and solved by the nondeterministic evaluator.

In SICP they build the amb evaluator in lisp along with a REPL that knows how to retrieve and print the multiple results returned by the evaluation. Rather than building my own Scala REPL, I chose to treat the nondeterministic evaluation as a generator. Thus a nondeterministic computation is implemented as a special kind of generator, and it returns its values as does a generator.

In my previous blog post I showed how to use Scala's delimited continuations to create a standalone generator. I now extend that generator to support nondeterministic evaluation. The use of continuations is an essential part of this implementation. Unlike in my previous examples of the use of continuations, where continuations were captured but only executed a single time, in this case a single continuation is executed multiple times.

As seen in the example in the Goal section above, the implementation uses a class called AmbEval, which defines the amb and require methods.
AmbEval.scala

package net.jimmc.scoroutine

import scala.collection.Iterator
import scala.util.continuations._

class AmbEval[T] extends StandaloneGenerator[T] {
    def amb[A](seq:Iterable[A]):A @cpsParam[Unit,Unit] = {
        shift { k:(A=>Unit) =>
            val it = seq.iterator
            reset[Unit,Unit] {
                //Use of var for v is workaround for Scala bug #3501
                var v:A = null.asInstanceOf[A]
                while (it.hasNext) {
                    v = it.next
                    k(v)
                    stepUntilDone
                }
            }
        }
    }

    def require(condition: =>Boolean):Unit @cpsParam[Unit,Unit] = {
        if (!condition) { amb(List()) }
    }
}

The amb method is mostly straightforward: it iterates through the values provided to it and calls the supplied continuation for each value. The continuation represents the remainder of the code following the call to amb, which means all of the code following the call to amb will be executed multiple times, once with each value supplied to the call to amb. Each of these calls is "searching" the solution space using one value from the set of alternatives supplied to amb.

When the calling code calls amb a second time, amb once again turns around and calls the remaining code multiple times, once for each value passed to amb. Thus the application code following the second call to amb gets executed once for each combination of every value in the first call to amb times every value in the second call to amb, which is the cross-product of those two set of alternatives. Likewise if the application has a third or fourth call to amb; each call to amb multiplies the number of times the following code is executed.

One subtlety of the implementation is the call to stepUntilDone. The call to the continuation k(v), which calls the code in the application following its call to amb, will return when that code has finished running; but if that code calls yld, it will be suspended, and control will return to amb after that suspension. At this point we need to suspend the amb code as well, and when it is resumed, ensure that we resume the continuation code that we called as k(v). As long as the continuation called from amb continues to suspend itself by calling yld, we need to continue suspending ourself in the same way. Once the continuation called from amb finishes and returns to amb without suspending itself, then amb can continue in its loop and invoke the continuation with the next selected value.

Note that using the yld method to return values from the generator and allowing multiple calls to yld by ensuring that every branch finishes its execution gives us a capability not in the lisp implementation defined in SICP and shown above. In that implementation, a valid choice is indicating by successfully reaching the end of a branch; the valid value is the return value of the function. In our implementation, a single branch can return multiple valid values by calling yld multiple times. This means that, in the Scala spirit, you are free to write your own code that imperatively determines for itself the validity of some of the potential alternatives rather than always using the amb and require methods to prune out invalid alternatives.

The stepUntilDone method implements the above algorithm to ensure that the called continuation completes. In order to know if the called continuation has suspended itself or completed execution, stepUntilDone needs to examine private data in the StandaloneGenerator class, so the cleanest solution is to add the stepUntilDone method to that class:

//Part of StandaloneGenerator.scala
    def stepUntilDone:Unit @suspendable = {
        //Use of var for saveStep is workaround for Scala bug #3501
        var saveStep:(Unit=>Unit) = null
        while (nextStep.isDefined) {
            saveStep = nextStep.get
            suspend     //sets nextStep to point here
            saveStep()
        }
    }

Note that the previously saved continuation from nextStep is saved in the local variable saveStep, which in turn is captured as part of the continuation then saved by the call to suspend. This provides a stacking mechanism that allows us to nest multiple calls to amb and properly manage the required backtracking. Since we are using local storage for this, we can have multiple instances of nondeterministic generators simultaneously suspended.

In both SICP and my implementation, the amb function does a depth-first search of the space of alternatives. This means it is not suitable for problems that includes multiple sets of alternatives where one or more sets are infinite. In fact, it really only does well on collections of sets that are small enough that the cross-product of all of the sets of choices can be fully enumerated, since the code choosing among alternatives makes its choice trivially and without any knowledge of which choices might be better than others. Also, the search space must not include any non-terminating branches, since eventually the algorithm would select that branch and get stuck.

As in SICP, the require method simply calls amb with no alternatives if its predicate is false, thus pruning the search tree at that point.

I did not attempt to implement any kind of side-effects backtracking such as capturing changes to global variables and undoing them after a branch finishes. Instead, regarding attempting to use code with side effects within a nondeterministic evaluation block, I offer this common suggestion: Don't Do That!

Examples

Using the AmbEval class we can easily code up the examples given in SICP. We start with the imports we use for all of the examples below:

import scala.collection.Iterator
import scala.util.continuations._
import net.jimmc.scoroutine._

Our examples will all be implemented as generator classes that extend the AmbEval class. We can see the results of each such computation by creating an instance of that class and printing out all of the values returned by the iterator. To simplify this, we define a little helper function to dump all of the results of an iterator:

def dump[T](gen:Iterator[T]) {
    for (x <- gen) println(x)
}

Here's how we can use this to print the results of evaluating the MultipleDwelling class given in the Goal section above:

dump(new MultipleDwelling)

output:

List((baker,3), (cooper,2), (fletcher,4), (miller,5), (smith,1))

Here are a few more examples, with their output given in a comment at the end of each code block.

A Pythagorean Triple Between

This problem is from SICP (exercise 4.35):

"implement a procedure that finds Pythagorean triples, i.e., triples of integers (i,j,k) between the given bounds such that i < j and i^2 + j^2 = k^2"

APythagoreanTripleBetween.scala

class APythagoreanTripleBetween(low:Int,high:Int) extends AmbEval[(Int,Int,Int)] {
    generate {
        val i = amb(low to high)
        val j = amb(i to high)
        val k = amb(j to high)
        require(i*i + j*j == k*k)
        yld((i,j,k))
    }
}

output from dump(new APythagoreanTripleBetween(1,20)):

(3,4,5)
(5,12,13)
(6,8,10)
(8,15,17)
(9,12,15)
(12,16,20)

Liars

This problem is from SICP (exercise 4.42):

Solve the following ``Liars'' puzzle (from Phillips 1934):
Five schoolgirls sat for an examination. Their parents -- so they thought -- showed an undue degree of interest in the result. They therefore agreed that, in writing home about the examination, each girl should make one true statement and one untrue one. The following are the relevant passages from their letters:

Betty: ``Kitty was second in the examination. I was only third.''
Ethel: ``You'll be glad to hear that I was on top. Joan was second.''
Joan: ``I was third, and poor old Ethel was bottom.''
Kitty: ``I came out second. Mary was only fourth.''
Mary: ``I was fourth. Top place was taken by Betty.''
What in fact was the order in which the five girls were placed?

Liars.scala

class Liars extends AmbEval[List[(String,Int)]] {
    def distinct(vals:List[Int]):Boolean = {
        vals.distinct.length == vals.length
    }
    generate {
        val betty = amb(List(1,2,3,4,5))
        val ethel = amb(List(1,2,3,4,5))
        val joan = amb(List(1,2,3,4,5))
        val kitty = amb(List(1,2,3,4,5))
        val mary = amb(List(1,2,3,4,5))
        require(distinct(List(betty,ethel,joan,kitty,mary)))
        require((kitty==2 && betty!=3) || (kitty!=2 && betty==3))
        require((ethel==1 && joan!=2) || (ethel!=1 && joan==2))
        require((joan==3 && ethel!=5) || (joan!=3 && ethel==5))
        require((kitty==2 && mary!=4) || (kitty!=2 && mary==4))
        require((mary==4 && betty!=1) || (mary!=4 && betty==1))
        yld(List(
            ("betty",betty),
            ("ethel",ethel),
            ("joan",joan),
            ("kitty",kitty),
            ("mary",mary)))
    }
}

output from dump(new Liars):

List((betty,3), (ethel,5), (joan,2), (kitty,1), (mary,4))

RosettaExample

This problem is from the rosettacode.org wiki page for Amb:

The example is using amb to choose four words from the following strings:

set 1: "the" "that" "a"

set 2: "frog" "elephant" "thing"

set 3: "walked" "treaded" "grows"

set 4: "slowly" "quickly"

It is a failure if the last character of word 1 is not equal to the first character of word 2, and similarly with word 2 and word 3, as well as word 3 and word 4. (the only successful sentence is "that thing grows slowly").

RosettaExample.scala

class RosettaExample extends AmbEval[List[String]] {
    generate {
        def joins(s1:String, s2:String) = s1.endsWith(s2.substring(0,1))
        val w1 = amb(List("the","that","a"))
        val w2 = amb(List("frog","elephant","thing"))
        val w3 = amb(List("walked","treaded","grows"))
        val w4 = amb(List("slowly","quickly"))
        require(joins(w1,w2))
        require(joins(w2,w3))
        require(joins(w3,w4))
        yld(List(w1,w2,w3,w4))
    }
}

output from dump(new RosettaExample):

List(that, thing, grows, slowly)

Other Implementations

If you poke around on the net you can find implementations of nondeterministic evaluators such as the amb evaluator. Some of these implementations suffer from one or more of three problems:

They use a for-comprehension or direct sequence iteration rather than an external amb evaluator. To see the difference, consider how the code would have to be modified in order to choose alternatives from each set of choices in random order rather than left-to-right. In an amb evaluator, this change can be made in one place.
They don't separate the application requirements from the mechanism that makes choices among alternatives. This can be seen by considering how a second example problem would be implemented in the same framework. It should be possible to implement the second problem by sharing code used in the implementation of the first problem but without either modifying or duplicating any code from the first problem.
They use a global variable to store a stack of continuations. This makes it impossible to run two independent nondeterministic evaluations at the same time.

Implementations of amb in various languages:

RosettaCode, implementations in many languages - but many of the implementations suffer from the problems listed above. In particular, the Scala implementation uses direct sequence iteration (in the form of a recursive tail operation on a list) and does not separate the application requirements (of first and last letters of adjacent words being the same) from the mechanism that makes choices among alternatives.
Nondeterministic evaluation in under 300 bytes of Python - Uses a global variable to store a stack of continuations.
Ruby - Uses a global variable to store a stack of continuations.
C#, Linq - Uses direct sequence iteration.
Scheme

Some interesting terms:

Angelic choice - always avoids choices that lead to nonterminating branches.
Demonic choice - always makes choices that lead to nonterminating branches.
Erratic choice - choices may or may not lead to nonterminating branches.

Standalone Generic Scala Generator

2010-09-08T20:33:00.000-07:00

A generic Scala generator class built directly on Scala's shift and reset operators.

In my previous post I showed a generic generator class built on top of my coroutines library. I commented in that post that I was taking the expedient approach of using my existing library, but that it would be possible to package all of the functionality into the Generator class.

I soon realized that it would in fact be relatively easy to do that packaging, and that the resulting relatively simple class would probably make a good vehicle for demonstrating the usefulness of Scala's delimited continuations. Thus I give you the StandaloneGenerator class:

package net.jimmc.scoroutine

import scala.collection.Iterator
import scala.util.continuations._

class StandaloneGenerator[T] extends Iterator[T] {
    private var nextValue:Option[T] = None
    private var nextStep:Option[Unit=>Unit] = None

    /** Subclass calls this method to generate values.
     * @param body The code for your generator.
     */
    protected def generate(body: => Unit @suspendable) {
        reset {
            suspend
            body
        }
    }

    /** Yield the next generated value.
     * Call this code from your generator to deliver the next value.
     */
    protected def yld(x:T):Unit @suspendable = {
        nextValue = Some(x)
        suspend
    }

    /** Retrieve the next generated value.
     * Call this from your main code.
     */
    def next:T = {
        step
        nextValue match {
            case None => throw new NoSuchElementException("next on empty generator")
                    //make it similar to the equivalent Iterator exception
            case Some(x) => nextValue = None; x
        }
    }

    /** True if there is another value to retrieve.
     * Call this from your main code.
     */
    def hasNext:Boolean = {
        step
        nextValue.isDefined
    }

    /** Save our continuation to resume later. */
    private def suspend:Unit @suspendable = {
        shift { k:(Unit=>Unit) =>
            nextStep = Some(k)
        }
    }

    /** If we have a next step but we don't have a value queued up,
     * run the generator until it calls yld or completes. */
    private def step = {
        if (nextValue.isEmpty) nextStep foreach { nextStep = None; _() }
    }
}

The StandaloneGenerator class is a plug-compatible replacement for the Generator class described in my previous post, as long as the derived generator does not use fancy scheduling as in the Primes Generator example. So, for example, you could take the Integers Generator example from that post, replace the two occurences of Generator with StandaloneGenerator, and everything would work the same way.

We have two variables: nextValue is our one-element queue where we store the next value to be returned by the generator, and nextStep is our "scheduler queue" where we store our continuation each time we suspend the generator to return a value. Both of these variables are of type Option so that we can tell when they hold a value.

Control is managed by the two functions suspend and step. The suspend method has a shift block that could not be much simpler: all it does is store the passed-in continuation in the nextStep variable. Since the body of a shift block is always the last thing executed within the scope of the CPS code (delimited either by the enclosing reset block or an explicitly invoked continuation), the fact that suspend does not execute its continuation means that after suspend does its thing, control returns to the point just past the enclosing reset, or to the next statement after the explicit continuation call.

I considered calling the step method resume instead, to make it clear that it was the complement to suspend, but from the point of view of the code calling step, by the time control returns to the point after the call to step, the generator code has already been suspended again: it has completed running one step, which is from one yld call to the next.

The step function executes our continuation if we have one, but only if we don't already have a value in nextValue. Using foreach on an Option is a neat way to execute a block of code only if the Option has a value (i.e. is not None). In this case, since the contents of nextStep (if it has any) is a function, the placeholder variable _ gets set to the continuation and the code fragment _() is what actually executes the continuation. Here are two other ways this function could be implemented that do the same thing:

    private def step1 = {
        if (nextValue.isEmpty) nextStep match {
            case None => //do nothing
            case Some(p) => nextStep = None; p()
        }
    }

    private def step2 = {
        if (nextValue.isEmpty && nextStep.isDefined) {
            val p = nextStep.get; nextStep = None; p()
        }
    }

Let's walk through this and see how it works (assuming the generator generates at least one value):

The main code instantiates a generator, which passes its generator body to the generate function, which calls suspend, which saves that body in nextStep without executing it.
The main code calls hasNext, which calls step, which runs the continuation. This starts the generator body code running, which runs until it calls yld with the first value. That first value is stored in nextValue and the generator code is suspended, with the continuation stored in nextStep. Since we now have a value stored in nextValue, hasNext returns true.
The main code calls next. Since we have a value in nextValue, the call to step does nothing (it is only there in case the caller calls next without first calling hasNext). The value in nextValue is returned, and that variable is cleared (set to None).
Each time the main code calls hasNext and it calls step, the continuation stored in nextStep is executed, the generator code calls yld with the next value, that value is stored into nextValue, the continuation is stored in nextStep, and the generator is suspended, and hasNext returns true.
Eventually (for a finite generator) there is a call to step where the generator finishes execution without calling yld. When this happens, no values are stored in either nextValue or nextStep. Since there is no value in nextValue, hasNext returns false. Since there is also no value in nextStep, further calls to step do nothing, and hasNext will continue to return false.

I dare say this might be one of the simplest realistic examples of the use of Scala's reset and shift operators that you will find. Two variables, six functions each not more than four lines of body code, 16 lines of function body code in total, 35 lines of code altogether.

Scala Generators

2010-09-07T20:53:00.000-07:00

An implementation of generators on top of Scala's delimited continuations.

In my previous post I described a library that supports coroutines on top of Scala's delimited continuations capability. In this post I show how you can easily create generators on top of that coroutine library (net.jimmc.scoroutine). This is a second example of the kind of interesting construct that can be built on top of Scala's delimited continuations.

As with my previous post on coroutines, you don't need to understand reset and shift if you just want to use the Generator class shown here to write and use your own generators. But, as with coroutines, you should have a basic understanding of CPS code and its restrictions when writing generators.

Generators
Integers Generator
Primes Generator
Same Fringe
More Possibilities

Generators

A generator is a routine that produces values like an iterator but is structured as a function. The generated values are returned by calling a special function, typically called yield, with each value that is generated. In our case, since yield is a reserved word in Scala, we will use yld instead.

Generators and coroutines are closely related. Depending on the implementation, generators and coroutines may be almost the same thing or fairly different, but in any case, if you have either one, you can implement the other one on top of it. Since we already have coroutines in the net.jimmc.scoroutine library described in my previous post, we will implement generators on top of coroutines using that library.

You can think of this approach as using the Producer-Consumer pattern, where we set up a generator as the producer and we allow the main code to act as the consumer. We create a generic Generator class that does the following:

Creates a CoScheduler that we use to control the generator.
Creates a CoQueue buffer into which we will place the generated values.
Provides convenience functions yld (in place of the reserved word yield) and generate.
Provides next and hasNext functions for the consuming code to call from a non-CPS context, and so that a Generator can be used as an Iterator.

This is all simple and straightforward. Here is the code for Generator:

package net.jimmc.scoroutine

import scala.collection.Iterator
import scala.util.continuations._

/** Generic generator class.
 */
class Generator[T] extends Iterator[T] {
    val sched = new DefaultCoScheduler
    val buf = new CoQueue[T](sched,1)

    /** Subclass calls this method to generate values.
     * @param body The code for your generator.
     */
    def generate(body: => Unit @suspendable) {
        sched.addRoutine("gen") { body }
        sched.run
    }

    /** Yield the next generated value.
     * Call this code from your generator to deliver the next value.
     */
    protected def yld(x:T):Unit @suspendable = {
        buf.blockingEnqueue(x)
    }

    /** Retrieve the next generated value.
     * Call this from your main code.
     */
    def next:T = {
        sched.run
        buf.dequeue
    }

    /** True if there is another value to retrieve.
     * Call this from your main code.
     */
    def hasNext:Boolean = {
        sched.run
        !buf.dequeueBlocker.isBlocked
    }
}

We are not concerning ourselves with performance here, so we are simply using the available DefaultCoScheduler as our scheduler. As a future optimization, we could develop a scheduler optimized for a single coroutine and use that as our scheduler for simple generators that fit that criterion. We could go further and use neither a scheduler nor CoQueue, packaging all of the functionality directly into the Generator class; but we are using the more expedient approach of using those two pieces, since we already have them and are familiar with their use from our experience with coroutines.

Integers Generator

Here is how we would use our generic Generator class to create a generator that will generate integers up to a specified maximum value:

import net.jimmc.scoroutine.Generator

class IntGen(max:Int) extends Generator[Int] {
    generate {
        var x = 1
        while (x<=max) {
            yld(x)
            x = x + 1
        }
    }
}

The one catch to remember here is that the body of the generate call is CPS code, so as with the body of a coroutine, there are some restrictions on what control constructs we can use. Thus we use a while loop with a var rather than a for loop, since the latter does not yet work with the continuations compiler plugin.

Given the above generator class, here is a simple GenInts object with a main function that creates an instance of that generator, then calls it to print out its values:

object GenInts {
    def main(args:Array[String]) = {
        val gen = new IntGen(4)
        for (i <- gen)
            println(i)
    }
}

Alternatively, we could replace the for loop with direct calls to hasNext and next:

object GenInts {
    def main(args:Array[String]) = {
        val gen = new IntGen(4)
        while (gen.hasNext)
            println(gen.next)
    }
}

Primes Generator

It is possible to use shift and reset directly to code up a generator, but because our coroutine library implements a scheduler to which new coroutines can be added at any time, this gives you the ability to create generators that include dynamic filter pipelines.

The example I use for this is the Sieve of Eratosthenes, a method of calculating primes in which, each time a prime is found, it is added to a list of prime divisors that are used for testing each new candidate. In this GenPrimes example, I create a new filter for each prime and add it to the pipeline. You can do this much more efficiently in Scala using a Stream, but this example illustrates the technique of dynamically building a pipeline within a generator.

import scala.util.continuations._

import net.jimmc.scoroutine.CoQueue
import net.jimmc.scoroutine.Generator

object GenPrimes {
    def main(args:Array[String]) = {
        val gen = new PrimeGen()
        for (i <- gen) {
            println("Prime: "+i)
        }
    }
}

class PrimeGen extends Generator[Int] {
    val bufSize = 1
    val out1 = new CoQueue[Int](sched,bufSize)

    sched.addRoutine("prime2")(nextPrime(2,out1))
    generate {
        def gen(n:Int):Unit @suspendable = {
            out1.blockingEnqueue(n)
            gen(n+1)
        }
        gen(2)
    }

    def nextPrime(p:Int, in:CoQueue[Int]):Unit @suspendable = {
        var out:Option[CoQueue[Int]] = None
        yld(p)
        def sieve():Unit @suspendable = {
            val n = in.blockingDequeue()
            if ((n%p)!=0) {
                if (!out.isDefined) {
                    out = Some(new CoQueue[Int](sched,bufSize))
                    val rName = "prime"+n
                    sched.addRoutine(rName)(nextPrime(n,out.get))
                }
                out.get.blockingEnqueue(n)
            } else {
                in.dequeueBlocker.waitUntilNotBlocked
            }
            sieve()
        }
        sieve()
    }
}

This example starts by setting up two coroutines: the addRoutine call sets up the first filter in the pipeline, which reads values from the out1 queue and filters our all numbers divisible by 2. The generator call sets up the other initial coroutine, which generates every integer and feeds it into the first filter in the pipeline. We start off this counting generator with the first prime number, 2.

The nextPrime function is called each time we see a new prime. It starts by outputting its prime parameter value p as a value of the GenPrimes generator. It then goes into a loop reading its input buffer and looking for values which are not divisible by its prime number. The first time it finds one (when out is not yet defined) it registers (with a call to addRoutine) a new coroutine based on a new instance of nextPrime that uses our output as its input. It then passes each candidate prime along to that next filter in the sieve pipeline.

You can tell this is CPS code because of the suspendable annotations, which is a cue to realizing that the code might not behave quite as you think. For example, the gen function within the body of the generate call is recursive, so you might think it would cause a stack overflow. But since we are in a CPS function and the call to blockingEnqueue is a call to a CPS function, the recursive call to gen is turned into a continuation and executed later from the scheduler, so it is in fact not recursive. Likewise the recursive call to sieve is not really recursive for the same reason.

Another CPS detail is the call to waitUntilNotBlocked. It would seem to be functionally unnecessary, since the first thing in the sieve function is a call to blockingDequeue. However, this is the same attempt to avoid blocking as discussed in my previous post; without this call our code will not work.

Same Fringe

The SameFringe problem has been called the "killer application" for coroutines. Given two trees, they have the same fringe if the leaves of the two trees, read from left to right, are the same.

With coroutines, or in this case generators, the simple solution to this problem is to create a generator that takes a tree and returns the sequence of leaves of that tree, then compare the outputs of two of those generators on the two trees to be compared.

We start with a simple tree definition:

sealed abstract class Tree[T]
case class Branch[T](left:Tree[T], right:Tree[T]) extends Tree[T]
case class Leaf[T](x:T) extends Tree[T]

Given this tree definition, we write a generator that walks a tree and yields all of the leaves:

import scala.util.continuations._
import net.jimmc.scoroutine.Generator

class TreeFringe[T](tree:Tree[T]) extends Generator[T] {
    generate {
        def walk(t:Tree[T]):Unit @suspendable = {
            t match {
                case Leaf(x) => yld(x)
                case Branch(left,right) => walk(left); walk(right)
            }
        }
        walk(tree)
    }
}

Since our generators implement the Iterator trait, we can compare two generators as two iterators with this little piece of code, making the assumption that the tree leaf values are never null:

    def sameFringe[T](tree1:Tree[T], tree2:Tree[T]):Boolean = {
        !((new TreeFringe(tree1)).zipAll(new TreeFringe(tree2),null,null).
            exists(p=>p._1!=p._2))
    }

Alternatively, we could use this more verbose version:

    def sameFringe[T](tree1:Tree[T], tree2:Tree[T]):Boolean = {
        val fringe1 = new TreeFringe(tree1)
        val fringe2 = new TreeFringe(tree2)
        while(fringe1.hasNext && fringe2.hasNext) {
            if (fringe1.next != fringe2.next)
                return false;
        }
        !(fringe1.hasNext || fringe2.hasNext)
    }

We add a SameFringe object with a main method that creates some test trees, prints out the leaves of each tree using our generator, then calls our sameFringe method to check for equality.

object SameFringe {
    def main(args:Array[String]) = {
        val t1 = Branch(Branch(Leaf(1),Leaf(2)),Leaf(3))
        val t2 = Branch(Leaf(1),Branch(Leaf(2),Leaf(3)))
        val t3 = Branch(Leaf(1),Branch(Leaf(2),Leaf(4)))
        println("t1:"); for (x <- (new TreeFringe(t1))) println(x)
        println("t2:"); for (x <- (new TreeFringe(t2))) println(x)
        println("t3:"); for (x <- (new TreeFringe(t3))) println(x)
        println("sameFringe(t1,t2)="+sameFringe(t1,t2))
        println("sameFringe(t1,t3)="+sameFringe(t1,t3))
    }
    //include the sameFringe method in this object
}

More Possibilities

Some other possible uses for generators or coroutines:

Pipelines: A sequence of tasks can operate on a stream of data, with each task reading data from an input queue and writing to an output queue which is the input queue of the next task in the sequence.
Fan-out: A single producer with multiple consumers can be implemented by using a fan-out coroutine that reads from its input queue and writes the same data to multiple output queues, each of which is the input queue to one of the multiple consumers.
Fan-in: Multiple producers can use a single shared output queue so that the coroutine using that queue as its input queue receives data from multiple sources. If you stick with a single-thread scheduler, you don't have to worry about synchronization or other concurrent access issues on the shared queue. By combining Pipelines, Fan-out and Fan-in, we can create arbitrary networks of communicating coroutines.
State machines: For any situation in which a task has to maintain state based on one or more inputs, a coroutine or generator can be used to allow some of that state to be stored as the location of current execution in the code, which often makes the code simpler to write and maintain.
Parsers: A parser is a typical example of a producer that reads an input stream and maintains state. As the parser collects input characters (which could be provided by another coroutine in a pipeline) and resolves them into tokens, it writes them to its output queue where the tokens are available to the routine handling the next level of analysis.

Scala Coroutines

2010-09-06T14:38:00.000-07:00

An implementation of coroutines on top of Scala's delimited continuations.

In my previous post I said that delimited continuations could be used to create interesting control constructs. In this post I give examples of one such construct: coroutines.

I describe the implementation of a library to make it easier to write coroutines, and I give an example that is built on that library. If you want to go straight to the example, see the section Producer-Consumer.

Like my previous post on delimited continuations, this is a long post. However, though long, it should be much easier going than that post. You don't need to read and understand that post in order to understand this post, but it will help in two places:

In the discussion of the CoScheduler API and implementation, an understanding of reset and shift is required.
You need to understand at some level about CPS code and its restrictions when writing coroutines or using the CPS-only methods in CoQueue and Blocker.

Coroutines
Why Use Coroutines
Building a Coroutine Library
Blocker
CoQueue
An Attempt to Avoid Blocking
CoScheduler API
CoScheduler Implementation
DefaultCoScheduler
Other Schedulers
Producer-Consumer
Resources

Coroutines

The Wikipdeia coroutines page says coroutines are a generalization of subroutines: whereas a subroutine starts at the beginning every time it is called, a coroutine starts at the beginning the first time it is called, but can start at any other point on successive calls. Generally this means that on successive calls, it continues running from the point where it most recently returned.

Instead of using a return statement, coroutines typically use a yield statement. A yield statement indicates that the routine is done executing for now, and will resume execution following the yield statement the next time it is called.

In the classic definition of coroutines, the yield statement indicates which coroutine is to be run next. With two coroutines, each always yields to the other; with more than two, a coroutine might have code to determine which other coroutine to yield to.

Unfortunately for coroutines, yield is already a keyword in Scala, so we can't use it for our purposes. We can either pick a slightly different word such as yld or yieldTo, or we can just use a different term altogether.

The classic example of the use of coroutines is a pair of routines, one of which (the producer) generates data and one of which (the consumer) consumes data. These two routines are connected by a queue; the producer puts data into the queue and the consumer takes data out of the queue.

This same producer-consumer pair is also a typical example of multi-thread code. Ted Neward uses this producer-consumer example in his blog post describing the concurrency benefits of using Scala.

In the multi-thread producer-consumer example, the producer thread runs and places data into the queue until the queue is full, at which point that thread stops running until the queue empties out enough for it to add more data. Meanwhile the consumer thread runs and takes data out of the queue until the queue is empty, at which point that thread stop running until the queue contains more data. If the host on which the multi-thread application is running contains more than one processor, both of these threads might be running at the same time.

I like to think of coroutines as being like multi-thread code, only without multiple threads. The coroutine version of the producer-consumer example works essentially the same as the multi-thread version, except that only one of the two is ever running at one point in time. The producer runs and places data into the queue until it is full, at which point it pauses and the consumer starts running. The consumer takes data out of the queue until it is empty, at which point it pauses and the producer starts running again.

In both the multi-thread and the coroutine version of this example, there is some state that is saved while each routine is paused waiting for the queue to fill or empty. In the multi-thread example, that state is saved in the thread. In our coroutine example, we use a different mechanism to save that state: a delimited continuation.

Why Use Coroutines

If coroutines are like multi-thread code, why use them and have to deal with continuations rather than just using threads? Here are some possible reasons:

With the default scheduler that runs everything in one thread, you don't need to worry about concurrency issues such as multiple concurrent access to shared state.
You can create your own scheduler to control when to run each of your coroutines. If you want that scheduler to use a thread pool and run coroutines concurrently, you can do that (assuming you then deal with concurrency issues in your coroutines).
An application can handle more suspended continuations than it can suspended threads (for example, see slide 19 of Phillip Haller's presentation on Actors, where he says an app can handle up to 5,000 threads, but up to 1,200,000 actors).

Building a Coroutine Library

It is possible to write coroutines directly in Scala code using reset and shift, but dealing with delimited continuations can be tricky, so I wanted to isolate all of that code into a reusable library that would make it easier to write coroutines as well as allow encapsulating more sophisticated capabilities within the library. The package name I selected for this library is net.jimmc.scoroutine. The source code is available on github.

I started with a change that makes these coroutines look less like coroutines and more like the multi-thread model: rather than have a coroutine specify what other coroutine is to be run, I wanted to be able to specify only that the coroutine is ready to give up control. Essentially, rather than yielding to another coroutine, I always yield to a scheduler, and the scheduler selects and then yields to the next coroutine. Given such a scheduler (described below), we can create a few simple constructs on which to build our coroutine API.

Blocker

In the typical producer-consumer example, there is an explicit check to see if the routine is blocked, and if so, then a call to yield is made. I wanted something more generic, so I created an abstract trait Blocker to represent the condition that a routine could be blocked by something:

package net.jimmc.scoroutine

trait Blocker {
    def isBlocked: Boolean
}

The implementations of this for the producer and consumer are straightforward: for the producer, isBlocked returns true when the queue is full; for the consumer, isBlocked returns true when the queue is empty.

Given the isBlocked method, the typical coroutine always includes a code fragment that looks something like this:

while (isBlocked)
    yield control

Since we will always be yielding control to the scheduler, we can encapsulate this into a more convenient method, which I have called waitUntilNotBlocked. I added this function to my Blocker trait, and delegated it to a scheduler of type CoScheduler:

package net.jimmc.scoroutine

trait Blocker {
    val scheduler: CoScheduler  //class must override to provide instance
    def isBlocked: Boolean

    def waitUntilNotBlocked:Unit = {
        scheduler.waitUntilNotBlocked(this)
    }
}

We pass this to the scheduler so that it can call our isBlocked method and continue our execution only when isBlocked returns false.

There is one more detail to be added to Blocker, but it is an important one. I stated above that this implementation is built on top of delimited continuations. When we call waitUntilNotBlocked and we are blocked, we want the coroutine library to wait until we are no longer blocked and then continue execution of our routine. The coroutine library will be using delimited continuations to do this, and since our routine might be suspended, the signature for the waitUntilNotBlocked method must include the suspendable annotation. We add that annotation along with a suitable import statement to get our final version of Blocker:

package net.jimmc.scoroutine

import scala.util.continuations._

trait Blocker {
    val scheduler: CoScheduler  //class must override to provide instance
    def isBlocked: Boolean

    def waitUntilNotBlocked:Unit @suspendable = {
        scheduler.waitUntilNotBlocked(this)
    }
}

CoQueue

Once we have Blocker, it is easy to compose a blocking version of the standard Queue class (where by "blocking" I mean that the coroutine will be suspended until the specified Blocker is no longer blocked). We want a version of the Queue.enqueue function that blocks when the queue is full, and a version of the Queue.dequeue function that blocks when the queue is empty. We create a thin wrapper around the Queue class, which we call CoQueue, to implement our blocking methods for use with our coroutines. For each of our two blocking conditions, we create an instance of Blocker with those conditions as each of their isBlocked functions, and we use those Blocker instances to create our blockingEnqueue and blockingDequeue methods.

Because the blockingEnqueue and blockingDequeue methods might block, they must be annotated as suspendable, which means they can only be called from within CPS code. Here is our entire CoQueue class:

package net.jimmc.scoroutine

import scala.util.continuations._
import scala.collection.mutable.Queue

class CoQueue[A](val scheduler:CoScheduler, val waitSize:Int)
        extends Queue[A] { coqueue =>

    val enqueueBlocker = new Blocker() {
        val scheduler = coqueue.scheduler
        def isBlocked() = length >= waitSize
    }

    val dequeueBlocker = new Blocker() {
        val scheduler = coqueue.scheduler
        def isBlocked() = isEmpty
    }

    def blockingEnqueue(x:A):Unit @suspendable = {
        enqueueBlocker.waitUntilNotBlocked
        enqueue(x)
    }

    def blockingDequeue():A @suspendable = {
        dequeueBlocker.waitUntilNotBlocked
        dequeue
    }
}

An Attempt to Avoid Blocking

You might wonder if we could implement blockingEnqueue as follows so as to avoid the call to the scheduler's waitUntilNotBlocked method:

//this won't compile
    def blockingEnqueue(x:A):Unit @suspendable = {
        if (enqueueBlocker.isBlocked)
            enqueueBlocker.waitUntilNotBlocked
        enqueue(x)
    }

However, the compiler gives this error message:

CoQueue.scala:22: error: type mismatch;
 found   : Unit
 required: Unit @scala.util.continuations.cpsParam[Unit,Unit]
        if (enqueueBlocker.isBlocked)
        ^

Syntactically, the problem is that the above one-sided if statement is equivalent to

        if (enqueueBlocker.isBlocked)
            enqueueBlocker.waitUntilNotBlocked
        else
            ()

The type of () is Unit, but the type of waitUntilNotBlocked is Unit @suspendable, so there is a type mismatch.

You might think we could use some trickery such as this:

//compiles, but won't run properly
    def unitSuspendable:Unit @suspendable = ()

    def blockingEnqueue(x:A):Unit @suspendable = {
        if (enqueueBlocker.isBlocked)
            enqueueBlocker.waitUntilNotBlocked
        else
            unitSuspendable
        enqueue(x)
    }

This will compile without errors, but will not work properly. The problem is that we are trying to define one code path that is CPS (through waitUntilNotBlocked) and one path that is not (through unitSuspendable). The CPS compiler plugin transforms the code to use continuations, which, as you might recall from the discussion in my previous post, packages the rest of the function up in a continuation and passes it along to the called function. But the unitSuspendable expression does nothing with that continuation; it neither executes it nor saves it for later execution. Thus as soon as this code path is taken, the continuation - which represents the remainder of the execution of the entire delimited continuation, including the caller of this function - is dropped, and the whole delimited continuation is done.

CoScheduler API

The scheduler is the piece of the coroutine library that saves the continuations for all of the participating coroutines and determines when to execute those continuations. By design, all of the tricky stuff is encapsulated in this class. I have divided the discussion of the scheduler into two section: this first section discusses at a high level the tasks for which the schedule must take responsibility, and defines an API to perform those tasks. The following section describes the implementation of that API. If you don't want to get too far into the delimited continuation stuff, you can read just this section and skip the implementation section.

I started with the requirements that it should be possible to write a scheduler that:

uses one thread for all participating coroutines, or uses a thread pool so that multiple coroutines can run at once;
uses a simple algorithm to select which coroutine to run next, such as round-robin, or a more complex algorithm, such as a priority-based approach;
can be instantiated multiple times so that different collections of coroutines can be managed with different schedulers.

In order to allow all of the above, the scheduler API is defined in a trait, which I call CoScheduler. CoScheduler needs to define three basic functions:

Register a coroutine. I chose to do this with a method that accepts a block of code which is the coroutine body. Since the coroutine body might be suspended, the signature for that argument must include the suspendable annotation. I call this method addRoutine. To improve tracing, I also pass in a name argument that can be used to identify that coroutine.
Wait until a coroutine is no longer blocked. This is the method to which Blocker.waitUntilNotBlocked will delegate. It is also called waitUntilNotBlocked, and takes an argument which is the Blocker whose isBlocked method will be used to make that determination. Since this method will be called from the coroutine body or a method called from that body, it must be marked as suspendable.
Run a coroutine. There are two flavors of this: run a single step, returning as soon as one coroutine has run and has returned control to the scheduler, or run as many steps as possible, until there are no more unblocked coroutines to run. I call these two methods runNextUnblockedRoutine and runUntilBlockedOrDone, respectively. Since these methods are meant to be called from the main application, not from within a coroutine, they are not marked as suspendable.

When one of the run methods returns, we would like to know whether there are some blocked coroutines, all of our coroutines have completed, or we don't know which because we only ran one routine. In order to return this indication, we define a sealed class RunStatus with three case objects representing these three possibilities.

The API of our CoScheduler trait thus looks like this:

package net.jimmc.scoroutine

sealed abstract class RunStatus
case object RanOneRoutine extends RunStatus
case object SomeRoutinesBlocked extends RunStatus
case object AllRoutinesDone extends RunStatus

trait CoScheduler {
    def addRoutine(name:String)(body: => Unit @suspendable)

    def waitUntilNotBlocked(b:Blocker):Unit @suspendable

    def runNextUnblockedRoutine():RunStatus
    def runUntilBlockedOrDone():RunStatus
}

If you are interested in using the scoroutine library to write coroutines, but you don't care how it works internally, then you can skip the next few sections and pick up again at Producer-Consumer.

CoScheduler Implementation

The reason for implementing CoScheduler as a trait rather than a class is to make it easier to create multiple implementations. On the other hand, there is some functionality which is likely to be the same in all implementations, and since Scala allows us to include code in traits, we will add the implementation of those methods to the trait.

For example, given the runNextUnblockedRoutine method, the runUntilBlockedOrDone method is a simple loop that calls runNextUnblockedRoutine until it does not run something.

Likewise, if we internally create an instance of a Blocker in addRoutine, we can implement both that method and waitUntilNotBlocked on top of a single method that stores a continuation, which we will call setRoutineContinuation.

This means we can create a concrete scheduler class that extends the CoScheduler trait by implementing just two functions: runNextUnblockedRoutine and setRoutineContinuation.

Below is what our implementation of CoScheduler looks like after making the above changes.

package net.jimmc.scoroutine

import scala.util.continuations._

sealed class RunStatus
case object RanOneRoutine extends RunStatus
case object SomeRoutinesBlocked extends RunStatus
case object AllRoutinesDone extends RunStatus

trait CoScheduler { cosched =>
    private[scoroutine] def setRoutineContinuation(
            b:Blocker, cont:Option[Unit=>Unit]):Unit
    def runNextUnblockedRoutine():RunStatus

    /* We use a class rather than an object because we are using the
     * instance as a key to find more info about the associated routine. */
    class BlockerNever() extends Blocker {
        val scheduler = cosched
        val isBlocked = false
    }

    def addRoutine(name:String)(body: => Unit @suspendable) {
        reset {
            val blocker = new BlockerNever()
            waitUntilNotBlocked(blocker)
            body
        }
    }

    def runUntilBlockedOrDone():RunStatus = {
        var status:RunStatus = RanOneRoutine
        while (status==RanOneRoutine) {
            status = runNextUnblockedRoutine()
        }
        status
    }

    def waitUntilNotBlocked(b:Blocker):Unit @suspendable = {
        shift( (cont: Unit=>Unit) => {
            setRoutineContinuation(b,Some(cont))
        })
    }
}

As we already knew based on the existence of the suspendable annotation, there are two methods that deal with CPS code: addRoutine and waitUntilNotBlocked.

Before examining these functions, it is worth reviewing one point about how reset and shift work. When there is a shift call within a reset block, the CPS compiler plugin transforms the code within the reset block such that the code after the shift block is passed as a continuation argument to the shift block. The code within the shift block is thus the last code to be executed within the reset block. The code that is within the reset but outside of the shift is CPS code, but the code within the shift block is not CPS code. In other words, once within a reset block, we are executing CPS code until we get into the shift block, at which point we are no longer executing CPS code. The continuation contains CPS code; if we call the continuation from within our shift code, we transition from non-CPS code into CPS code. But if we happen to save the continuation, we can directly execute it later from any non-CPS code, and that will likewise transition us into the CPS code of the continuation.

The waitUntilNotBlocked function takes as an argument the Blocker that will tell us when the calling coroutine is allowed to run again, and, along with the continuation passed in to the shift, passes it to setRoutineContinuation. That function saves the continuation and its associated Blocker and returns without executing the continuation. Because we are returning without executing the continuation, control returns to the first statement past the end of the enclosing reset block, or, if the current code/continuation (i.e. the CPS code containing the call to waitUntilNotBlocked) was directly executed from non-CPS code, to the statement after the point at which that continuation was executed.

The addRoutine function creates a Blocker that never blocks, then calls waitUntilNotBlocked with that blocker. Since waitUntilNotBlocked is a CPS function (marked with the suspendable annotation), the remainder of the code in the reset block is turned into a continuation and passed along to waitUntilNotBlocked. When that method calls shift, the continuation we passed to waitUntilNotBlocked - i.e. our call to body - is part of the continuation passed to the shift. Thus when that method saves the continuation, that saved continuation includes the call to the coroutine body. Since the continuation is not immediately executed, control returns to the end of the reset block, and we return from addRoutine with our coroutine sitting in the scheduler ready to start running.

DefaultCoScheduler

Given the CoScheduler trait described above, the only functionality that remains for our concrete class is to implement a mechanism for storing continuations and selecting the next one to run. The DefaultCoScheduler implements a simple round-robin scheduling mechanism, selecting the next runnable continuation each time it is invoked. Note that this implementation has been designed to be simple, but is not very efficient. In particular, it will not exhibit good performance when there are a large number of coroutines of which only a few are runnable at any time.

We define a case class BlockerInfo to tie together a Blocker and its associated continuation, an ArrayBuffer to store an ordered set of those, and a map to find one given a Blocker.

The setRoutineContinuation function adds a new BlockerInfo to our array if we don't already have one for the given Blocker, or updates the existing one if we do.

The runNextUnblockedRoutine function does a simple linear scan through the array of items, starting just past where we left off the last time, looking for the first unblocked continuation and running it. If there were no runnable continuations, we return a status code without running anything.

package net.jimmc.scoroutine

import scala.collection.mutable.ArrayBuffer
import scala.collection.mutable.HashMap

class DefaultCoScheduler extends CoScheduler {
    val blockerIndexMap = new HashMap[Blocker,Int]
    case class BlockerInfo(val blocker:Blocker, index:Int,
            var cont:Option[Unit=>Unit])
    val blockerList = new ArrayBuffer[BlockerInfo]
    var nextIndex = 0

    private[scoroutine] def setRoutineContinuation(
            b:Blocker,cont:Option[Unit=>Unit]) {
        if (blockerIndexMap.get(b).isEmpty) {
            val nextIndex = blockerIndexMap.size
            blockerIndexMap.put(b,nextIndex)
            blockerList += BlockerInfo(b, nextIndex, cont)
        } else {
            val n = blockerIndexMap(b)
            blockerList(n).cont = cont
        }
    }

    def runNextUnblockedRoutine():RunStatus = {
        var blockedCount = 0
        for (i <- 0 until blockerList.size) {
            val index = (nextIndex + i) % blockerList.size
            val bInfo = blockerList(index)
            if (bInfo.cont.isDefined && bInfo.blocker.isBlocked) {
                blockedCount += 1
            }
            if (bInfo.cont.isDefined && !bInfo.blocker.isBlocked) {
                nextIndex = index + 1
                val nextCont = bInfo.cont
                bInfo.cont = None
                nextCont.get()          //run the continuation
                return RanOneRoutine
            }
        }
        if (blockedCount > 0) {
            SomeRoutinesBlocked
        } else {
            AllRoutinesDone
        }
    }
}

Note that DefaultCoScheduler does not import the continuations package. It does not use reset, shift, or any of the CPS annotations such as suspendable. This is because none of this code is CPS code. runNextUnblockedRoutine is called from non-CPS code, and although setRoutineContinuation is called from CPS code, it does not itself call any CPS functions nor does it use shift, so it does not need to be declared as CPS code.

Other Schedulers

DefaultCoScheduler implements a basic scheduling algorithm. It is intended for use with small numbers of coroutines and has not been optimized. Other schedulers could be written that are optimized for other situations, such as large numbers of coroutines, coroutines with different priorities, or "stickiness" so that a running coroutine continues to run until it is blocked before the next coroutine runs. Since the code that creates the coroutines starts by creating the scheduler that controls those coroutines, it would be simple to create a scheduler other than DefaultCoScheduler for use with a particular set of coroutines.

Producer-Consumer

Let's see how the Producer-Consumer example (ProdConTest) looks using the scoroutine library:

import scala.util.continuations._

import net.jimmc.scoroutine.DefaultCoScheduler
import net.jimmc.scoroutine.CoQueue

object ProdConTest {
    def main(args:Array[String]) = {
        val prodcon = new ProduceAndConsume()
        prodcon.run
    }
}

class ProdCon() {
    val sched = new DefaultCoScheduler
    val buf = new CoQueue[Int](sched,2)

    def run() {
        sched.addRoutine("producer"){
            var i = 0
            while (i < 4) {
                buf.blockingEnqueue(i)
            }
        }
        sched.addRoutine("consumer"){
            val total = buf.blockingDequeue +
                    buf.blockingDequeue + buf.blockingDequeue
            println("consume total is "+total)
        }
        sched.runUntilBlockedOrDone
    }
}

After the imports and a simple main method for testing, we have the ProdCon class with the actual producer-consumer definition.

We start by setting up two objects: the scheduler that will control our two coroutines, and a queue for communication between them. We then register two coroutines with our scheduler, one for the producer and one for the consumer, and we call sched.runUntilBlockedOrDone to run the coroutines until there is nothing runnable left on that scheduler.

You can't tell in this example, but the code blocks being passed to addRoutine are CPS code, the same as the body of a reset block. If you decide to refactor this code and push the blockingEnqueue or blockingDequeue calls down into a subroutine, that subroutine will have to be marked with the suspendable annotation. Also, because coroutine bodies are CPS code, there are there are some restrictions on what control constructs can be used. You can see what this looks like in the ProdConTestWithSubs source code in the scoroutine examples.

I will give some more examples in my next post, a followup about Generators.

Resources

My original blog post on Delimited Continuations, which includes its own Resources section.
The net.jimmc.scoroutine library on github.
python-multitask, a similar framework for Python.

Delimited Continuations

2010-08-08T14:08:00.000-07:00

Scala's delimited continuations, introduced in version 2.8, can be used to implement all sorts of interesting control constructs.

This is a very long blog post. It took me quite a while to get my head around Scala's reset and shift operators. To help others hopefully avoid the stumbling blocks I encountered, I have tried here to start with the basics and build up from there in some detail. If you want a shorter explanation, see the Resources section at the end of this post for pointers to some other blog entries that are more succinct.

Mechanics
Continuation Passing Style (CPS)
Nested CPS
Full versus Delimited Continuations
Uses
CPS With Return
Reset and Shift
Annotations
Nested Shift
Control Construct Restrictions
Advice
Resources

Mechanics

In order to use Scala's delimited continuations, you must use version 2.8, and you must use the continuations (or CPS) compiler plugin. You do this by specifying a command line option when running both the compiler and the runtime:

$ scalac -P:continuations:enable ${sourcefiles}
$ scala -P:continuations:enable ${classname}

In your source code, you must import the appropriate continuations elements, which you can do most simply by using a wildcard to import everything:

import scala.util.continuations._

If you forget to do the import you will get an error message similar to this:

<console>:6: error: not found: value reset
       reset {
       ^

Continuation Passing Style (CPS)

In order to understand how Scala's delimited continuations work, you have to understand the "continuation passing style", or CPS.

Consider this code in which a method makes a subroutine call:

def main {
    pre
    sub()
    post
}
def sub() {
    substuff
}

where pre and post represent all of the code in main respectively before and after the call to sub, and substuff represents all of the code in sub.

When the sub method gets called, the system, in effect, instructs the processor to execute the sub code, then to continue execution within main immediately after the call to sub.

We can conceptually refactor the code in main so that all of the stuff in pre is in a separate method, and all of the post stuff is in a separate method. We can further refactor the code so that each section (pre, sub, post) takes in all of its input data as arguments and passes all of its data changes out as an aggregate return value (such as a Map or Tuple) of the method for that section. Adding arguments and return value to main, we have something that looks like this:

def main(m:M):Z = {
    val x:X = pre(m)
    val y:Y = sub(m,x)
    val z:Z = post(m,x,y)
    return z
}
def sub(m:M,x:X):Y {
    val y:Y = substuff(m,x)
    return y
}

Now, instead of the system automatically continuing execution at post after finishing sub, let's make that explicit in our code by passing the chunk of code that calls post as an extra argument to sub. We will then modify sub so that, after doing all of its calculations and generating the values it would have returned to main as y, it instead calls post with its arguments as specified, and returns as its own value the return value of post, which is z in main.

def main(m:M) {
    val x:X = pre(m)
    val z:Z = sub(m,x, { post(m,x,_) } )
    return z
}
def sub(m:M,x:X, subCont: (Y) => Z) {
    val y:Y = substuff(m,x)
    val z:Z = subCont(y)
    return z
}

When we pass the code fragment containing post to sub, Scala generates a closure that captures the values available to post at that point, including m and x, so that when that closure is evaluated later it can get those values.

Note that the main method no longer sees y, the original return value from sub, so it can't be explicitly passed to post; instead, we use a placeholder, which is filled in by the code in sub that calls post. We can rewrite that line to use the more explicit function syntax (where, for convenience, we use y as our parameter name):

    val z:Z = sub(m,x, { (y:Y) => post(m,x,y) } )

The gist of CPS is that we don't use return. Rather than calling a subroutine and having it return to us, as is the case in the normal Direct Style, we pass a continuation to the subroutine for it to execute when it is done.

Nested CPS

In the above example we have only taken the first step in converting to CPS. To be able to take advantage of CPS, we need to complete the transformation.

At the top, our main method is still returning a value. Since we have no return in CPS, how do we handle this? The answer is that the topmost level can not return a value. Let's add a top-level wrapper like this:

def prog(m:M) {
    val z:Z = main(m)
    println(z)
    System.exit(z.exitValue)
}

Now we can make the same CPS transformation on prog and main as we did before on main and sub:

def prog(m:M) {
    main(m, { (z:Z) =>
        println(z)
        System.exit(z.exitValue)
    })
}

def main(m:M, mainCont:(Z)=>Unit):Unit = {
    val x:X = pre(m)
    val z:Z = sub(m,x, { (y:Y) => post(m,x,y) } )
    mainCont(z)
}

We are still using a return statement in sub, with code in main following the return from sub. To fix this, we need to push the mainCont in main into the continuation we pass to sub. We modify both main and sub to do this:

def main(m:M, mainCont:(Z)=>Unit):Unit = {
    val x:X = pre(m)
    sub(m,x, { (y:Y) => {
        val z:Z = post(m,x,y) } )
        mainCont(z)
    })
}

def sub(m:M,x:X, subCont: (Y) => Unit) {
    val y:Y = substuff(m,x)
    subCont(y)
}

We have now threaded our top-level continuation - the one that includes the call to System.exit - all the way down to sub, so when we execute the subCont in sub, it will first execute the post method with the code in main that originally appeared after sub, then it will execute the code in prog that originally appeared after the call to main, which will call println and then exit the program by calling System.exit.

If we wanted to convert substuff to CPS, we would apply the same transformation to it and sub, after which the call from sub to substuff would pass an additional argument which was the continuation of the rest of sub, which includes the continuation passed from main to sub, which in turn includes the continuation passed from prog into main.

As you can see, each continuation that we pass down to another subroutine always includes the continuations for all of the callers. In other words, every continuation includes all of the rest of the program to be executed after the called subroutine is done. The other important point is that in every method where we call a subroutine using CPS, that call is always the very last thing in the method.

Full versus Delimited Continuations

In the discussion above we have assumed that the entire program is converted over to CPS. This is the classical definition of continuations, which can be referred to as full continuations. However, using CPS in languages (such as Scala) that were not specifically designed for it can be awkward, so it would be nicer if we could restrict the use of CPS to the specific areas in our code where we want to use it.

This is exactly the intent of a delimited continuation. Rather than attempting to capture the entire remainder of the program execution in a continuation, we only capture the remaining execution of the program up to a specified point.

If we reexamine the start of our sample program, the prog method, we see that the only difference between it and any arbitrary method is that we can't return a Direct Style value from it. If we remove the call to System.exit, we can call prog from normal Direct Style code, with CPS being used within prog and all of its converted subroutines. Program execution within the CPS code proceeds normally using CPS, each method ending by passing a continuation along to the next method. After the last continuation is finally executed, the CPS code is done and control returns to the caller of prog.

def prog(m:M) {
    main(m, { (z:Z) =>
        println(z)
    })
}

Uses

We have gone to a lot of trouble to restructure our code to use CPS while keeping the functionality the same. Now we can examine how we can make changes to the code that are only possible because it uses CPS.

The key ability that CPS gives us is that we have an explicit object (the continuation) representing the remainder of execution of our program (or, in the case of a delimited continuation, of a portion of our program). In the code sample above, we executed that continuation once we reached the end of the line in sub. But what would happen if, instead of executing the continuation at that point, we just saved it somewhere, such as into a singleton?

object ContinuationSaver {
    var savedContinuation:Option[()=>Unit] = None
    def save(saveCont: =>Unit) = savedContinuation = Some(saveCont _)
}
def sub(m:M,x:X, subCont: (Y) => Unit) {
    val y:Y = substuff(m,x)
    ContinuationSaver.save { subCont(y) }
}

After sub saves the continuation, it is done, and in fact the entire delimited continuation is done; control returns to the caller of prog. But in ContinuationSaver we still have the continuation that represents execution of the remainder of that portion of the program, which we can execute later. In effect, we have placed the execution of that code into suspended animation, to be revived at some later time of our choosing.

Not only can we call the continuation later, we can call it multiple times. We can also write a more sophisticated ContinuationSaver that can save multiple continuations and keep track of which ones we should execute later, including the order and whether to call them multiple times. We can even save the continuations to persistent storage or move them to another computer, as is done by Swarm.

CPS With Return

In pure CPS, there are no returns. But code in Scala does return, even when we are using CPS. In the previous section I used the phrase "control returns to the caller of prog." This happens in the normal way, by having each of the intervening methods return to its caller until the stack unwinds to the first CPS call. I have assumed that each CPS method returns no value (Unit), but there is nothing preventing us from adding code to each method in the transformed CPS chain to make it return a value.

The examples above demonstrate a transformation from Direct Style code to CPS code, and that transformation always results in code that returns Unit. If we add a return value to the transformed code, this is not something we can get as a result of using the above transformation technique.

What happens if we add a return value to our CPS code? In our examples above, the execution of the continuation was always the last thing in the subroutine. If we keep this as our default behavior, then when we change the CPS methods to return a value, the return value from the last CPS method in a chain of continuations will propagate back up through the chain of CPS callers all the way out to the topmost CPS method, and will appear to the Direct Style code as the value of that outermost method. Of course, one of the intervening CPS method might modify or replace that value as it is being returned through it.

For example, let's take the most recent version of sub above (the one that saves the continuation for later execution) and make it return an Int value:

object ContinuationSaver {
    var numberOfSavedContinuations = 0
    var savedContinuation:Option[()=>Unit] = None
    def save(saveCont: =>Unit):Int = {
        savedContinuation = saveCont _
        numberOfSavedContinuations = numberOfSavedContinuations + 1
        numberOfSavedContinuations
    }
}
def sub(m:M,x:X, subCont: (Y) => Unit):Int = {
    val y:Y = substuff(m,x)
    ContinuationSaver.save { subCont(y) }
}

We also change the rest of the methods in our calling chain to allow us to propagate this value all the way out. Since the call to sub is the last call in main, all we need to do is change the return type on main to match the return type of sub. Likewise, since the call to main is the last call in prog, we change the return type of prog to match the return type of main:

def prog(m:M):Int = {
    main(m, { (z:Z) =>
        println(z)
    })
}

def main(m:M, mainCont:(Z)=>Unit):Int = {
    val x:X = pre(m)
    sub(m,x, { (y:Y) => {
        val z:Z = post(m,x,y) } )
        mainCont(z)
    })
}

We could, if we wanted to, modify main to make a change to the value returned by sub before passing it back as its own return value, or we could make main return something else entirely.

If you think about the CPS code as having been created by transforming some Direct Style code, you can see that the untransformed code had its original return type, and the now-CPS transformed code has a (potentially different) transformed return type.

Reset and Shift

Finally, we have enough background to understand Scala's reset and shift keywords.

The Scala implementation of delimited continuations was created by Tiark Rompf of EPFL, and is described in his explanatory paper on Delimited Continuations in Scala with co-authors Ingo Maier and Martin Odersky. There are also some quotes below from some of Tiark's posts.

Reset is the keyword that demarcates the limits of the delimited continuation. Within the body of the reset, the code is CPS code; the return value of reset is not CPS.

Shift is the keyword that indicates the bottoming out of the CPS path. The body of the shift is not CPS code, but it's untransformed return value is CPS. The shift call gets passed as its argument the continuation that has been collected from all of the callers out to the (dynamically) enclosing reset.

Reset and shift are thus the keywords that take you from Direct Style to CPS, and from CPS to Direct Style, respectively. All of the code between reset and shift is CPS. Any method that includes shift must be marked as CPS, and any method that calls a CPS method must be marked as CPS, until you reach the enclosing reset call.

When you use reset and shift in your code, the continuations compiler plugin transforms your code in a manner similar to the CPS transformation I described above. All of the code from the end of the shift block to the end of the enclosing method or reset block is packaged up as a closure and passed to the body of the shift block as the continuation function.

Let's break down some examples of reset and shift in Scala.

reset {
  shift { k: (Int=>Int) =>
    k(7)
  } + 1
}

The shift statement tells the compiler plugin to restructure the code as in our CPS examples, by converting the code after the shift call into a continuation that gets passed as an argument to the shift. To make it easier to see what that means in this case, let's do that code transformation in a few steps.

First, we assign the result of the shift call to a variable and use that variable later in the code:

reset {
  var r = shift { k: (Int=>Int) =>
    k(7)
  }
  r + 1
}

Second, we convert all of the code following the shift into a function and call it:

reset {
  var r = shift { k: (Int=>Int) =>
    k(7)
  }
  def f(x:Int) = x + 1
  f(r)
}

The function f is our continuation function that represents all of the code between the end of the shift block and the end of the enclosing reset block. Finally, we transform the code as is done by the compiler plugin, binding our continuation function f(x) to the shift parameter k, and making the return value of the fully transformed code be the return value of the body of the shift:

reset {
  def f(x:Int) = x + 1
  f(7)
}

Now we can easily see that the return value is 8.

We can apply the same transformations to

reset {
  shift { k: (Int=>Int) =>
    k(k(k(7)))
  } + 1
}

to get

reset {
  def f(x:Int) = x + 1
  f(f(f(7)))
}

from which we can quickly calculate that this will return a value of 10.

All of our transformations have no effect on anything outside of the reset; for example,

reset {
  shift { k: (Int=>Int) =>
    k(7)
  } + 1
} * 2

just multiplies the return value of the reset expression by 2, so the result of this code snippet would be 16.

Tiark's paper gives this interesting example:

reset {
  shift { k: (Int=>Int) =>
    k(k(k(7))); "done"
  } + 1
}

and points out that the value of this code snippet is "done". The continuation function k is called three times, but the value of that expression is discarded. If we apply our code transformations as before, we see that this transforms into:

reset {
  def f(x:Int) = x + 1
  f(f(f(7))); "done"
}

which makes it more obvious why the result of this code snippet is "done".

A key detail to note here is that the value of the evaluated reset block is not the value of the last expression in that block, as it is in most code. Instead, the value of the evaluated reset block is the value of the last expression in the shift block that gets executed within that reset block. Execution of the body of the shift is always the last thing that happens within the enclosing reset block.

When you look at a shift block and see its return value being used in an expression, as in the "shift + 1" examples above, remember that, due to code transformation, that "return" from the shift block never actually happens as a return. Instead, once execution reaches the shift block, the code after that block gets passed to it as a continuation; if the code in the shift block calls the continuation, the value which is passed as an argument to the continuation appears as the value being returned from the shift block. Thus the type of the argument passed to the shift block's continuation function is the same as the type of the return value of the shift in the source code, and the type of the return value of that continuation function is the same as the type of the return value of the original last value in the reset block that encloses the shift block.

There are thus three types associated with shift:

The type of the argument to pass to the continuation, which is the same as the syntactic return type of the shift in the source code.
The type of the return from the continuation, which is the same as the return type of all of the code that follows the shift block in the source code (i.e. the type of the last value in the block of code between the shift block and the end of the function or reset block containing the shift block). This is called the untransformed return type.
The type of the last value in the shift block, which becomes the type of the return value of the enclosing function or return block. This is called the transformed return type.

In the signature for shift, the above three types appear as A, B and C, respectively:

def shift[A, B, C](fun: ((A) => B) => C): A @scala.util.continuations.cpsParam[B,C]

The two types in the cpsParam annotation always represent the untransformed and the transformed return types, respectively. The CPS annotations are described in more detail below.

The signature for reset only uses two types: the first type is the untransformed type of the code block passed to reset, which matches the B type of shift, and the second type is the type of the transformed code block, which matches the C type of shift, and is also the real return type of the reset block to its caller. The scaladoc for reset uses parameter type names A and C, but I write it here using B and C so that the signature of the ctx by-name parameter matches the signature of the return value of shift:

def reset[B, C](ctx: => B @scala.util.continuations.cpsParam[B,C]): C

Here's where those types appear:

C = reset { ...; A = shift { k:(A=>B) => ...; C } ...; B }

In the following example, A=Int, B=String and C=Boolean:

def is123(n:Int):Boolean = {
  reset {
    shift { k : (Int=>String) =>
      (k(n) == "123")
    }.toString
  }
}

Annotations

As you saw above, the signatures for reset and shift include the cpsParam annotation. The compiler plugin uses this type annotation to select what pieces of code to transform to CPS; in Tiark's paper this is referred to as a "type-directed selective CPS transform." If you just use reset and shift without any subroutine calls, you may never need to explicitly use a CPS annotation. But if you put any shift calls into subroutines, as described below, then you will need to use a CPS annotation.

The base annotation is cpsParam[-B, +C]. This annotation tells the compiler that the corresponding block of code has an untransformed return value of type B and a transformed return value of type C, as described in the discussion of the types for reset and shift above.

To simplify the annotation for the common case where the transformed return type is the same as the untransformed type, the continuations package defines the convenience type cps:

type cps[A] = cpsParam[A, A]

If you are looking at old posts on the web, be aware that the cpsParam annotation used to be called simply cps; the old cps annotation was renamed to cpsParam and the new one-type-parameter cps type alias was added.

In the Uses section above we discussed the possibility of saving away the continuation for later execution, after which control returns to the caller. If we do this, we can't return a value from the suspended code to the original caller, since that code has not been executed yet, and the eventual executor of the continuation may not know where it came from, so it too is likely not to care about a return value.

In order to simplify the source code for this typical case, the Scala continuations library includes a special annotation type, suspendable:

type suspendable = cpsParam[Unit, Unit]

In addition to being more succinct, this annotation type can be used to make it clear that this function may suspend its continuation so that it can finish execution later.

Nested Shift

In all of the above examples, the shift block appears directly inside the reset block, and the cpsParam type of the reset block must match the cpsParam type of the shift block.

What happens if you put the shift block in a separate function and call that function from the reset block? In this case, the function containing the shift block must be marked as a CPS function by using the cpsParam annotation on its return type, and that cpsParam type must be the same as the cpsParam type of the enclosed shift block. When this function is invoked from within the reset block, the compiler plugin knows how to transform that block such that the code after the call to the CPS function becomes part of a continuation which is passed in to the CPS function, just as in the Nested CPS examples above.

def is123(n:Int):Boolean = {
  reset {
    is123sub(n)
  }
}

def is123sub(n:Int):String @cpsParam[String,Boolean] = {
    shift { k : (Int=>String) =>
      (k(n) == "123")
    }.toString
}

The function containing the shift block can be refactored to push that shift block down into another function, in which case that new function must also have the same signature as the original function and the shift block. Thus the entire chain of functions between the reset and the shift are all tied together with the same CPS signature.

What if you have an existing CPS function, but you want to call it and change its return type? If you were to follow the pattern of regular code, you might start by trying something like this in order to return floating point 1 or 0 rather than the Boolean true or false returned by a reset block that just calls is123sub.

//this won't compile
def is123f(n:Int):Float = {
    reset {
        val x = is123sub(n)
        if (x) 1.0 else 0.0
    }
}

This does not work as expected; the line of code following the call to is123sub is not operating on what will be the return value of the reset block, despite it being the last statement in that block. Instead, due to the code transformation described above that is being done by the CPS compiler plugin, code added after the call to is123sub gets bundled up as part of the continuation passed to the shift block within is123sub. The code that follows the call to the CPS function must end with a type that matches the first parameter of the cpsParam part of the signature of the function; in this case, String The untransformed return type of is123sub is also String, so in this case the block of code that follows the call to is123sub must take a String (as the return value of the call to is123sub) and must also return a String (which becomes the return value of the shift block within is123sub).

If we want to intercept the Boolean value that is being calculated in the shift block within is123sub, we must do that from within another shift block. The body of a shift block is written in Direct Style, and our subroutine is123sub is CPS, so we can't call it from within the new shift block. What we have to do is to put the new shift block before the call to is123sub. The call to is123sub then becomes part of the continuation that is passed to the new shift block, and we can add code within the new shift block that receives the transformed result of the shift block in is123sub and converts it as desired.

To see the control flow a little more clearly, you can execute this code snippet:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Here's the output the above code produces:

A
B
D
E
G
F
C

You can see from the order of execution that the second shift block is being executed as part of the continuation that is passed to the first shift block. Despite the fact that one appears before the other in the source code, the two shift blocks are actually nested. The compiler plugin notices this and handles them slightly differently to prevent the nested shift block from escaping from the enclosing reset block.

To show how all of the types thread together, here is a little piece of code with explicit type annotations on the reset and shift blocks in which you can see sets of places for which the same type needs to be used. The assert statements help show how the values are getting passed around.

def nestedShifts[T1,T2,T3,T4,T5](t1:T1,t2:T2,t3:T3,t4:T4,t5:T5):T2 = {
    reset[T1,T2] {
        val s1:T3 = shift[T3,T5,T2] { k1: (T3=>T5) =>
            val r1:T5 = k1(t3)
            assert(r1==t5)
            t2  //this is the return value of nestedShifts
        }
        assert(s1==t3)
        val s2:T4 = shift[T4,T1,T5] { k2: (T4=>T1) =>
            val r2:T1 = k2(t4)
            assert(r2==t1)
            t5
        }
        assert(s2==t4)
        t1
    }
}

If you get a compiler error when nesting CPS functions like this, try modifying the code to assign the value of the nested CPS function to a local variable, then end with that variable:

def is123f(n:Int):Float = {
    reset {
        val x = shift { k:(Int=>Boolean) =>
            if (k(n)) 1.0f else 0.0f
        }
        val r = is123sub(x)
        r
    }
}

If you leave out the val r and just end the reset block with the call to is123sub, you will get an error such as this:

<console>:13: error: type mismatch;
 found   : String @scala.util.continuations.cpsParam[String,Boolean]
 required: String @scala.util.continuations.cpsParam[String,Float]
           is123sub(x)
                   ^

Control Construct Restrictions

Because of the code transformation performed by the continuations compiler plugin, there are some control constructs that can not be used when calling a CPS function.

Using return statements in a CPS function is unlikely to do what you expect, and may cause type mismatch compiler errors, so you should not use them.

When using an if statement, you may get an error like this:

Foo.scala:21: error: then and else parts must both be cps code or neither of them

Tiark's advice is not to use explicit return, and maybe use shiftUnit on the non-CPS value.

The compiler plugin does not handle try blocks, so you can't catch exceptions within CPS code. Those exceptions will be propagated out to the enclosing reset block and can be caught there - unless the continuation is suspended and executed later, in which case any exceptions would be propagated to the reset block of the code doing that later execution.

You need to be careful when using looping constructs. As Tiark says,

Capturing delimited continuations inside a while loop turns the loop basically into a general recursive function.

You can follow the above link for details, but basically each invocation of shift within a looping construct allocates another stack frame, so after "looping" many times you will likely get a StackOverflowError.

Some looping constructs can not be used with a shift inside them. To quote Tiark again:

In a reset block you can do anything, but shifts are not allowed everywhere. The limitation is that everything on the call path between a shift and its enclosing reset must be "shift-aware". That rules out the regular foreach, map and filter methods because they know nothing about continuations, so they can't call closures containing shift.

Advice

As I mentioned at the start of this post, it took me some time to feel that I had a good understanding of how reset and shift work. You may not get it in one reading of this post. As with any new coding concept, the best way to gain a working understanding is to try using it in some of your own code. You will need patience; the CPS error messages are not always clear.

If you are interested in playing with control constructs, such as actors or generators, then you should definitely take the time to understand reset and shift. You might also want to take a look at Swarm.

On the other hand, you may never need to deal with reset and shift. Now that they are available in Scala, I expect some people will create libraries that build on reset and shift to present APIs for developers that are simpler to understand. Still, even when using those simpler APIs you may find that an understanding of the content of this post will be useful.

Resources

Wikipedia article about CPS.
Tiark Rompf's explanatory paper on Delimited Continuations in Scala. Some heavy going, but also includes a number of examples of different capabilities that can be built on top of delimited continuations.
Rich Dougherty's 'Delimited continuations in Scala' blog entry of 2009-02-24.
Rich Dougherty's 'Tail calls, @tailrec and trampolines' blog entry of 2009-04-05 discusses stack size management, including a section that mentions Scala continuations.
Daniel Sobral's 'Delimited Continuations Explained (in Scala)' blog entry of 2009-07-04.
Josh Suereth's 'How you should think about Delimited Continuations in Scala' blog entry of 2010-03-10.
Scaladoc for the scala.util.continuations package.
Swarm, a distributed programming system that captures delimited continuations in order to move them around the network for execution on other nodes. You can see a video introducing Swarm on their Google Code page.

Updated 2010-08-09 to fix error pointed out by mgm7734.
Updated 2010-09-26 to fix error pointed out by Nikolay.

My Misperception of Scala's Ordered Trait

2010-05-28T21:40:00.000-07:00

A brief tale of a little misperception that I had, and how it was corrected.

The Ordered trait in Scala is typically used when defining a class of objects that know how to order themselves by comparing against other instances of that class. The typical class definition looks something like this:

case class Thing(val n:Int) extends Ordered[Thing] {
    def compare(that: Thing): Int = { this.n - that.n }  //[1]
}

When I first started looking at these definitions, they just looked wrong to me: it seemed like Ordered[Thing] depended on the definition of Thing, and Thing in turn was defined in terms of Ordered[Thing]; a circular definition!

It is of course not a circular definition. The appropriate interpretation was made obvious to me recently while reviewing some Scala code with a co-worker, who was using the Ordered trait in a non-canonical way. Instead of the usual use of Ordered as in the above class definition, his class definition looked similar to this:

case class Thing(val n:Int) extends Ordered[Any] {
    def compare(that: Any): Int = that match {
        case i:Int => this.n - i
        case x:Thing => this.n - x.n
        case _ => throw new IllegalArgumentException("bad type")
    }
}

The reason he did this was because he wanted to be able to compare a Thing - which has an Int value as part of its definition - against either a Thing or an Int. The smallest common superclass of Thing and Int is Any, so his compare method had to accept an argument of type Any, which in turn meant the Ordered trait must be Ordered[Any].

This somewhat unusual use of Ordered led us to another small problem. He had an Array[Thing], sorted according to Thing.compare, on which he wanted to do a binary search. We couldn't find a binary search built in to Scala, but it was simple enough to find one on the web. We grabbed the Scala implementation of binary search from RosettaCode.org (and changed the type of the argument from IndexedSeq[A] to Array[A] since we were using Scala 2.7):

def binarySearch[A <% Ordered[A]](a: Array[A], v: A) = {
  def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
    case _ if high < low => None
    case mid if a(mid) > v => recurse(low, mid - 1)
    case mid if a(mid) < v => recurse(mid + 1, high)
    case mid => Some(mid)
  }
  recurse(0, a.size - 1)
}

Our code to call the binarySearch method looked something like this:

val a:Array[Thing] = Array(Thing(1), Thing(3), Thing(5), Thing(6))
val x = binarySearch(a,3)

It failed to compile, with an error like this REPL output:

<console>:7: error: type mismatch;
 found   : Array[Thing]
 required: Array[Any]
       val x = binarySearch(a,3)
                            ^
<console>:7: error: no implicit argument matching parameter type (Any) => Ordered[Any] was found.
       val x = binarySearch(a,3)
               ^

The cause of this pair of error messages may be obvious to some people, but we scratched our heads a while trying to figure out what we had done wrong. Eventually we realized that the binarySearch method was making the assumption that the element type of the array was same as the type of the sort; in other words, the binarySearch method only worked on arrays of elements where each element, of type A, implemented Ordered[A]. Since our Thing class did not do that, we were getting a type mismatch when trying to pass it to binarySearch.

The solution was to modify binarySearch to explicitly have two type parameters, one for the element type of the array (A) and one for the ordering type of those elements (B), i.e. the type of the values against which we can compare the array elements:

def binarySearch[A,B](a: Array[A with Ordered[B]], v: B) = {
  def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
    case _ if high < low => None
    case mid if a(mid) > v => recurse(low, mid - 1)
    case mid if a(mid) < v => recurse(mid + 1, high)
    case mid => Some(mid)
  }
  recurse(0, a.size - 1)
}

Going through this exercise helped me clearly see the distinction between the element type and the ordering type, and more generally to firmly excise the mistaken perception of circular dependency I mentioned at the start of this post. Now when I see class Foo extends Bar[Foo], it's easy for me to remember that just means that class Foo implements methods, as declared in Bar, that happen to take arguments of type Foo [2].

Footnotes

[1] Using a straight subtraction like this for the comparison will fail in extreme cases, such as if the first value is MAX_VALUE and the second value is negative; however, in the interest of keeping the code example simple, I have used this very short and understandable code snippet.

[2] Yes, I know this is not a very precise statement: Bar[Foo] might only define variables rather than methods, or the methods might take arguments of type List[Foo] rather than Foo, or any of a number of other variations.

Updated 2010-07-10 to escape angle brackets as pointed out by tolund.

Reload That Config File

2010-01-10T22:05:00.000-08:00

It is common for applications to load a configuration file on startup to control various options. Some applications can also reload their configuration file while running, allowing you to modify the application configuration without having to restart the application.

Goals
Dependency Injection
Config Contents
Config Objects
Seven Steps
Unit Testing
Implementation Options

Goals

Configuration files (or config files) are useful because they let us change the behavior of an application with a mechanism that is much simpler and faster than modifying the application source and recompiling it. Being able to reload the configuration of a running application allows us to take that concept a bit further, as generally we can make reloading the configuration operationally simpler and faster than shutting down and restarting the application.

When reloading the configuration, we have the following goals:

Reloading a configuration should be a simple operation for the operator to trigger.
It should not be possible to load an invalid configuration. If the operator tries to do so, the application should continue running with the old configuration.
When reloading a configuration, the application should smoothly switch from the old configuration to the new configuration, ensuring that it is always operating with a consistent configuration. More precisely, an operational sequence that requires a consistent set of configuration parameters for the entire sequence should complete its sequence with the same set of configuration parameters as were active when the sequence started.
The application should provide feedback so that the operator knows what the application is doing. Logging, notification or statistics about configuration reloads should be available.

Dependency Injection

Dependency injection (DI) is a form of structural configuration in which different suppliers of a service are wired into an application based on the contents of a configuration file. In the typical case, these configurations are unlikely to change once an application has started. Although in principle it is possible to reload a DI configuration, and thus all of the discussion below could apply, in practice you might want to separate out the kind of relatively static structural configuration that is typically done with DI from the more dynamic parametric configuration that you might want to change while the application is running, and use different mechanisms to implement those two sets of configurations.

Alternatively, you can selectively disallow (as part of your validation step) configuration changes that are too much work to implement, requiring the user who wants to make such changes to restart the application.

Config Contents

If you think of a config file as being a set of late-binding commands for controlling the behavior of an application program, it should be clear that the most flexible config file is one that is itself a program. Applications that already have a built-in interpreter, such as emacs and applications written in Lisp, often simply feed their config files to their interpreter, giving them the full power of a Turing-complete language in which to express site-specific program behavior.

If you have an interpreter available, this can be a reasonable option: it is simple to implement, takes little work to document (assuming you already have to provide documentation for the interpreted language anyway), and provides a great deal of flexibility. One potential downside is that you might not want all of the power of the language to be available in a config file; in particular, if you are using the language internally, your program may have made available certain functions that you don't want a user to call from a config file. If your application already has a security framework built in to it, this may be easy enough to do, or you may not be concerned about it. In any case, you should at least be aware of this potential pitfall if you choose to use a language as your config file syntax.

At the other end of the spectrum, you could choose a standard name=value format, such as Windows INI file or a Java Properties file If you have a relatively simple application with just a few config parameters to set, this is probably a reasonable option.

You can treat all of your config data as strings and let the application deal with each individually, or you can define a set of datatypes that can be uniformly represented in a config file. This might include lists of data or other compound types.

One of the typical capabilities implemented in config systems is the ability to group config parameters into logical groupings. The standard Windows INI file does this with its [section] prefixes. You can simulate this in a Properties file by selecting a character to be a name separator (typically a period), then using that separator character to define names for your parameters that indicate their grouping. This can easily be extended to multiple levels to allow a hierarchy of grouped parameters.

Once you have groups of config parameters, you might want to implement some kind of inheritance mechanism, whereby you can declare a set of names and values in group A, then declare that group B has the same item values as group A, possibly with some specified exceptions. Or perhaps you would like to be able to set the value of a parameter to be the same as the value of some other parameter, or some combination or transformation of other parameters.

You can continue to add more capabilities to your config file, but once you start getting too complex, you probably want to adopt an existing language syntax to avoid creating something that is complicated to implement and maintain, tedious to document, and difficult to learn and use.

If you do use a language for your config file, you may need to modify your approach in order to be able to implement all of the steps given below. In particular, you should not directly modify your operational objects from the config file, as this violates the separation of config data from the application and makes it more difficult to validate the entire config before activating it. One solution is to make your config file code only set data into the new Config objects that are being created for the reload process. Other solutions are possible, such as setting up a mock execution environment in which code can be validated before being applied, but a detailed discussion of such techniques is outside the scope of this post.

When choosing a format, you might consider whether you plan on maintaining config files through a program (either the application being configured or a separate config maintenance application), or if editing config files with a text editor is sufficient. Some applications maintain their config files in XML format for this reason, as there are many packages that can easily read and write XML files, as well as do basic syntax checking outside of the application being configured. Properties files can also be easily written, but there are many other formats that could be used. This can get tricky if you are trying to use an application to maintain config files when you are using a general purpose language for those files.

No matter what format you settle on for your config files, the same concerns discussed below apply regarding reloading the config.

Config Objects

In the approach described here we store in-memory configuration information in special Config objects that are separate from the operational objects that they configure. Defining separate Config objects gives us these benefits:

It allows us to represent multiple configurations simultaneously. In particular, it allows us to load and operate on a configuration that is separate from the currently active configuration.
It provides a convenient location to collect the methods that manipulate or otherwise access the configuration parameters.

There should be a set of Config objects that correspond to the different operational objects that can be configured. Each different class of operational object to be configured should have a different custom class of Config object associated with it. An operational class with multiple instances should have a separate instance of its Config class associated with each operational instance.

The various Config objects should be related to each other in the same way as the operational objects are related to each other; for example, if operational object A can have multiple children of type B, then ConfigA should be able to have multiple children of type ConfigB. There should be a single Config object which serves as the root Config object from which all other Config objects can be reached.

If the application is written such that there is a single application-wide active configuration, then the application should have a singleton which is the active root Config object. In the discussion below, I assume that such a singleton exists; if your application has multiple contexts, each with a different set of config info, you should interpret the word "singleton" to refer to the single active root config for the context whose config is being updated.

All of the Config classes can inherit from a standard base Config class that provides implementations of common useful methods such as type-safe calls to get integer and date parameters.

Seven Steps

There are seven steps involved in loading or reloading configuration data: Trigger, Locate, Load, Validate, Activate, Report, and Use. Each of these steps can be considered independently of the others. Each step has its own design decisions and implementation choices. In the approach we are using, the Config objects mentioned above are the common data shared by all but the first two steps.

Trigger

If your application is going to reload its configuration information, it needs to know when to do that. There are a number of options:

Your app can check for changes on a regular interval and reload if the source has changed. This is a typical approach used with logging configuration files such as for log4j, in which you can specify automatic reloading with a call to the static configureAndWatch method of DOMConfigurator or PropertyConfigurator.
If your app has a command line interface (CLI), you can add a command that reloads the config info.
If your app has a web interface, you can add a web page that controls config reloads. This can be a full web page with a form and feedback, or a simple URL that triggers a reload.
On a Unix system, a standalone app such as a daemon can be written such that a reload is triggered on receipt of a signal. You can then use the kill command to send the process that signal. SIGHUP (signal 1) is often used by Unix daemon programs for this purpose, some examples being acpid, dnsmasq, postgresd, smartd, smbd, winbindd, and ypbind.
For a Java app, you can enable JMX and use that to send commands to your application with a JMX console app such as jconsole or MC4J. JBoss uses this technique, allowing you to reload its log4j config using the JBoss jmx-console.
For many apps, you can pretty easily add a web interface, such as by using Jetty for Java apps, for the purpose of allowing control and status feedback.

You may want to limit how often a reload can be triggered to prevent a DOS attack (or the same effect caused by a bug in whatever is producing the trigger).

Locate

Once the app has been triggered to reload the config info, it needs to locate that info. Some options:

Assume the data is in the same location as before and reopen that location, such as is often done for a log4j config file.
Provide the location of the data along with the trigger. This is easy to do if you have a CLI, web form, or web URL, not so easy if you are using a timer or a Unix signal.

Some applications (such as one that uses the standard Props class in Lift, including the way Lift handles its log4j configuration) have more sophisticated file lookup mechanisms that allow configuration information to be split among multiple files or segregated according to the runtime environment to be used. If you are using a package that looks for one or more out of a set of possible files, and you want to be able to add or remove a config file and then reload, you should check to make sure the package is able to reload files and that it will rescan its set of possible files and not just assume that the same config files should be used as when they were first loaded.

Load

Once the data has been located, it needs to be loaded into memory where it can be manipulated. Note that you should load the data into a new Config object or set of objects so that you can do the validation checks on it before activating it.

You should not have to write the code that actually loads the data, as there are a number of usable options available. As an example, you can store your config data in the standard Java Properties format, then load that data using Properties.load. After reading the data into a Properties object, you can create your custom Config objects from the data in the Properties object.

Validate

Once the config data is loaded into your Config objects, you are ready to validate the new configuration. You should make the following checks:

Ensure that the syntax of all configuration values is correct. Depending on how you loaded the data and converted it to your Config objects, some of these checks may already have been done. If there are any values which have not yet been checked for correct syntax, those values should be checked now.
Perform semantic checks on individual parameters. This includes things such as checking that numbers are within allowable ranges, or that each selection parameter has a value that is one of the allowable selections for that parameter.
Perform validity checks on multiple parameters. This includes situations in which you have two or more parameters that are related and which thus must have values consistent with each other.
Compare the new set of Config objects against the current set to ensure that all proposed changes are allowed. You may decide that some changes are too much work to bother to implement; you can disallow those changes in this step.

With a Config class that corresponds to each configurable operational class, we can put the validation code directly in those classes rather than in the operational classes.

After completing the above validation steps, and assuming there were no errors, you have done all error checking and know that you will be able to switch to the new config without errors, but you have not yet done so.

Errors in any of these steps should be collected so that they are available for Reporting.

Activate

Assuming that the loaded Config objects pass all of your validation tests, it is time to activate the new Config. While conceptually simple, this is the trickiest step.

The key issue here is ensuring that the application works properly in the presence of concurrent access to the config data. You want to make sure that the application cleanly switches from using the old configuration to using the new one, without the possibility that some operations will be performed with part of the old configuration and part of the new one.

There are two basic updates you need to make, which correspond to the two basic approaches to using the data:

Update the active root Config singleton.
Update all operational objects that contain configuration state.

Handling the first approach is pretty easy: inside a synchronized block, update the active root Config singleton. When another thread begins an operational sequence that relies on any config parameters, it reads the current root Config singleton (in a synchronized block) and keeps it in a local variable for the duration of the operational sequence. All queries for config parameters during that sequence are done against the local Config variable, ensuring that the entire sequence uses a single Config even if the Config singleton is updated in the middle of that operational sequence.

If you are using the second approach, updates are a bit trickier. It would be simple if the activation thread could just update the state in the operational objects, but another thread may currently be running and using those operational objects in an active operation. You can't just update the state in all of the operational objects from the activation thread because the operational thread might then pick up the new state in the middle of one operational sequence, and we assume that starting an operational sequence with one state and finishing it with another state will cause problems.

The key to handling changes when using this second approach is to build on how we solved changes to the first approach by capturing the value of the active root Config singleton at the start of the operational sequence. That starting point is the point at which we know (by definition) that it is safe to change over to a new config. When we start our operational sequence, we capture the currently active Config into a local variable, as described above as the solution for changes to the first approach. We then check to see if the config has changed since the last time we started the sequence. We do this by comparing our newly captured Config against the Config that we used the previous time we executed our sequence, which means we need a second variable that stores that previous Config. If the newly captured Config is not the same as the previous Config we used, then we reconfigure our operational objects according to the newly captured Config, then save that as well as the most recently used Config for the next execution.

When using the above solution, if the only time you update the operational state is when a thread starts an operational sequence, and that thread waits for a long time before beginning execution of the sequence, then the switch of the operational state to the new config may not happen for a long time. Despite having validated our new config, it is possible that, due to a bug, the new config will fail when we attempt to apply it to our operational objects, and it is generally better to have that happen immediately when the config is activated rather than much later, when it might not be obvious that the problem is due to the new config. In order to avoid this situation, you should add code to make your threads wake up and apply the new config immediately after it is activated, even if there is no other work for them to do.

If you have multiple independent operational sequences you should separately capture a copy of the active Config at the start of each sequence. However, you need to make sure that each sequence is in fact independent of the others as far as the config parameters that each uses, since when using the above approach you may end up with two threads executing different sequences at the same time with one using the old config and the other using the new config.

If the different threads are related, such that it is not acceptable for one thread to be using the new config while another is still using the old config, then you will have to use a different approach. In this case, you will probably need to write some code to ensure that no thread starts using a new config until all threads have stopped using the old config.

You can do this with two flags, properly synchronized:

config-in-use
ok-to-use-config

The activation thread turns off ok-to-use-config, then waits until config-in-use is zero. At that point it updates the root Config singleton and turns on ok-to-use-config.

The operational threads check ok-to-use-config before capturing the current config. If turned off, they wait until it is turned on. They then increment config-in-use, use the config, and decrement config-in-use when done. Synchronized and try/catch blocks should be used to avoid race conditions and ensure the config-in-use count doesn't get stuck on.

Report

Feedback is important. Ideally, the user should get the following feedback:

When loading of an updated config is triggered, the user should get feedback on whether or not the new configuration was activated.
If the new configuration was not activated, the user should get feedback on why the new configuration was rejected (i.e. he should see a list of config errors).
Ideally, at a later point in time it should be possible for the user to determine what configuration is currently being used and how long it has been active. This is useful in situations where an on-disk config was changed at some point in the past but not loaded into the application.

Generally the reporting feedback channel is related to the trigger mechanism:

If you use a CLI command to trigger the reload, that command can print out the feedback.
If you use a web page to trigger the reload, the web response page can display the feedback.
If you use JMX, the feedback can be returned through that protocol.
If you use a web URL, the HTTP response can include the feedback.

If you application does logging, the feedback can be logged to the log file. This can be done in addition to any of the above feedback mechanisms.

Use

It is important to ensure that the config parameters used are consistent throughout an operational sequence, even when a config reload occurs while that sequence is executing, as discussed above in the Activate section above. Once you have handled that, you can move on to other usage aspects.

There are two basic approaches to using the active config parameters:

Use the current Config object directly each time a config value is needed. This is suitable for simple options that are tested each time a specific behavior or feature is desired.
Load data from the current Config object into operational objects. This is necessary when some of the config info refers to state that is managed by an operational object, such as the endpoint for a TCP connection.

The first approach provides for simpler updating of the config data, but sometimes the second approach is necessary for performance reasons or due to how state information is stored in other objects. The timing for when to update config state in operational objects is discussed in the Activate section above.

A minimal implementation of the Config object would provide just a single method to retrieve any parameter by name, such as is provided by the Properties.getProperty method. While this is easy to implement, it does not provide as much protection against programming errors as other approaches described below.

For type safety, you should implement (or use a package that provides) a set of methods with specific return types that match the types of your config parameters. You can then pass in the name of each parameter and not have to type-cast the result.

For maximum type safety your Config object should provide methods specific to each config parameter being retrieved. This ensures not only that you have the correct return type for the parameter, but that you have not accidentally mistyped a parameter name in a call to retrieve its value. (Of course, your unit tests should also catch this error, but you will catch it sooner and more surely with compile-time checks.)

Unit Testing

Keeping the configuration management code in separate Config objects improves the testability of your code. You can write unit tests for your Config objects to test that they properly locate, load (or reload), and validate config files, and you can create a set of mock Config objects that you can use to test how your application responds to different configurations.

A more complete test suite will include tests that verify proper functionality when a reload operation is performed by one thread while one or more other threads are in the middle of processing and using config data. However, a detailed discussion of this kind of multi-thread testing is beyond the scope of this post.

Implementation Options

You can write all of your own config code from scratch, or you can leverage an existing package. Whatever approach you take, you will want to ensure that your application handles all seven of the steps discussed above.

A few packages are listed below, with a discussion of the steps for which they provide support. For bullet items marked no support you will have to write your own code. None of the packages provides support for all of the steps. Even if a package did provide that support, you must still provide application-specific code for validation, activation, and use.

Caveat: Except for Properties, I have not used the packages listed below. My evaluation of their capabilities is based entirely on reading the documentation and examining the source code, so it is possible that I have made some mistakes in that evaluation.

Properties (Java)
JavaConfig (Java)
Apache Commons Config (Java)
Configgy (Scala)

Properties (Java)

The standard Java library includes the Properties class, which can be used for simple applications that require only a few parameters.

Trigger: no support.
Locate: no support.
Load: You can load a properties file with a single call to Properties.load, where you pass in the name of the file to load.
Validate: no support.
Activate: no support.
Report: no support.
Use: The Properties.get method will return the value of a property as a String. You can use this directly as a generic call to retrieve config parameters by name, or you can layer your type-safe methods on top of this.

JavaConfig (Java)

JavaConfig (not to be confused with Spring JavaConfig, which is used for Dependency Injection configuration) reads config files using the standard Properties file format. The package provides a generic Config class, which you subclass to create your application-specific config class. It handles a defined set of data types.

JavaConfig specifically does not include any logging, so that it can be used to read the configuration for another logging package.

Trigger: no support.
Locate: no support.
Load: You pass the name of a properties file to the Config constructor, which loads the properties file.
Validate: After instantiating your config object, you call the validateConfiguration method on it, which returns a ConfigValidationResult object that contains the validation results. This validateConfiguration method calls all of your getter methods. For each of your methods that throws an exception, the message is collected and made available through the ConfigValidationResult object.
Activate: no support.
Report: The ConfigValidationResult class collects the error messages from all of your getter methods that throw exceptions, and makes them available
Use: The base Config class provides type-safe methods such as getInt and getBoolean that accept a parameter name. In your config class that extends that class, you define a getter method for each of your config parameters. Each of your methods should call one of the underlying type-safe methods, passing it a config parameter name, and return that result. Your method should also perform any validation checks and throw an exception if there are any validation errors.

Apache Commons Config (Java)

Apache Commons Config provides a mechanism to allow config info to be loaded from a variety of sources, such as files or databases. You can mix config info from multiple different sources, such as reading some info from a database and some from system properties, and access it all through a single config object. It supports file includes and value substitution.

Trigger: The package org.apache.commons.configuration.reloading provides a mechanism for defining a reload strategy when using file-based configuration, such as reloading on access to a config element if the file has changed, and some support for using JMX to trigger a reload.
Locate: You can pass in a relative filename, and the package will look in various locations for a config file of that name to load.
Load: You can create a configuration object for a specific data source, such as a file, or you can create a composite configuration object from multiple other configuration objects.
Validate: no support.
Activate: no support.
Report: no support.
Use: There are a set of type-safe methods to which you pass an item name and receive back its value.

Configgy (Scala)

Configgy includes logging as well as configuration, so it can use its own config files to configure logging. Its config files look like a cross between an XML file and a Properties file, with hierarchy represented by XML syntax, and individual parameters looking more like Properties. It handles a defined set of data types and has the ability to represent lists of values for a single parameter.

Configgy supports a lot of options when defining parameters, including hierarchy, inheritance, includes, variable substitution (including system properties), and conditional assignment.

Note that Configgy allows the application to set values in the config after it has been loaded into memory. As with any situation in which one datastructure might be shared among multiple threads, you should be very cautious with this capability. In particular, if you have a thread which has read the config and used that data to set state in its own application objects, setting the value in the config object alone may not have the desired effect. Your application can set up a subscriber for changes, which will be called when there are runtime changes to a config value, but you need to handle synchronization of these runtime changes in the same manner as when reloading the entire config. And your application code that is calling the set method must be prepared to handle a thrown exception if a subscriber decides the change is invalid.

The examples given in the Configgy documentation use a Scala object (as opposed to class) and does not discuss reloading, but there is a reload method available on the main object, which should work if you use the approach described above (using a pair of flags) for the case when all threads are related. Also, there are separate config objects being used under the covers, so it should be possible to use those directly, rather than the main object, if you want to be able to switch some threads over to your new config while some other threads continue to use the old config.

If you are writing a Scala application, Configgy is probably your best option.

Trigger: There is some JMX support built in; reload is not one of the methods available from the JMX interface, but it should not be too difficult to add it.
Locate: Configgy has calls to allow you to set the location of the config file to load. You can call this before calling reload() to control the source for the reload.
Load: You call Configgy with a filename and it loads that file and any file referenced with an include statement.
Validate: Configgy uses a subscription/callback model to let the application know when data has been changed. Your callback is called with an argument that tells you whether Configgy is doing a validation pass or an activation ("commit") pass. On the validation pass, your callback can throw an exception to indicate that the new value fails validation.
Activate: The validate/commit subscription model provides hooks to allow you to write your own validation and activation, but you still need to consider synchronization when using multiple threads.
Report: no support.
Use: There is a set of type-safe methods to which you pass a parameter name, which can be hierarchical.

Improve Your Releases

2009-12-03T20:14:00.000-08:00

There is more to a good software release than a good program.

If you are releasing software and want it to be successful, you have to do more than just write a good program. You need to consider all of the things the user will want to do with your software before and after actually using it.

You can look at the steps below as an interpretation of the phases of the software lifecycle from the perspective of the user. Depending on how well you do your job, the user will have a better or worse experience with each of these phases. If, for one of these phases, you do nothing, the user is likely to have an unpleasant experience when he gets to that phase.

Develop
Release
Distribute
Install
Support
Upgrade
Patch
Migrate
Uninstall

Develop

This is the phase that most open-source developers focus on. If we were looking at the software life cycle in a little more detail, we would split this phase into three separate phases: design, code, and test. In commercial development these three phases are often handled by separate groups, but from the user's perspective they can be lumped together as being the factors that contribute to the overall quality and usability of the software.

This is the time in which to consider all of the points below so that you can create your system in a way that makes it easy to do the right thing for all of the other phases of the software life cycle.

Release

Once the software comes out of test, it must be packaged up as a Release. It is useful for a user easily to be able to tell what released artifact he has acquired and what version of that artifact he has. The simplest way to handle this is to define a released artifact as being a single file. If you think you need to release a collection of files, they should be packaged up as a single file, such as in zip, tgz (tar-gzip), dmg or iso format. You can then give each file a name and version number to allow the user to identify it.

You may have a product that is composed of a number of other released artifacts. You can bundle these into one larger artifact that is a collection of the other artifacts plus an installer that can invoke the installers of the other artifacts, or that knows how to install those other artifacts directly. Operating system installers work in this way.

Once your released artifact is in a single file and appropriately labeled, it is easy to take the next step: generate and publish a checksum for that file. If, for any reason, the user is unsure about what artifact and version he has, he can then run a checksum on his file and compare it against your official list of checksums. Using a cryptographic checksum provides protection not only against accidental corruption, but against intentional modification (hacking) of the artifact as well. Depending on the level of security desired, you can use md5, sha1, or sha256 for your checksum. Operating system distributions such as Fedora do this, including the additional security step that the published list of checksum values is digitally signed.

Distribute

Your user needs to get your released artifacts. Long ago this used to be done by distributing physical media such as DVDs, CDs, floppies, or tapes. Today most distribution is done over the internet, which makes this step far simpler than it used to be.

Open source projects have easy solutions available through such services as sourceforge and github. Many commercial providers also distribute their software from download pages on their web sites, often with additional security such as restricting web access to customers with accounts, and using license files to enable specific functionality in the installed software.

Given how widespread and well-understood this model is, it makes sense to use it for internal software as well: set up a web site where your users can find all of your released artifacts. If the list of artifacts is small, you can just set up a few directories with files in them and serve up those files with your web server. When the number of artifacts gets large enough so that browsing listings gets cumbersome, you can add a search form. If you need to restrict which of your internal users have access to your downloads, you can do that in the same way as commercial vendors do, with password access or license-file control of the installed application.

Install

The user should be able to install the complete application from the downloaded artifact with a single command, or at most two commands (an unpack command followed by execution of a setup script). Installing a Windows application is generally done by downloading an exe file and then executing it; a Mac install is generally done by downloading a dmg file, double clicking on it, and dragging the app into another folder; a Java install is often done by downloading a jar file and then executing it (such as by running java -jar on it). These are all examples of simple installation mechanisms. Once running, an installer can direct the user to select values for options and installation paths.

In particular, you should not require the user to unpack the software and then manually execute a number of other steps such as moving files around or editing config files. These are steps that should be handled by an installer.

When the files are installed on the user's system, there should be an easy way to determine what version is installed and in use. This information should be easily available in the application, such as in an About menu in a GUI application. If a user might install multiple artifacts from your collection, there should be a simple way to get a list of all artifacts installed and in use along with their version numbers so that you can unambiguously tell what versions of your software are being used at that site.

Support

Finally, the user is using your software. If your software is well designed, well written and well tested, the user should have no problems using it and all will be well. In reality, it is unlikely that no user will ever have any problems with your software. When a user does have problems, what will he do (other than grumble or swear at your software, that is)? Assuming the user is motivated to solve the problem rather than just giving up, he will seek out resources that can provide him with the information he needs to solve his problem. You can make his life easier in this step by providing some or all of the following:

A Users Guide or set of guides (tutorial, reference).
In-application help (context-specific, page-specific, links to the manual, search, how-to).
On-line forums where users can share their problems and solutions.
Direct support, via telephone, email, or chat.

If a user experiences a crash or runs into a bug, it might be nice if he can easily submit a crash report or a bug report so that you can more effectively fix the problem. If so, you will want that report to automatically include the list of installed artifacts and versions, as discussed above in the Install section.

Upgrade

If your software is successful you will probably release new versions of it. A user who is already using your software should be able to start using the new version of your software with minimal hassle. As with the initial install, installing an upgrade should be done with at most one or two commands, as it could be with an upgrader that guides the user through whatever questions need to be answered for the upgrade.

You can add an option to your application to check for upgrades and ask the user if he wants to download and install them, saving the user the hassle of separately doing those steps. If you choose to implement this, you should allow the user to disable it. There should also still be a way that the user can download an upgrade (as a single file, just as with an initial install), copy it to another machine, and install it there, in case he is running on a machine that is not connected to the network or is behind a firewall that prevents your automated download from working.

There are two ways in which an upgrade is different from an install, leading to two additional goals for the upgrader:

If the user has any configuration or customization, that should be carried over to the new version.
If the user starts running the new version and soon discovers that it is unusable for him, he should quickly be able to roll back to the previous version.

An approach to handle the first goal is to keep the configuration and customization in a separate directory, such as in the user's home directory, or (for Unix systems) in /etc or (for Windows systems) in the Registry. There can still be problems when upgrading if the format of the config and customization files changes, or if the items being configured and customized have changed between versions. Your upgrader should take care of this.

One relatively easy way to satisfy the second goal is to install each version of the application in a separate directory that contains the version number in the name, then providing a current directory that is a link to the version to be used. Rolling back to a previous version might then be as simple as deleting the current link and recreating it to point to the previous version. Ideally, however, this rollback is also done by a program you provide, in case a rollback also requires any other changes such as to the configuration and customization files.

The upgrade and rollback should of course update the list of installed artifacts and current versions.

Patch

Occasionally you might want to deliver a minor update or bug fix to your software. You might send out one modified file and ask the user to install it in a specific location to fix a bug.

While this sounds like an easy mechanism for quick fixes, in the long run you will be better off ensuring that your upgrade process is streamlined enough that you can package up that one file in an upgrade and use your upgrade process.

The problem with sending out patch files and doing ad-hoc installs like this is that it makes it very difficult to keep track of what is installed at a customer site. If you send out four or five patches and then the customer starts reporting unique bugs, will you know what software is running at that site so you can track down those bugs? You could work on setting up a system to keep track of those patches, but you might as well invest that effort into making your upgrade process easier to use.

Perhaps you think that each customer will have a different set of patches, and you don't want to send the same patches to all of your customers, so you don't want to make them all standard upgrades. If it is really the case that you want to deliver different things to different customers, then you are not really delivering one artifact, you are delivering separate artifacts to each customer. In this case, you should just call them different artifacts, give them their own version numbers, and send out upgrades for those separate artifacts. In that way you can continue to use your standard upgrade process, and you can always know exactly what your customer has by collecting the list of artifacts and their version numbers for all of the artifacts installed at a customer site.

If you really think you need to send out patches, consider the following goals:

It should be easy for the user to install the patch with a single command.
It should be difficult for the user to make a mistake when installing the patch, such as could happen if he has to manually install files into specific directories or manually edit any files.
It should be easy for the user to rollback the patch if it doesn't work.
It should be possible for both you and the user to know exactly what version of software is installed at the site, including what patches have been applied, even if there is a patch of a patch.

If it seems to you that implementing a patch mechanism that does all of this is easier than adding some improvements to your upgrade process and perhaps dividing up a couple of your artifacts to more accurately reflect how you are actually installing them, then go for it.

Migrate

At some point one of your users might decide that he wants to stop using your software and move to some other package. If you are a commercial software provider you might think this is not something that should be in your list of goals - why should you help out a competitor? - but if you are interested in doing what is best for your user, you should at least recognize this phase of the software lifecycle and make a conscious decision about it. The better you treat a leaving customer, the more likely it is that he will some day be a returning customer.

To support your users in this step, you should provide export tools that allow the user to export all of his data from your application in a standard format. Depending on the application, this might mean exporting a CSV file, an XML file, an Open Document file, or something else.

If you also implement an import capability that reads the same standard file format as your export produces, this could help you in the future if you ever change your internal storage representation from one version to the next: just export from the old version into a file using the standard format, upgrade to the new version, and import that file.

Uninstall

Whether or not a user chooses to move to a different product, he may eventually decide he is done using your software and he would like to remove it from his system. As with the install, it should be possible for the user to uninstall your software with a single command. If an application was installed simply by unpacking it, that single command might be to remove that unpacked directory. With a more complicated installation, uninstallation is likely also to be more complicated, making an uninstaller program more important.

If you have set up your application such that the user-customized portions are separate from the standard install, your uninstaller can give the user the option of keeping those portions. Similarly, if the application maintains user data in its own directories, you should get confirmation from the user before deleting those files and give the user the option of keeping them.

You might also want to consider how you want your installer to behave if the user runs the uninstaller, keeps his customizations and data, then runs the installer. A user might want to do this to downgrade to a previous version if you do not otherwise provide a simple solution for that. Or perhaps you treated a departing customer well enough that he is now returning to your product, in which case he might be pleased to find that his old preferences and customizations are still available.

Overriding vals as Optional Parameters

2009-11-04T21:41:00.000-08:00

For simple cases you can use Scala vals, selectively overridden, as a way of implementing optional parameters. Overriding can also be used for other interesting tricks.

Optional Class Parameters
Optional Trait Parameters
Early Definition
Required Trait Parameters
Abstract Class Parameters
Type Parameters
Caveats

Optional Class Parameters

In Java, a typical idiom for initializing an object that has a large number of optional parameters, of which only a few usually get set, is to construct the object and then call setter functions to customize each of the optional parameters. While this technique can be convenient, it leaves open the possibility that the setter might get called later on in the objects lifecycle at a time when changing that value could cause problems.

One solution to this problem is to use the builder pattern. This solution is available in Scala as well, and can be taken a step farther than in Java by using the type-safe builder pattern.

The type-safe builder can be overly complicated for many situations. Sometimes it would be nice to have something simpler than even the simplest of builders.

Scala 2.8 will have named parameters with default values, which will make it pretty easy to create classes that have optional parameters, although you might not want to do this if you have 30 optional parameters. Meanwhile, there is another approach you can use: overriding vals.

The approach is pretty simple: you define a base class with a constructor that includes all of the required parameters, and you then add a val for each of the optional parameters. When you want to create an instance of that class that sets some of the optional parameters, you create an anonymous subclass by adding a set of braces after the new statement that creates the instance, and inside the braces you override each val that you want to set.

In this example we define a Car class that represents a few pieces of information about a car. model and color are required parameters and appear in our constructor. Our optional parameters are hasRadio and hasSunRoof, so we make those vals rather than constructor parameters, and we assign them their default values. We include a toString method so we can easily see the results.

class Car(model:String, color:String) {
    val hasRadio = false
    val hasSunRoof = false

    override def toString() = {
        "Car{"+
            "model="+model+ 
            ",color="+color+
            (if (hasRadio) ",hasRadio" else "")+
            (if (hasSunRoof) ",hasSunRoof" else "")+
        "}"
    }
}

The normal use would be to call the constructor with no additional arguments:

val c1 = new Car("Ford", "red")
println(c1)

//Car{model=Ford,color=red}

To specify one of our optional arguments, we add a code block to the new call, which creates an anonymous subclass in which our val overrides the default:

val c2 = new Car("Chevy", "blue") { 
    override val hasRadio = true 
}   
println(c2)

//Car{model=Chevy,color=blue,hasRadio}

We can pass in values from the caller's context rather than constants:

val myHasSunRoof = true
val c3 = new Car("Honda", "white") {
    override val hasSunRoof = myHasSunRoof
}
println(c3)

//Car{model=Honda,color=white,hasSunRoof}

Optional Trait Parameters

You can use this same approach to pass in values for instance variables in traits, which don't have constructor parameters. For example, say we define a trait for an optional Touring package for our car:

trait Touring {
    val hasNavSystem = false
    val hasExtraSuspension = false
    val hasTowHitch = false
    val hasRunningBoards = false

    override def toString() = {
        super.toString()+
            "+Touring{"+
            (if (hasNavSystem) "navSystem," else "") +
            (if (hasExtraSuspension) "extraSuspension," else "") +
            (if (hasTowHitch) "towHitch," else "") +
            (if (hasRunningBoards) "runningBoards," else "") +
        "}"
    }
}

Now we can create an instance of a Car with Touring and pass in values for some of those "optional constructor parameters" defined in the Touring trait:

val c4 = new Car("Honda","white") with Touring {
    override val hasSunRoof = true      //from Car
    override val hasNavSystem = true    //from Touring
    override val hasRunningBoards = true  //from Touring
}

println(c4)

//Car{model=Honda,color=white,hasSunRoof}+Touring(hasNavSystem,hasRunningBoards,}

NOTE: Due to a bug in older versions of Scala, at least through 2.7.6, overriding a val on a trait as in the above example does not work. This does work properly in Scala 2.8.0 (at least it does in the 20091006 nightly build).

Early Definition

You may have a situation in which some of the vals that you are initializing in a trait or class depend on other vals. In this case, overriding a val as we did above may not give you the result you want: the initializer of the superclass runs to completion before the initializer of the subclass, which means all of the vals in the superclass get set before any of the overriding vals are evaluated.

For example, say we modify our Touring trait by adding a maxTowWeight value, as shown in bold below:

trait Touring {
    val hasNavSystem = false
    val hasExtraSuspension = false
    val hasTowHitch = false
    val hasRunningBoards = false
    val maxTowWeight = if (!hasTowHitch) 0 else
        { if (hasExtraSuspension) 1500 else 1000 }

    override def toString() = {
        super.toString()+
            "+Touring{"+
            (if (hasNavSystem) "navSystem," else "") +
            (if (hasExtraSuspension) "extraSuspension," else "") +
            (if (hasTowHitch) "towHitch," else "") +
            (if (hasRunningBoards) "runningBoards," else "") +
            "maxTowWeight="+maxTowWeight +
        "}"
    }
}

When we instantiate a Car with Touring the constructor code for Touring executes before the constructor code for the new class. In particular, val maxTowWeight gets evaluated before the overriding values are evaluated, so it always ends up with a value of zero:

val c5 = new Car("Honda","white") with Touring { override val hasTowHitch = true }

println(c5)

//Car with Touring = Car{model=Honda,color=white,hasRadio=false,hasSunRoof=false}+Touring{towHitch,maxTowWeight=0}

Scala provides a mechanism to address this issue: Early Definition (Scala Language Specification, section 5.1.6). The vals that you specify in the Early Definition block are evaluated in the context of the calling class, then that set of values is placed into the context of the new class being instantiated such that all of those values are available at the beginning of the process of instantiation, even before the initializer for Object is executed. In this way, any expression which uses one of those vals will have access to the value provided in the Early Definition.

It could be used with our Car example like this:

val c6 = new { override val hasTowHitch = true } with Car("Honda","white") with Touring

println(c6)

//Car with Touring = Car{model=Honda,color=white,hasRadio=false,hasSunRoof=false}+Touring{towHitch,maxTowWeight=1000}

A class definition for the above example could look like this:

class TouringCarWithHitch(name:String, color:String) extends {
            override val hasTowHitch = true
        } with Car(name,color) with Touring {
    //normal class overrides and additional elements here
}

val c7 = new TouringCarWithHitch("Honda","white")
//c7 is the same as c6 (but we have not implemented ==)

Required Trait Parameters

If you want to define a trait that has required parameters rather than optional parameters, you can omit the value from the declarations and instead specify only the type, which causes the val to be abstract. For example, if we want to make the hasTowHitch and hasNavSystem parameters to our modified Touring trait be required, that would look like this:

trait Touring {
    val hasNavSystem:Boolean   //abstract (no value)
    val hasExtraSuspension = false
    val hasTowHitch:Boolean    //abstract (no value)
    val hasRunningBoards = false
    val maxTowWeight = if (!hasTowHitch) 0 else
        { if (hasExtraSuspension) 1500 else 1000 }

    override def toString() = {
        super.toString()+
            "+Touring{"+
            (if (hasNavSystem) "navSystem," else "") +
            (if (hasExtraSuspension) "extraSuspension," else "") +
            (if (hasTowHitch) "towHitch," else "") +
            (if (hasRunningBoards) "runningBoards," else "") +
            "maxTowWeight="+maxTowWeight +
        "}"
    }
}

Now when we declare a concrete instance of this class, we are required to define values for those two variables else we will get a compiler error. Since the base declaration is now abstract, we omit the override keyword on those vals:

val c8 = new Car("Honda","white") with Touring {
    override val hasSunRoof = true      //from Car
    val hasNavSystem = true             //from Touring; required
    override val hasRunningBoards = true  //from Touring; optional
    val hasTowHitch = false             //from Touring; required
}

println(c8)

//Car{model=Honda,color=white,hasSunRoof}+Touring(hasNavSystem,hasRunningBoards,maxTowWeight=0}

Abstract Class Parameters

Sometimes it is convenient to use an abstract val rather than a constructor parameter for abstract classes. For example, say you have a Service and you want to define a set of case classes for service messages. The base class should have a reference to the Service object so that it can easily be processed by generic service methods, but each case class should also have the same reference as a case value for easy matching. For consistency, since these are the same value, the name should be the same. You could do this by defining the base class with one parameter declared as a val to make it accessible, then define the case classes to override that value, like this:

abstract class Service
abstract class ServiceMessage(val service:Service)
case class ServiceStart(override service:Service) extends ServiceMessage(service)
case class ServiceStop(override service:Service) extends ServiceMessage(service)

The case class automatically adds a val keyword to each of our parameters, so we need to specify the override keyword, but can omit the val keyword.

We can simplify our case classes a bit by changing the base class val from a constructor parameter to an abstract val, like this:

abstract class Service
abstract class ServiceMessage { val service:Service }
case class ServiceStart(service:Service) extends ServiceMessage
case class ServiceStop(service:Service) extends ServiceMessage

Not only have we dropped the override keyword, but we are also not passing the service parameter to the superclass. The implied val keyword on the case class parameters creates a concrete instance of the service parameter that overrides the abstract value defined in the base class.

Type Parameters

Just as scala has value parameters, concrete value members and abstract value members, it likewise has type parameters, concrete type members and abstract type members. The approach used above on values can generally by applied to types as well: rather than defining a class with a type parameter, you can often define that class with a type member. If the type is a required type that must be overridden by the extending class, make the type member abstract; if you want the subclass to be able to default to the type used in the superclass, use a concrete type and let the subclass use the override keyword if it wants to override that type.

Bill Venners has a nice blog post where he discusses the question of when to use a type parameter and when to use an abstract type member, with a reference to an interview with Martin Odersky where he talks about abstract type members in comparison to instance variables.

Caveats

Although in many ways you are free to choose between using a constructor parameter versus a class member, they are not entirely equivalent. In particular, once you start building up class hierarchies using abstract and concrete members with overrides, you have to be careful that the initialization order is what you expect. In the Early Definition section above I gave one example of how values can fail to initialize correctly due to ordering issues. That one is pretty easy to understand, but they can sometimes be far more subtle and hard to spot.

One thing you can do that will sometimes fix such problems is to use the lazy keyword on your value members in order to get lazy initialization. This causes initialization of the value to be delayed until the first time it is used, rather than being eagerly initialized when the class is initialized. Note that if you declare a concrete variable as lazy, then an overriding instance of that variable must also be declared as lazy; if the original concrete variable is not lazy, the overriding variable can not be lazy.

Note that overriding a val in Scala is not the same as declaring a variable of the same name in a subclass in Java. Consider this Java test program Test.java:

public class Test {
    public static void main(String[] args) {
        (new Test1()).test1();
        (new Test2()).test1();
        (new Test2()).test2();
    }
}

class Test1 {
    public int t = 1;

    public void test1() {
        System.out.println("t="+t);
    }
    public void test2() {
        System.out.println("t="+t);
    }
}

class Test2 extends Test1 {
    public int t = 2;

    public void test2() {
        System.out.println("t="+t);
    }
}

and the apparently equivalent Scala test program Test.scala (where I have used Java-like syntax where possible so that you can run "diff" on the two files):

object Test {
    def main(args: Array[String]) {
        (new Test1()).test1();
        (new Test2()).test1();
        (new Test2()).test2();
    }
}

class Test1 {
    val t = 1

    def test1() {
        System.out.println("t="+t);
    }
    def test2() {
        System.out.println("t="+t);
    }
}

class Test2 extends Test1 {
    override val t = 2

    override def test2() {
        System.out.println("t="+t);
    }
}

Copy these out to Test.java and Test.scala, then compile and run each one (don't try to compile both and then run both in the same directory, as the class files will collide). The Java test prints this out:

t=1
t=1
t=2

The Scala test prints this out:

t=1
t=2
t=2

Note the difference in the middle line, where we have called Test2.test1(). The Java program prints 1, but the Scala program prints 2. This is because the declaration of t in Test2 in Java does not override the value in Test1, it shadows it. The Test1 value of t is still there, and it used by any method in Test1 that refers to that variable.

In Scala, by contrast, references to t in Test1 refer to the overridden value provided by Test2. Scala can do this because, consistent with the Uniform Access Principle, a variable in Scala is accessed by a pair of functions to get and set its value. When a value is overridden, that creates new access functions in the subclass that override the access functions in the base class.

Scala Case Statements As Partial Functions

2009-10-11T17:53:00.000-07:00

A Scala case statement can be either a Function1 or a PartialFunction depending on the context.

In my previous post I presented a simple Publisher that I used to decouple my Swing actors from their targets. Reader nairb774 pointed out that the standard Scala library includes a Publisher class. In fact, there are two Publisher classes in Scala, scala.collection.mutable.Publisher and scala.swing.Publisher. Although I like my publisher class better, the swing publisher did have one feature that I thought was useful: it accepted as a callback a PartialFunction rather than, as mine did, a Function1. That would mean, I thought, that I could pass in a case statement as a callback.

For example, continuing the Mimprint example from my previous post, if I were only interested in Enabled events published by a particular publisher, rather than explicitly checking this in my callback with an isInstanceOf or a match statement that includes a case _ => clause, I could just use a one-line case statement:

    showSingleViewerPublisher.subscribe { case e:Enabled => doSomething() }

My calling code in Publisher would call apply on the PartialFunction callback only if a call to its isDefinedAt method returned true, thus avoiding the MatchError that would occur if I treated it like a Function1 and called its apply method when the value was not Enabled. This seemed like useful functionality, so I decided to add it. I thought it would be easy, but unfortunately it was not.

Consider the following three definitions that assign a case statement to a partial function, full function, or no explicit function type, respectively:

val pfv:PartialFunction[String,Unit] = { case "x" => println("Got x") }
val ffv:Function1[String,Unit] = { case "x" => println("Got x") }
val nfv = { case "x" => println("Got x") }

For the first line, the variable pfv gets assigned a value which is a PartialFunction representing the case statement. For the second line, you might think that, since PartialFunction extends Function1 and we are assigning the same value to ffv as we did to pfv, that the variable ffv would be assigned a value which is a PartialFunction, just as for the value pfv. This is not the case.

The Scala Language Specification (SLS) explicitly states, in section 8.5, that the type of an anonymous function comprised of one or more case statements must be specified as either a FunctionK or a PartialFunction, and that the value generated by the compiler is different depending on that specified target type. So the value that gets assigned to ffv is a Function1, and ffv.isInstanceOf[PartialFunction[_,_]] evaluates to false. Note that we could assign the value pfv to the variable ffv, in which case ffv would have a value which is a PartialFunction and ffv.isInstanceOf[PartialFunction[_,_]] would evaluate to true.

What happens if you don't specify the type, as in the third line above where we assign the same value to nfv? You might think the compiler could infer the type of the resulting value, but since, as specified in the SLS, the type must be explicitly specified as either a FunctionK or a PartialFunction, our assignment to nfv is actually not a valid statement, and it fails to compile. It would be nice if the error message said something like "You must explicitly specify either a FunctionK or a PartialFunction for a case statement", but instead it gives this relatively unhelpful message:

<console>:4: error: missing parameter type for expanded function ((x0$1) => x0$1 match {
  case "x" => println("Got x")
})
       val nfv = { case "x" => println("Got x") }
                ^

In my case, the situation in which I encountered this message was a little different. Here is an example showing the problem I ran into:

class PF[T] {          //partial function type
    def sub(x:PartialFunction[T,Unit]) = x
}
class FF[T] {           //full function type
    def sub(x:Function[T,Unit]) = x
}
class NF[T] {           //no unique function type
    def sub(x:PartialFunction[T,Unit]) = x
    def sub(x:Function[T,Unit]) = x
}

val pf = new PF[String]
val ff = new FF[String]
val nf = new NF[String]

pf.sub{ case "x" => println("x") }   //works, result is PartialFunction
ff.sub{ case "x" => println("x") }   //works, result is Function1
nf.sub{ case "x" => println("x") }   //fails with compiler error msg

Calling the above method sub with a case statement works when there is only one method of that name, whether it takes a Function1 or a PartialFunction, but although the compiler has no problem compiling the overloaded pair of functions, once they both exist the compiler can no longer unambiguously determine the target type for the case statement, so it delivers that same error message "missing parameter type for expanded function".

In my case I was trying to modify the subscribe method in my Publisher class so that I could pass in either a regular function, such as println(_), or a PartialFunction, in particular an in-line case statement. The three options I tried are essentially classes PF, FF and NF listed above. When I used approach NF I was unable to directly pass in a case statement, but instead would get the compiler error mentioned above. When I used approach PF I could pass in a case statement as a PartialFunction, but I could not pass in a regular function. When I used approach FF I could pass in a regular function, and could pass in and properly deal with a PartialFunction, since it extends Function1, but when I used an in-line case statement it would get compiled as a Function1 rather than a PartialFunction, which would cause execution to fail when a value was passed to that case statement that it did not cover (since it was not a PartialFunction and thus did not have an isDefinedAt method to call first).

I don't like option FF because it would allow code (specifically, an in-line case statement) to compile but then not execute as expected. Options PF and NF are not very useful as is, since neither directly supports both case statements and full functions.

In a mailing list response to someone who was attempting to use option NF in his application, Paul Phillips suggested using option FF with a helper function pf that accepts a PartialFunction and returns the same value, then wrapping any case statements inside a call to that helper function; or, alternatively, assigning the case statement to a val declared as a PartialFunction before passing it to method sub. Unfortunately, if the user forgets to use either of these techniques on a case statement and just passes it directly to method sub in option FF, it will be handled as a Function1 rather than a PartialFunction, so it will compile but not behave as expected.

Paul's suggestion would also work in option NF (and in option PF, although in that case it would be redundant), which would behave much the same as option FF from the user's perspective except that passing a bare case statement to the overloaded method sub would not compile, so we would no longer have the undesirable situation of something that compiles but behaves unexpectedly.

As an alternative to Paul's pf helper function, I could write a helper function ff that takes a Function1 and turns it into a PartialFunction with an isDefinedAt method that always returns true. I would then use this with option PF. This would allow me to directly pass in case statements, but I would have to wrap all regular functions in a call to ff.

I have not yet made any changes to my Publisher class, since I don't particularly like either of the options and I don't currently really need the ability to use in-line case statements. Meanwhile, if I get the compiler error "missing parameter type for expanded function" while trying to use an in-line case statement, at least I now know one more thing to check for.

A Simple Publish/Subscribe Example in Scala

2009-10-07T07:27:00.000-07:00

Here is an example where using a simple publish/subscribe mechanism allowed me to clean up some of my early Scala code.

My Mimprint program (now also on github) was originally written in Java, then ported to Scala soon after I first started learning that language. As such, much of that original ported code was "Java written in Scala". As I have continued to internalize the Scala approach I have gone back and modified various parts of the program to make it cleaner.

In one part of the program I set up a collection of menu checkboxes to allow the user to enable or disable various features. As those features are enabled or disabled, the states of other screen components change; sometimes a component is enabled or disabled, sometimes a component is hidden or made visible.

My original Java-ish Scala code to do this looked something like this (with irrelevant parts omitted):

class ViewListGroup ... {
    ...
    private var singleComp:Component = _
    private var mShowFileInfo:SCheckBoxMenuItem = _
    private var mShowFileIcons:SCheckBoxMenuItem = _
    private var mShowDirDates:SCheckBoxMenuItem = _
    private var mShowSingleViewer:SCheckBoxMenuItem = _

    def getComponent():Component = {
        ...
        singleComp = playViewSingle.getComponent()
        ...
        //Add our menu items
        mShowFileInfo = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowFileInfo")(
                    showFileInfo(mShowFileInfo.getState))
        mShowFileInfo.setState(true)
        m.add(mShowFileInfo)

        mShowFileIcons = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowFileIcons")(
                    showFileIcons(mShowFileIcons.getState))
        mShowFileIcons.setState(false)
        m.add(mShowFileIcons)

        mShowDirDates = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowDirDates")(
                    showDirDates(mShowDirDates.getState))
        mShowDirDates.setState(playViewList.includeDirectoryDates)
        ...
        m.add(mShowDirDates)

        mShowSingleViewer = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowSingleViewer")(
                    showSingleViewer(mShowSingleViewer.getState))
        mShowSingleViewer.setState(true)
        m.add(mShowSingleViewer)
        showSingleViewer(mShowSingleViewer.getState)
                //make sure window state is in sync with menu item state
        ...
    }
    ...

    def showFileInfo(b:Boolean) {
        playViewList.showFileInfo(b)
        mShowFileInfo.setState(b)
        mShowFileIcons.setEnabled(b)
        mShowDirDates.setEnabled(b)
    }

    def showFileIcons(b:Boolean) {
        playViewList.showFileIcons(b)
        playViewList.redisplayList()
    }

    def showDirDates(b:Boolean) {
        playViewList.includeDirectoryDates = b
        playViewList.redisplayList()
    }

    def showSingleViewer(b:Boolean) {
        singleComp.setVisible(b)
        singleComp.getParent.asInstanceOf[JSplitPane].resetToPreferredSizes()
        mShowSingleViewer.setState(b)
        playViewList.requestSelect
    }
    ...
}

There were two things about this code that I didn't like:

Mutable instance variables using var, particularly since they were not really variable. These values were being assigned once, not at construction time, but had to be available to other methods.
The close binding between the different UI components, since the action method called by one component directly modified attributes of possibly a number of other components.

After a recent conversation with a friend I realized that I could probably improve this code by using a publish/subscribe mechanism to loosen the coupling between the components. Mimprint already had an ActorPublisher class, where each subscriber is an Actor that accepts messages of the published object type, but in this case I wanted a lighter weight implementation, since I knew the subscriber actions would be quick. Also, this being Swing, the subscriber actions that update screen state should run in the Swing event thread, and the events being published are also coming from the event thread, so the simple thing to do is to run the subscriber actions directly from the publish method.

Writing a publish/subscribe handler in Scala is pretty easy, and for me it was even simpler, as I already had one. I grabbed my ListenerManager and modified it to use the publish/subscribe terminology. I also added synchronization to make it multi-thread safe, although for this app I don't really need it. It now looks like this:

package net.jimmc.util

/** Manage a subscriber list.
 * There are no guarantees on the order of subscribers in the list.
 * This code is a slightly modified version of ListenerManager
 * as published to my blog in April 2009.
 */
trait Publisher[E] {
    type S = (E) => Unit
    private var subscribers: List[S] = Nil
    private object lock
        //By using lock.synchronized rather than this.synchronized we reduce
        //the scope of our lock from the extending object (which might be
        //mixing us in with other classes) to just this trait.

    /** True if the subscriber is already in our list. */
    def isSubscribed(subscriber:S) = {
        val subs = lock.synchronized { subscribers }
        subs.exists(_==subscriber)
    }

    /** Add a subscriber to our list if it is not already there. */
    def subscribe(subscriber:S) = lock.synchronized {
        if (!isSubscribed(subscriber))
            subscribers = subscriber :: subscribers
    }

    /** Remove a subscriber from our list.  If not in the list, ignored. */
    def unsubscribe(subscriber:S):Unit = lock.synchronized {
        subscribers = subscribers.filter(_!=subscriber)
    }

    /** Publish an event to all subscribers on the list. */
    def publish(event:E) = {
        val subs = lock.synchronized { subscribers }
        subs.foreach(_.apply(event))
    }
}

For each menu checkbox I would like to set up a publisher. In every case, I just need to publish whether that checkbox has just been enabled or disabled. I defined a simple case class hierarchy to represent the Enabled and Disabled messages:

sealed abstract class Abled
case object Enabled extends Abled
case object Disabled extends Abled

I then created a publisher class that uses that event type:

class AbledPublisher extends Publisher[Abled]

I want to easily publish the Enabled or Disabled object based on the current state of a checkbox, so I added an AbledPublisher companion object with an apply method to do that:

object AbledPublisher {
    object Abled { def apply(b:Boolean) = if (b) Enabled else Disabled }
}

Conversely, upon receiving an Abled event in a subscriber for a UI component I want to be able to enable or disable that component. I could use a match statement with cases for Enabled and Disabled, but a simpler way is to modify the Abled case class hierarchy to encode a boolean state value into the Abled case object to allow easy translation from an Abled object back to a state:

sealed abstract class Abled { val state:Boolean }
case object Enabled extends Abled { override val state = true }
case object Disabled extends Abled { override val state = false }

Finally, I packaged up the case class hierarchy inside the AbledPublisher object to control scoping. The final AbledPublisher file looks like this:

package net.jimmc.util

//For subscribers of things that turn on and off
class AbledPublisher extends Publisher[AbledPublisher.Abled]

// use "import AbledPublisher._" to pick up these definitions
object AbledPublisher {

    sealed abstract class Abled { val state:Boolean }
    case object Enabled extends Abled { override val state = true }
    case object Disabled extends Abled { override val state = false }

    object Abled { def apply(b:Boolean) = if (b) Enabled else Disabled }
}

Given the above AbledPublisher class and object, I modified my code so that the action method called by each menu checkbox publishes an Enabled or Disabled event that matches the new state of the checkbox, and for each place in the old code where an action method called a state-changing method on another component I set up that target component as a subscriber to the appropriate publisher that, when it receives a published event, takes appropriate action on itself.

With the above changes, and a slight change to my SCheckBoxMenuItem class so that it passes itself to the action callback, the code now looks like this:

import net.jimmc.util.AbledPublisher
import net.jimmc.util.AbledPublisher._

class ViewListGroup ... {
    vlg:ViewListGroup =>
    ...
    private val showFileInfoPublisher = new AbledPublisher
    private val showSingleViewerPublisher = new AbledPublisher
    private val showDirectoriesPublisher = new AbledPublisher
    ...

    def getComponent():Component = {
        ...
        val singleComp = playViewSingle.getComponent()
        showSingleViewerPublisher.subscribe((ev)=> {
            singleComp.setVisible(ev.state)
            singleComp.getParent.asInstanceOf[JSplitPane].resetToPreferredSizes()
        })
        ...
        //Add our menu items
        val mShowFileInfo = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowFileInfo")((cb)=>
                    showFileInfo(cb.getState))
        mShowFileInfo.setState(true)
        showFileInfoPublisher.subscribe((ev)=>
            mShowFileInfo.setState(ev.state)
        )
        m.add(mShowFileInfo)

        val mShowFileIcons = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowFileIcons")((cb)=>
                    showFileIcons(cb.getState))
        mShowFileIcons.setState(false)
        showFileInfoPublisher.subscribe((ev)=>
            mShowFileIcons.setState(ev.state)
        )
        m.add(mShowFileIcons)

        val mShowDirDates = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowDirDates")((cb)=>
                    showDirDates(cb.getState))
        mShowDirDates.setState(playViewList.includeDirectoryDates)
        mShowDirDates.setVisible(includeDirectories)
        showFileInfoPublisher.subscribe((ev)=>
            mShowDirDates.setState(ev.state)
        )
        showDirectoriesPublisher.subscribe((ev)=>
            mShowDirDates.setVisible(ev.state)
        )
        m.add(mShowDirDates)

        val mShowSingleViewer:SCheckBoxMenuItem = new SCheckBoxMenuItem(
                viewer,"menu.List.ShowSingleViewer")((cb)=>
                    showSingleViewer(cb.getState))
        mShowSingleViewer.setState(true)
        showSingleViewerPublisher.subscribe((ev)=>
            mShowSingleViewer.setState(ev.state)
        )
        m.add(mShowSingleViewer)
        showSingleViewer(mShowSingleViewer.getState)
                //make sure window state is in sync with menu item state
        ...
    }
    ...

    def showFileInfo(b:Boolean) {
        playViewList.showFileInfo(b)
        showFileInfoPublisher.publish(Abled(b))
    }

    def showFileIcons(b:Boolean) {
        playViewList.showFileIcons(b)
        playViewList.redisplayList()
    }

    def showDirDates(b:Boolean) {
        playViewList.includeDirectoryDates = b
        playViewList.redisplayList()
    }

    def showSingleViewer(b:Boolean) {
        showSingleViewerPublisher.publish(Abled(b))
        playViewList.requestSelect
    }
    ...
}

The total number of lines of code in ViewListGroup is actually a bit more than before, but I find the code a little easier to understand because all of the code that acts on a UI component is now localized in one place in the source file. All of the vars that held pointers to those components are now gone, replaced by a few vals for the publishers. The publishers use vars to maintain internal state, but that state is simple and easily understood, well encapsulated and multi-thread safe.

There is still more cleanup work to be done in Mimprint. For example, in the above code the checkbox action methods such as showFileInfo and showFileIcons call methods on the playViewList object as well as publishing an Abled event. Instead, I could set up playViewList as a listener on each of the published events, then make the menu checkbox actions directly publish an event and get rid of the showXXX methods. I will leave that for another round of cleanup.

Initializing Immutable Variables in Scala

2009-10-01T21:53:00.000-07:00

One of the guidelines I picked up when I learned Scala is to use immutable variables as much as possible. Besides the trivial but satisfying detail of making the declaration of an immutable variable (val) take no more characters than a mutable one (var), Scala also provides some interesting ways to set the values into those immutable variables.

In Scala, immutable variables are identified by declaring them using the val keyword rather than var. In Java, immutable variables are identified by adding the final qualifier to the variable declaration. But a Java final variable has slightly different semantics than a Scala val: in Java, you can declare a final variable without specifying a value for it, then fill in the value later. Java allows the variable to be assigned once, after which it can not be assigned again. In Scala, a concrete val must have its value assigned as part of the definition.

Consider this sample Java class, Interval, which represents an interval on the real number line. We want to allow the constructor to be called with endpoints in either order, but we want to store them internally in sorted order.

//Java code
public class Interval {
    final double start;
    final double end;  //invariant: end>=start

    public Interval(double x1, double x2) {
        if (x1>x2) {
            start = x2;
            end = x1;
        } else {
            start = x1;
            end = x2;
        }
    }

    //other methods that use start and end go here
}

If you try this idiom in Scala, by replacing each final variable with a val but continuing to use the same initialization construct, you will get a compiler error "reassignment to val". When using a concrete val in Scala, you must supply the value in the statement where you declare the val.

For relatively simple cases, as in this example, we can take advantage of the fact that Scala allows us to build expressions with if in them, so we can express the same functionality as in the above Java code as follows:

class Interval(x1:Double, x2:Double) {
    val start = if (x2>x1) x1 else x2
    val end   = if (x2>x1) x2 else x1

    //other methods that use start and end go here
}

Sometimes the logic to calculate the values for the immutable variables is much more complicated than this and more expensive to calculate. Perhaps, as in our Java example, we don't want to recalculate that condition over again for each variable. We might also be more comfortable building up our values using mutable variables. We could take the easy and straightforward way and just use var rather than val for our variables, but it is worth a bit of effort to retain the immutability of our variables. Here is an approach I sometimes take:

class Interval(x1:Double, x2:Double) {
    val (start, end) = {
        def intervalNeedsReversing(a:Double,b:Double) = (a>b)
        if (intervalNeedsReversing(x1,x2))
            (x2, x1)
        else
            (x1, x2)
    }

    //other methods that use start and end go here
}

In the above approach, we have a block of code that calculates our values. Though not needed in this case, the intervalNeedsReversing function is an example of how you you can define functions within a block in order to refactor that code or better organize it. The value of the block is a tuple, which we then assign using a tuple-assignment to our immutable variables start and end.

A tuple-assignment is a pattern-matching operation that pulls apart the tuple data and stores each piece into the separate variables. It looks like the second line in this example:

val t2 = (123, "abc") //the type of t2 is Tuple2[Int, java.lang.String]
val (n, s) = t2  //assigns n=123, s="abc"

You can use any expression in place of t2 that has the same type, including a function call, a variable, a literal tuple, or a code block.

You can include a type on each variable name; if the types of the assigned variables don't match the corresponding types of the value on the right hand side, you will get a compiler error.

val (n:Int, s:String) = t2 //ok
val (s:String, n:Int) = t2 //error

The tuple syntax of parentheses around a comma-separated list of values is actually a shorthand for the TupleN class. For each pair of lines below, the first line is a shorthand ("syntactic sugar") for the second.

(a, b)
Tuple2(a, b)

(1, "x", "y")
Tuple3(1, "x", "y")

val (n, s) = t2
val Tuple2(n, s) = t2

The last of the three examples above is a pattern-matching assignment statement.

You can use the List pattern in an assignment as well:

val a :: b :: c = List(1,2,3,4)
    //This assigns a:Int=1, b:Int=2, c:List[Int]=List(3,4)

The List and Tuple classes can be used in a pattern-matching assignment like this because they each have an extractor defined by the unapply method in their companion object. You can use any extractor (that is, any declared object that includes an unapply method) in this way. For example, a case class can be used:

case class Foo(num:Int, str:String)
val f = Foo(42,"ok")
val Foo(n,s) = f //assigns n:Int=42, s:String="ok"

This works even if the case class happens to use mutable fields: the values at the time of the pattern match assignment are set into the new variables, which are immutable.

case class Bar(var num:Int, var str:String)
val b = Bar(42,"ok")
b.num += 1
b.str = "no"
val Bar(n,s) = b //assigns n:Int=43, s:String="no"
b.num += 1              //does not change n

For example, if you have a large number of values to set at once, you could declare a case class to represent them, and match on that to assign the values:

class AnotherExample {
    case class MyArgs(var name:String, var pathPart:String, var someNumber:Int)
    val MyArgs(path, part, num) = {
        val m = MyArgs("/path/foo/bar", "partX", 123)
        //change values of fields in m as desired
        m
    }
}

You thus get the benefit of having immutable variables for use in your constructed object, but you can use mutable private data within the block to make it easier to do your construction.

You can use this technique to initialize immutable variables within a method as well. Effectively, you are using mutable variables only for the limited scope in which they are desired. By enclosing them in a block you prevent code outside that block from modifying those mutable values.

Since this technique is based on pattern matching, you can use it with any legal pattern. Pattern matching is typically used in the case clauses of match statements.

Patterns can include nested constructs, which allows you to pull out values from deep within a structure when that structure is known. By using the @ operator within a pattern you can extract the value of an entire subpattern:

case class Foo(n:Int, var s:String)
case class Baz(f:Foo, b:Option[Baz])
val data = 123 :: Baz(Foo(3,"c"),Some(Baz(Foo(4,"d"),None))) :: 456 :: Nil

val _ :: Baz(Foo(_,a),Some(b @ Baz(c @ Foo(d,e),_))) :: f :: _ = data
// The above val statement assigns these values:
// a = "c"
// b = Baz(Foo(4,"d"),None)
// c = Foo(4,"d")
// d = 4
// e = "d"
// f = 456

The undersccore indicates a placeholder for a part of the pattern whose value we don't care about and don't want assigned to anything.

Note that the variable c refers to the same object as the Foo object that appears in variable b. We defined Foo with a var for s. If we change the value of the Foo object referenced by variable c, then we will see that change when we ask for the value of variable b:

scala> b
res0: Baz = Baz(Foo(4,d),None)

scala> c
res1: Foo = Foo(4,d)

scala> c.s = "x"

scala> c
res2: Foo = Foo(4,x)

scala> b
res3: Baz = Baz(Foo(4,x),None)

Although b and c are themselves immutable variables, if they point to the same mutable object then changes made to that object through one variable will be visible through the other variable.

As you learn Scala and see examples of case statements, remember that any syntax that is valid as the pattern match in a case statement is also valid as a pattern match in a val assignment.

Type Safe Builder in Scala, Part 4

2009-09-10T21:24:00.001-07:00

A type-safe builder with mutually exclusive parameters.

In my previous three posts I presented various versions of a type-safe builder that enforced, at compile time, that required setters were called exactly once and optional setters were called no more than once. In those examples there was a one-to-one correspondence between the setters (such as withBrand) and type variables that were used to enforce the number of calls to those methods (such as HAS_BRAND). We can use the type variables in different ways to change what combination of methods calls is allowed. In particular, we can have multiple parameters which can be set in various combinations, only some of which are allowed. For example, we can have two mutually exclusive parameters, where you must set either one but not the other.

To show how this works, I have created a builder for a Pyramid calculator that can be used to calculate the physical parameters of a rectangular pyramid. After creating a builder, you can call various setter methods to set some of the physical parameters of the pyramid, including the length, width and area of the base, the height, and the length of an upright edge. You must set exactly two out of three of the length, width and area of the base, and you must set one but not both of the height and edge. Once you have done that, you call build to get back the calculator from which you can retrieve any of the five physical parameters listed above plus volume. If you call too few or too many of the setters in each group, the call to build will not compile.

object Pyramid {

    //A small collection of class types to define a state machine that counts
    abstract class COUNTER              { type Count <: COUNTER }
    abstract class MANY extends COUNTER { type Count = MANY }
    abstract class TWO  extends COUNTER { type Count = MANY }
    abstract class ZERO_OR_ONE extends COUNTER
    abstract class ONE  extends ZERO_OR_ONE { type Count = TWO }
    abstract class ZERO extends ZERO_OR_ONE { type Count = ONE }

    //We require positive values for our calls
    class Positive(val d:Double) {
        if (d<=0) throw new IllegalArgumentException("non-positive value")
    }
    implicit def doubleToPositive(d:Double) = new Positive(d)
    implicit def intToPositive(n:Int) = new Positive(n)

    //The class that manages the state of our specification
    class Specs private[Pyramid]() { self:Specs =>
        //Caller must set exactly two out of three of these
        val length:Double = 0
        val width:Double = 0
        val area:Double = 0

        //Caller must set exactly one of these two heights
        val height:Double = 0   //vertical height to the tip
        val edge:Double = 0     //from base to tip along an edge

        //We maintain compiler-time state to count the two types of calls
        type TT <: {
            type COUNT_LENGTH <: COUNTER
            type COUNT_WIDTH <: COUNTER
            type COUNT_AREA <: COUNTER
            type COUNT_BASE <: COUNTER          // length, width or area
            type COUNT_HEIGHT <: COUNTER
            type COUNT_EDGE <: COUNTER
            type COUNT_VERT <: COUNTER          // height or edge
        }

        class SpecsWith(bb:Specs) extends Specs {
            override val length = bb.length
            override val width = bb.width
            override val area = bb.area
            override val height = bb.height
            override val edge = bb.edge
        }

        def setLength(d:Positive) = new SpecsWith(this) {
            override val length:Double = d.d
            type TT = self.TT {
                type COUNT_LENGTH = self.TT#COUNT_LENGTH#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setWidth(d:Positive) = new SpecsWith(this) {
            override val width:Double = d.d
            type TT = self.TT {
                type COUNT_WIDTH = self.TT#COUNT_WIDTH#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setArea(d:Positive) = new SpecsWith(this) {
            override val area:Double = d.d
            type TT = self.TT {
                type COUNT_AREA = self.TT#COUNT_AREA#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setHeight(d:Positive) = new SpecsWith(this) {
            override val height:Double = d.d
            type TT = self.TT {
                type COUNT_HEIGHT = self.TT#COUNT_HEIGHT#Count
                type COUNT_VERT = self.TT#COUNT_VERT#Count
            }
        }

        def setEdge(d:Positive) = new SpecsWith(this) {
            override val edge:Double = d.d
            type TT = self.TT {
                type COUNT_EDGE = self.TT#COUNT_EDGE#Count
                type COUNT_VERT = self.TT#COUNT_VERT#Count
            }
        }

    }

    //Starting point: nothing is set
    def apply() = new Specs {
        type TT = {
            type COUNT_LENGTH = ZERO
            type COUNT_WIDTH = ZERO
            type COUNT_AREA = ZERO
            type COUNT_BASE = ZERO
            type COUNT_HEIGHT = ZERO
            type COUNT_EDGE = ZERO
            type COUNT_VERT = ZERO
        }
    }

    //Required ending point: two base measures, one height measure,
    //no single parameter more than once
    type CompleteSpecs = Specs {
        type TT <: {
            type COUNT_LENGTH <: ZERO_OR_ONE
            type COUNT_WIDTH <: ZERO_OR_ONE
            type COUNT_AREA <: ZERO_OR_ONE
            type COUNT_BASE = TWO
            type COUNT_HEIGHT <: ZERO_OR_ONE
            type COUNT_EDGE <: ZERO_OR_ONE
            type COUNT_VERT = ONE
        }
    }

    //Calc1 includes the first set of values that can be calculated
    class Calc1 private[Pyramid](spec:CompleteSpecs) {
        import java.lang.Math.sqrt

        //The three related base measures
        lazy val length = if (spec.length!=0) spec.length
                          else spec.area/spec.width
        lazy val width =  if (spec.width!=0) spec.width
                          else spec.area/spec.length
        lazy val area =   if (spec.area!=0) spec.area
                          else spec.length*spec.width

        //The two related height measures
        lazy val height = if (spec.height!=0) spec.height
            else sqrt(spec.edge*spec.edge-length*length/4-width*width/4)
        lazy val edge =   if (spec.edge!=0) spec.edge
            else sqrt(length*length/4+width*width/4+spec.height*spec.height)

        lazy val volume = length * width * height / 3
    }

    implicit def specsOK(spec:CompleteSpecs) = new {
        def build = new Calc1(spec)
    }

}

As before, remember to import Pyramid._ when using this code.

Let's examine the code.

To start, I have a small type-based state machine, similar to what I used in my previous post. I changed the names of the classes to more accurately reflect the fact that I am counting the number of calls to methods, and I added a class to represent a count of two as distinct from larger numbers.

Next I define a class that ensures that the values passed to the setters are all strictly positive numbers (since they represent physical quantities), and I add a couple of implicit conversion methods to allow the caller to pass in ints or doubles. If the caller passes in a negative number, the builder will throw a runtime exception.

The Specs class is where I maintain my state information as the builder is being constructed. I use the same basic approach as in my previous post, with a set of parameter values and a set of compile-time constraints, the latter represented by the TT compound type. Note that in addition to the type parameter values that are directly associated with the parameters, which are used to ensure that each individual setter is called not more than once, there are two additional type values that do not directly correspond to parameter values or individual setters. The COUNT_BASE type value is associated with the length, width and area parameters, while the COUNT_VERT type value is associated with the height and edge parameters. This association is specified in the setter methods.

The SpecsWith class allows me to default all values to the previous step in the builder chain, so that I can override just the value I want to change in each setter.

Each of the five setters sets its parameter value, sets a new value for its individual type value counter, and also sets a new type value for one of the non-individual counters. Note how the setters for length, width and area all refer to COUNT_BASE, while the setters for height and edge both refer to COUNT_VERT.

I chose to define an apply() method rather than call it builder. This allows me to start my builder chain by specifying just Pyramid().

The CompleteSpecs type definition defines the end point that will be valid for a call to build. You can see here how it requires that COUNT_BASE be TWO and COUNT_HEIGHT be ONE. The other call counts can be zero or one.

Calc1 is the class that actually does the calculation of the physical parameters.

Finally, the specsOK implicit method provides the link that allows only a complete builder to call the build method that returns the calculator.

Here is an example of how you use it:

import Pyramid._       //we need the implicit conversion to be in scope
val p = Pyramid().setLength(10).setWidth(8).setHeight(6).build
p.length                //returns 10
p.area                  //returns 80
p.volume                //returns 160

Each of the following will give a compiler error:

Pyramid().setWidth(2).setHeight(2).build        //only one BASE param, need 2
Pyramid().setWidth(2).setLength(3).setArea(6).setHeight(2).build  //too many BASE params
Pyramid().setWidth(2).setWidth(3).setHeight(2).build  //setWidth called twice

Note the second example: even though the base area (6) is compatible with the width and length, this line gives a compiler error because three BASE parameters were specified; the compile time checks do not look at the values of the parameters.

Let's add a parameter for density such that, if we have called the setter for density, we can get back a calculator that can tell us the mass of the pyramid as well as everything else. The code below shows, in bold, what needs to be added to the above example in order to do that.

object Pyramid {

    //A small collection of class types to define a state machine that counts
    abstract class COUNTER              { type Count <: COUNTER }
    abstract class MANY extends COUNTER { type Count = MANY }
    abstract class TWO  extends COUNTER { type Count = MANY }
    abstract class ZERO_OR_ONE extends COUNTER
    abstract class ONE  extends ZERO_OR_ONE { type Count = TWO }
    abstract class ZERO extends ZERO_OR_ONE { type Count = ONE }

    //We require positive values for our calls
    class Positive(val d:Double) {
        if (d<=0) throw new IllegalArgumentException("non-positive value")
    }
    implicit def doubleToPositive(d:Double) = new Positive(d)
    implicit def intToPositive(n:Int) = new Positive(n)

    //The class that manages the state of our specification
    class Specs private[Pyramid]() { self:Specs =>
        //Caller must set exactly two out of three of these
        val length:Double = 0
        val width:Double = 0
        val area:Double = 0

        //Caller must set exactly one of these two heights
        val height:Double = 0   //vertical height to the tip
        val edge:Double = 0     //from base to tip along an edge

        //Optional value; if set, we can calculate mass
        val density:Double = 0

        //We maintain compiler-time state to count the two types of calls
        type TT <: {
            type COUNT_LENGTH <: COUNTER
            type COUNT_WIDTH <: COUNTER
            type COUNT_AREA <: COUNTER
            type COUNT_BASE <: COUNTER          // length, width or area
            type COUNT_HEIGHT <: COUNTER
            type COUNT_EDGE <: COUNTER
            type COUNT_VERT <: COUNTER          // height or edge
            type COUNT_DENSITY <: COUNTER
        }

        class SpecsWith(bb:Specs) extends Specs {
            override val length = bb.length
            override val width = bb.width
            override val area = bb.area
            override val height = bb.height
            override val edge = bb.edge
            override val density = bb.density
        }

        def setLength(d:Positive) = new SpecsWith(this) {
            override val length:Double = d.d
            type TT = self.TT {
                type COUNT_LENGTH = self.TT#COUNT_LENGTH#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setWidth(d:Positive) = new SpecsWith(this) {
            override val width:Double = d.d
            type TT = self.TT {
                type COUNT_WIDTH = self.TT#COUNT_WIDTH#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setArea(d:Positive) = new SpecsWith(this) {
            override val area:Double = d.d
            type TT = self.TT {
                type COUNT_AREA = self.TT#COUNT_AREA#Count
                type COUNT_BASE = self.TT#COUNT_BASE#Count
            }
        }

        def setHeight(d:Positive) = new SpecsWith(this) {
            override val height:Double = d.d
            type TT = self.TT {
                type COUNT_HEIGHT = self.TT#COUNT_HEIGHT#Count
                type COUNT_VERT = self.TT#COUNT_VERT#Count
            }
        }

        def setEdge(d:Positive) = new SpecsWith(this) {
            override val edge:Double = d.d
            type TT = self.TT {
                type COUNT_EDGE = self.TT#COUNT_EDGE#Count
                type COUNT_VERT = self.TT#COUNT_VERT#Count
            }
        }

        def setDensity(d:Positive) = new SpecsWith(this) {
            override val density:Double = d.d
            type TT = self.TT {
                type COUNT_DENSITY = self.TT#COUNT_DENSITY#Count
            }
        }

    }

    //Starting point: nothing is set
    def apply() = new Specs {
        type TT = {
            type COUNT_LENGTH = ZERO
            type COUNT_WIDTH = ZERO
            type COUNT_AREA = ZERO
            type COUNT_BASE = ZERO
            type COUNT_HEIGHT = ZERO
            type COUNT_EDGE = ZERO
            type COUNT_VERT = ZERO
            type COUNT_DENSITY = ZERO
        }
    }

    //Required ending point: two base measures, one height measure,
    //no single parameter more than once
    type CompleteSpecs = Specs {
        type TT <: {
            type COUNT_LENGTH <: ZERO_OR_ONE
            type COUNT_WIDTH <: ZERO_OR_ONE
            type COUNT_AREA <: ZERO_OR_ONE
            type COUNT_BASE = TWO
            type COUNT_HEIGHT <: ZERO_OR_ONE
            type COUNT_EDGE <: ZERO_OR_ONE
            type COUNT_VERT = ONE
        }
    }

    //Calc1 includes the first set of values that can be calculated
    class Calc1 private[Pyramid](spec:CompleteSpecs) {
        import java.lang.Math.sqrt

        //The three related base measures
        lazy val length = if (spec.length!=0) spec.length
                          else spec.area/spec.width
        lazy val width =  if (spec.width!=0) spec.width
                          else spec.area/spec.length
        lazy val area =   if (spec.area!=0) spec.area
                          else spec.length*spec.width

        //The two related height measures
        lazy val height = if (spec.height!=0) spec.height
            else sqrt(spec.edge*spec.edge-length*length/4-width*width/4)
        lazy val edge =   if (spec.edge!=0) spec.edge
            else sqrt(length*length/4+width*width/4+spec.height*spec.height)

        lazy val volume = length * width * height / 3
    }

    implicit def specsOK(spec:CompleteSpecs) = new {
        def build = new Calc1(spec)
    }

    //Second set of allowable computations
    type CompleteSpecs2 = Specs {
        type TT <: {
            type COUNT_LENGTH <: ZERO_OR_ONE
            type COUNT_WIDTH <: ZERO_OR_ONE
            type COUNT_AREA <: ZERO_OR_ONE
            type COUNT_BASE = TWO
            type COUNT_HEIGHT <: ZERO_OR_ONE
            type COUNT_EDGE <: ZERO_OR_ONE
            type COUNT_VERT = ONE
            type COUNT_DENSITY = ONE
        }
    }

    class Calc2 private[Pyramid](spec:CompleteSpecs2) extends Calc1(spec) {
        lazy val mass = spec.density * volume
    }

    implicit def specsOK2(spec:CompleteSpecs2) = new {
        def build2 = new Calc2(spec)
    }
}

To get the mass, we have to call all of the appropriate setters, including density, then call build2 rather than build to get our calculator. That will give us a calculator that can give us the mass value as well as all the values in the calculator returned by build.

val p = Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).build2
p.volume        //returns 4
p.mass          //returns 8

These examples fail:

Pyramid().setHeight(2).setWidth(3).setArea(6).build2   //no density
Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).setDensity(3).build2
        //density specified twice

I intentionally left out one line when adding the density code, so the following code compiles:

Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).setDensity(3).build

Since the build method returns a calculator that does not do anything with the density, this is perhaps not a problem. You can test your understanding of Scala types by figuring out what one line you need to add to the density example to make this last call fail to compile.

Type Safe Builder in Scala, Part 3

2009-09-09T20:41:00.000-07:00

Another solution to implementing a type-safe builder in Scala.

In my previous two posts I presented a couple of different implementations of the type-safe builder pattern originally presented by Rafeal de F. Ferreira. But there was something about them that bothered me: both of my implementations, both of Rafael's implementations, and gambistics' implementation written in response to my second attempt, all exhibit the same bothersome characteristic: every setter includes references to all of the state information (both type information and parameter values) being built up in the Builder.

I found this to be a very inelegant aspect of these solutions. Given N parameters with their corresponding setters, there is an O(N^2) maintenance problem: every time you add or remove a parameter, or make certain changes to existing parameters, such as changing name or type, you have to make that change in every setter method.

Below is an implementation without any source code interaction between the setters or parameters; each setter only deals with its own data. Adding, removing or changing any parameter and corresponding setter can be done without dealing with any of the other parameters, making this implementation O(N) for N parameters. As with my Part 2 implementation, this implementation handles both optional and required parameters, ensuring at compile time that required setters are called exactly once and optional setters are not called more than once.

object Scotch {

  //A small collection of class types to define a state machine
  abstract class STATE { type TrueOnce <: STATE }
  abstract class NOT_MULTI extends STATE
  abstract class MULTI extends STATE { type TrueOnce = MULTI }
  abstract class TRUE  extends NOT_MULTI { type TrueOnce = MULTI }
  abstract class FALSE extends NOT_MULTI { type TrueOnce = TRUE }

  sealed abstract class Preparation
  case object Neat extends Preparation
  case object OnTheRocks extends Preparation
  case object WithWater extends Preparation

  sealed abstract class Glass
  case object Short extends Glass
  case object Tall extends Glass
  case object Tulip extends Glass

  case class OrderOfScotch private[Scotch] (
        val brand:String, val mode:Preparation,
        val isDouble:Boolean, val glass:Option[Glass])

  class ScotchBuilder private[Scotch]() { self:ScotchBuilder =>
    val theBrand:Option[String] = None
    val theMode:Option[Preparation] = None
    val theDoubleStatus:Option[Boolean] = None
    val theGlass:Option[Glass] = None
    type TT <: {
      type HAS_BRAND <: STATE
      type HAS_MODE <: STATE
      type HAS_DOUBLE <: STATE
      type HAS_GLASS <: STATE
    }

    class ScotchBuilderWith(sb:ScotchBuilder) extends ScotchBuilder {
      override val theBrand = sb.theBrand
      override val theMode = sb.theMode
      override val theDoubleStatus = sb.theDoubleStatus
      override val theGlass = sb.theGlass
    }

    def withBrand(b:String) = new ScotchBuilderWith(this) {
      override val theBrand:Option[String] = Some(b)
      type TT = self.TT { type HAS_BRAND = self.TT#HAS_BRAND#TrueOnce }
    }

    def withMode(p:Preparation) = new ScotchBuilderWith(this) {
      override val theMode:Option[Preparation] = Some(p)
      type TT = self.TT { type HAS_MODE = self.TT#HAS_MODE#TrueOnce }
    }

    def isDouble(b:Boolean) = new ScotchBuilderWith(this) {
      override val theDoubleStatus:Option[Boolean] = Some(b)
      type TT = self.TT { type HAS_DOUBLE = self.TT#HAS_DOUBLE#TrueOnce }
    }
     
    def withGlass(g:Glass) = new ScotchBuilderWith(this) {
      override val theGlass:Option[Glass] = Some(g)
      type TT = self.TT { type HAS_GLASS = self.TT#HAS_GLASS#TrueOnce }
    }
  }

  //Starting point: nothing is set
  lazy val builder = new ScotchBuilder {
    type TT = {
      type HAS_BRAND = FALSE
      type HAS_MODE = FALSE
      type HAS_DOUBLE = FALSE
      type HAS_GLASS = FALSE
    }
  }

  //Required ending point: TRUE for required, NOT_MULTI for optional
  type CompleteBuilder = ScotchBuilder {
    type TT <: {
      type HAS_BRAND = TRUE
      type HAS_MODE = TRUE
      type HAS_DOUBLE = TRUE
      type HAS_GLASS <: NOT_MULTI
    }
  }

  implicit def enableBuild(builder:CompleteBuilder) = new {
    def build() = new OrderOfScotch(
            builder.theBrand.get, builder.theMode.get,
            builder.theDoubleStatus.get, builder.theGlass);
  }

}

It actually took me quite a while to come up with this solution. I spent a lot of time trying different things that almost worked. Scala's type system is powerful, but debugging is a bear.

Type Safe Builder in Scala, Part 2

2009-09-07T09:17:00.000-07:00

Here is a way to limit the number of calls to each setter method in a builder without using Church Numerals.

Update 2009-09-09: See also Part 3, which shows an O(N) implementation.

Copyright Note: The code in this post may not be covered by the LGPL.

The BuilderPattern code is a derivative of code posted by Rafael de F. Ferreira, so is covered by his copyright.

All code is used here for educational purposes under Fair Use.

A number of people commented in response to Rafael's original post that this type-safe builder approach (of explicitly using types to track desired behavior at compile-time) is much more complicated than a simple builder class in which the required parameters are constructor args to the builder, and the optional parameters are setters. Of course that's true, and with named parameters and default values coming in Scala 2.8, defining and using such builders can be even simpler. But, besides the fact that the type-safe approach can be used in more complex builders in which the constructor approach does not work well, the issue is not relevant, because the main point of this exercise is to see how Scala's type system can be used to do interesting things.

In my previous blog post I showed how to use Church Numerals to limit (at compile time) calls to setters to no more than once per setter. Using Church Numerals was handy for me because I already had them, so it was easy to switch from booleans to integers to keep track of how many times a setter was called.

Keeping count of calls this way could be useful in some context, but in this case all I was doing was ensuring that an item was called no more than once. Also, the recommendation I made in my closing paragraph to use multiple implicit conversion functions to deal with optional setters does not scale well when there are multiple optional setters.

Below is a simpler approach that ensures that required setters are called exactly once, that optional setters are called not more than once, that doesn't require Church Numerals, and that uses only a single implicit conversion method. As before, my changes from Rafael's original are in bold.

object BuilderPattern {
  sealed abstract class Preparation
  case object Neat extends Preparation
  case object OnTheRocks extends Preparation
  case object WithWater extends Preparation

  sealed abstract class Glass
  case object Short extends Glass
  case object Tall extends Glass
  case object Tulip extends Glass

  case class OrderOfScotch private[BuilderPattern] (val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])

  abstract class STATE { type TrueOnce <: STATE }
  abstract class NOT_MULTI extends STATE
  abstract class MULTI extends STATE { type TrueOnce = MULTI }
  abstract class TRUE  extends NOT_MULTI { type TrueOnce = MULTI }
  abstract class FALSE extends NOT_MULTI { type TrueOnce = TRUE }

  abstract class ScotchBuilder { self:ScotchBuilder =>
    protected[BuilderPattern] val theBrand:Option[String]
    protected[BuilderPattern] val theMode:Option[Preparation]
    protected[BuilderPattern] val theDoubleStatus:Option[Boolean]
    protected[BuilderPattern] val theGlass:Option[Glass]

    type HAS_BRAND <: STATE
    type HAS_MODE <: STATE
    type HAS_DOUBLE_STATUS <: STATE
    type HAS_GLASS <: STATE

    def withBrand(b:String) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = Some(b)
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND#TrueOnce
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
      type HAS_GLASS = self.HAS_GLASS
    }

    def withMode(p:Preparation) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = Some(p)
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE#TrueOnce
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
      type HAS_GLASS = self.HAS_GLASS
    }

    def isDouble(b:Boolean) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = Some(b)
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS#TrueOnce
      type HAS_GLASS = self.HAS_GLASS
    }
     
    def withGlass(g:Glass) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = Some(g)

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
      type HAS_GLASS = self.HAS_GLASS#TrueOnce
    }

  }

  type CompleteBuilder = ScotchBuilder {
    type HAS_BRAND = TRUE
    type HAS_MODE = TRUE
    type HAS_DOUBLE_STATUS = TRUE
    type HAS_GLASS <: NOT_MULTI
  }

  implicit def enableBuild(builder:CompleteBuilder) = new {
    def build() = 
      new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);
  }

  def builder = new ScotchBuilder {
    protected[BuilderPattern] val theBrand:Option[String] = None
    protected[BuilderPattern] val theMode:Option[Preparation] = None
    protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = None
    protected[BuilderPattern] val theGlass:Option[Glass] = None

    type HAS_BRAND = FALSE
    type HAS_MODE = FALSE
    type HAS_DOUBLE_STATUS = FALSE
    type HAS_GLASS = FALSE
  }
}

As before, remember to import BuilderPattern._ to ensure that the implicit conversion method is in scope when using this patterm.

The changes are straightforward:

I added the HAS_GLASS type to track the state of the number of calls to the withGlass method. It is coded in exactly the same way as the other state tracking types with the one exception of its value in the CompleteBuilder type. The CompleteBuilder type encodes which parameters are optional and which are required.
Rather than having two states (just TRUE and FALSE), I am using a little class hierarchy with three states, representing no calls to a setter (FALSE), one call to a setter (TRUE), and more than one call to a setter (MULTI).
Instead of just setting a state to TRUE when a setter is called, I am using a type member of the current state to implement a little state machine. The state machine transitions from FALSE to TRUE to MULTI and then stays in the MULTI state.
The TRUE and FALSE states are in a separate subtree NOT_MULTI so that I can specify a value that includes either of those states, but not the MULTI state. I use this value in the CompleteBuilder type to specify that the HAS_GLASS value can be either TRUE or FALSE.

Bottom line: this implementation provides compile-time checking that the required setters are called exactly once, that the optional setters are called at most once, and is much simpler than the Church Numerals implementation.

Type Safe Builder in Scala Using Church Numerals

2009-09-06T20:49:00.000-07:00

I present another possibly practical application of Church Numerals in Scala.

Update 2009-09-07: See also Part 2, which shows similar functionality without using Church Numerals.

Update 2009-09-09: See also Part 3, which shows an O(N) implementation.

Copyright Note: The code in this post may not be covered by the LGPL.

The BuilderPattern code is a derivative of code posted by Rafael de F. Ferreira, so is covered by his copyright.

The Church Numerals code is from my Practical Church Numerals blog post; see that post for copyright information.

All code is used here for educational purposes under Fair Use.

Recently I came across an article by Rafael de F. Ferreira, and a followup article with an alternate approach, on how to implement the Builder pattern in Scala in a way that is type-safe. In particular, his implementation allows for compile-time checking to ensure that each required field has been set by a call to a setter (in Rafael's code, the withXXX methods) in the Builder object. If the developer fails to call all of the required methods, the application will not compile. The error messages given by the compiler in this case are not necessarily clear, but I like the concept.

One of the thoughts that crossed my mind was, what happens if you call one of the setter methods twice? Rafael's type-safe code does not prevent that scenario; if the coder puts in two calls to the same setter method, it compiles without problem and calls the setter twice at run time.

Perhaps that is not a concern, but if we can use the compiler to ensure that required setters are called, could we also use it to ensure that setters are called no more than once? Rafael's code uses boolean type values to encode whether or not a value has been set. By using integer values for the types, we can keep a count of how many times a setter has been called. That sounds like a job for Church Numerals.

In my post Practical Church Numerals in Scala I showed how you could encode integers in the Scala type system using the Church Numerals construct, and use those numerals to construct a type-safe units class. We can do something similar here.

First, here is an implementation of Church Numerals taken from that blog posting. See that post for a description of how it works.

object ChurchNumerals {

    trait CInt {
        type Succ <: CInt
        type Add[N <: CInt] <: CInt
    }

    trait CPos extends CInt

    class CSucc[P <: CPos] extends CPos {
        type Succ = CSucc[CSucc[P]]
        type Add[N <: CInt] = P#Add[N]#Succ
    }

    final class _0 extends CPos {
        type Succ = CSucc[_0]
        type Add[N <: CInt] = N
    }

    type +[N1<:CInt, N2<:CInt] = N1#Add[N2]

    type _1 = _0#Succ
    type _2 = _1#Succ
    type _3 = _2#Succ
}

Below is my modified version of the type-safe Builder pattern using Church Numerals instead of booleans for the types. My changes from Rafael's original are in bold.

object BuilderPattern {
  import ChurchNumerals._

  sealed abstract class Preparation
  case object Neat extends Preparation
  case object OnTheRocks extends Preparation
  case object WithWater extends Preparation

  sealed abstract class Glass
  case object Short extends Glass
  case object Tall extends Glass
  case object Tulip extends Glass

  case class OrderOfScotch private[BuilderPattern] (val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])

  //FALSE and TRUE are not used, we use _0 and _1 instead

  abstract class ScotchBuilder { self:ScotchBuilder =>
    protected[BuilderPattern] val theBrand:Option[String]
    protected[BuilderPattern] val theMode:Option[Preparation]
    protected[BuilderPattern] val theDoubleStatus:Option[Boolean]
    protected[BuilderPattern] val theGlass:Option[Glass]

    type HAS_BRAND <: ChurchNumerals.CInt
    type HAS_MODE <: ChurchNumerals.CInt
    type HAS_DOUBLE_STATUS <: ChurchNumerals.CInt

    def withBrand(b:String) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = Some(b)
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND + _1
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
    }

    def withMode(p:Preparation) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = Some(p)
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE + _1
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
    }

    def isDouble(b:Boolean) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = Some(b)
      protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS + _1
    }
     
    def withGlass(g:Glass) = new ScotchBuilder {
      protected[BuilderPattern] val theBrand:Option[String] = self.theBrand
      protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode
      protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus
      protected[BuilderPattern] val theGlass:Option[Glass] = Some(g)

      type HAS_BRAND = self.HAS_BRAND
      type HAS_MODE = self.HAS_MODE
      type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS
    }

  }

  type CompleteBuilder = ScotchBuilder {
    type HAS_BRAND = _1
    type HAS_MODE = _1
    type HAS_DOUBLE_STATUS = _1
  }

  implicit def enableBuild(builder:CompleteBuilder) = new {
    def build() = 
      new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);
  }

  def builder = new ScotchBuilder {
    protected[BuilderPattern] val theBrand:Option[String] = None
    protected[BuilderPattern] val theMode:Option[Preparation] = None
    protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = None
    protected[BuilderPattern] val theGlass:Option[Glass] = None

    type HAS_BRAND = _0
    type HAS_MODE = _0
    type HAS_DOUBLE_STATUS = _0
  }
}
//Remember to use "import BuilderPattern._" in your code

As you can see, I have replaced the use of the boolean values TRUE and FALSE by the Church Numerals _0 and _1. Specifying the CompleteBuilder type as requiring _1 in all the positions ensures that the enableBuild implicit method will only be available if each setter has been called exactly once. You can try this out yourself in the Scala REPL. Copy and paste the above two chunks of code, plus the command import BuilderPattern._ to ensure the implicit conversion is in scope. You can then try the following examples. In particular, the third example contains two calls to withBrand, which fails in this implementation but succeeds in Rafael's original implementation.

builder.withBrand("x").withMode(BuilderPattern.Neat).build       //error
builder.withBrand("x").withMode(BuilderPattern.Neat).isDouble(true).build  //ok
builder.withBrand("x").withMode(BuilderPattern.Neat).isDouble(true).withBrand("y").build  //error

You may have noticed that I did not modify the withGlass method, so that method could be called more than once. If you want to restrict that method to be called zero or one time, you could add a HAS_GLASS type parameter for it, which you would keep track of in exactly the same way as the other three type parameters. The only difference would then be that you would have two flavors of CompleteBuilder, one with type HAS_GLASS = _1 and one with type HAS_GLASS = _0, along with two implicit conversion methods, one for each of the two CompleteBuilder types. This is an example of Rafael's comment that "we can specify any other point in the lattice" as a legal state from which to execute the build method. I leave the implementation of that step as an exercise for the reader.