On Exceptions, Mythological Monsters and Household Appliances

Philosophy aims at the logical clarification of thoughts. Philosophy is not a body of doctrine but an activity. A philosophical work consists essentially of elucidations. Philosophy does not result in 'philosophical propositions', but rather in the clarification of propositions. Without philosophy thoughts are, as it were, cloudy and indistinct: its task is to make them clear and to give them sharp boundaries.
Wittgenstein

If language is not correct, then what is said is not what is meant; if what is said is not what is meant, then what must be done remains undone; if this remains undone, morals and art will deteriorate; if justice goes astray, the people will stand about in helpless confusion. Hence there must be no arbitrariness in what is said. This matters above everything.
Confucius

Shit happens
Forrest Gump?

Exceptions are a controversial matter among programmers. We disagree about how to deal with them. We disagree if the should be checked by the compiler. We even disagree if they are useful at all. Sometimes controversy arises from real disagreement: I may argue that test-driven-development is the best way to write software while you might say that formal proofs are the way to go. Both sides can productively debate the issue and present thoughtful arguments either way. I posit that the polemics surrounding exceptions are not of this sort. They are, rather, brought about by the inherent confusion in the mechanism. Exceptions are the Hydra of current programming languages, under a simple banner — to handle exceptional conditions — they mix several mechanisms.

The heads

Let's begin with the humble throw term, which is a sort of procedure exit statement, causing the current routine to throw his hands up in the air, call it quits, and immediately return to the caller. The only other statement with a similar effect is return. Of course when calling return, we must return something! In statically typed languages, this something must have a type: the return type of the function or method. Exceptions muddle the picture, if we think of a throw as a kind of return then what is the type being returned? There can be many answers to this question, but let me put forth a proposal: the "return type" of a "throw" is, for all intents and purposes, a variant type, and that is the second head of the Hydra.

This warrants a small digression. Most functional languages have a way of saying "this type FOO is really either a BAR or a BAZ". So every place in the code that is handed a FOO must check whether it is a BAR or a BAZ and deal appropriately. We call FOO a variant type, and BAR and BAZ are its variants. The syntax for the check is called called a type-case¹.  And where have we seen syntax for checking the type of something and then acting on it? Catch clauses!

But of course many languages lack the concept of variant types. I'll argue that in practice, exception handling code in effect greenspuns variant types. First, we can observe that in languages with checked exceptions the declaration of the exceptions a method can throw — the throws clause in Java — is basically a variant type declaration in disguise. Even when working with unchecked exceptions variants lurk behind, encoded through subtyping. Just notice how little polymorphism is exploited in exception class hierarchies. Different exceptions are given different types for the sole reason of being distinguished in catch clauses. Just like variant types.

Ok, time for the next head of the monster. We'll continue to look at the catch clause, but this time we'll look at it as a control structure. As such, it is a strange beast, neither a repetition nor purely a decision structure. Once an exception is thrown, the calling method will stop everything it was doing and jump straight to a catch block. In a way, every exception-throwing method call can be seen as a regular call paired with a conditional jump. Dijkstra may not be rolling in his grave, but he is probably feeling a little tingly.

Since we've talked about control flow, let's direct our attention to the mischievous head of the Hydra: stack unwinding. After a throw happens, if the calling method doesn't care to handle an exception, his caller will have to bare the burden or leave it up to his caller, recursively unwinding the stack until some frame decides it can be bothered to catch the exception and deal with it. This is a pretty powerful feature, sometimes it's even exploited to simulate continuations in languages that lack them.²

One more head left: call stack introspection. Besides unwinding the call stack, exceptions may reify it. It is a limited form of reflection, typically used only to print stack traces to a log someplace where they can be attentively ignored. Common lore says capturing the stack frames is an expensive operation, and so should be executed only on, well, exceptional circumstances.

Exceptional Situations

The confusion bus doesn't stop here, I'm afraid. All the complexity we've examined so far is justified under a deceptively simple banner: to handle exceptional conditions. Hidden in these four words is the vast range of situations that may be interpreted as "exceptional". Like any piece that deals with the subject of exceptions, we can't escape the temptation to suggest a taxonomy. At least this one is short, these are the three main categories of "exceptional situations":

• Programming error: A traditional example would be code trying to index an array beyond it's bounds. Ideally we would design our abstractions so as to make it impossible to commit such coding errors. From formal grammars to dependent type systems this ideal has been driven much of the research on programming languages over the years. Unfortunately, at least for now, we cannot always evade the need for run-time checks.
• External failure: Something bad happened to some component not within control of the application. Examples: network cable cut, disk crapped out, database died, sysadmin was drunk and lost a round of UNIX Russian roulette.
• Invalid user entry: "If an error is possible, someone will make it. The designer must assume that all possible errors will occur and design so as to minimize
  the chance of the error in the first place, or its effects once it gets made. Errors should be easy to detect, they should have minimal consequences, and, if possible, their effects should be reversible." This is from Don Norman's superb The Design of Everyday Things. The book is so good I'm going to slip another quote in here: "The designer shouldn't think of a simple dichotomy between errors and correct behaviour; rather, the entire interaction should be treated as a cooperative endeavor between person and machine, one in which misconceptions can arise on either side"

Let's not forget we are classifying "exceptional situations", not exception types. Here is an example that I hope will make the distinction clear. Take the always popular FileNotFoundException, that is thrown when application code attempts to read a file and the file isn't there: where do we place it on our little taxonomy? Imagine the application is a boring old word processor and the user types in the wrong file name. That obviously is a case of invalid user entry. Now, consider the case of a mail server attempting to open the file where it stores all queued outgoing mail. This file was probably created by the server application itself, maybe during the installation procedure, and its absence would be an indication that something is very borked in the server environment. The same File Not Found event is now clearly an external failure. This matters, because the strategy used for dealing with the three categories is different, as we'll soon see.

