Planet Scala

1366 x 768 MeeGo tablet coming to Germany in two weeks

SPDE Menger Sierpinski Ball

def debug(msg: => String) {
 if (slf4jLogger.isDebugEnabled) slf4jLogger debug msg
}

class MyClazz extends SomeClazz with Logging
  ...
  logger debug "SLF4S just rocks!"
  ...

Broader redirect handling, support for Google ClientLogin, a JSON extractor for optional properties, and OAuth compatibility with Twitter’s streaming API.

Samsung’s idea of bicycling with technology looks more fun, less authorized than Apple’s

The revamped collections API is one of cornerstones of the recently released Scala version 2.8.
It provides an incredibly rich toolset for working with object collections and as such is one of the most important parts of the Scala runtime library. The Scala team has made an effort to provide thorough documentation uncovering its feature breadth, the most important sources of information...

If copyright violations are just like theft (and they are not, if you think about it for 1.5 seconds), why are the penalties millions of dollars more than for shoplifting?

As a follow-on to Further Understanding scala.Option, following are another 10 exercises (numbered 16 to 25). Included are solutions to the original 1 to 15 exercises. Instructions are in the comments.

// Scala version 2.8.0.final
// http://scala-tools.org/repo-releases/org/scala-tools/testing/scalacheck_2.8.0/1.7/scalacheck_2.8.0-1.7.jar
 
 
/*
 
  PART 1
  ======
  Below are 15 exercises numbered 1 to 15. The task is to emulate the scala.Option API
  without using Some/None subtypes, but instead using a fold (called a
  catamorphism).
 
  A couple of functions are already done (map, get)
  to be used as an example. ScalaCheck tests are given below to
  verify the work. The desired result is to have all tests passing.
 
  The 15th exercise is not available in the existing Scala API so
  instructions are given in the comments.
 
 
  Part 2
  ======
 
  Below are 10 exercises numbered 16 to 25. The task is to implement additional
  methods for the Optional data type. These methods are not provided in the
  scala.Option API so to determine the correct result requires reading the method
  type signature and ensuring that the tests pass.
 
  The 25th exercise is notable in that its signature says nothing about
  scala.Option yet it is usable for Option (see the test for example).
 
 
  Revision History
  ================
 
  23/08/2010
  * Initial revision
 
  ----------------
 
  23/08/2010
  * Fixed prop_getOrElse. Thanks Michael Bayne.
 
  ----------------
 
  26/08/2010
  * Add lazy annotation to orElse method.
 
  ----------------
 
  01/09/2010
  Added Part 2
 
  02/09/2010
  * Fixed mapOptionals test (why wasn't it failing?). Thanks Alec Zorab.
  * Added comments including *** special note ***
 
*/
 
 
trait Optional[A] {
  // single abstract method
  def fold[X](some: A => X, none: => X): X
 
  import Optional._
 
  // Done for you.
  def map[B](f: A => B): Optional[B] =
    fold(f andThen some, none[B])
 
  // Done for you.
  // WARNING: undefined for None
  def get: A =
    fold(a => a, error("None.get"))
 
  // Exercise 1
  def flatMap[B](f: A => Optional[B]): Optional[B] =
    fold(f, none)
 
  // Exercise 2
  // Rewrite map but use flatMap, not fold.
  def mapAgain[B](f: A => B): Optional[B] =
    flatMap(f andThen some)
 
  // Exercise 3
  def getOrElse(e: => A): A =
    fold(s => s, e)
 
  // Exercise 4
  def filter(p: A => Boolean): Optional[A] =
    fold(a => if(p(a)) some(a) else none, none)
 
  // Exercise 5
  def exists(p: A => Boolean): Boolean =
    fold(p, false)
 
  // Exercise 6
  def forall(p: A => Boolean): Boolean =
    fold(p, true)
 
  // Exercise 7
  def foreach(f: A => Unit): Unit =
    fold(f, ())
 
  // Exercise 8
  def isDefined: Boolean =
    fold(_ => true, false)
 
  // Exercise 9
  def isEmpty: Boolean =
    fold(_ => false, true)
 
  // Exercise 10
  def orElse(o: => Optional[A]): Optional[A] =
    fold(_ => this, o)
 
  // Exercise 11
  def toLeft[X](right: => X): Either[A, X] =
    fold(Left(_), Right(right))
 
  // Exercise 12
  def toRight[X](left: => X): Either[X, A] =
    fold(Right(_), Left(left))
 
  // Exercise 13
  def toList: List[A] =
    fold(List(_), Nil)
 
  // Exercise 14
  def iterator: Iterator[A] =
    fold(Iterator.single(_), Iterator.empty)
 
  // Exercise 15 The Clincher!
  // Return a none value if either this or the argument is none.
  // Otherwise apply the function to the argument in some.
  // Don't be afraid to use functions you have written.
  // Better style, more points!
  def applic[B](f: Optional[A => B]): Optional[B] =
    f flatMap map
 
  // Utility
  def toOption: Option[A] = fold(Some(_), None)
 
  // Utility
  override def toString = 
    fold("some[" + _ + "]", "none")
 
  // Utility
  override def equals(o: Any) =
    o.isInstanceOf[Optional[_]] && {
      val q = o.asInstanceOf[Optional[_]]
      fold(a => q.exists(a == _),
           q.isEmpty)
    }
}
 
