Wednesday, June 13, 2012

Unit testing isn't enough. You need static typing too.

When I was working on my research for my Masters degree I promised myself that I would publish my paper online under a free license, as soon as I had graduated. Unfortunately there seems to be an unwritten rule of Graduate School research. You spend so much time focusing on a single topic of study that by the time you graduate you are sick of it. So more than year later I'm finally putting my paper online. For those that don't want to read the full paper (it's not terribly long for a research paper at 60 pages, but it's no tweet either) I'll include a shorter summary below. The summary will omit some important information and so if you would like to provide constructive or destructive feedback I ask that the feedback be directed towards the full paper and not the quick summary.

For me research I wanted to test the frequently cited claim by proponents of dynamically typed programming languages that static typing was not needed for detecting bugs in programs. The core of this claim is as follows:
  1. Static typing is insufficient for detecting bugs, and so unit testing is required.
  2. Once you have unit testing static type checking is redundant.
  3. Because static typing rejects some valid programs static typing is harmful.

Despite the fact that I had heard and read this claim many times I couldn't find any research to back this claim up. So I decided to conduct an experiment to see if in practice unit tests really did obviate static typing for error detection. I also wanted to see if developers frequently use dynamic constructs that can't be expressed in a statically typed programming language.

My experiment would consist of finding examples of open source, unit tested programs written in a dynamically typed programming language and manually translating them into a statically typed programming language. I would then quantify how many (if any) defects were detected by the type checker, and how many dynamic constructs couldn't be directly expressed due to being rejected by the static type checker. I should emphasize that for this experiment I would *not* be simply rewriting the program, but doing a direct line by line translation from one programming language to another. I would not count defects that were not detected by the type checker, nor any defects that could not be reproduced in the original program.

Before starting the experiment I needed to choose a dynamically typed programming language that I would translate programs from. I also needed to choose a statically typed programming language that I would translate those programs to. The criteria for the dynamically typed programming language were as follows:
  • The language should be dynamically typed
  • The language should have support for and a culture of unit testing
  • The language should have a large corpus of open source software for studying
  • The language should be well known and considered a good language among dynamic typing proponents
With this criteria in mind I selected Python. The next step is to chose the statically typed programming language. For this selection I used the following criteria:
  • The language should be statically typed
  • The language should execute on the same platform as Python
  • The language should be strongly typed
  • The language should be considered a good language among static typing proponents
I selected Haskell for the statically typed programming language.

The next step was to choose some unit tested programs to translate from Python into Haskell. I randomly picked four projects, The Python NMEA ToolkitMIDIUtilGrapeFruit and PyFontInfo from the https://code.google.com/ and https://bitbucket.org source code hosting sites.

The Python NMEA Toolkit

The translation of the Python NMEA Tookit from Python to Haskell led to the discovery of nine type errors. Three of them could be triggered by malformed input and the other six by an incorrect usage of the API. Only one of the type errors would have been guaranteed to have been discovered had full unit test coverage been employed. Additionally there was one run time error that could be eliminated once static typing was applied. Two unit tests could have been eliminated as their only function was to perform type checking. No dynamic constructs were used that could not be directly translated into Haskell.

MIDIUtil

The translation of MIDIUtil led to the discovery of 2 type errors. Only one of the type errors would have been certainly been caught had full unit test coverage been employed. An additional run time error could also be eliminated by static typing. None of the unit tests only tested for type safety and so none of them could be eliminated. The MIDIUtil code did use struct.pack and struct.unpack which could not be directly translated as they both rely on format strings that determine the type of arguments and return values. However in all cases the format strings were hard-coded, so the Haskell version could instead use hard-coded functions instead of the hard-coded format strings with no loss in expressiveness. Had the MIDIUtil code stored these format strings in external configuration files then the program would likely have required a re-design to express it in a statically typed language.

GrapeFruit

The translation of GrapeFruit to Haskell did not result in the discovery of any type errors. A single run time error could be eliminated by static typing. Additionally a single unit test could have been eliminated that only tested for type safety. No dynamic constructs were used that could not be directly translated into Haskell.

PyFontInfo