The Inevitable Cross Product

Time to look at how the heads of the hydra fare up to our new categories:

Programming errors are, by definition, unexpected. If we aren't expecting them, there is no point in writing code to handle different exception types. What could you do when you know some code tripped a NullPointerException that's different from what you would do if the offence was an IndexOutOfBounds? In other words, the variant types head is useless here. Exceptions triggered by programming errors are usually caught in a generic stack frame, in the bowels of infrastructure code — through the magic of stack unwinding — and dealt with by logging the error type, message, and stack trace. After logging there is little left to do but to roll over and die. In multi-user systems, killing the whole process is not very polite, so we might nuke just the current work item. This is the gist of the fault barrier pattern. Call stack introspection is a very valuable aid to pinpoint the bug. So valuable that I go as far as point its absence as the single most important reason to avoid C for teaching programming to beginners.

Practical strategies for dealing with external failures aren't too different. We tend to exploit stack unwinding to catch the exceptions in a frame deep in infrastructure land and log them in pretty much the same way. But, every so often, we might want to code a different action, such as to retry the operation or to trigger a compensation transaction. In these relatively rare cases it might be useful to deal distinctly with different variants. Another aspect where external failures are distinct from programming errors is that call stack introspection isn't so helpful: if the failure is external, the exact place in the code where it was detected is of little significance. Of course, it is important that the exception carries enough information to enable a system administrator to find the origin of the fault by just looking at the log.

Invalid user input is a different beast altogether. Variants are definitely useful; after all it's important to let the user know if their request was over quota rather than under quota. On run-of-the mill interactive OLTP systems, we handle invalid user entry by providing immediate feedback on what was wrong. But not every case is so simple: in some circumstances it may be important to identify suspicious input and raise security flags; in others, we could offer suggestions for the user to correct the data; in asynchronous interactions, we might want to proceed with the action substituting a default or normalized value for the invalid input; and so on. Altogether, there is a wide range of handling strategies, mostly domain-specific. This is a key observation, as not only handling strategies, but also the detection and the very definition of what values are invalid, are full of domain specific decisions. I would go as far as proposing that the controversial domain exceptions all boil down to cases of invalid user input.

What about the other heads of the monster, are they helpful for invalid user inputs? Call stack introspection is clearly not needed. Moreover, the performance costs of reifying the stack can be detrimental for the not-so-rare instances of invalid input. This isn't just premature optimization, as the conscience of these costs can prevent users from even considering exceptions for the domain logic. What about stack unwinding? I'm afraid I don't really have an answer for this one. On the one hand, domain specific handling logic seems to fit naturally in the calling method. On the other paw, if all we do is inform the user that something happened, a generic code further down the stack is awfully convenient.³ 

So what?

We've seen that the feature by the name exceptions is really a hodgepodge of language constructs. Beyond the technical aspects, the very raison d'être for the feature is also muddled. It's as if some crazy nineteenth century inventor decided that since people need to be protected from the heat and, hey, food needs cooling to be preserved as well, why not make buildings like large refrigerators? Just keep the food near the bottom where it's colder, the humans near the top where it's not freezing, and presto! His solution is absurd, but that is because the problem itself is ill-formulated: "to keep stuff cool" is not an useful problem statement.  "To deal with exceptional circumstances" isn't either.

I don't know if the above ramblings are of any practical significance. I certainly don't have any concrete proposal to make things better. My only hope is that language designers will keep in mind context and necessity when devising new constructs.

¹ In languages where pattern matching is available, it subsumes type-cases. In fact, one way of thinking about pattern matching is that it is a sophisticated form of type-case.

² Some languages without full support for exceptions do offer a feature called long jumps, that is very close to what I'm calling stack unwinding.

³ To further complicate the issue, languages offering variant types usually allow different program structuring techniques. For instance, instead of a direct chain of method calls we may thread a monad through a series of functions.

Type-safe printf in scala ‽

All the excitement surrounding Scala's next big release - 2.8.0 - reminds me of another big release a few years ago. Java 5 was poised to be a huge leg up for developers, long feature lists were all over the java blogosphere: generics, enums, enhanced for-loops, autoboxing, varargs, util.concurrent, static imports, and so on; in sum, a whole heap of goodness. But there were a few odd ducks hidden in the feature lists, most notably "an interpreter for printf-style format strings".

Anyone who has been around curly-brace-land long enough knows that printf (or java.util.Formatter) serves one main purpose: it's a poor substitute for built-in variable interpolation in the language. Unfortunatly Scala also lacks variable interpolation and there isn't much we can do about it: our BDFL has ruled. But, there is another use for printf, as a shortcut for applying special formatting for some value types. We can specify a currency format using the string "%.2f USD", or a short american date format with "%tD". We can even go wild and use the two together:

In Java:

String.format("%.2f USD at %tD", 133.7, Calendar.getInstance());

In Scala:

"%.2f USD at %tD" format (133.7, Calendar.getInstance)

This snippet is saying that 133.7 should be formatted as a decimal with two digits after the point, and Calendar.getInstance() - the horrific Javaism for "right now" - should be formatted as a date, not a time. What always trips me up is that the order of the values must exactly correspond to the order of the format specifiers. It's a simple task, but my tiny little brain keeps messing it up. Let's see if our good friend the Compiler can help.

Formatters
The first step is to have our logic leave it's String hideout and show itself. So, instead of "%.2f", we'll say F(2)^*, and instead of "%tD" we'll say D(T). D and F are now Formatters:

trait Formatter[E] {
 def formatElement(e: E):String
}
 