object Optional {
  // Done for you
  def none[A]: Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = none
  }
 
  // Done for you
  def some[A](a: A): Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = some(a)
  }
 
  // Utility
  def fromOption[A](o: Option[A]): Optional[A] = o match {
    case None    => none
    case Some(a) => some(a)
  }
 
  // *** Special note ***
  // Some of these functions are likely to be familiar List functions,
  // but with one specific distinction: in every covariant value appearing in
  // the type signature, this value is wrapped in Optional.
  // For example, the unwrapped:
  // filter:          (A => Boolean) => List[A] => List[A]
  // and the wrapped:
  // filterOptionals: (A => Optional[Boolean]) => List[A] => Optional[List[A]]
  // 
  // There are other functions of a similar nature below.
 
  // Exercise 16
  // If a none is encountered, then return a none, otherwise,
  // accumulate all the values in Optional.
  def mapOptionals[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Exercise 17
  // If a none is encountered, then return a none, otherwise,
  // accumulate all the values in Optional.
  def sequenceOptionals[A](a: List[Optional[A]]): Optional[List[A]] =
    error("todo")
 
  // Exercise 18
  // Use sequenceOptionals
  def mapOptionalsAgain[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Exercise 19 
  // Use mapOptionals
  def sequenceOptionalsAgain[A](a: List[Optional[A]]): Optional[List[A]] =
    error("todo")
 
  // Exercise 20
  // If a none is encountered, return none, otherwise,
  // flatten/join by one level.
  def joinOptionals[A](a: Optional[Optional[A]]): Optional[A] =
    error("todo")
 
  // Exercise 21
  def filterOptionals[A](p: A => Optional[Boolean], a: List[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 22
  def fillOptionals[A](n: Int, a: Optional[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 23
  // Use sequenceOptionals
  def fillOptionalsAgain[A](n: Int, a: Optional[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 24
  // Methods mentioning Optional in the type signature are prohibited, except applic and map
  def mapOptionalsYetAgain[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Consider: def joinOptional[A](a: Optional[Optional[A]]): Optional[A]
  // This function "flattens" the Optional into a Some value if possible.
  // It is not possible to write this using only applic and map (try it!).
 
  // Bye bye Option-specificity!
  // (setting up for Exercise 25)
  trait Applic[F[_]] {
    def point[A](a: A): F[A]
    def applic[A, B](f: F[A => B], a: F[A]): F[B]
 
    final def map[A, B](f: A => B, a: F[A]): F[B] =
      applic(point(f), a)
  }
 
  object Applic {
    implicit val OptionalApplic: Applic[Optional] = new Applic[Optional] {
      def point[A](a: A): Optional[A] = some(a)
      def applic[A, B](f: Optional[A => B], a: Optional[A]): Optional[B] = a applic f
    }
  }
 
  // Exercise 25
  // The Double-Clincher!
  def mapWhatever[A, B, F[_]](f: A => F[B], a: List[A])(implicit z: Applic[F]): F[List[B]] =
    error("todo")
}
 
import org.scalacheck._
import Arbitrary.arbitrary
import Prop._
 
object TestOptional extends Properties("Optional") {
  import Optional._
 
  implicit def ArbitraryOptional[A](implicit a: Arbitrary[A]): Arbitrary[Optional[A]] =
    Arbitrary(arbitrary[Option[A]] map fromOption)
 
  property("map") = forAll ((o: Optional[Int], f: Int => String) =>
    (o map f).toOption == (o.toOption map f))
 
  property("get") = forAll((o: Optional[Int]) =>
    o.isDefined ==>
      (o.get == o.toOption.get))
 
  property("flatMap") = forAll((o: Optional[Int], f: Int => Optional[String]) =>
    (o flatMap f).toOption == (o.toOption flatMap (f(_).toOption)))
 
  property("mapAgain") = forAll ((o: Optional[Int], f: Int => String) =>
    (o mapAgain f).toOption == (o map f).toOption)
 
  property("getOrElse") = forAll ((o: Optional[Int], n: Int) =>
    (o getOrElse n) == (o.toOption getOrElse n))
 
  property("filter") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o filter f).toOption == (o.toOption filter f))
 
  property("exists") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o exists f) == (o.toOption exists f))
 
  property("forall") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o forall f) == (o.toOption forall f))
 
  property("foreach") = forAll ((o: Optional[Int], f: Int => Unit, n: Int) => {
    var x: Int = n
    var y: Int = x
 
    o foreach (t => x = x + t)
    o.toOption foreach (t => y = y + t)
 
    x == y
  })
 
  property("isDefined") = forAll ((o: Optional[Int]) =>
    (o.isDefined) == (o.toOption.isDefined))
 
  property("isEmpty") = forAll ((o: Optional[Int]) =>
    o.isEmpty == o.toOption.isEmpty)
 
  property("orElse") = forAll ((o: Optional[Int], p: Optional[Int]) =>
    (o orElse p).toOption == (o.toOption orElse p.toOption))
 
  property("toLeft") = forAll ((o: Optional[Int], n: Int) =>
    (o toLeft n) == (o.toOption toLeft n))
 
  property("toRight") = forAll ((o: Optional[Int], n: Int) =>
    (o toRight n) == (o.toOption toRight n))
 
  property("toList") = forAll ((o: Optional[Int]) =>
    o.toList == o.toOption.toList)
 
  property("iterator") = forAll ((o: Optional[Int]) =>
    o.iterator sameElements o.toOption.iterator)
 
  // *** READ THIS COMMENT FIRST ***
  // Note that scala.Option has no such equivalent to this method
  // Therefore, reading this test may give away clues to how it might be solved.
  // If you do not wish to spoil it, look away now and follow the
  // instruction in the Exercise comment.
  property("applic") = forAll ((o: Optional[Int => String], p: Optional[Int]) =>
    (p applic o).toOption ==
    (for(f <- o.toOption;
         n <- p.toOption)
    yield f(n)))
 
  def trace[A](a: A) = {
    println(a)
    a
  }
 
  property("mapOptionals") = forAll((f: Int => Optional[String], o: List[Int]) =>
  {
    val i = o map f
    mapOptionals(f, o) == (if(i forall (_.isDefined)) some(i map (_.get)) else none)
  })
 
  property("sequenceOptionals") = forAll((o: List[Optional[String]]) =>
      sequenceOptionals(o) == (if(o exists (_.isEmpty)) none else some(o map (_.get))))
 
  property("mapOptionalsAgain") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapOptionalsAgain(f, o) == mapOptionals(f, o))
 
  property("sequenceOptionalsAgain") = forAll((o: List[Optional[String]]) =>
      sequenceOptionalsAgain(o) == sequenceOptionals(o))
 
  property("joinOptionals") = forAll((o: Optional[Optional[String]]) =>
      joinOptionals(o) == (if(o.isDefined && o.get.isDefined) o.get else none))
 
  property("filterOptionals") = forAll((f: Int => Optional[Boolean], o: List[Int]) =>
      filterOptionals(f, o) == (if(o exists (f(_).isEmpty)) none else some(o filter (f(_).get))))
 
  property("fillOptionals") = forAll((n: Int, o: Optional[String]) =>
      (n < 1000) ==> // prevent stack consumption
      (fillOptionals(n, o) == (if(n <= 0) some(Nil) else (o map (List.fill(n)(_))))))
 
  property("fillOptionalsAgain") = forAll((n: Int, o: Optional[String]) =>
      (n < 1000) ==> // prevent stack consumption      
      (fillOptionalsAgain(n, o) == fillOptionals(n, o)))
 
  property("mapOptionalsYetAgain") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapOptionalsYetAgain(f, o) == mapOptionals(f, o))
 
  property("mapWhatever") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapWhatever(f, o) == mapOptionals(f, o))
 
  /*
  $ scala -classpath .:scalacheck_2.8.0-1.7.jar TestOptional
  + Optional.map: OK, passed 100 tests.                                         
  + Optional.get: OK, passed 100 tests.                                         
  + Optional.flatMap: OK, passed 100 tests.                                     
  + Optional.mapAgain: OK, passed 100 tests.                                    
  + Optional.getOrElse: OK, passed 100 tests.                                   
  + Optional.filter: OK, passed 100 tests.                                      
  + Optional.exists: OK, passed 100 tests.                                      
  + Optional.forall: OK, passed 100 tests.                                      
  + Optional.foreach: OK, passed 100 tests.                                     
  + Optional.isDefined: OK, passed 100 tests.                                   
  + Optional.isEmpty: OK, passed 100 tests.                                     
  + Optional.orElse: OK, passed 100 tests.                                      
  + Optional.toLeft: OK, passed 100 tests.                                      
  + Optional.toRight: OK, passed 100 tests.                                     
  + Optional.toList: OK, passed 100 tests.                                      
  + Optional.iterator: OK, passed 100 tests.                                    
  + Optional.applic: OK, passed 100 tests.                                      
  + Optional.mapOptionals: OK, passed 100 tests.                                
  + Optional.sequenceOptionals: OK, passed 100 tests.                           
  + Optional.mapOptionalsAgain: OK, passed 100 tests.                           
  + Optional.sequenceOptionalsAgain: OK, passed 100 tests.                      
  + Optional.joinOptionals: OK, passed 100 tests.                               
  + Optional.filterOptionals: OK, passed 100 tests.                             
  + Optional.fillOptionals: OK, passed 100 tests.                          
  + Optional.fillOptionalsAgain: OK, passed 100 tests.                     
  + Optional.mapOptionalsYetAgain: OK, passed 100 tests.                        
  + Optional.mapWhatever: OK, passed 100 tests.          
  */  
}

In simpler times (say 2001) Soar was just Tcl. That is to say, Soar was a module, dynamically loaded into a Tcl interpreter at run-time. When loaded, Soar added a bunch of useful commands to the interpreter. Like run, matches, preferences, and probably most importantly, the sp command. When you “sourced” a Soar file, the Tcl interpreter just executed commands, loading rules, setting watch levels, etc.

The main drawback to this whole situation was that Tcl didn’t always lend itself to friendly embedding in other programs. It had funny rules about threads and, if Tk was involved, demanded to have its message queue pumped. And, of course, very few people get to know Tcl enough to like it :)

On the other hand, you could create macros for repetitive Soar structures, define new RHS functions, manipulate I/O. In short, you had the power of a full programming language mixed in with your Soar code.

With Soar 8.6 Soar’s tight integration with Tcl was broken, replaced by SML and a stricter command interpreter. It still looked like Tcl commands, but there were no Tcl control structures, variables, etc. Way it goes. When I initially started work on JSoar, I needed to quickly bootstrap a command interpreter so I could load existing code into the kernel. I turned to Tcl, in the form of Jacl, a Java implementation of Tcl. It saved a lot of time and, since Soar’s syntax was still basically Tcl, no one would really notice.

Of course, as I mentioned, no one wants Tcl, so over the last couple weeks, I’ve added a new scripting layer to JSoar. This time, I’m taking advantage of the Java Scripting API, JSR-223. This allows any scripting language with a JSR-223 implementation to be pretty seamlessly accessed from Java (and vice versa). With this new capability, it’s now possible to automate Soar agents, implement simple agent environments, and extend SoarUnit testing to include I/O, all from within a Soar source file. All with a variety of languages including Ruby, JavaScript, Python, Clojure, Groovy, etc.

A scripting engine (a language implementation) is invoked with the script command:

script javascript {
   soar.onInput(function(e) {
      soar.wmes.add("my-input", "hello");
   });
   soar.onOutputCommand("say", function(e) {
      soar.print("The agent says: " + e.greeting);
   });
}

This little bit of code sets up an input phase callback and creates a WME on the agen’ts input-link. It also handles an output command called “say”. The equivalent Java code would be … more ceremonious. Not to mention setting up a new project, compiling, etc, etc is a major hassle.

As an example, I’ve implemented a simple waterjugs environment in JavaScript, Ruby, and Python. Here are some things you can do:

• Generate input
• Handle output commands
• Auto-convert hashes (JavaScript objects, Python dicts, or Ruby hashes) to input structures
• Install new RHS functions
• Add new commands
• and on and on

Also, with maybe a little more work, I might have a pretty good story for dealing with I/O in SoarUnit tests. Stay tuned.

More detailed info on JSoar scripting support can be found on the JSoar wiki.

UPDATE: an update site including Jin’s GSoC work is now available.

I was lucky enough to be the mentor on a Scala IDE for Eclipse project which was selected for this year’s Google Summer of Code. Jin Mingjian was the student for this project, and it’s been wonderful to work with him over the last few months.

Jin completed his Doctoral degree at the Institute of Electrical Engineering in the Chinese Academy of Sciences this summer … having to deal with his PhD defence at the same time as the GSoC project was quite a tall order!