The translation of PyFontInfo resulted in the discovery of six type errors. Two run time errors could be eliminated by static typing. A single unit test could have been eliminated. The PyFontInfo code also used struct.pack and struct.unpack which can not be directly translated, but a simple work around exists.

Results

The translation of these projects revealed that all of these projects could have been written in a statically typed programming language with only minor code changes. Furthermore, unit testing did not seem to be an adequate replacement for static type checking. A total of seventeen type errors were discovered. All of the type errors that were discovered were the result of bugs in the original Python code that were not discovered by the unit tests. Many of the bugs existed in code that did have unit test coverage.

Conclusion

The results of this experiment indicate that unit testing is not an adequate replacement for static typing for defect detection. While unit testing does catch many errors it is difficult to construct unit tests that will detect the kinds of defects that would be programatically detected by static typing. The application of static type checking to many programs written in dynamically typed programming languages would catch many defects that were not detected with unit testing, and would not require significant redesign of the programs.

Future Work

The translation of these four projects do provide an interesting data point on the effectiveness of unit testing for defect detection. I hope that others will try to conduct similar experiments on more samples of dynamically typed programs.


The full length paper is located here.
The original Python code and the Haskell translation are here.

Thursday, May 24, 2012

The Go Programming Language Has Exceptions

It seems like every other post I read about Go states that the Go programming language doesn't have exceptions. This is followed by either an excited explanation on why exceptions are bad and why you don't want them anyway, or an explanation on why Go is deficient because it doesn't have exceptions. It's time to set the record straight. Go has exceptions. Now I really want to believe it. So close your eyes and repeat the following ten times "Go has exceptions". It's OK I'll wait for you to finish. Are you done? Do you believe it? OK now that you know that Go has exceptions in your heart of hearts. I should probably point out that Go really doesn't have exceptions. If you look at the language spec you'll see that there is no section on exceptions. There is no "try", "catch" or "throw" keywords, and nothing on "finally". Even though Go doesn't have exceptions it does have constructs which exhibit exception like semantics that can be used when you want to use exceptions for error handling. Their just not called exceptions.

In the Go language spec there is a section on handling panics. If you read it carefully you'll notice that the description of "panic" sounds a lot like the description of "throw". You may also notice that "recover" sounds lot like "catch", and you can use "defer" in place of "finally". There is no replacement for the "try" key word as Go's "panic", "recover" and "defer" work on function boundaries not on "try/catch" scopes. So there you have it. Even though Go doesn't have exceptions it does have constructs that can be used to handle exceptional error conditions and that closely resemble exceptions.

This raises the question. If Go has exception like constructs, why do people frequently claim that it doesn't have exceptions and you only handle errors via returning an "error" value? I think there are two reasons for this. First of all in the early days of Go there was no "recover" keyword. Any call to panic would terminate the program so people got used to the idea that Go didn't have an exception mechanism. Secondly the convention is for packages to handle any uses of "panic" internally and then to return error values to their callers. This convention means that you never have to worry about recovering from someone else's panic when calling into a Go package. You can however use exception handling internal to your package or in your application, but you don't have to. So it's possible to write Go code and never encounter exceptions. Ensuring that a libraries panics won't leak into your code solves many of the problems with exceptions.

So can we please stop saying that Go doesn't have exceptions? While it may be technically accurate it's misleading. Instead why don't we just say that Go has two complementary error handling mechanisms, one is by returning error values, but much nicer than C's, the other is exception like, but it solves many of the issues with exceptions.

Tuesday, May 1, 2012

Making Elastic Applications More Friendly in Go

Many networked applications are elastic. They'll use as much or as little bandwidth as available. For example web browsing, email and ssh sessions will continue to function properly over lower bandwidth connections. However many applications such as audio or video streaming are inelastic and require a minimum bandwidth in order to work properly. If you download email over a dial-up connection it may take a long time but it will still work. If you stream video over a dial-up connection it will likely not play correctly. Unfortunately many elastic applications are written to use as much bandwidth as possible and so  they may interfere with inelastic applications. For example if you run iTunes while streaming video in a browser iTunes will use as much bandwidth as it can, even if ends up interrupting the streaming video. A simple solution to this problem is to add controls to elastic applications to limit how much bandwidth they'll use. Both the curl and wget command line utilities provide such controls, but applications with such controls seem to be the exception rather than the rule.