case class F(precision: Int) extends Formatter[Double] {
 def formatElement(number: Double) = ("%."+precision+"f") format number
}
 
import java.util.Calendar
abstract class DateOrTime
object T extends DateOrTime
object D extends DateOrTime

case class T(dateOrTime: DateOrTime) extends Formatter[Calendar] {
 def formatElement(calendar: Calendar) = dateOrTime match {
   case Time => "%tR" format calendar
  case Date => "%tD" format calendar
 }
}

Chains
Next we tackle the issue of how to chain formats together. The best bet here is to use a composite, very similar to scala.List ^***. We even have a :: method to get right-associative syntax. This is how it looks like:

val fmt = F(2) :: T(D) :: FNil

And this is the actual, quite unremarkable, code:

trait FChain {
  def :(formatter: Formatter) =
    new FCons(formatter, this)

  def format(elements: List[Any]):String
}

object FNil extends FChain {
  def format(elements: List[Any]):String = ""
}

case class FCons(formatter: Formatter, tail: FChain) extends FChain { 
  def format(elements: List[Any]):String = 
    formatter.formatElement(elements.head) + tail.format(elements.tail)
}

There is still a missing piece. Remember "%.2f USD at %tD"? We have no way of chaining the " USD at" to our formatters. This is what we want to be able to write:

val fmt = F(2) :: " USD at " :: T(D) :: FNil

The solution is simple, we overload :: in FChain:

trait FChain {
  ...
  def ::(constant: String) =
    new FConstant(constant, this)
  ...
}

and create a new type of format chain that appends the string constant:

case class FConstant(constant:String, tail: FChain) extends FChain { 
  def format(elements: List[Any]):String = 
    constant + tail.format(elements)
}

Cool, that works. But wait; what have we gained so far? The problem was to match the types of the formatters with the types of the values, and we aren't really using types at all. The remedy, of course, is to keep track of them.

Cue the Types
We want to check the types of the values passed to the FChain.format(), but this method currently takes a List[Any], a List of anything at all. We could try to parameterize it somehow and make it take a List[T], a list of some type T, instead. But, if we take a List[T], it means all values must be of the same type T, and that's not what we want. For instance, in our running example we want a list of a Double and a Calendar and nothing more.

So, List doesn't cut it. Fortunately, the great Jesper Nordenberg created an awesome library, metascala, that contains an awesomest class: HList. It is kind of like a regular List, with a set of similar operations. But it differs in an important way: HLists "remember" the types of all members of the list. That's what the H stands for, Heterogeneous. Jesper explains how it works here.

We'll change FChain to remember the required type of the elements in a type member, and to require this type in the format() method:

trait FChain {
  type Elements <: HList
  ...
  def format(elements: Elements):String
}

FNil is pretty trivial, it can only handle empty HLists (HNil):

object FNil extends FChain {
   type Elements = HNil

   def format(elements: Elements):String = "" 
}

FCons is somewhat more complicated, it is parameterized on the type of the head element, and on the type of the rest of the chain:

case class FCons[E, TL <: HList](formatter: Formatter[E], tail: FChain { type Elements = TL }) extends FChain { 
  type Elements = HCons[E, TL]

  def format(elements: Elements):String = 
    formatter.formatElement(elements.head) + tail.format(elements.tail)
}

We also had to tighten-up the types of the constructor parameters: formatter is now Formatter[E] ^** — so it can format elements of type E, and tail is now FChain{type Elements=TL} — so it can format the rest of the values. The Elements member is where we build up our list of types. It is an HCons: a cons pair of a head type - E - and another HList type - TL. We changed how to FCons constructor parameters, so we also need to change the point where we instantiate it, in FChain:

trait FChain {
  type Elements <: HList
   ...
  def ::[E](formatter: Formatter[E]) =
    new FCons[E, Elements](formatter, this)
  ...
}

Just passing along the type of the formatter and of the elements so far to FCons. FConstant has to be changed in an analogous way. This is it, now format() only accepts a list whose values are of the right type. Check out an interpreter session:

scala> (F(2) :: " USD at " :: T(D) :: FNil) format (133.7 :: Calendar.getInstance :: HNil)
res5: java.lang.String = 133.70 USD at 10/10/09

scala> (F(2) :: " USD at " :: T(D) :: FNil) format (Calendar.getInstance :: 133.7 :: HNil)
:25: error: no type parameters for method ::: (v: T)metascala.HLists.HCons[T,metascala.HLists.HCons[Double,metascala.HLists.HNil]] exist so that it can be applied to arguments (java.util.Calendar)
 --- because ---
no unique instantiation of type variable T could be found
       (F(2) :: " USD at " :: T(D) :: FNil) format (Calendar.getInstance :: 133.7 :: HNil)

Some random remarks

• The interpreter session above nicely showcases the Achilles heel of most techniques for compile-time invariant verification: the error messages are basically impenetrable.
• A related issue with this kind of metaprogramming is that it's just plain hard. The code in this post looks pretty simple (compared with, say, JimMcBeath's beautiful builders), but it took me days of fiddling around with metascala to find an adequate implementation.
• Take the above two points together and it's clear that we are talking about a niche technique. Powerful, but not for everyday coding.
• Since I've mentioned the word coding, the FChain structure showed here looks like a partial encoding of a stack-automaton. Stack automata can represent context-free grammars, if I remember my college classes correctly. That said, I don't see any particular use for this tidbit of information.
• Since this is random remarks section, I'll randomly remark that we can implement the whole thing without type members and refinements. Just good old type parameters in action.
• Since it is possible to use nothing but type parameters, and Java has type parameters, would it be possible to implement our type-safe Printf in Java? Quite possibly, a good way to start would be with Rúnar Óli's HLists in Java. Just take care not to get cut wading through all those pointy brackets. 
• A powerful type system without type inference is useless. Quoting  Benjamin Pierce: "The more interesting your types get, the less fun it is to write them down".
  