He had this to say about himself and about his project …

I have been involved with the Eclipse community for a long time. When I discovered Scala this year, I realized that it was the language that I need. The openness of Scala struck me, as much as the technical merits of the language itself. The Scala IDE community combines two great open source communities and this summer’s GSoC gave me the opportunity to work on it. I like being part of this community. Join us to help to create great Scala tools!

Now that the GSoC ‘pencils down’ date has arrived, it is time to report to the community about the achievements of my Scala IDE project. The goal of this project is to provide Advanced Semantic Tools for the Scala IDE for Eclipse.

First, I am very appreciative for lots of helpful suggestions, advice and encouragement from my mentor Miles Sabin and other guys in the community. Without their help, it would not have been possible to finish this project.

There is a wiki page on the Scala IDE project site which explains some aspects of the features. Let me introduce them by starting with an example code snippet,

object String2Int {
  val a = "1";
  var b: java.lang.String = "3";
  implicit val somewords = new SomeWords("yeah!")

  implicit def string2Int(s: String) = {
    ((s.toInt)+1)
  }

  def main(args:Array[String]) {
    printInt(string2Int("3"))
    printInt(a+b)
    printIntWithSomeWords("5")(new SomeWords("..."))
    printIntWithSomeWords(2)

    val map = Map( 1 ->"one",2->"two")
  }

  def printInt(a:Int) {
    println(a)
  }

  def printIntWithSomeWords(a: Int)(implicit sw: SomeWords) {
    println(a)
    println(sw.words)
  }

  class SomeWords(val words: String)
}

This code stems from an example in Programming in Scala. But I modified it to be “more implicit”.

When you open the editor, all the places where implicit conversions and implicit parameters occur (not the implicit definitions themselves) have been highlighted, as follows,

Perhaps you don’t like the default green squiggly underlines as the visual indicator of implicit occurrences? Then you can customize the highlight style via Windows -> Preferences -> Scala -> Editor -> Syntax Coloring as follows,

You can hide the highlighting by clearing the checkboxes and setting the underline style to “none”. In future we will add an enable/disable check box to simplify this process.

Along with the visual annotation for implicits, we provide automation around the annotation, known in Eclipse terminology as “quick assists”. The default shortcut for quick assist is “Ctrl+1″. The following screenshot shows the quick assist for an implicit conversion,

After applying this quick assist we get the explicit version of above implicit conversion,

The following screenshot shows the quick assist for implicit parameters,

After the applying the quick assist, we see the implicit arguments defined in the scope explicitly inlined as follows,

One of Scala’s important features is support for type inference. With type inference we are not forced to write many tedious type decorations. However, Scala is a strongly type language and in some contexts it is better to declare the type explicitly, for example method return types.

So we have added functionality which provides explicit type completion, activated automatically by typing “:”. The current implementation is limited to val and method definitions for which the type can be inferred.

The following screenshot shows that I want to add an explicit type for val map. So I type the “:” after the map identifier. Then I get the inferred type quick assist here,

When I press Enter, we see the following,

Currently the explicit type is a little long. In future we will allow the qualified part to be moved to the import section.

It is a best practice to add explicit return types for methods (other than for methods which return Unit type). And sometimes you forget to add the “=” when defining a method. This makes the whole method return Unit unfortunately. With our new functionality and that best practice quick assist, you can find and fix this kind of mistake easily. For example, suppose you wanted to add the type for the method by “:” auto-completion. But you find that the proposed type is Unit. Then you will realize that you missed the “=”,

Correct it and add the right type again as follows,

Adding explicit types for val and method definition is a piece of cake now. In future we will improve explicit type completion to propose types from the classpath if the exact type cannot be inferred.

What do you think about these new features? A build/update site of the GSoC branch will be available shortly and any feedback will be appreciated. When the features has been proven stable, we will merge them into the main distribution. Then everyone can try them out!

Recently I repeatedly found myself wondering whether relying on Scalas rich wrappers for convenience was actually coming with some performance cost or not. Not that it really matters in all but some really time-critical edge cases, however, I remember reading something about modern JVMs being able to completely optimize these wrapping constructs away (by means of so-called “escape analysis”?), so maybe there...

Normally I don't go for flame bait titles. But I haven't finished my morning coffee yet so I can't help myself. There's once again a debate raging across the internet about whether Scala is more or less complex than Java, along with the more nuanced argument that yes, it is more complex but only framework and library developers have to contend with this complexity. This argument usually happens when someone posts a little bit of code like this:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

And then someone responds like this:

Why do not people realize that Java is too difficult for the average programmer? That is the true purpose of Scala, to escape the complexity of Java code! Framework code in Scala, with heavy use of implicit keywords and all kinds of type abstractions, is very difficult. This is correct, but this code is not meant for innocent eyes. You do not use that sort of code when you write an application.

I've seen this type of thinking before. A few years ago I had a bout of insanity and lead an ASP.NET project using ASP.NET 2.0. I had no .NET experience prior to this project. The project failed, although the reasons for that failure are legion and unimportant here. But I noticed something about ASP.NET developers: they have no clue how the technology works. It's a black box. Do you why? Because it is a black box. I searched and searched and couldn't even find a good illustration of the lifecycle for an ASP.NET page that's using events. This type of information is put front and center in the Java world. It's absolutely buried in the Microsoft world. Or at least the parts of it that target the hoards of VB programmers that are undyingly loyal to MS. The framework is magic dust created by the great wizards in Redmond so that you can build solutions for your customers. Do not question the dust. Think about VB. Or, no don't, it might damage your brain. My coffee hasn't quite kicked in, so I should have some immunity, so I'll do it for you. VB is a black box (well, at old school VB6). It was designed to allow people who do not know how to really program, and who will probably never know how to program, to create applications. It's completely flat, opaque abstraction. The dichotomy between the application developer and the framework developer is as high and as thick as the gates of Mordor.

There are many people in the Scala community that claim Scala's complexity can be hidden from the application program. I don't believe them, but there's a chance that they are right. It's technically feasible, and I can see how it could happen if Scala started attracting lots of VB programmers. I can't see how it's going to attract lots of VB programmers, but apparently many people in the Scala community think Scala is for VB programmers. So we'll just have to wait and see...

Recently we have seen a heated debate on whether Scala is too complicated for normal programmers or whether it’s in fact a rather simple language to program in. Here are two representative blogposts of the debate. The comments on the posts are also worth reading. I have written up some thoughts here.

<o:p> </o:p>

There is currently lots of talk about Scala being to complex. Instead of more arguing I implemented the same bit of functionality in Scala and in Java and let everyone decide for themselves.

There is some nice example code in the manual to the The Scala 2.8 Collections API which partitions a list of persons into two lists of minors and majors. Below are the fleshed out implementations in Scala and Java.

First Scala:

object ScalaMain {
  case class Person(name: String, age: Int)

  val persons = List(
    Person("Boris", 40),
    Person("Betty", 32),
    Person("Bambi", 17))

  val (minors, majors) = persons.partition(_.age <= 18) 

  def main(args: Array[String]) = {
    println (minors.mkString(", "))
    println (majors.mkString(", "))
  }
}

And now Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

class Person {
    private final String name;
    private final int age;

    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        else if (other instanceof Person) {
            Person p = (Person) other;
            return name == null ? p.name == null : name.equals(p.name)
                    && age == p.age;

        }
        else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        int h = name == null ? 0 : name.hashCode();
        return 39*h + age;
    }

    @Override
    public String toString() {
        return new StringBuilder("Person(")
            .append(name).append(",")
            .append(age).append(")").toString();
    }
}

public class JavaMain {

    private final static List<Person> persons = Arrays.asList(
        new Person("Boris", 40),
        new Person("Betty", 32),
        new Person("Bamby", 17));

    private static List<Person> minors = new ArrayList<Person>();
    private static List<Person> majors = new ArrayList<Person>();

    public static void main(String[] args) {
        partition(persons, minors, majors);
        System.out.println(mkString(minors, ","));
        System.out.println(mkString(majors, ","));
    }

    private static void partition(List<? extends Person> persons,
            List<? super Person> minors, List<? super Person> majors) {

        for (Person p : persons) {
            if (p.getAge() <= 18) minors.add(p);
            else majors.add(p);
        }
    }

    private static <T> String mkString(List<T> list, String separator) {
        StringBuilder s = new StringBuilder();
        Iterator<T> it = list.iterator();
        if (it.hasNext()) {
            s.append(it.next());
        }
        while (it.hasNext()) {
            s.append(separator).append(it.next());
        }
        return s.toString();
    }

}

Impressive huh? And the Java version is not even entirely correct since its equals() method might not cope correctly with super classes of Person.

HTTP requests: you want to serve them. You want to respond in the 200s. But some requests just don’t make the cut. They lack the attributes you’re looking for, or they have the attributes but in the wrong proportion. In short, some requests are just a bad match.

