Scala's Delimited Continuations -- A Use Case

When I first talked about the upcoming Scala 2.8 Delimited Continuations, I did not go into what uses I foresaw for them, mostly because I was pretty sure people would find uses I could never have imagined for it.

Well, people did find uses I could never have imagined, it turns out! If Scala and Distributed Computing are your things -- hell, if even one of them is your thing! -- do go check Swarm out.

Is rewritting really bad?

Paul Chiusano tell us his Scala success story, and while I find it interesting, there's something that attracts my attention in it. He says:

Finally, I'd like to scrutinize the folk wisdom that rewrites are generally a bad idea.

That got me thinking a bit. That wisdom predates some developments which only became widespread practices recently. In particular, BDD and Continuous Integration.

It occurs to me that if I decide to rewrite something from scratch, I'll have a large set of tests in the form of BDD (which tests for Behavior, so a lot of it should still apply), plus the tests for all bugs that were caught and fixed, for which you them add tests to help with CI.

Furthermore, because you are doing BDD and CI, and possibly TDD for low level stuff, you won't get far with the same errors in case you re-introduce them.

That's something to think about... maybe the old wisdom requires some revisiting.

At any rate, I'd like to point out that this particular piece of wisdom might have become widespread because of this article by Joel Spolsky. I'll quote one part of it, though:

These problems can be solved, one at a time, by carefully moving code, refactoring, changing interfaces. They can be done by one programmer working carefully and checking in his changes all at once, so that nobody else is disrupted. Even fairly major architectural changes can be done without throwing away the code.

Well, that's precisely what Paul Chiusano did! So, on the other hand, perhaps is too soon to dispose of that wisdom...

Type Safe Builder Pattern

I was reading these days an interesting article by Jim McBeath about type safe builder patterns. The interesting part was the use of Church encoding to be able to control the ordinality of certain types, but as I went to the original article by Rafael de F. Ferreira, I found the silliest criticism, which I quote below:

My but it's sad that Java/Scala has to resort to a design pattern for this (if I'm understanding the post correctly).

In Python, we have keyword arguments and default argument values, which allows for very rich parameter declarations.

Well, first of all, a builder pattern is targetted at complex objects. Imagine, for instance, a maze with multiple rooms and passages, where the creation process might entail adding hundred of such components. Not exactly the sort of thing you want to pass as a single parameter list, I'd imagine. In fact, it might not even be possible to do it, because you might not have all information needed in the same place and/or time.

But, most importantly, "keyword arguments" do not enforce type safety. So even if it were an alternative to any problem requiring the Builder pattern, it would fail at the basic premise of the article, which is providing type safety.

So, I decided to show something you can't do with keyword arguments, which, by the way, are called "named parameters" in Scala 2.8, which is mutual exclusion. I'm adapting this example from here, which was written in reply to a follow up by Jim on his original article.

For this example, I assume a "Car" builder, where one has to make a choice about number of doors and brand, and may also choose to get a convertible, but the convertible is incompatible with cars with five doors. This code is nowhere as clear as Jim's, but gets the job done faster, so I could get on with my life. :-)

So, I hope you like it. And if you can clean it up, or come up with more likely scenarios, please share it.

// This code is based on an idea of Rafael de F. Ferreira and was implemented as a response to
// Jim McBeath's blog post http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-part-2.html
// Everyone is free to use, modify, republish, sell or give away this work without prior consent from anybody.

