Sunday, November 22, 2009

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-case1.  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.2

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

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.

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

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

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

Saturday, October 10, 2009

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.

Monday, September 28, 2009

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.

Saturday, March 07, 2009

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