The Unfiltered web toolkit gives you two ways to handle request parameters. (Those two are in addition to the infinitely many ways you could handle the parameter map yourself, or even directly access the HttpServletRequest if you want to go there.) The first was really easy to build. It’s a natural extension of the pattern matching that Unfiltered uses generally:

object Number extends Params.Extract(
  "number", 
  Params.first ~> Params.int
)
class MyFilter extends unfiltered.Planify({
  case POST(Path("/hi", Params(Number(num, _), _))) => 
    ResponseString(num.toString)
})

And that would give you a filter that only responds when a parameter is supplied that’s called “number” and is an integer. It’s a little odd that the extractor must be defined in an object outside the partial function that defines request handling, but the real shortcoming of this approach is that you can’t easily define behavior for when the parameter is missing, or bad. You can nest pattern matching statements to catch some of the failure conditions, but it’s not going to be pretty (or complete).

For an internal service, or a prototype of an external one, descriptively responding to bad inputs may not be a concern. In that case, go to town with the parameter extractor object. It’s an easy and typesafe way to define and handle acceptable inputs. It offloads the effort of dealing with errorneous input to the client making the request.

But most services can’t just tell bad clients to bug off. For them, there’s QParam. It can map parameter failures to very specific error responses, no matter how many parameters fail.

For example!

This rather dense chunk of code will match on any GET request to “/even”, and respond with either a 200 or 400 depending on the validity of the parameters supplied. Its parameter requirements are defined in a for expression, whose yield statement is only evaluated if no errors have accumulated. After defining the requirements, you apply a set of parameters and provide a function to handle the error list if it is non-empty.

In this case we start with a parameter “number” which must parse into an int or the error object “nonnumber” will be recorded. (The type of error objects for an expression is inferred from the first error object supplied.) Secondly, it must satisfy the predicate { (_: Int) % 2 == 0 } or we’ll note that it was “odd”, and finally it must exist or else it is “missing”. If any requirement on a parameter fails, its remaining requirements are skipped and the next parameter is evaluated.

How does it work? It’s a variation of the state-transformer monad, apparently. I knew how I wanted parameter evaluation to work, and tried to write it “from scratch” but that didn’t produce anything useful. So I ripped off some code from ScalaQuery (yes—the SQL API) and that somehow did work. I thought my hack job was pretty slick and showed it to Chris League, who spoke to our Meetup group about these fancy topics recently. He promptly rewrote it. After some further negotiation, this is what we ended up with:

And so on.

In case you want to try this stuff out, we added some fun parameter gymnastics to Unfiltered’s template project. It’s a giter8 template, so if you have g8 on your path you can

$ g8 softprops/unfiltered

and be on your way. Of course, no one has g8 on their path yet, so you could be the first person in your timezone to make the exciting leap to the future of Scala applications installed and launched by sbt.

It’s been a busy summer.

Below are 15 (probably fun) exercises for anyone interested in obtaining a deeper understanding of scala.Option and algebraic data types in general. I could write the same in Haskell but this will require either type-classes or rank-n types (GHC extension), so I thought I’d give that a miss.

Instructions are in the comments. Let me know if there are any questions.

// Scala version 2.8.0.final
// http://scalacheck.googlecode.com/files/scalacheck_2.8.0-1.8-SNAPSHOT.jar
 
 
/*
 
  Below are 15 exercises. The task is to emulate the scala.Option API
  without using Some/None subtypes, but instead using a fold (called a
  catamorphism).
 
  A couple of functions are already done (map, get)
  to be used as an example. ScalaCheck tests are given below to
  verify the work. The desired result is to have all tests passing.
 
  The 15th exercise is not available in the existing Scala API so
  instructions are given in the comments.
 
  Revision History
  ================
 
  23/08/2010
  Initial revision
 
  ----------------
 
  23/08/2010
  Fixed prop_getOrElse. Thanks Michael Bayne.
 
  ----------------
 
  26/08/2010
  Add lazy annotation to orElse method.
 
*/
 
 
trait Optional[A] {
  // single abstract method
  def fold[X](some: A => X, none: => X): X
 
  import Optional._
 
  // Done for you.
  def map[B](f: A => B): Optional[B] =
    fold(f andThen some, none[B])
 
  // Done for you.
  // WARNING: undefined for None
  def get: A =
    fold(a => a, error("None.get"))
 
  // Exercise 1
  def flatMap[B](f: A => Optional[B]): Optional[B] =
    error("todo")
 
  // Exercise 2
  // Rewrite map but use flatMap, not fold.
  def mapAgain[B](f: A => B): Optional[B] =
    error("todo")
 
  // Exercise 3
  def getOrElse(e: => A): A =
    error("todo")
 
  // Exercise 4
  def filter(p: A => Boolean): Optional[A] =
    error("todo")
 
  // Exercise 5
  def exists(p: A => Boolean): Boolean =
    error("todo")
 
  // Exercise 6
  def forall(p: A => Boolean): Boolean =
    error("todo")
 
  // Exercise 7
  def foreach(f: A => Unit): Unit =
    error("todo")
 
  // Exercise 8
  def isDefined: Boolean =
    error("todo")
 
  // Exercise 9
  def isEmpty: Boolean =
    error("todo")
 
  // Exercise 10
  def orElse(o: => Optional[A]): Optional[A] =
    error("todo")
 
  // Exercise 11
  def toLeft[X](right: => X): Either[A, X] =
    error("todo")
 
  // Exercise 12
  def toRight[X](left: => X): Either[X, A] =
    error("todo")
 
  // Exercise 13
  def toList: List[A] =
    error("todo")
 
  // Exercise 14
  def iterator: Iterator[A] =
    error("todo")
 
  // Exercise 15 The Clincher!
  // Return a none value if either this or the argument is none.
  // Otherwise apply the function to the argument in some.
  // Don't be afraid to use functions you have written.
  // Better style, more points!
  def applic[B](f: Optional[A => B]): Optional[B] =
    error("todo")
 
  // Utility
  def toOption: Option[A] = fold(Some(_), None)
}
 
object Optional {
  // Done for you
  def none[A]: Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = none
  }
 
  // Done for you
  def some[A](a: A): Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = some(a)
  }
 
  // Utility
  def fromOption[A](o: Option[A]): Optional[A] = o match {
    case None    => none
    case Some(a) => some(a)
  }
}
 
import org.scalacheck._
import Arbitrary.arbitrary
import Prop._
 
object TestOptional {
  import Optional._
 
  implicit def ArbitraryOptional[A](implicit a: Arbitrary[A]): Arbitrary[Optional[A]] =
    Arbitrary(arbitrary[Option[A]] map fromOption)
 
  val prop_map = forAll ((o: Optional[Int], f: Int => String) =>
    (o map f).toOption == (o.toOption map f))
 
  val prop_get = forAll((o: Optional[Int]) =>
    o.isDefined ==>
      (o.get == o.toOption.get))
 
  val prop_flatMap = forAll((o: Optional[Int], f: Int => Optional[String]) =>
    (o flatMap f).toOption == (o.toOption flatMap (f(_).toOption)))
 
  val prop_mapAgain = forAll ((o: Optional[Int], f: Int => String) =>
    (o mapAgain f).toOption == (o map f).toOption)
 
  val prop_getOrElse = forAll ((o: Optional[Int], n: Int) =>
    (o getOrElse n) == (o.toOption getOrElse n))
 
  val prop_filter = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o filter f).toOption == (o.toOption filter f))
 
  val prop_exists = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o exists f) == (o.toOption exists f))
 
  val prop_forall = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o forall f) == (o.toOption forall f))
 
  val prop_foreach = forAll ((o: Optional[Int], f: Int => Unit, n: Int) => {
    var x: Int = n
    var y: Int = x
 
    o foreach (t => x = x + t)
    o.toOption foreach (t => y = y + t)
 
    x == y
  })
 
  val prop_isDefined = forAll ((o: Optional[Int]) =>
    (o.isDefined) == (o.toOption.isDefined))
 
  val prop_isEmpty = forAll ((o: Optional[Int]) =>
    o.isEmpty == o.toOption.isEmpty)
 
  val prop_orElse = forAll ((o: Optional[Int], p: Optional[Int]) =>
    (o orElse p).toOption == (o.toOption orElse p.toOption))
 
  val prop_toLeft = forAll ((o: Optional[Int], n: Int) =>
    (o toLeft n) == (o.toOption toLeft n))
 
  val prop_toRight = forAll ((o: Optional[Int], n: Int) =>
    (o toRight n) == (o.toOption toRight n))
 
  val prop_toList = forAll ((o: Optional[Int]) =>
    o.toList == o.toOption.toList)
 
  val prop_iterator = forAll ((o: Optional[Int]) =>
    o.iterator sameElements o.toOption.iterator)
 
  // *** READ THIS COMMENT FIRST ***
  // Note that scala.Option has no such equivalent to this method
  // Therefore, reading this test may give away clues to how it might be solved.
  // If you do not wish to spoil it, look away now and follow the 
  // instruction in the Exercise comment.
  val prop_applic = forAll ((o: Optional[Int => String], p: Optional[Int]) =>
    (p applic o).toOption ==
    (for(f <- o.toOption;
        n <- p.toOption)
    yield f(n)))
 
  val props =
    List(
      prop_map,
      prop_get,
      prop_flatMap,
      prop_mapAgain,
      prop_getOrElse,
      prop_filter,
      prop_exists,
      prop_forall,
      prop_foreach,
      prop_isDefined,
      prop_isEmpty,
      prop_orElse,
      prop_toLeft,
      prop_toRight,
      prop_toList,
      prop_iterator,
      prop_applic
    )
 
  /*
  $ scala -classpath .:scalacheck_2.8.0-1.8-SNAPSHOT.jar TestOptional
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                       
  */
  def main(args: Array[String]) {
    props foreach (_.check)
  }
}