---

The whole code:

import metascala._
import HLists._

object Printf {
 trait FChain {
  type Elements <: HList

  def ::(constant: String) =
   new FConstant[Elements](constant, this)
  
  def ::[E](formatter: Formatter[E]) =
   new FCons[E, Elements](formatter, this)

  def format(elements: Elements):String
 }

 case class FConstant[ES <: HList](constant:String, tail: FChain { type Elements = ES }) extends FChain { 
  type Elements = ES

  def format(elements: Elements):String = 
   constant + tail.format(elements)
 
 }
 
 object FNil extends FChain {
  type Elements = HNil
  def format(elements: Elements):String = ""
 }

 case class FCons[E, TL <: HList](formatter: Formatter[E], tail: FChain { type Elements = TL }) extends FChain { 
  type Elements = HCons[E, TL]

  def format(elements: Elements):String = 
   formatter.formatElement(elements.head) + tail.format(elements.tail)
 
 }
 
  trait Formatter[E] {
   def formatElement(e: E):String
  }
   
  case class F(precision: Int) extends Formatter[Double] {
   def formatElement(number: Double) = ("%."+precision+"f") format number
  }
   
  import java.util.Calendar
  abstract class DateOrTime
  object T extends DateOrTime
  object D extends DateOrTime
  
  case class T(dateOrTime: DateOrTime) extends Formatter[Calendar] {
   def formatElement(calendar: Calendar) = dateOrTime match {
     case T => "%tR" format calendar
    case D => "%tD" format calendar
   }
  }
 }

* Or F(precision=2) thanks to Scala 2.8 awesome named parameter support.

** In fact, the previous untyped version didn't even compile, as Formatter has always been generic. Sorry for misleading you guys.

*** If you are unfamiliar with how Scala lists are built, check out this article.

Context, context, context

Joel Spolsky's latest diatrabe, and the outcry the blogosphere predictably issued, got me thinking about, well, about an old joelonsoftware article: Five Worlds. This one is a favorite of mine, maybe second only to the classic The Law of Leaky Abstractions. The point, in a nutshell, is that we too often forget the importance of context when discussing our trade.

I personally believe the Agile movement induced solid progress in software development teams worldwide, but we shouldn't forget where it came from: corporate software projects. Extreme Programming was born in a Chrysler project, it doesn't get much more corporate than this. Most of the signatures under the Agile Manifesto come from consultants, and again, is there anything more corporate that consultants?

This isn't meant to be a put-down of enterpresey work. I am myself a consultant and won't apologise for it. But it pays to look at the differences between the internal corporate projects world and the software product development world:

• Corporate projects tend to be wide: lots of forms gathering data, lots of reports spitting data out, huge ugly menus. Products are usually more focused, with fewer interaction points that are backed with more sophisticated logic.
• A consequence is that, while a developer for an internal corporate system might see any given screen a handful of times throughout the project, a software product developer can live inside the system almost as much as the end users (and so, catch more bugs).
• Corporate systems are expected to reproduce complicated real-life behavior. Tax codes and compliance requirements come to mind. Sounds boring, but at least there are clear expectations for what the correct functioning of the software should be. Another way to put it is that in these systems, it's feasible to anticipate putative bugs. In a product, on the other hand, there could be many undesirable characteristics that are impossible to precisely specify (say we're working on a game, and level 3 should be just a notch more difficult than level 2 but still much easier that level 4 - how would you precisely specify that?).
• First impressions are crucial for a product. A 1.0 dud can kill a startup - just think of Cuil. Not only it must work, it must be polished, discoverable and pretty. The incentive framework for internal products is very different; as long as the team delivers anything at all, even if almost useless, it's often possible to change course and steer the project towards the actual needs.

Reading these points, it seems that I'm justifying a lower standard of code quality in product development. I'm not. TDD really does allow you to go faster, I can't even fathom what would be like to code without refactoring every few seconds, and all the old sayings about how we spend much more time reading that writing code are true, regardless of how crucial is that we reach that 1.0 milestone.

I was desperatly trying to avoid this cliché, but I just couldn't resist. In the end, we should really try to learn from each other. Agile teams should spend more time thinking about the people who will live in their systems day-in-day-out, and product devs might have a thing or two to learn from the fast pace of a pair TDD-ing away.

Software

This is my Quality is Dead hypothesis: a pleasing level of quality for end users has become too hard to achieve while demand for it has simultaneously evaporated and penalties for not achieving it are weak. The entropy caused by mindboggling change and innovation in computing has reached a point where it is extremely expensive to use traditional development and testing methods to create reasonably good products and get a reasonable return on investment. Meanwhile, user expectations of quality have been beaten out of them. When I say quality is dead, I don’t mean that it’s dying, or that it’s under threat. What I mean is that we have collectively– and rationally– ceased to expect that software normally works well, even under normal conditions. Furthermore, there is very little any one user can do about it.

James Bach

If you look at engineering or maths, we've been doing that for thousands of years, so we now know how to build a building and make it solid. With code, we've been doing computer science for 70-75 years, so we are still scratching the surface - we don't have a real theory or like physics, where they have a good foundation. We have the Turing machine that doesn't really reflect distributed computation. The lambda calculus captures certain parts, then there is a lot of process algebra, but it's not yet clear that we really have understood everything, which I think is fantastic, because that means there is opportunity to discover new things.

Erik Meijer

Much of what is wrong about our field is that many of the ideas that happened before 1975 are still the current paradigm. He [Alan Kay] has a strong feeling that our field has been mired for some time, but because of Moore’s law, there are plenty of things to work on. The commercialization of personal computing was a tremendous distraction to our field and we haven’t, and may not, recover from it.