A few weeks ago I started rewriting an application in Go for managing podcasts. As I frequently get internet connection over a 3G connection I wanted to make sure that this application didn't monopolize my network connection. I needed a way to limit the amount of bandwidth that my podcast application would use. As I started working on a solution I recognized that it may be beneficial to others. A bit of work and a lot of fun later iothrottler was born.

Using iothrottler is quite easy. You create an 'IOThrottlerPool' with the maximum amount of bandwidth that should be used by clients of the pool, and then add clients by calling the 'AddReader', 'AddWriter', 'AddReadWriter', or 'AddConn' methods. These methods return types who's bandwidth are limited by the pool. Of course the pools bandwidth limitation can be dynamically adjusted by calling the 'SetBandwidth' method. More detailed documentation and examples are provided by the package.

Implementing this package in Go was really fun. Go's interfaces make it easy to add network bandwidth control to both new and existing applications. Go's interfaces also mean that you can use iothrottler to limit other types of IO such as file IO.

If you're writing an elastic application in Go please consider bandwidth throttling to your application. Bandwidth throttling makes your user's lives much better.

Bug reports, pull requests, feature requests and questions about iothrottler are always welcome.

Happy Hacking!

Tuesday, April 3, 2012

Object Oriented Go

Because Go doesn't have classes some have concluded that it's not an object oriented language. This is simply not true. I thought I'd share a simple problem that I needed to solve in Go in an object oriented way. Note that this won't demonstrate all of it's object oriented capabilities but it shows how one can create simple objects with methods.

When writing code I've frequently used a technique for poor mans profiling where you start a timer, perform a set of operations and then see how much time has elapsed. This technique is not a substitute for real profiling tools like valgrind, but it sometimes is handy and sufficient. In C++ or Java I'd create a Timer class that will get the current time when it's constructed and then add an elapsed() method which will return how many nano/milli seconds have passed since the object was constructed. I needed this for a Go project I'm working on and this is how I did it:

First of all I define a new type.

This code defines a new type Timer that will have the same representation in memory as the time.Time structure but it's treated as a new type by the type checker. This means that if you try to call a time.Time method on a Timer object you'll get a compiler error. You can however convert a time.Time to a Timer and vice-versa by type casting.

Now that we have a new type lets create a function for creating a new Timer. In Java we'd probably call this method timerFactory, but will just call it StartTimer().

The time.Now() call returns a new time.Time object representing the current date and time, which we then type cast to a Timer and return it.

Now we want to add a method to our Timer object that will return the number of nanoseconds that have elapsed since the Timer was created.

The ElapsedNanoseconds() method gets the new date and time with time.Now() and subtracts the original time. We must cast the Timer to time.Time because it's a different type, and then we return the number of nanoseconds that have elapsed.

We can now use our new Timer type as follows:

That's it! This works great as is but sometimes you don't need nanosecond resolution, millisecond resolution might be just fine. So lets add a new method to our Timer type to get the elapsed time in milliseconds instead.


While this code works perfectly fine, the code will make it easy for us to write a bug. Consider the following:

This code creates two Timer objects and attempts to compare the elapsed time between them. Unfortunately the units on the shortDelay are nanoseconds and the units on the longDelay are milliseconds. Comparing these values this way would make our High School Algebra teachers sad. Luckily we can fix this by defining new types for the nanosecond and millisecond delays.
We defined two new types Nanosecond and Millisecond. Each are based off of int64 so they'll have the same memory layout as an int64, but they're treated as different types by Go's type system. Now if we try and write code to compare these values we get an error message like "invalid operation: shortDelay > longDelay (mismatched types Nanosecond and Millisecond)". We're using the type system to enforce units on time! Now wouldn't it be nice to be able to convert from a Nanosecond to a Millisecond? We can do that by adding conversion methods to the Nanosecond and Millisecond types.

We can now fix our buggy use of Timer like so.



That's it! We created three new types Timer, Millisecond, Nanosecond (they would be classes in C++/Java) and one factory function and three new methods. The full code with the example usage can be downloaded and executed by typing "go run main.go".