One of the unfortunate aspects of many of the "published" (meaning blogged) Scala Actor benchmarks out there is that they rarely pay much attention, if any, to the affects of seemingly idiomatic patterns on performance. Some of the main culprits are:

1. react versus receive (event-based versus threaded)
2. loop/react versus recursive react
3. loop/receive versus receive/while
4. tweaking (or failing to tweak) the scheduler

I've been working on setting up a "benchmarking framework" in conjunction with experimenting with modifications to the underlying thread pool so that all the possible permutations are automatically tested. What I have right now is a classic "ring" benchmark setup to permute the schedulers and loop/react versus recursive react. The loop/react pattern is more idiomatic (or at least more common), but higher overhead, and it looks something like this:

loop {
  react {
    case Msg(m) => // do stuff
    case Stop => exit()
  }
}

The reason it is high-overhead is that both loop and react raise control flow exceptions that result in the creation of new tasks for the thread pool when they are hit, so for each loop, two exceptions are raised and two tasks are executed. There's overhead in both of the operations, especially raising the exceptions. The recursive react pattern looks like this, so it can avoid the extra exception/task:

def rloop(): Unit = react {  //this would be called by the act() method
  case Msg(m) => {
    // do stuff
    rloop()
  }
  case Stop => // just drop out or call exit()
}

Using loop instead of recursive react effectively doubles the number of tasks that the thread pool has to execute in order to accomplish the same amount of work, which in turn makes it so any overhead in the scheduler is far more pronounced when using loop. Now, I should point out that the overhead really isn't that large, so if the actor is performing significant computations it will be lost in the noise. But it's fairly common to have actors do fairly little with each message. Here's some results from the ring benchmark using 10 rings of 10,000 actors passing a token around them 100 times before exiting. I'm using multiple rings because otherwise there is no parallelism in the benchmark. These are being run on my dual core Macbook.

The fork/join schedulers are faster than the ResizableThreadPoolScheduler because rather than have all of the worker threads pull tasks off of a single, shared queue; each thread maintains its own local dequeue where it can place tasks directly onto if they are generated while it is running a task. This creates a kind of "fast path" for the tasks that involves much less overhead.

I believe the primary reason ManagedForkJoinScheduler is faster because ForkJoinScheduler does not always leverage the "fast path," even when in theory it could be used. I'm unsure about some of the rationale behind it, but I know some of the time the fast path is bypassed probabilistically in order to reduce the chances of starvation causing deadlock in the presence of long running or blocking tasks. ManagedForkJoinScheduler escapes this particular issue by more actively monitoring the underlying thread pool, and growing it when tasks are being starved. The second reason, and I'm somewhat unsure of the actual degree of the affects, if that ForkJoinScheduler configures the underlying thread pool so that the threads work through the local dequeues in FIFO order, while ManagedForkJoinScheduler configures the pool such that the local dequeues are processed in LIFO order. Processing in LIFO order allows the pool to take advantage of locality with regard to the tasks, basically assuming that the last task generated is the most likely to use data that's currently in cache, and thus reduce cache misses.

The benchmark outputs a lot more information than I captured in the above table. If you'd like to run it, you can obtain the code here. The project uses sbt, so you'll need to have it working on your computer. After you run update in sbt to download all of the dependencies, you can run the ring benchmark as follows:

$ sbt
[info] Building project ManagedForkJoinPool 1.0 against Scala 2.8.0
[info]    using ManagedForkJoinPoolProject with sbt 0.7.4 and Scala 2.7.7
> ringbenchmark
[info] 
[info] == compile ==
[info]   Source analysis: 1 new/modified, 0 indirectly invalidated, 0 removed.
[info] Compiling main sources...
[info] Compilation successful.
[info]   Post-analysis: 79 classes.
[info] == compile ==
[info] 
[info] == copy-resources ==
[info] == copy-resources ==
[info] 
[info] == ringbenchmark ==
[info] RingBenchmark ManagedForkJoinScheduler LoopReact 2 ....output truncated...

You can tweak the benchmarks by modifying the sbt project file. If you do run them, I'm very interested in the results.

Have you ever noticed that other people's microbenchmarks tend to be hard to run and often impossible to duplicate? And are frequently caveated to the hilt? When it gets down to it, a benchmark is really an experiment, and ideally a scientific experiment. That means all factors that are relevant to the results should be clearly recorded, and the tests should be easy for others to duplicate.

Custom sbt actions for benchmarks

In order to test and run benchmarks on the work I'm doing around creating a managed variant of the JSR-166y ForkJoinPool along with supporting infrastructure for use with Scala Actors, I'm creating a test harness that captures a host of environmental factors about how it was run, and writing sbt actions to make it easy to run the benchmarks and automatically permute the variables.

It still needs a lot of work, but I had some trouble figuring out a really basic task so I thought I'd share it. Basically I wanted to build a Task object that consists of several tasks based on information in the project definition and permuted parameters. It actually pretty easy, as you can see in the snippet below from my project definition:

  /** this task executes the PingPong benchmark using each available scheduler */
  lazy val pingpongbench = pingpongTaskList
  /** produces a sequence of run tasks using all the available schedulers  */
  def pingpongTaskList = {
    val pairs = 100
    val messagesPerPair = 10000
    val tasks = for(sched <- schedulers) yield pingpongTask(sched, pairs, messagesPerPair)
    tasks.reduceLeft((a, b) => a && b)
  }

You can see the whole file here. Basically Task has an && operator that essentially allows you to concatenate one task with another task. This allows you to build a whole chain of tasks. In the example above, I'm having it run the benchmark once for each scheduler configuration. Soon, I'm going to make it permute other parameters. But right now my test harness isn't playing nicely with the schedulers included in the Scala distribution, so first things first.

There's also one other little customization, which is documented, but I think it's important for benchmarking. By default, sbt runs your code in its own process. This can cause problems with multithreaded code, especially if it doesn't terminate properly. It also means the next benchmark to run has to content with any junk that the previous benchmark left around. So I configured sbt to fork new processes. It just required one line:

override def fork = forkRun

Important variables

Here's what I'm capturing for each run right now so that the results can all be dumped into a big spreadsheet for analysis. I'd like to capture more information about the host machine, such as more information about the CPUs and the loading when the benchmark is being run, but haven't got that far yet. Currently these are all captured from within the benchmark process, mostly using system properties and the Runtime object.

1. Test Name - obviously needed so that results from multiple benchmarks can be stored in the same file
2. Scheduler - this is my primary variable right now, I want to run each benchmark with each scheduler while holding everything else constant
3. # of Cores/Processors - essential so that anyone looking at the results has an idea about the hardware used
4. Java VM Name - different VMs can perform quite differently
5. Java VM Version - performance characteristics change from version to version (usually getting better)
6. Java Version - same reason as above, but this is probably the more publicly known version number
7. Scala Version - this could be important in the future, as it becomes more common for different projects to be on different version of Scala
8. OS Name and version - again, it can affect performance
9. Processor Architecture
10. Approximate Concurrency (number of simultaneously alive actors) - this allows us to examine concurrency levels versus resource consumption, more concurrency does not necessarily mean that more cores or threads would be helpful
11. Approximate Parallelism (number of simultaneously runnable actors) - this measures how many cores/threads the benchmark can really keep busy</il>
12. Approximate Total Messages - this estimates the amount of activity that takes place during the benchmark, generally the benchmarks I'm looking at contain very little logic because they are intended to measure overhead introduced by the framework
13. Total Wall Clock Time (seconds) - as measured using nanoTime within the benchmark process
14. Initial Thread and Maximum Observed Thread Count - used to examine automatic expansion of the thread pool
15. Initial Free Memory and Minimum Observed Free Memory - threads use a fair amount of memory, so performance impacts may show up as pressure on the GC as well has contention for the CPU
16. Initial and Maximum Observed Total Memory - threads use a lot of memory, so it's important to track usage
17. Verbose - debugging output pretty much invalidates any of these tests

You sound somewhat obsessed with fonts.

For my first larger, Scala-only project I just set up a brand-new project space.
Normally all my projects have an IntelliJ IDEA project structure set up for the day-to-day work. However, I usually also include a paralleling project spec for some build system for creating the final deployment or distribution artifacts. For all my Java projects this is (and always has been)...