One of Alan’s undergraduate degrees is in molecular biology. He can’t understand it anymore despite having tried to review new developments every few years. That’s not true in computer science. The basics are still mostly the same. If you go to most campuses, there is a single computer science department and the first course in computer science is almost indistinguishable from the first course in 1960. They’re about data structures and algorithms despite the fact that almost nothing exciting about computing today has to do with data structures and algorithms.

Alan Kay (paraphrased by Phil Windley)

[Actually, check the comments for Alan's clarification].

Comments on Comments on the Previous post

• Henry Ware suggested a modification to the builder with abstract members removing a lot of the boilerplate. Incidentally, this is a nice illustration of how nested types can be put to a good use in Scala.
• Justin ported the code to Haskell, which was very cool.
• A couple of commenters suggested that languages with support for default parameter values (like Python and Groovy) don't need elaborate constructs such as the builder pattern. There are two ways to respond. One is to remind that the intent of the pattern, specially as originally described in the GoF book, has little to do with optional data. The other is to acknowledge that I probably put too much emphasis on this issue and forgot to mention a very common idiom for building objects in Scala: just declare mandatory "parameters" as abstract vals and optional ones as concrete vals with default values, like so:
  

  abstract class OrderOfScotch {
    val brand:String
    val mode:Preparation
    val isDouble:Boolean 
    val glass:Option[Glass] = None
  }

  
  And to instantiate:
  

  val myDose = new OrderOfScotch {val brand = "Bobby Runner"; val mode = OnTheRocks; val isDouble = false}

• I guess that's it. Thanks y'all.
  

Type-safe Builder Pattern in Scala

The Builder Pattern is an increasingly popular idiom for object creation. Traditionally, one of it's shortcomings in relation to simple constructors is that clients can try to build incomplete objects, by omitting mandatory parameters, and that error will only show up in runtime. I'll show how to make this verification statically in Scala.


So, let's say you want to order a shot of scotch. You'll need to ask for a few things: the brand of the whiskey, how it should be prepared (neat, on the rocks or with water) and if you want it doubled. Unless, of course, you are a pretentious snob, in that case you'll probably also ask for a specific kind of glass, brand and temperature of the water and who knows what else. Limiting the snobbery to the kind of glass, here is one way to represent the order in scala.

sealed abstract class Preparation  /* This is one way of coding enum-like things in scala */
case object Neat extends Preparation
case object OnTheRocks extends Preparation
case object WithWater extends Preparation

sealed abstract class Glass
case object Short extends Glass
case object Tall extends Glass
case object Tulip extends Glass

case class OrderOfScotch(val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])

A client can instantiate their orders like this:

val normal = new OrderOfScotch("Bobby Runner", OnTheRocks, false, None)
val snooty = new OrderOfScotch("Glenfoobar", WithWater, false, Option(Tulip));

Note that if the client doesn't want to specify the glass he can pass None as an argument, since the parameter was declared as Option[Glass]. This isn't so bad, but it can get annoying to remember the position of each argument, specially if many are optional. There are two traditional ways to circumvent this problem — define telescoping constructors or set the values post-instantiation with accessors — but both idioms have their shortcomings. Recently, in Java circles, it has become popular to use a variant of the GoF Builder pattern. So popular that it is Item 2 in the second edition of Joshua Bloch's Effective Java. A Java-ish implementation in Scala would be something like this:

class ScotchBuilder {
  private var theBrand:Option[String] = None
  private var theMode:Option[Preparation] = None
  private var theDoubleStatus:Option[Boolean] = None
  private var theGlass:Option[Glass] = None

  def withBrand(b:Brand) = {theBrand = Some(b); this} /* returning this to enable method chaining. */
  def withMode(p:Preparation) = {theMode = Some(p); this}
  def isDouble(b:Boolean) = {theDoubleStatus = some(b); this}
  def withGlass(g:Glass) = {theGlass = Some(g); this}

  def build() = new OrderOfScotch(theBrand.get, theMode.get, theDoubleStatus.get, theGlass);
}

This is almost self-explanatory, the only caveat is that verifying the presence of non-optional parameters (everything but the glass) is done by the Option.get method. If a field is still None, an exception will be thrown. Keep this in mind, we'll come back to it later.

The var keyword prefixing the fields means that they are mutable references. Indeed, we mutate them in each of the building methods. We can make it more functional in the traditional way:

object BuilderPattern {
  class ScotchBuilder(theBrand:Option[String], theMode:Option[Preparation], theDoubleStatus:Option[Boolean], theGlass:Option[Glass]) {
    def withBrand(b:String) = new ScotchBuilder(Some(b), theMode, theDoubleStatus, theGlass)
    def withMode(p:Preparation) = new ScotchBuilder(theBrand, Some(p), theDoubleStatus, theGlass)
    def isDouble(b:Boolean) = new ScotchBuilder(theBrand, theMode, Some(b), theGlass)
    def withGlass(g:Glass) = new ScotchBuilder(theBrand, theMode, theDoubleStatus, Some(g))

    def build() = new OrderOfScotch(theBrand.get, theMode.get, theDoubleStatus.get, theGlass);
  }

  def builder = new ScotchBuilder(None, None, None, None)
}

The scotch builder is now enclosed in an object, this is standard practice in Scala to isolate modules. In this enclosing object we also find a factory method for the builder, which should be called like so:

import BuilderPattern._

val order =  builder withBrand("Takes") isDouble(true) withGlass(Tall)  withMode(OnTheRocks) build()