object Scotch {
sealed abstract class Preparation
case object Neat extends Preparation
case object OnTheRocks extends Preparation
case object WithWater extends Preparation

case class OrderOfScotch private[Scotch](val brand:String, val mode:Preparation, val isDouble:Boolean)

trait Option[+X]
case class Some[+X](x:X) extends Option[X]{
  def get:X = x
}
trait None extends Option[Nothing] // this differs in the original implementation
case object None extends None

case class Builder[HAS_BRAND<:Option[String],HAS_MODE<:Option[Preparation],HAS_DOUBLE<:Option[Boolean]] private[Scotch]
             (brand:HAS_BRAND
             ,mode:HAS_MODE
             ,isDouble:HAS_DOUBLE
             ) {
  def ~[X](f:Builder[HAS_BRAND,HAS_MODE,HAS_DOUBLE] => X):X = f(this)
}
           
def withBrand[M<:Option[Preparation],D<:Option[Boolean]](brand:String)(b:Builder[None,M,D]):Builder[Some[String],M,D] =
  Builder(Some(brand),b.mode,b.isDouble)
def withMode[B<:Option[String],D<:Option[Boolean]](mode:Preparation)(b:Builder[B,None,D]):Builder[B,Some[Preparation],D] =
  Builder(b.brand,Some(mode),b.isDouble)
def isDouble[B<:Option[String],M<:Option[Preparation]](isDouble:Boolean)(b:Builder[B,M,None]):Builder[B,M,Some[Boolean]] =
  Builder(b.brand,b.mode,Some(isDouble))

def build(b:Builder[Some[String],Some[Preparation],Some[Boolean]]):OrderOfScotch =
  OrderOfScotch(b.brand.get,b.mode.get,b.isDouble.get)

def builder:Builder[None,None,None] = Builder(None,None,None)

def test {
  val x:OrderOfScotch = builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ build
  // builder ~ isDouble(true) ~ withMode(Neat) ~ build // fails
  // builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ withBrand("Blubber") ~ build // fails
  x
}
}

A Number Puzzle

My friend came up with a new puzzle. Given a 3x3 matrix, fill it with the numbers 1 through 9, without repetition, in such a way that adding the three digits from any line, column or diagonal will yield exactly the same result.

This time I went for conciseness. Instead of laying out a 3x3 array -- or what have you -- I'll take a list of 9 elements, and assume the elements are laid out left to right, then top to down, so that the third element of the second line is the sixth element of the list, for example. Now, before I try to solve it, I have to devise a way to test the conditions. First, let's create a list of list of indices for each line, column of diagonal possible. This can be done programmatically, of course, like this:

 
val cols = List.range(0,3)
val lines = cols map (_ * 3)
val allLines = lines map (l => cols map (l + _))
val allCols = cols map (c => lines map (c + _))
val diagLR = lines zip cols map Function.tupled(_+_)
val diagRL = lines zip cols.reverse map Function.tupled(_+_)
val indices = diagLR :: diagRL :: allLines ::: allCols

I decided just to enter it by hand, though:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))

Now, I want to test this. Suppose I have a list of numbers representing the solution. I can replace the indices by the corresponding number like this:

 
indices map (_ map (solution(_)))

from which is quite easy to compute how much each line, column and diagonal adds to:

 
indices map (_ map (solution(_)) sum)

One way, then, to check if all numbers are equal is to simply compare them:

 
indices map (_ map (solution(_)) sum) match { case head :: tail => tail forall (_ == head) }

Not concise enough for me, though. I prefer this:

 
(indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Our test function, then, is:

 
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Now, how to compute the solutions? We can do it recursively with lists, recursions, filters, etc. Too much work. Let's just enumerate the possible solutions. The first element can be represented by the index over a nine-elements list of a "seed" solution. The second element can be represented by an index over the eight-element list of remaining elements, and so on. We can disambiguate the first index from the second by multiplying the second by 9, and add both. We can repeat this over and over for every other element in the list. So, to go from a number representing the solution, plus a seed list, to the solution, we can write this function:

 
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))

Now, given this representation of the solutions of this problem, it should be clear that the number of solutions is the factorial of 9, so there are solutions from 0 to 9! - 1. So, let's create a seed, and, non-strictly (to avoid out of memory errors), generate our possible solutions:

 
val seed = 1 to 9 toList
val possibleSolutions = Stream.range(0, seed reduceLeft (_*_)) map (numToIndices(_, seed))

Keeping the head of a stream is not a good idea, though. We need to filter for the actual solutions before assigning it to any val. Which, of course, we'll give you the final solutions:

 
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Not particularly efficient, but the line count is good:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))
val seed = 1 to 9 toList
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Which we can then print with:

 
println(solutions map (_.iterator grouped 3 map (_ mkString) mkString "\n") mkString "\n")