Last year over 80 developers had a great time at the Scala LiftOff in San Francisco. Since then there has been a tremendous growth in the world wide Lift/Scala community and lots of excitement with the releases of Lift 2.0 and Scala 2.8.0. Scala LiftOff has gone international to allow more people to catch up with the latest developments and let more developers talk over the latest stuff. This year you can join other enthusiastic members of the Scala and Lift community in London, New York or San Francisco and find out what's going on. David Pollak, the power behind Lift, and many industry experts will be at all three while you will have a chance to meet Martin Odersky, the creator of Scala, at the London event. The first one is in September so you will need to register soon.

Scala 2.8 has introduced a great number of improvements and additions. They are summarized in the release notes. Over the next weeks, we will publish a series of stories that explain the major new features one-by-one. We start this week with the Scala 2.8 collections API.

In the eyes of many, the new collections framework is the most significant change in Scala 2.8. Scala had collections before (and in fact the new framework is largely compatible with them). But it's only 2.8 that provides a common, uniform, and all-encompassing framework for collection types.

As I have been doing quite a lot of localisation work recently, I thought it prudent to port the native2ascii tool over to SBT so that I didn’t constantly have to keep using it manually on the command line. If you are interested, you can grab the source code from here

If order to get started with the plugin add it to your Plugins.scala within your project:

  import sbt._
  class Plugins(info: ProjectInfo) extends PluginDefinition(info) {
    val n2a = "eu.getintheloop" % "sbt-native2ascii-plugin" % "0.1.0" 
  }

...and then mix the Native2Ascii trait into your project:

  class SampleProject(info: ProjectInfo) 
    extends DefaultWebProject(info) 
    with Native2AsciiPlugin {
    ...
  }

Ensure you have all your localization .txt files in src/main/i18n and by default they will be translated into your application resources folder in src/main/resources.

Then, from your SBT prompt just hit:

All being well you should then see something like:

  [info] == native2ascii ==
  [info] Encoding '.txt' to '.properties' file(s) in src/main/resources
  [info] Translation complete.
  [info] == native2ascii ==

Skills Matter and Xebia will be providing a series of Scala training sessions starting in October and initially located in London, Amsterdam and Paris. In response to the growing demand Scala courses are being made available through local, well established commercial partners. The courses have been designed by Martin Odersky and will be delivered by him and Iulian Dragos.

These two day courses are excellent for developers or systems architects wanting to learn about Scala and need to understand how it can fit into their development tool-bag. Next courses are available in:

London, UK 4/5 October 2010 Skills Matter. Learn more about the course and register.
Amsterdam, NL 14/15 October 2010 Xebia. Learn more about the course and register.

The recently released parboiled version 0.9.8 comes with a brand-new feature that will hopefully make parboiled an attractive tool for an even larger developer community: a Scala facade.
Before v0.9.8 parboiled was a pure-Java library written mainly for Java developers. It basically consisted of two things, an efficient recursive-descent PEG parsing engine and an...

I have my ticket. How about you?  It's £150 at the moment.

What we're looking at here is a two day unconference, meaning we get a chance to learn about things we're interested in by figuring it out on the day, talking to people, rather than being lectured at.  I thoroughly enjoyed the Scala Lift Off last year in San Francisco, so I'm looking forward to the London one.  Especially as it close by, rather than 8,720km away.

Permalink | Leave a comment  »

Play is a MVC, convention-based, stateless web framework for Java with growing support for Scala too.

It's not for me as I can't face going back to MVC and the kinds of presentation languages they use. Having said that, if you like MVC, and you're not already using Grails or Rails or a similar framework, I strongly urge you to look at Play as there's some nice technology in there. 

Everything I know about Play comes from Rustem Suniev's talk for the London Scala User Group at Skilsmatter on Wednesday. The slides and video are already on-line and they contain a really nice live-coding demo of Play which gave me a good sense of what the framework is about.  Nice work—and pizza courtesy of autoquake.com (who are hiring).

One comment I will make is that Play pushes it's stateless-ness prominently. For many of us I suspect our default position is that stateful=bad and stateless=good.  That sounds sane, but you probably do need some state in your application, and you have to deal with it somehow, or push the issue somewhere, which leaves me feeling that state v. stateless thing is all a bit more complicated that we often think it is.  It certainly does not automatically mean better scaling or performance, but there are definite positives to it.  I'm glad to see the Play community discussing state and exploring some nice ideas.  Just don't assume a label of "stateless" solves all your scaling problems—if you're lucky enough to have any :-)

Permalink | Leave a comment  »

Brendan McAdams gives an introduction to MongoDB and the libraries available for using it with Scala.

Doug Tangren presents the Unfiltered toolkit for serving HTTP requests in Scala.

Now that the dust has settled on the Scala 2.8.0.final release, we have some breathing space to think about moving the Scala IDE for Eclipse on towards it’s first release independently of the release of the Scala toolchain — you’ll recall that a big part of the motivation for the move from SVN at EPFL to git at Assembla was to allow the IDE release cycle to be decoupled from the release cycle of the language — now it’s time to take advantage of that.

One part of the decoupling process has been rebooting the version numbering scheme for the IDE. We have three sets of versions to juggle with — the Scala toolchain version, the Eclipse version and the version of the SDT itself. Previously it made sense for the SDT to share it’s version number with the Scala toolchain, but that doesn’t work now that the two can move independently. So, to celebrate the birth of the Scala IDE for Eclipse as an independent open source project in a new OSGi namespace (org.scala-ide rather than ch.epfl.lamp), we’re starting from scratch and are currently at 1.0.0-SNAPSHOT heading for a 1.0.0 release. Readers who have been following the nightly updates for a while will be relieved to know that care has been taken to ensure that upgrades should be smooth despite change of namespace and the decrease in the version number.

Astute readers will have noticed a Maven-ish tinge to the new versioning scheme. That’s no accident, and I’m delighted to report that the move from an Ant-based build to a Tycho/Maven 3.0 based build is now complete and has been a more or less unqualified success. In particular, Tycho’s ability to manage the Eclipse target platform dependencies and build intricacies has been of enormous benefit — without it the Helios build would have taken even longer to arrive. The magic that is git has also paid off here as it’s allowing us to develop a Helios-specific branch with an ease that I would previously have thought impossible.

We still have a little way to go before that first release (I’ll post on the release plan and timetable shortly) but in the meantime I’d like to give you an update on current developments. So, without further ado …

New and Noteworthy

Refactoring Support

Mirko Stocker’s Scala Refactoring framework is now included in the SDT. Currently there is support for Rename, including in-place renaming of local identifiers:

We have an Extract Method refactoring:

and an Inline Local refactoring:

We also have an Extract Local refactoring and the beginnings of Organize Imports — so far existing imports will be tidied, but adding and removing imports is still work in progress.

Mirko’s site and thesis goes into a lot more detail, but in summary he’s done a fantastic job of separating out the lexical noise so that authors of refactorings can concentrate on the essence of the transformations involved without being distracted by whitespace or comment issues. The refactoring API is based on the standard scalac AST and is IDE-independent — we’d both love to see people contribute refactorings whether or not they’re Eclipse users.

Formatting

Matt Russell’s Scala Formatter Scalariform is also now included.

Before:

After:

As you can see, it does a good job of formatting XML literals as well as ordinary Scala source. Like Mirko’s refactoring work, Scalariform has an IDE independent core and we’d welcome contributions from all parties.

Mark Occurrences

Matt has also contributed an implementation of Mark Occurrences which will be familiar to users of Eclipse’s Java tooling — this is somthing I’ve always found invaluable:

Code Templates

David Bernard has added support for code templates for common boilerplate and which are offered as completion proposals in the Scala editor in the same way that Java code templates are presented the Java editor.

Requesting completion of a code template for a main method:

The resulting expansion:

Quick Fix Imports

More a bug fix than a new feature — Colin Howe contributed this initially — Daniel Ratiu has reinstated the quick fix which adds an import for a missing type.

Structured Selections

Matt has added support for Eclipse’s structured selection model — Alt-Shift-Up / Alt-Shift-Down select larger and smaller portions of the AST respectively:

It works particularly nicely alongside the Extract Method and Extract Local refactorings mentioned above.

XML Syntax Highlighting

Matt has also carried on his work on Scala syntax highlighting thanks to which we now have full support for XML literals:

As well as the highlighting of XML elements and attributes, you’ll see from the screenshot that Scala syntax (keywords, string literals etc.) which appear in XML content are now correctly left as unhighlighted text.

Scala IDE support in m2eclipse

To complement the use of Maven in the SDT’s own development process, we’re making rapid progress in ensuring that the Maven experience is as smooth as possible. In particular David Bernard has done sterling work on the m2eclipse Scala integration started by Jason van Zyl with my encouragement at EclipseCon this year.

An open platform with a growing community

Hopefully a few things are very evident from all of the above. One is that there’s a lively and growing community of active contributors around the project. Another is that the Scala IDE for Eclipse as an umbrella project is very much open to collaborations with projects which aren’t Eclipse-specific, or indeed tied to any kind of IDE at all — both Mirko’s refactoring tools and Matt’s formatter can be used from the command line or incorporated into other kinds of source manipulation tools.