Looking back at the ScotchBuilder class and it's implementation, it might seem that we just moved the huge constructor mess from one place (clients) to another (the builder). And yes, that is exactly what we did. I guess that is the very definition of encapsulation, sweeping the dirt under the rug and keeping the rug well hidden. On the other hand, we haven't gained all the much from this "functionalization" of our builder; the main failure mode is still present. That is, having clients forget to set mandatory information, which is a particular concern since we obviously can't fully trust the sobriety of said clients*. Ideally the type system would prevent this problem, refusing to typecheck a call to build() when any of the non-optional fields aren't set. That's what we are going to do now.

One technique, which is very common in Java fluent interfaces, would be to write an interface for each intermediate state containing only applicable methods. So we would begin with an interface VoidBuilder having all our withFoo() methods but no build() method, and a call to, say, withMode() would return another interface (maybe BuilderWithMode), and so on, until we call the last withBar() for a mandatory Bar, which would return an interface that finally has the build() method. This technique works, but it requires a metric buttload of code — for n mandatory fields 2ⁿ interfaces should be created. This could be automated via code generation, but there is no need for such heroic efforts, we can make the typesystem work in our favor by applying some generics magic. First, we define two abstract classes:

abstract class TRUE
abstract class FALSE

Then, for each mandatory field, we add to our builder a generic parameter:

class ScotchBuilder[HB, HM, HD](val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {

  /* ... body of the scotch builder .... */

}

Next, have each withFoo method pass ScotchBuilder's type parameters as type arguments to the builders they return. But, and here is where the magic happens, there is a twist on the methods for mandatory parameters: they should, for their respective generic parameters, pass instead TRUE:

class ScotchBuilder[HB, HM, HD](val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {
  def withBrand(b:String) = 
      new ScotchBuilder[TRUE, HM, HD](Some(b), theMode, theDoubleStatus, theGlass)

  def withMode(p:Preparation) = 
    new ScotchBuilder[HB, TRUE, HD](theBrand, Some(p), theDoubleStatus, theGlass)

  def isDouble(b:Boolean) = 
    new ScotchBuilder[HB, HM, TRUE](theBrand, theMode, Some(b), theGlass)

  def withGlass(g:Glass) = 
    new ScotchBuilder[HB, HM, HD](theBrand, theMode, theDoubleStatus, Some(g))
}

The second part of the magic act is to apply the world famous pimp-my-library idiom and move the build() method to an implicitly created class, which will be anonymous for the sake of simplicity:

implicit def enableBuild(builder:ScotchBuilder[TRUE, TRUE, TRUE]) = new {
  def build() = 
    new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);
}

Note the type of the parameter for this implicit method: ScotchBuilder[TRUE, TRUE, TRUE]. This is the point where we "declare" that we can only build an object if all the mandatory parameters are specified. And it really works:

scala> builder withBrand("hi") isDouble(false) withGlass(Tall) withMode(Neat) build()
res5: BuilderPattern.OrderOfScotch = OrderOfScotch(hi,Neat,false,Some(Tall))

scala> builder withBrand("hi") isDouble(false) withGlass(Tall)  build()                
<console>:9: error: value build is not a member of BuilderPattern.ScotchBuilder[BuilderPattern.TRUE,BuilderPattern.FALSE,BuilderPattern.TRUE]
       builder withBrand("hi") isDouble(false) withGlass(Tall)  build()

So, we achieved our goal (see the full listing below). If you are worried about the enormous parameter lists inside the builder, I've posted here an alternative implementation with abstract members instead. It is more verbose, but also cleaner.

Now, remember those abstract classes TRUE and FALSE? We never did subclass or instantiate them at any point. If I'm not mistaken, this is an idiom named Phantom Types, commonly used in the ML family of programming languages. Even though this application of phantom types is fairly trivial, we can glimpse at the power of the mechanism. We have, in fact, codified all 2ⁿ states (one for each combination of mandatory fields) as types. ScotchBuilder's subtyping relation forms a lattice structure and the enableBuild() implicit method requires the supremum of the poset (namely, ScotchBuilder[TRUE, TRUE, TRUE]). If the domain requires, we could specify any other point in the lattice — say we can doll-out a dose of any cheap whiskey if the brand is not given, this point is represented by ScotchBuilder[_, TRUE, TRUE]. And we can even escape the lattice structure by using Scala inheritance. Of course, I didn't invent any of this; the idea came to me in this article by Matthew Fluet and Riccardo Pucella, where they use phantom types to encode subtyping in a language that lacks it.

---

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

  sealed abstract class Glass
  case object Short extends Glass
  case object Tall extends Glass
  case object Tulip extends Glass

  case class OrderOfScotch(val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])

  abstract class TRUE
  abstract class FALSE

  class ScotchBuilder
  [HB, HM, HD]
  (val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {
    def withBrand(b:String) = 
      new ScotchBuilder[TRUE, HM, HD](Some(b), theMode, theDoubleStatus, theGlass)

    def withMode(p:Preparation) = 
      new ScotchBuilder[HB, TRUE, HD](theBrand, Some(p), theDoubleStatus, theGlass)

    def isDouble(b:Boolean) = 
      new ScotchBuilder[HB, HM, TRUE](theBrand, theMode, Some(b), theGlass)

    def withGlass(g:Glass) = new ScotchBuilder[HB, HM, HD](theBrand, theMode, theDoubleStatus, Some(g))
  }

  implicit def enableBuild(builder:ScotchBuilder[TRUE, TRUE, TRUE]) = new {
    def build() = 
      new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);
  }

  def builder = new ScotchBuilder[FALSE, FALSE, FALSE](None, None, None, None)
}

* Did you hear that noise? It's the sound of my metaphor shattering into a million pieces

EDIT 2008-07-09 at 19h00min: Added introductory paragraph.

A couple of interesting DSLs