So I’d like to finish by inviting you to join us — whether or not you’re an Eclipse user there is plenty the project as a whole has to offer, and plenty that you could contribute in return. Looking forward to seeing you on the user and developer mailing lists!

Just about a month after the last release parboiled 0.9.8 has hit its github download page today.
It is once again a major step forward, with quite a few changes and additions, some of them being significant enough to accompany the release with a small series of blog posts. They should be of interest to both, people currently using previous parboiled...

• Default values for vars


• Catch-all on import statements


• Hiding imported members from catch-all import


• Ignoring type parameters in type patterns


• Existential type shorthand


• Wildcard pattern


• Omitting arguments to create partially applied function


• Omitting entire argument list to create partially applied function


• Omitting argument lists to create a partially applied curried function


• Omitting all argument lists to create a partially applied curried function


• Anonymous function shorthand (thanks #scala)

• Passing a Seq as a repeated parameter


• Matching repeated parameters


• In alphanumeric identifiers


• In mixed identifiers


• In literal identifiers


• In symbol literals


• In identifier of special _root_ package


• In XML literals

Scala compiler plugin, “generates type safe scala wrappers for java protoc output”

Since my last post describing App Engine mapreduce, a new InputReader has been added to the Java project for reading from the Blobstore. Nick Johnson wrote a great demo where indexing was done via reading code uploaded to the blobstore. This was demo’d at Google I/O. Now that the library is officially part of the project, it’s become much easier for developers to build Mappers that map across some large, contiguous piece of data as opposed to Entities in the datastore.The most obvious use case is data import. A developer looking to import large amounts of data would take the following steps:

1. Create a CSV file containing the data you want to import. The assumption here is that each line of data corresponds to a datastore entity you want to create
2. Upload the CSV file to the blobstore. You’ll need billing to be enabled for this to work.
3. Create your Mapper, push it live and run your job importing your data.

This isn’t meant to be a replacement for the bulk uploader tool; merely an alternative. This method requires a good amount more programmatic changes for custom data transforms. The advantage of this method is that the work is done on the server side, whereas the bulk uploader makes use of the remote API to get work done. Let’s get started on each of the steps.

Step 1: Create a CSV file with the data you want to upload

We’re going to go through an example of uploading City and State information. MaxMind.com provides a free GeoIP CSV file. The free version isn’t as full featured as the paid version, but it’ll do fine for our demo. Be sure that if you use this file in any kind of production application that you read and understand the license first! For simplicity, we’re going to parse out only cities in the United States using grep. The file should now contain lines that look like this:

605,"US","NY","Valhalla","10595",41.0877,-73.7768,501,914
606,"US","PA","Pittsburgh","15222",40.4495,-79.9880,508,412
607,"US","MO","Bridgeton","63044",38.7667,-90.4201,609,314
608,"US","CA","San Francisco","94124",37.7312,-122.3826,807,415
609,"US","NY","New York","10017",40.7528,-73.9725,501,212
610,"US","PA","Bear Lake","16402",41.9491,-79.4448,516,814
611,"US","NJ","Piscataway","08854",40.5516,-74.4637,501,732
612,"US","NY","Keuka Park","14478",42.5669,-77.1325,555,315
613,"US","VT","Brattleboro","05302",42.8496,-72.6645,506,802

2. Create an upload handler for your CSV file and upload the CSV file

We’re going to create a basic handler for uploading a CSV file and displaying the key. We’ll need to pass this key to our mapper later. There isn’t too much magic here; it’s very similar to the sample code available for the basic blobstore example.

We’ll do a quick overview of the code we need here, but for the purposes of this post, it’s out of scope. We’ll need these files:

upload.jsp

<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
    pageEncoding="ISO-8859-1"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<%@page import="com.google.appengine.api.blobstore.BlobstoreService"%>
<%@page import="com.google.appengine.api.blobstore.BlobstoreServiceFactory"%>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Upload your CSV file here</title>
</head>
<body>
    <% BlobstoreService blobstoreService = BlobstoreServiceFactory.getBlobstoreService(); %>
    <form action="<%= blobstoreService.createUploadUrl("/upload") %>" method="post" enctype="multipart/form-data">
        <input type="file" name="data">
        <input type="submit" value="Submit">
    </form>
</body>
</html>

UploadBlobServlet.java

package com.ikai.mapperdemo.servlets;

import java.io.IOException;
import java.util.Map;

import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import com.google.appengine.api.blobstore.BlobKey;
import com.google.appengine.api.blobstore.BlobstoreService;
import com.google.appengine.api.blobstore.BlobstoreServiceFactory;

@SuppressWarnings("serial")
public class UploadBlobServlet extends HttpServlet {
	public void doPost(HttpServletRequest req, HttpServletResponse resp)
			throws IOException {

		BlobstoreService blobstoreService = BlobstoreServiceFactory.getBlobstoreService();
		Map<String, BlobKey> blobs = blobstoreService.getUploadedBlobs(req);
		BlobKey blobKey = blobs.get("data");

		if (blobKey == null) {
			resp.sendRedirect("/");
		} else {
			resp.sendRedirect("/upload-success?blob-key=" + blobKey.getKeyString());
		}
	}

}

SuccessfulUploadServlet.java

package com.ikai.mapperdemo.servlets;

import java.io.IOException;

import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

@SuppressWarnings("serial")
public class SuccessfulUploadServlet extends HttpServlet {
	public void doGet(HttpServletRequest req, HttpServletResponse resp)
			throws IOException {

		String blobKey = req.getParameter("blob-key");

		resp.setContentType("text/html");
		resp.getWriter().println("Successfully uploaded. Download file: <br/>");
		resp.getWriter().println(
				"<a href='/serve?blob-key=" + blobKey
						+ "'>Click to download</a>");
	}

}

Source code for this and other helper functions should be available in the Github repository.

Step 3: Create your Mapper

Now we get to the fun part. We need to create our Mapper. A prerequisite for understanding what’s coming next is reading the last post about Mapper I wrote, so check that out before proceeding if you aren’t familiar with Mapper basics. Our Mapper class looks like this:

ImportFromBlobstoreMapper.java

package com.ikai.mapperdemo.mappers;

import java.util.logging.Logger;

import org.apache.hadoop.io.NullWritable;

import com.google.appengine.api.datastore.Entity;
import com.google.appengine.tools.mapreduce.AppEngineMapper;
import com.google.appengine.tools.mapreduce.BlobstoreRecordKey;
import com.google.appengine.tools.mapreduce.DatastoreMutationPool;

/**
 *
 * This Mapper imports from a CSV file in the Blobstore. The CSV
 * assumes it's in the MaxMind format for cities, states, zipcodes
 * and lat/long.
 *
 *
 * @author Ikai Lan
 *
 */
public class ImportFromBlobstoreMapper extends
		AppEngineMapper<BlobstoreRecordKey, byte[], NullWritable, NullWritable> {
	private static final Logger log = Logger.getLogger(ImportFromBlobstoreMapper.class
			.getName());

	@Override
	public void map(BlobstoreRecordKey key, byte[] segment, Context context) {

		String line = new String(segment);

		log.info("At offset: " + key.getOffset());
		log.info("Got value: " + line);

		// Line format looks like this:
		// 10644,"US","VA","Tazewell","24651",37.0595,-81.5220,559,276
		// We're also assuming no errant commas in this simple example

		String[] values = line.split(",");
		String state = values[2];
		String cityName = values[3];
		String zipcode = values[4];
		Double latitude = Double.parseDouble(values[5]);
		Double longitude = Double.parseDouble(values[6]);		

		state = state.replaceAll("\"", "");
		cityName = cityName.replaceAll("\"", "");
		zipcode = zipcode.replaceAll("\"", "");

		if(!zipcode.isEmpty()) {
			Entity zip = new Entity("Zip", zipcode);
			zip.setProperty("state", state);
			zip.setProperty("city", cityName);
			zip.setProperty("latitude", latitude);
			zip.setProperty("longitute", longitude);

			Entity city = new Entity("City", cityName);
			city.setProperty("state", state);
			city.setUnindexedProperty("zip", zipcode);

			DatastoreMutationPool mutationPool = this.getAppEngineContext(context)
					.getMutationPool();
			mutationPool.put(zip);
			mutationPool.put(city);
		}

	}
}

Let’s explain the things in this Mapper that are new:

public class ImportFromBlobstoreMapper extends
AppEngineMapper<BlobstoreRecordKey, byte[], NullWritable, NullWritable>

Note this line. It’s different from our previous Mappers in that the type arguments are no longer Key and Entity, but BlobstoreRecordKey and byte[]. The source for BlobstoreRecordKey is here. Remember that map-reduce is about some large body of data and breaking it into smaller pieces to operate on. BlobstoreRecordKey represents a pointer to range of data in our Blobstore. byte[] is a byte[] array actually containing that data.

public void map(BlobstoreRecordKey key, byte[] segment, Context context)

Again, notice the new types. By default, we are splitting on a newline, so segment represents a single line. We can change what we split on by specifying a terminator in mapreduce.xml.

		String line = new String(segment);

		// Line format looks like this:
		// 10644,"US","VA","Tazewell","24651",37.0595,-81.5220,559,276
		// We're also assuming no errant commas in this simple example

		String[] values = line.split(",");
		String state = values[2];
		String cityName = values[3];
		String zipcode = values[4];
		Double latitude = Double.parseDouble(values[5]);
		Double longitude = Double.parseDouble(values[6]);		

		state = state.replaceAll("\"", "");
		cityName = cityName.replaceAll("\"", "");
		zipcode = zipcode.replaceAll("\"", "");

This is very naive String parsing. Nothing fancy here.

		if(!zipcode.isEmpty()) {
			Entity zip = new Entity("Zip", zipcode);
			zip.setProperty("state", state);
			zip.setProperty("city", cityName);
			zip.setProperty("latitude", latitude);
			zip.setProperty("longitute", longitude);

			Entity city = new Entity("City", cityName);
			city.setProperty("state", state);
			city.setUnindexedProperty("zip", zipcode);

			DatastoreMutationPool mutationPool = this.getAppEngineContext(context)
					.getMutationPool();
			mutationPool.put(zip);
			mutationPool.put(city);
		}

Again, very straightforward if you’ve seen this before. Some zipcodes in our CSV file subset are empty, so we’ll check for that and just not create an Entity. We’re adding 2 entities to the mutation pool here – a City and a Zipcode. This ensures that we can search by key when we do a datastore get. Remember that fetches by key are always faster than fetches with a query, since a query requires an index scan followed by a batch get, whereas the datastore can perform a get in a single operation.

That’s it for our Mapper. Let’s add a configuration:

  <configuration name="Import all data from the Blobstore">
    <property>
      <name>mapreduce.map.class</name>

      <!--  Set this to be your Mapper class  -->
      <value>com.ikai.mapperdemo.mappers.ImportFromBlobstoreMapper</value>
    </property>

    <!--  This is a default tool that lets us iterate over blobstore data -->
    <property>
      <name>mapreduce.inputformat.class</name>
      <value>com.google.appengine.tools.mapreduce.BlobstoreInputFormat</value>
    </property>

    <property>
      <name human="Blob Keys to Map Over">mapreduce.mapper.inputformat.blobstoreinputformat.blobkeys</name>
      <value template="optional">blobkeyhere</value>
    </property>        

    <property>
      <name human="Number of shards to use">mapreduce.mapper.shardcount</name>
      <value template="optional">10</value>
    </property>        

  </configuration>

We’ve changed 2 properties here: the input format class as well as a property for the blobstore key pointing to the data to iterate over.

Step 4: Deploy!

We can now package our application up and deploy it! Make sure that you built a new JAR file with the new classes in appengine-mapreduce! If you have the old JAR file, it won’t include the BlobstoreInputFormat class that we need to do our work.

Step 5: Using the Mapper

Let’s browse to our upload hander at /upload.jsp. The page should be pretty bare.

Once the upload has finished, we’ll be on a page that looks like this:

Let’s copy the blob-key in the URL. It’s not the most streamlined approach but it works. We’ll use it in the next screen when we browser to our mapper:

We’ll copy-paste the key to replace “blobkeyhere” and hit “Run”. And now we play the waiting game – we’ll be able to check on the status of our Mapper in the UI, or check on Tasks, or look in the datastore to see if the data has been imported correctly:

Get the code

The code is here on Github:

http://github.com/ikai/App-Engine-Java-Mapper-API-demos

It’s been updated with the new examples.

Summary

So there you have it: another way of importing data into the datastore. This isn’t a replacement for the bulk uploader, just another option. Here are some useful links for additional information:

App Engine Mapreduce issues tracker – report issues here

Nick Johnson’s post explaining how he built the code search example

One last tip: the best place for questions or discussion is probably the App Engine Discussion Groups, not the comments.

Happy hacking.

In a previous post I wrote about different interpolate methods in my program for linearly interpolating numbers and vectors. The methods for numbers and vectors are exactly the same, except for the types of the arguments and return value. So, ofcourse I wanted to write a generic interpolate method to avoid repeating myself.

For a type V to be useable by the interpolate method, it must satisfy two requirements:

1. It can be multiplied by a number, resulting in a V.
2. You can add two Vs together, resulting in a V.

I started with the idea to do this with a structural type (despite the performance disadvantage that structural types suffer from because methods are called via reflection – I just wanted to know if this could work in principle).

The requirements on the type can be described by a structural type directly, and then the interpolate method can be written in terms of the type V:

trait Container {
  type V = {
    def *(t: Double): V
    def +(v: V): V
  }

  def interpolate(t: Double, a: V, b: V): V = a * (1.0 - t) + b * t
}

That looks straightforward. But unfortunately, it doesn’t work…

<console>:8: error: recursive method + needs result type
           def +(v: V): V
                        ^
<console>:7: error: recursive method * needs result type
           def *(t: Double): V
                             ^

Note that the methods * and + in the type V refer to the type itself. Unfortunately, this is not allowed: structural types cannot be recursive, and that’s why you get these error messages. It’s impossible to use a structural type for the generic interpolate method.

On StackOverflow, oxbow_lakes put me on another track: you can do this with type classes. Type classes are an idea that comes from Haskell. The description on Wikipedia reads a bit academic and abstract, but the idea is really simple: a type class is simply a type that specifies some property of other types (it classifies types). Have a look at these two type classes, for example:

// A Multipliable is something that can be multiplied with a T, resulting in an R
trait Multipliable[-T, +R] { def *(value: T): R }

// An Addable is something that you can add a T to, resulting in an R
trait Addable[-T, +R] { def +(value: T): R }

These two can be combined into a type class Interpolatable, which satisfies the two requirements that are necessary for the interpolate method:

trait Interpolatable[T] extends Multipliable[Double, T] with Addable[T, T]

The interpolate method can now be written using this type class as follows:

def interpolate[T <% Interpolatable[T]](t: Double, a: T, b: T): T = a * (1.0 - t) + b * t

So, now we have a generic interpolate method that works on anything that can be viewed as an Interpolatable[T] (note the view bound, specified using <%). Ofcourse you now have to tell Scala that a type you want to use this with can indeed be viewed as an Interpolatable[T]; this can be done with an implicit conversion. For example for Double you can put the following implicit conversion somewhere so that it’s in scope:

implicit def doubleToInterpolatable(v1: Double) = new Interpolatable[Double] {
    def *(t: Double): Double = v1 * t
    def +(v2: Double): Double = v1 + v2
}

This all works great, but note that all in all we didn’t gain much with this approach. Although the interpolate method is generic, it’s still necessary to write an implicit conversion for each type that we want to use with the generic method – the repetition has simply shifted from the interpolate method itself to the implicit conversions that we have to write. In principle, though, the approach is valuable; interpolate is just a simple example. Suppose that you’d have a much larger and more complicated method than interpolate, then using this approach with type classes would really be worth it.

Here’s an interesting presentation by Daniel Spiewak in which he also talks about type classes.

A sidestep to C++

Note that in C++, using templates, it’s very easy to write a generic interpolate function that works on any type that satisfies the requirements, and you don’t need to specify this for each type that you want to use:

template <class T>
T interpolate(double t, T a, T b) {
    return a * (1.0 - t) + b * t;
}

There’s a big difference between templates in C++ and generics in Scala or Java. A template in C++ is used to generate code for some concrete type at the moment its necessary, and the compiler checks if the code generated from the template is valid (which it is if the concrete type satisfies the requirements). For example, if you use the template on doubles, the compiler generates an instance of the template specifically for double:

double interpolate(double t, double a, double b) {
    return a * (1.0 - t) + b * t;
}

In C++ there is no need to explicitly specify what the * and + functions do for the types that you want to interpolate; they automatically fall into place in the generated code.

  
• A =:= B, which mandates that A and B should exactly match
 
• A <:< B, which mandates that A must conform to B
 
• A A <%< B, which means that A must be viewable as B

Scala 2.8 has been released 4 weeks ago. Following our poll on the main page of the site, over 500 projects (more than 50%) have been converted to 2.8 already or the migration will be completed very soon. Now that this major version update is done, I wanted to give a quick sketch of what's to follow.

Contents

• 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

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

import scala.util.continuations._

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

Continuation Passing Style (CPS)

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

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
}

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
}

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

Nested CPS

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

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)
}

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)
}

Full versus Delimited Continuations

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

Uses

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

CPS With Return

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) }
}

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)
    })
}

Reset and Shift

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

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

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

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

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

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

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

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

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

• 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.

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

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

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

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

Annotations

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

type suspendable = cpsParam[Unit, Unit]

Nested Shift

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

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

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

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")
}

A
B
D
E
G
F
C

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
    }
}

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
    }
}

<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

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

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

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

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.