It may not yet be an industry tsunami, but there certainly is a growing wave of interest in Domain Specific Languages. As often happens when thinking about programming language design, there appears to be an excessive concern with syntax and little talk of semantics. Dave Thomas points out how much effort is wasted playing syntactic games to make code look like English; effort that would be better spent identifying and representing the domain. To prove his point he talks about make and active record and Groovy builders as examples of successful DSLs. I've stumbled upon some more examples of semantically interesting DSLs on a couple of papers and thought it would be worthwhile to share some stuff I learned in the process.


Kay
Alan Kay is one of the giants in our little science, known for his fearless disposition to carry out "big ideas". His most recent endeavor, partnering with Ian Piumarta and others, is a good example of that. The project is called "Steps Toward the Reinvention of Programming" and aims to build a complete software system, from the metal up to the applications, in under 20 KLOC. Some of that magic will be achieved through, you guessed it, domain specific languages. To quote from first published report.

We also think that creating languages that fit the problems to be solved makes solving the problems easier, makes the solutions more understandable and smaller, and is directly in the spirit of our “active-math” approach. These “problem-oriented languages” will be created and used for large and small problems, and at different levels of abstraction and detail.

The project is only a year-old, so it is understandably far from the goal of a full-system. But they have already delivered bits and pieces that give an idea of the path forward. A particularly cool part is their TCP/IP stack implementation. The first step in any networking stack is to unmarshal packet headers according to some specification. For IP we look in RFC-791 and find a lovely piece of ASCII art describing just that:

+-------------+-------------+-------------------------+----------+----------------------------------------+
| 00 01 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15 | 16 17 18 | 19 20 21 22 23 24 25 26 27 28 29 30 31 |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|   version   | headerSize |       typeOfService      |                     length                        |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|                     identification                  | flags    |                  offset                |
+---------------------------+-------------------------+----------+----------------------------------------+
|       timeToLive          |         protocol        |                    checksum                       |
+---------------------------+-------------------------+---------------------------------------------------+
|                                               sourceAddress                                             |
+---------------------------------------------------------------------------------------------------------+
|                                             destinationAddress                                          |
+---------------------------------------------------------------------------------------------------------+

Most implementations just hardcode these definitions, and those for TCP, and for UDP, and so on. Of course the footprint of the traditional approach is too high for Kay and Piumarta purposes. They opted for a seemingly odd technique: just grab the data from the specifications. Here is, in its entirety, the code for unmarshaling IP headers:

                                           { structure-diagram }
+-------------+-------------+-------------------------+----------+----------------------------------------+
| 00 01 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15 | 16 17 18 | 19 20 21 22 23 24 25 26 27 28 29 30 31 |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|   version   | headerSize |       typeOfService      |                     length                        |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|                     identification                  | flags    |                  offset                |
+---------------------------+-------------------------+----------+----------------------------------------+
|       timeToLive          |         protocol        |                    checksum                       |
+---------------------------+-------------------------+---------------------------------------------------+
|                                               sourceAddress                                             |
+---------------------------------------------------------------------------------------------------------+
|                                             destinationAddress                                          |
+---------------------------------------------------------------------------------------------------------+
                           ip -- Internet Protocol packet header [RFC 791]

This is actual working code. But wait; didn't they just swept the parsing dirt under the rug? The rug here being the code to parse this fine looking tables. Surprisingly, that code is a whopping 27 lines of clean grammar definitions with semantic actions. The "trick", so to speak, is the underlying parsing mojo provided my Piumarta's OMeta system. Which is, by the way, itself implemented in about 40 lines of OMeta code. Yeah, turtles all the way down and all that stuff...

Ok, this is all very cute, but I seem to have fallen on my own trap and can't stop talking about syntax. The next bit of this networking stack is a little more interesting, the problem now is to handle each incoming TCP packet according to a set of specified rules such as "in response to a SYN the server must reply with a SYN-ACK packet". Here is the code:

['{ svc     = &->(svc? [self peek])
    syn     = &->(syn? [self peek]) .   ->(out ack-syn    -1 (+ sequenceNumber 1) (+ TCP_ACK TCP_SYN) 0)
    req     = &->(req? [self peek]) .   ->(out ack-psh-fin 0 (+ sequenceNumber datalen (fin-len tcp))
                                                             (+ TCP_ACK TCP_PSH TCP_FIN)
                                                             (up destinationPort dev ip tcp
                                                                 (tcp-payload tcp) datalen))
    ack     = &->(ack? [self peek]) .   ->(out ack           acknowledgementNumber
                                                             (+ sequenceNumber datalen (fin-len tcp))
                                                             TCP_ACK 0)
            ;
    ( svc (syn | req | ack | .) | .     ->(out ack-rst       acknowledgementNumber
                                                             (+ sequenceNumber 1)
                                                             (+ TCP_ACK TCP_RST) 0)
    ) *
  } < [NetworkPseudoInterface tunnel: '"/dev/tun0" from: '"10.0.0.1" to: '"10.0.0.2"]]

The set of rules above is nothing more than a grammar and the code to construct response packets is implemented as corresponding semantic actions. This snippet is much harder do grok than the pretty tables we just saw, but it's much more interesting as well. The crucial idea is to pattern-match on the stream of incoming packets looking for flag patterns and respond accordingly. What's nice is that they already had a well-honed pattern matching language in OMeta's Parsing Expression Grammars. I should note that a powerful parsing engine is not a Golden Hammer, but it is a useful and underutilized computational model. And realizing that is much more significant, IMHO, than the procrustean effort of trying to shoehorn "natural language" text into a general purpose programming language.


Pierce
Now let's turn our attention to a different kind of DSL, developed for the Harmony project led by Pierce at UPenn. The problem to solved here is synchronizing bookmark data among different browsers. Seems a far cry from "reinventing computer programming", but there are some intricacies involved, as we shall soon see. The basic approach taken is to transform each browser-specific representation to an abstract view, synchronize the data in this abstract form, and than propagate it back to the concrete form. If you squint hard enough you can see these transformations are a form of the general "view-update problem" known from database literature. Instead of extracting a view from a set of tables, updating it, and propagating the changes back to the original tables, they get an abstract representation from a concrete one, update it (the synchronization proper), and putback the modified data to the original concrete format. So, one concrete input for Mozila would be the following html-ish file:

<html>
 <head> <title>Bookmarks</title> </head>
 <body>
  <h3>Bookmarks Folder</h3>
  <dl>
   <dt> <a href=\"www.google.com\"
           add_date=\"1032458036\">Google</a> </dt>
   <dd>
    <h3>Conferences Folder</h3>
    <dl>
     <dt> <a href=\"www.cs.luc.edu/icfp\"
             add_date=\"1032528670\">ICFP</a> </dt>
    </dl>
   </dd>
  </dl>
 </body>
</html>

The abstract representation of that data is :

{name -> Bookmarks Folder
 contents ->
  [{link -> {name -> Google
              url -> www.google.com}}
   {folder ->
     {name -> Conferences Folder
      contents ->
       [{link ->
         {name -> ICFP
          url -> www.cs.luc.edu/icfp}}]}}]}

That's a textual representation of a labeled tree. Each {..} is a tree node, subnodes are identified by a label (i.e. label -> {...} ) and stuff inside square brackets are lists. So, basically we have two tree "schemas" and wish to translate between them. Here is where domain specific languages will come into play. We could naively propose to just whip up a couple of XSLTs and be done with it. The get direction would be trivial, but the putback is trickier. Note that the abstract representation lacks information about the add_date of the bookmarks; this is because not all browsers store this data. In a way, the abstract format is a minimal subset of the kinds of data that each browser is interested in. So, the putback of new bookmarks coming from non-Mozilla browsers could just default to some arbitrary date value, but we don't want to lose the data we have for existing bookmarks! This rules-out using a simple stylesheet for the putback.

Essentially, this is why the view-update problem is an interesting research question. The relevance to this post is the path Harmony's team chose to solve it, building a bidirectional language*. It's similar to a functional language, but instead of functions they have lenses. A lens is a pair of functions, one for get (from the concrete to the abstract) and one for putback. A putback lens takes a modifed abstract element and the original concrete element, mapping to an update concrete element.

Rephrasing more formally, though diverging from the notation used in the paper, a lens L would be a pair of functions (Lg, Lp). Using A as the domain of abstract elements and C for the domain of the concrete elements, the functions would be defined in:

Lg: C -> A
Lp: (C x A) -> C

So far we haven't gained much, but the above definitions allow us to express our requirements of "information conservation" as equations:

Lp(Lg(c), c) = c for all c in C
Lg(Lp(a, c)) = a for all a in A and c in C

Any lens obeying this equations can be called "well-formed". To exemplify, here is the identity lens (the arrow pointing up is the get and the opposite is the putback):



Absolutely uninteresting, as to be expected from any identity operation, but note that last line. It is the lens' type signature. Yes, this DSL has a full-blown type system! Take a look at a more interesting example, the map lens, which is analogous to the map function from functional programming:



The behavior isn't complicated, map is parametrized by another lens l, and just applies it to each subnode in the concrete tree for get. In the putback direction, it also just applies the putback for each element in the abstract tree, relying on the assumption that l behaves correctly for nodes missing in c. Now look at the scary type signature, which, to be perfectly honest, I don't fully comprehend myself. It is there to assure the well-formedness of map (and a couple of other properties), based on the type of l.

Lest I reproduce the entire paper here, and completely butcher it in the process, I'll cut to the final chapter of the story and show the program that maps between Mozilla's bookmark format and the abstract representation:

link =
  hoist *;
  hd [];
  hoist a;
  rename * name;
  rename href url;
  prune add_date {$today};
  wmap {name -> (hd []; hoist PCDATA)}

folder = hoist *;
  xfork (*h} {name}
    (hoist *t;
     hd [];
     rename dl contents)
  wmap {name -> (hoist *;
                               hd [];
                               hoist PCDATA)
               contents -> (host *;
                                    list_map item)}

item =
  wmap {dd -> folder, dt -> link};
  rename_if_present dd folder;
  rename_if_present dt link

bookmarks =
  hoist html;
  hoist *l
  tl {|head --> {| * --> [ {|title --> {|* -->
          [{|PCDATA --> Bookmarks|}]|}|}]|}|};
  hd [];
  hoist body;
  folder

I'm afraid I'm unable to explain much of this program without going deeper than is appropriate here. But see how much is accomplished in probably fewer lines of code than would be required for expressing a mere transformation in XSLT . And of course, the whole bookmark synchronization thing is just a toy problem; the resulting system is powerful enough to tackle larger beasts. See the other papers in the project website, where they apply lenses to the traditional relational view-update problem, to character Strings and to data replication in distributed settings.


Wrapping up

• DSL design is language design, and that involves more than just syntax.
• Sometimes an well-known computational model can be repurposed to fit domain requirements, like Kay and Piumarta did adopting a grammar parsing engine to process a packet stream.
• Automata and similar non-turing-complete models can be very useful in Domain Specific Languages.
  
• Sometimes it pays to develop whole new semantics for your DSL.
• Of course there is little that is actually "wholly new" in the world. Taking Harmony's semantics for example, the team did apply a lot of domain theory to prove the totality of their lens combinators.
  
• If you can identify invariants that are hard to get right, it may pay to express them in a type system. But be warned that this is no child's play; even Pierce didn't go all the way to building a typechecker for his lenses.
  
• Have fun!