Thomas Jung's Blog

Why I Created Daily Feed Recycler

2011-12-13T20:04:00.000+01:00

The motivation behind Daily Feed Recycler is that there is too much content on the Internet: good and bad. Once I found a good source, I do not have enough time to actually read everything. I just can’t read 5k word articles in a row. Even if I had the time to do it, I cannot mentally. It’s not fun.

Feeds are a wonderful tool for authors and readers. They allow to stay informed about the changes on a page. Feed aggregators are part of this reading experience. They let you manage feeds: read articles, mark as read, subscribe and aggregate feeds. Applications creating feeds get this for free and there are a multitude of feed aggregators available.

Feeds help with time problem to some extent, but they - wonderful as they are - have a dark side. Instead of solving the problem of organizing content in a way that you can read really good stuff, they organize content in a way that you can read the latest stuff. Yes, the new content is cool, but the classics are here to stay. You will not get a tweet from Goethe. With Daily Feed Recycler the good stuff is on an equal footing with the latest stuff. The content for every day is presented as new stuff in your feed aggregator.

Content has to be presented in a digestible manner. Deep reading, not just skimming to get an overview. Time and mental energy has to be organized in a way to allow reading. The Daily Feed Recycler is thought of as a way to break down content in smaller parts and add a reminder that there’s still good content to read. Using your feed aggregator you can decide when you read it, if you ignore it or if you read it at all. Feed aggregators are quite good nowadays and their flexibility is useful here.

You can now create your own channel of daily content: the full bash reference, the mayor Linux man pages or the list of all decision biases from Wikipedia. Everything you like. I’m often looking for daily feeds but there are not that many of them out there, because it’s a lot of work to do and depends on a certain level of expertise. Daily Feed Recycler is not a competitor for the existing curated daily feeds. A curated feed can have a much better quality through an expert selection and logical ordering of content.

Daily Feed Recycler follows the “Release early, Release often” philosophy. There are bugs, missing features and rough edges. I hope you find it useful nonetheless.

Find cruft with a new Mercurial extension

2011-07-15T07:10:00.001+02:00

After some fun with the quick and untested shell script that finds the oldest code in a Subversion repository, it is the next step to write a Mercurial extension. The simple Mercurial extension cruft does basically the same job as the shell scripts for Subversion. Being an extension it’s nicely integrated into Mercurial as the other extensions.

Python and Mercurial are relatively easy to get into. Mercurial provides the Developer Info page which is really good. Additionally, there’s a guide how to write a Mercurial extension. The guide is good start for the Mecurial development. The rest can be easily picked up by reading the code of other commands and extensions.
The code is readable and there are no big hurdles.

The only thing I missed while writing the extension is type information in method signatures. As much as I like Python it’s ridiculous to write the type information in the pydoc and let the developer figure out the types. This one of the trade-offs you have to live with.

Testing Mercurial extensions

It suffices to understand the integration tests tool Mercurial uses to test the extension itself. There’s some documentation for this as well. The basic idea behind Cram is to start a process and check against the expected output.

The integration test tool defines a small language. All lines that have no indentation are comments. Indented lines starting with $ are executed and all other lines are the expected output. For example a test looks like this:

init

 $ hg init

 $ cat <<EOF >>a
 > c1
 > c2
 > EOF
 $ hg ci -A -m "commit 0"
 adding a

cruft

 $ hg cruft
 0 a c1
 0 a c2

First a repository is initialized: a file called a with the content (c1,c2) is committed and then the Mercurial is started with the cruft command. Without options the cruft extension prints all lines with newest lines first. The expected output is (0 a c1, 0 a c2) which is means the revision 0 file a and line c1; revision 0 file a and line c2.

It’s fairly easy to get started with this tool. The only downside in my tests is that the they reuse the same test fixture and do not reset the fixture for each test. They are not executed in isolation, which has a whole range of problems - redundancy and readability for example - but I didn’t feel that it was worth the effort to structure the tests otherwise.

Installing the extension

The easiest way to install the extension is to download the cruft.py to a local folder and add a link to the extension file in the .hgrc file.

[extensions]
cruft=~/.hgext/cruft.py

Using the extension

After the installation you can execute pretty much the same commands as with the shell script version.

hg help cruft

hg cruft

(no help text available)

options:

-l --limit VALUE   oldest lines taken into account
-c --changes       biggest change sets
-f --files         biggest changes per file
-X --filter VALUE  filter lines that match the regular expression
    --mq            operate on patch repository

use "hg -v help cruft" to show global options

I use here the quickcheck source code to show some sample output.

hg cruft -l 5 -X "^(\s*}\s*|\s*/.*|\s*[*].*|\s*|\s*@Override\s*|.*class.*|import.*|package.*)$" quickcheck-core/src/main

This finds the oldest 5 lines using the Java source code specific exclusion pattern (parentheses, imports, class definitions etc.) for the quickcheck-core/src/main folder. The output contains the revision number, source file and source code line.

5 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/TupleGenerator.java public Object[] next() {
5 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/TupleGenerator.java ArrayList<Object> next = new ArrayList<Object>(generators.length);
5 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/TupleGenerator.java for (Generator<?> gen : generators) {
5 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/TupleGenerator.java next.add(gen.next());
5 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/TupleGenerator.java return next.toArray();

You can also find the biggest change sets for the last 500 lines.

hg cruft -X "^(\s*}\s*|\s*/.*|\s*[*].*|\s*|\s*@Override\s*|.*class.*|import.*
|package.*)$" -l 500 -c quickcheck-core/src/main

This prints the revisions number, number of changed lines and commit comment of the change set.

49 41 removed getClassification method from Property interface
moved Classification into quickcheck.property package
177 43 MutationGenerator, CloningMutationGenerator and CloningGenerator added
139 50 fixed generic var arg array problems
5 53 initial check in

Finally, you can find the files with the most lines changed by a single change set (again with the filter and for the 500 oldest lines).

hg cruft -X "^(\s*}\s*|\s*/.*|\s*[*].*|\s*|\s*@Override\s*|.*class.*|import.*
|package.*)$" -l 500 -f quickcheck-core/src/main

This prints the revision number, file name, number of changes and change set commit comment.

176 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/AbstractTreeGenerator.java 27 added tree generator
177 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/CloningGenerator.java 28 MutationGenerator, CloningMutationGenerator and CloningGenerator added
139 quickcheck-core/src/main/java/net/java/quickcheck/generator/support/DefaultFrequencyGenerator.java 36 fixed generic var arg array problems
49 quickcheck-core/src/main/java/net/java/quickcheck/characteristic/Classification.java 41 removed getClassification method from Property interface
moved Classification into quickcheck.property package

Conclusion

Developing a Mercurial extension is relatively easy given Python, the good Mercurial documentation, the good readability of the code and integration test tool. If you’re using Mercurial you should give Mercurial extension development a try. I’ve only recently read into Python again so this is the Python beginner’s version of a Mercurial extension. Help to improve the implementation is always appreciated.

Learning Python and seeing how things are implemented there is fun. Looking at the PEPs and the associated process, they feel much more accessible and open than JSRs. The PEPs are also a track record of the advances the language makes and problems it tries to solve one after the other. There’s stuff in Python that you’ll probably never see in Java like the generator expressions. Everyone who had to replace an internal loop with an iterator will understand that this is not a toy. The language features seem to sum up quite nicely and result in a productive environment. As always, some things are unfamiliar or missing but there’s no perfect platform.

Find cruft in your source code repository

2011-05-30T09:35:00.002+02:00

Micheal Feathers wrote in his blog post “The Carrying-Cost of Code: Taking Lean Seriously”
that is necessary to remove old code from your product to be able to add new features. His argument is that you get a better understanding of your production code this way. Rewriting your code constantly leads to more readable and compact code.

"There are many places in the industry where existing mountains of code are a drag on progress.
[..]
Younger organizations without as much software infrastructure often have a competitive advantage provided they can ramp up to a base feature set quickly and provide value that more encumbered software-based companies can't. It's a scenario that plays out over and over again, but people don't really talk about it.
[..]
I'd like to have code base where every line of code written disappears exactly three months after it is written.
[..]
I have the suspicion that a company could actually do better over the long term doing that, and the reason is because the costs of carrying code are real, but no one accounts for them."

His reasoning goes so far as to ask product owners to remove features that are not needed. Software size seems to increase strictly monotonic. This makes maintenance harder and more costly. I’m not sure if you have to follow the advice strictly too improve your situation. Before you start arguing with your boss about removing features, it is a good idea to look for low-hanging fruit first: the oldest lines.

Metric

The heuristic comes from the observation that a) software has bugs and that b) if the software is actually used bugs will be found and fixed. Fixing the bugs leads to new code as does changes in coding style, new APIs etc. Old unchanged code is either bug-free, feature-complete and state-off-the-art or something nobody cares about. I’d say the metric is not too bad to find some victims. (A metric like this one should be a tool to find problems not an absolute measurement. Metrics should not be taken too seriously and nobody should be tempted to cheat.)

To put the idea into practice I’ve hacked some scripts to find suspects in a subversion repository. The scripts are:

find the oldest lines in your repository
find biggest change sets in your repository considering the oldest lines
find files that are changed the most by a change set considering the n oldest lines

Too get some data I’ll use the legacy subversion repository of the Quickcheck project. Quickcheck moved to Mercurial some time ago. It’s a test to see if something significant can be found with this metric.

The readme contains instructions how you can run the scripts with your subversion repository. The script are based on a local repository mirror to speed up analysis. The analysis can be execute on any subtree of the repository.

Oldest lines

Finding the oldest lines is quite simple first get all file names with svn list and then use svn blame to get the date for every line. These output is sorted by the revision (descending) of each line.

The output of the oldest_lines.sh is unfiltered. To extract useful information it has to be filtered. The filter.sh does this for Java source code: removing empty lines, single closing braces, package declaration, imports and comments.

These are the last lines of the filtered output for Quickcheck:

$ ./filter.sh | tail -5

6     blob79    public int compare(Pair<Object, Double> o1, Pair<Object, Double> o2) { File: characteristic/Classification.java Line: 162
6     blob79    next.add(gen.next()); File: generator/support/TupleGenerator.java Line: 34
6     blob79    ArrayList<Pair<Object, Double>> toSort) { File: characteristic/Classification.java Line: 150
6     blob79    @SuppressWarnings("unchecked") File: generator/CombinedGenerators.java Line: 126
6     blob79     Object[] next = generator.next(); File: generator/CombinedGenerators.java Line: 128

A potential victim here is the Classification class. It’s rudiment from the original Quickcheck implementation but never was used heavily. It’s a nice idea to do statistical testing but Classification could be removed from Quickcheck without loosing a significant feature.

Biggest change sets

The second script top_change_sets.sh finds the biggest change sets considering only the n oldest lines. This results in an interesting output for the code base (oldest 1500 lines, top 5 change sets):

$ ./top_change_sets.sh 1500 5

r182 | blob79 | 20071219 19:15:24 +0100 (Wed, 19 Dec 2007) | 1 line
basic failed test instances serialization feature implementation
136 changes

r270 | blob79 | 20090603 18:52:52 +0200 (Wed, 03 Jun 2009) | 1 line
added pojo (a.k.a object) generator for interfaces
104 changes

r6 | blob79 | 20070707 07:29:14 +0200 (Sat, 07 Jul 2007) | 1 line
initial check in
68 changes

r204 | blob79 | 20080323 19:29:28 +0100 (Sun, 23 Mar 2008) | 1 line
added svn keyword id
52 changes

r198 | blob79 | 20080323 18:29:26 +0100 (Sun, 23 Mar 2008) | 3 lines
fixed logging for serializing and deserializing runner
mandate a user set characteristic name (for serialization of test values)
added system property for number of runs
48 changes

Revision 182,198 were commits related to the obscure test data serialization and deserialization scheme. Something I’ve already removed in the latest release. The two changes resulted in 184 lines still present in the current source.

The revision 270 is not less obscure. It’s a declarative POJO object generator. The revision is so high in the list because it forced a lot of changes. This is not a good sign: obscure feature and lots of changes. That’s something worth to investigate.

Revision 6 is the initial check in. So this should be okay.

The last open issue revision 204 is the attack of the code formatters. They should be used with prudence as long as the down-stream tools can’t handle the changes properly. (Source control system should understand the AST of the source language.)

File changes

Now we can take a look at the files with most changes from a single revision. If you execute the query top_changes_in_file.sh (500 oldest lines, top 5) for the Quickcheck source code you’ll see:

$ ./top_changes_in_file.sh 500 5
r182 | blob79 | 2007-12-19 19:15:24 +0100 (Wed, 19 Dec 2007) | 1 line
basic failed test instances serialization feature implementation
34 changes | file: RunnerImpl.java

r180 | blob79 | 2007-12-07 18:59:59 +0100 (Fri, 07 Dec 2007) | 3 lines
MutationGenerator, CloningMutationGenerator and CloningGenerator added
26 changes | file: generator/support/CloningGenerator.java

r182 | blob79 | 2007-12-19 19:15:24 +0100 (Wed, 19 Dec 2007) | 1 line
basic failed test instances serialization feature implementation
24 changes | file: SerializingRunnerDecorator.java

r6 | blob79 | 2007-07-07 07:29:14 +0200 (Sat, 07 Jul 2007) | 1 line
initial check in
22 changes | file: characteristic/Classification.java

r179 | blob79 | 2007-10-13 09:14:30 +0200 (Sat, 13 Oct 2007) | 1 line
added tree generator
22 changes | file: generator/support/AbstractTreeGenerator.java

Besides the usual suspects serialization support and the Classification class two new suspects emerge: mutation generator and a tree generator. In favor of the tree generator and mutation generator implementation, they might be useful but aren’t widely used so this something worth to look at.

Conclusion

The metrics found multiple source files that are worth investigating. One feature that is already removed (serialization support), one likely victim (classification) and multiple places that are worth checking (mutation generator, tree generator, declarative POJO generator). The metrics seems to find unloved children in the code that are good candidates for removal or implementation improvements.

I always like to remove code. Fewer lines of code means fewer spots where problems may emerge. Nobody can argue that if you can remove unused code that it’s better to keep the useless code - even if it’s tested and production-quality. That’s something like a reverse YAGNI. If you really care the code will never disappear. You can find it in your source code management system. You should be okay with that fact that the old code will lose it’s relevance due to changes to the production system implementation. It can be a inspiration how it could be done if the world hadn’t changed. The burden of these changes are also the reason why it’s better to remove the code in the first place. Dragging it with you without any gain is plain waste.

Quickcheck 0.6 Release

2011-05-09T18:55:00.001+02:00

The version 0.6 of Quickcheck is ready to use. The main features are support for deterministic execution of generators and improvements on generators. The JUnit runner support was removed in this release.

You can read an in detail description of deterministic execution in this blog post.

The 0.6 release adds the following generators:
- map generator maps(Generator<K> keys, Generator<V> values)
- subset generator sets(Set<T>)
- submap generator maps(Map<K, V>)
- unique generator using a Comparator<T> to decide if two values are considered equivalent: uniqueValues(Generator<T>, Comparator<? super T>)
- excluding generator based on a collection of input and a collection of excluded values: excludeValues(Collection<T> values, Collection<T> excluded
- content generator type parameter are now co-variant for lists, iterators, sets and object arrays to allow creation of super type container generators (like Generator<List<Object>> = lists(integers()))
- PrimitiveGenerator added generators:
- generator for java.lang.Object instances

The dropped Junit Runner support means that the @ForAll annotation is no longer supported. Until lambda expression are supported in Java (hopefully) the Iterable adapter is a good workaround that allows to execute tests without too much boiler-plate. If you need all features the inner class will work just fine. Inner classes will become much better with the SAM-type conversion in Java 8 which is part of the language changes in Project Lambda.

The general development direction and the main theme I’ve been working on besides the release was the support for generator expressions. This is a good way to implement tests for equals methods where a equals method should return false when one of the significant attributes of an object is not equal. You have to write a lot of boiler-plate to test a simple statement like: “This is not equal if one of the attributes is not equal” now. With generator expression this should become much easier.

It’s quite tricky to create a nice API for expressions. One cul-de-sac was to implement it as a builder with a fluent interface. The method chaining is not an adequate. The chaining forces you to linerialize the definition of the expression. This does not fit well into the world of generators where delegation and nesting are natural concepts. I burned some time before I got that the underlying problem cannot be fixed with a clever API. I hope the current approach terminates and the expression support is something you can work with in the 0.7 release.

Using deterministic generators with Quickcheck

2011-03-22T20:48:00.001+01:00

The 0.6 release of Quickcheck supports deterministic generators. The goal is to be able to make the generation of values reproducible. This is useful when you are working with a bug from your favourite continuous integration server or when you would like to run a piece of code in the debugger repeatedly with the same results.

A non-goal of the support is to remove the random nature Quickcheck. Values are still random to allow a good coverage but reproducibility is supported when needed. This way you have the best of both worlds.

Quickcheck uses internally the linear congruential random number generator (RNG) implemented in the Java’s Random class. The interesting property of the RNG in the context of reproducible values is stated in the javadoc.

If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers.

You can configure the seed used by Quickcheck with the RandomConfiguration class. It’s important to set the seed for every individual test method otherwise a RNG’s return values are dependent on execution order of the test methods. If you run different tests, add a new tests or execute the tests in a different order other values will be generated.

The seed is generated randomly for the normal execution. This is the result of the RandomConfiguration.initSeed method call. This way Quickcheck still produces random values. Use the setSeed method to set the seed for a test method.

Instead of using the RandomConfiguration directly you should use the SeedInfo JUnit method rule that will run with every test method. Additionally, it adds the seed information, that is needed to reproduce the problem, into the AssertionError thrown.

The SeedInfo can be used like every other JUnit method rule. It’s added as an member of the test class. The example generates values in a way that the assertion always fails.

@Rule public SeedInfo seed = new SeedInfo();

@Test public void run(){
  Generator<Integer> unique = uniqueValues(integers());
  assertEquals(unique.next(), unique.next());
}

An example error message is:

java.lang.AssertionError: expected:<243172514> but was:<-917691317> (Seed was 3084746326687106280L.)

You can also use the SeedInfo instance to set the seed for a test method to reproduce the problem from the AssertError.

Rule public SeedInfo seed = new SeedInfo();

@Test public void restore(){
  seed.restore(3084746326687106280L);
  Generator<Integer> unique = uniqueValues(integers());
  assertEquals(unique.next(), unique.next());
}

Instead of setting the seed for individual tests you can also set the initial seed once for the random generator used by the JVM. If you run the test example from above (without the SeedInfo method rule member) and the configuration -Dnet.java.quickcheck.seed=42:

@Test public void run(){
   Generator<Integer> unique = uniqueValues(integers());
   assertEquals(unique.next(), unique.next());
}

You should get the result:

java.lang.AssertionError: expected:<977378563> but was:<786938819>

The configuration of seed values replaces the serialization and deserialization support of earlier Quickcheck versions. Setting the seed is a much simpler way to reproduce values over multiple JVM executions.

Revert - Sometimes going back is the way forward

2011-03-21T18:38:00.000+01:00

Revert is the reverse gear of your version control software. It removes all local changes and brings the local workspace back to clean state of a committed revision. It is an important tool in the revision control software tool box. Once in a while there is no way forward so you have to go backward to make progress.

This may sound unintuitive. We are trying to make a change not reverse it. Why should the tool that destroys all this hard work be the best option in some circumstances? Firstly, you do not lose everything. Even if you revert everything you gain some knowledge. At least that this exact way does not work. This is a good data point. Secondly and more obviously, revert let’s you start with a fresh state. More often than not we are able to reach a working state again. Removing everything is the fastest way to get to there.

I see mainly two scenarios for the revert command: planned mode and the accidental mode.

Planned mode revert

Starting with a working state of your committed source code you can do some exploratory work. Find out what you where looking for and revert.

Now you can start the work in a informed way from a working state. The artifacts of the exploration are removed. After reverting you do know that the state you are starting from works. To verify that an workspace state works you do need tools to catch the problems: a decent test coverage and other quality assurance measures.

A corollary is that because you are planning to revert anyway you can change your workspace in every way you need for the exploration.

Accidental mode revert

The first scenario was a bit too idyllic: you started your work with an exploratory mind set, found the precious information and clean up after yourself. Everything is planned, clean and controlled. This scenario is valid. You can do the exploratory work voluntarily. More often it is the case that you have dug yourself in. You need to find a way out.

Is this a hole or the basement?

The first issue is to know when your in a hole and there is little chance to get out.

Say you commit roughly every hour. Now you did not commit for four hours. Your change set becomes bigger and bigger. You see no way to get your tests running again. Different tests are broken after multiple trials to fix everything. Your in a hole.

You made a change and it resulted in absolutely unexpected problems. Your tests are broken. You do not know why. There are red lights all over the place. Your in a hole.

You made small, controlled, incremental changes for some time without committing. You did not bother to commit because everything was so simple. Now the changes become bigger you would like to commit but you can’t because you can’t bring the whole system to run again. You are in a hole.

The commonality of the three examples is that your not in control of the process. The world you created determines your next steps. This happens to everyone. It’s normal. It happens all the time. Otherwise our work would be predictable day in and out - how boring. (I would go so fare as to say that in other circumstances it’s a good sign that you can follow the inherent conclusions of your system. This way it’s productive that you are determined by the conclusions of your system because it is consistent.)

If there is such a thing as experience in hole digging it’s to see the problem coming and to stop early. If it happened often enough to you, you should know the signs. You’ll know that knee deep holes are deep enough to stop and that it’s not necessary to disappear completely.

Ways out

Now after you found out that have a problem all energy should be put in it. Don’t try to be too smart. Solve this one problem. You have two options to get out of the hole: fixing the current state or revert.

Fixing the current state can work. You find enough information to fix the problem. You’ll lose some time but nothing of your work. Once the current state works it’s good a idea to commit now. This creates a save point. If there are more problems lurking down the road you can always come back to this state. The problem is that you might not find the problem. Finding a way out now is hard. Your change set adds to the complexity of the underlying problem. Your changes obfuscate the problem and make it harder to analyze. Everything you do will increase the change set complexity further.

When fixing the current state is too hard, you have to revert your work to keep up the pace. Now you have the problem that you have already sunk so much time and the next step is to roll everything back to the state you started from. This does not feel pleasant. The upside is that even though you reverted the code not everything is lost. You still have more knowledge about the problem. This knowledge can be used on the second and hopefully last attack. Make notes if you need them to remember the information you gathered.

The first attempt was in the wrong direction and/or too big. It is a good idea to make smaller steps with interim commits to create save points you can revert to. This creates a safety net if you bump into the problems again. You can revert repeatedly to chop smaller portions of the problem until it is solved. You decrease the size of the changes until you can understand a problem. Once in a while strange things happen and a single line change has crazy effects. After removing such road blocks you can make bigger steps again.

There is of course a middle way: trying to revert only partially. Without creating and applying patches you have only one direction to go (revert) and you'll swiftly have to revert everything (because your change history is lost). I’ll come back to an approach to use diff and patch to do partial reverts in a controlled way later.

Bringing the costs of reverts down

The problem with reverts is that they are expensive. Work you've already done is removed from the source tree. Not something we are especially proud of.

The problem is only as big as the change set that is flushed down the toilet. You should commit as often as your infrastructure allows: the execution time of tests and the integration costs are the main factor here. (You can move some of the cost into the continuous integration environment you're using.) As always this is a trade-off between the work lost and the overhead created by frequent commits. Committing every hour is probably a good idea. Just do whatever fit’s your needs best.

The other factor is the right attitude to the revert operation. If you have already spent a lot of time on a problem and could not find a fix, it’s likely you won’t find it in this direction and a fresh approach is needed. You can actually save a lot of effort by aborting this failed attempt. This will also bring the total costs of a inevitable later revert down.

Conclusion

Failed attempts are not the problem. We have to learn from our failures. They are just too often and valuable to loose. Making failures is okay. Samuel Beckett put it nicely:

Ever tried. Ever failed. No matter. Try again. Fail again. Fail better.

Members in unit tests considered harmful

2011-02-07T21:41:00.001+01:00

I’ve been reading Domain Specific Languages by Martin Fowler. It is a good book to formalize API design and gives you a new perspective to think about your software. You can buy this book even if you’re not planning to implements DSLs in the future. A DSL is a differently marketed API anyway - but that’s another blog.

I don’t like the style of the tests presented in the book. Martin captures testing of DSLs at the beginning of the book (3.6. Testing DSLs page 53). The tests use members heavily. I’ve seen this style already in Robert C. Martin’s Clean Code. Both are TDD pundits so I thought it’s not too widely known that you can write tests with better readability.

The code that is tested is a controller that uses a state machine to react on events with transitions to the next state.

Use of members in unit tests

The testing style I object to looks like this:

@Test public void event_causes_transition(){
    fire(trigger_a);
    assertCurrentState(a);
}

Sorry, this looks nice but it’s not readable. What is the fixture? What is the class tested and the methods called? What are the parameters of the call and the result? What does the assertion check? You can figure it out, but it’s not easy and you have to navigate a lot in the source file.

No members in unit tests

Now contrast that with this member-less style:

@Test public void event_causes_transition(){
    Event trigger_a = anyEvent();
    State a = anyState();
    Controller controller = controller(stateMachine(transition(trigger_a, a)));

    controller.handle(trigger_a.getId());

    assertEquals(a, controller.getCurrentState());
}

It’s longer than the original version, but everything is in one place. You still setup an initial state but it is completely local. The naming is kept in synch with the original version so you can correlate implementations. The naming is local to the test. It can be specific in member-less style: "a" should be a "state" and "trigger_a" a "trigger".

As you can see in the test, it creates an event and a state. The details of both seem not to be significant for the test. This insignificance is stated in the test explicitly. Then a controller is setup up with a state machine that has one transition. After you have done the setup, you can actually call the method you want to test and check the result.

Every test method following this style has the sequence: setup, execute, assert while keeping everything in the scope of the test: no members!

Code organization and readability

After contrasting the two implementation styles let’s try to explain why the member-less style is more readable.

If tests make heavy use of members, they look nice at the surface: no redundancy, nice method names and helper methods to keep the intend clear. Why is this less readable that the member-less style? The problem is the missing context and necessary navigation in the test code to get the context before you can understand what is actually tested.

If you recorded the navigation of a reader you would see something similar to the following:

the setup methods

memorize setup members

test method: execute statement (fire)
execute helper implementation

recall setup members
memorize result members

test method: assert statement (assertCurrentState)
assert statement implementation

recall result members

As you can see, the reader has to navigate and remember a lot to get the initial setup of the test and keep track of the transition triggered by the execution.

In every place were the reader has to remember some information there’s the potential that an additional navigation is necessary, because he could simply not remember enough context. This becomes even harder when you start to organize the tests into test class hierarchies. The context to remember is the context of all super classes members, execution method implementations and assertion method implementations. Naturally, our ability to store information is limited. Less context information to remember is better for the readability of a test.

So the nice test from above actually looks like this in reality:

@Test a(){
    //a lot of navigation and to remember
    a();
    //dito
    b();
    //dito
}

Ideal organization of code

This is not readable. Ideally, something readable is a linear text laid out exactly in the way you need it to work on your current problem. You build up the context as you go without loosing time navigating. A second ideal of readability is that every information necessary is in one spot. All your context is visible to you at the same time.

The two ideals effect each other. Given a problem complex enough, you cannot have a compact linear representation. Either it’s linear or compact.

Additionally, you make trade-offs to remove redundancy from code. If you are asking yourself whether you reorganize to remove redundancy don’t forget that the most important feature of a test is readability. Introduce some redundancy as long as it helps to understand your test.

Organize to allow effective navigation

You cannot organize code in a way it can be read linearly for all purposes, but you can organize it in a way that the navigation capabilities of IDEs allow effective navigation. Every navigation starts in the test method and is done by looking up the definition of a helper method. The full context is kept in local variables, parameters and return values.

You can start to read a test class from every test method without losing vital information. No navigation to members is necessary:

Event trigger = anyEvent();
State state = anyState();
Controller controller = controller(stateMachine(transition(trigger, state)));

The member-less style makes the setup explicit. Try to name all setup helper methods following the Principle of Least Astonishment. They are nicely named and should state what their individual guarantee is. Accordingly, a method that creates an valid event without further guarantees is named anyEvent().

controller.handle(trigger.getId());

Now the actual method to test can be executed. The member-less style shows exactly what is going on. It presents crystal clear the parameters used and the result value received. There is no navigation overhead. The instances from the setup are used to run the actual test. If there is an execution result it is stored in the local context of the test method.

assertEquals(state, controller.getCurrentState());

After the execution you can do the assertion on the resulting state or result. This again uses only instances from the method scope. Sometimes it is useful to introduce custom assertions to remove redundancy. In this style the assertion method works only on the parameters given, e.g. assertState(state, controller).

If you tracked the navigation for the member-less test style you would get something like this:

test
setup methods

memorize state

test

recall setup state
execute method
assert method

The result is not the ideal of a linearly readable test, but the navigation to the definition and back to the test is relatively swift. You can be sure that you did not miss vital information as everything is in one place. Removing uncertainty is the key to a simpler reasoning about the test at hand.

Avoid test class hierarchies

The member-less test setup also helps to avoid test class hierarchies that are are only introduced to allow different fixtures for a sets of tests. Sometimes this is avoided in member style test by doing some setup globally in members and in the test method, but this complicates the reasoning even more. With a member-less test you can have a different setup for every test method. Normally, you organize the setup methods in a way that they build on each other to avoid redundancy.

Avoid isolation from the API

If you put the method execution and assertion into separate methods - like the member heavy style does - you introduce the danger of hiding API problems. One argument for TDD is to experience your API from the point of view of a user. When the actual method calls are in helper methods you do isolate yourself from the API reality your users are facing. It should be nice enough to do the setup, execution and assertion directly with it. Otherwise you have a design problem. The test code should be as much as possible analogous to the code users of an API have to write.

Conclusion

I hope I provided a new perspective to look at the organization of unit tests. If you have objections with this approach feel free to add a comment. If you are interested in this and other aspects of testing software, you can have a look at Test Principles from my co-worker Gaetano Gallo. He covered this idea under "Self containment" in his blog.

Inverse Function Test Pattern in Quickcheck

2010-12-07T20:32:00.000+01:00

I already mentioned the inverse function test pattern in the introduction to specification-based testing using Quickcheck. Now I would like to present the pattern in more detail with an example.

The basic idea of testing with inverse functions is simple. We have two functions f and its inverse function f-1. If we apply f to an input value and then take the result and apply it to f-1 this should result in the input value again: f-1(f(x)) = x.

This test pattern is applicable for all kinds of functions for example compression and encryption. In the business application domain create and delete are examples of operations that can be tested this way. Another example are do and undo operations of command objects. In both examples, doing and undoing an action leaves the state of the world unchanged.

There are some constraints on the applicability of the test pattern. The function f has to have a inversion function so it is a bijective function and one of the functions f or f-1 have to be tested. Otherwise the intermediary result could be invalid. For example, if you test a create and a delete operation together, the inverse function test passes if both operations do nothing.

The example used to illustrate the inverse function testing is a simple square function.

public double square(double a) {
 double square = a * a; 
 return square;
}

The inverse function test can be implemented with concrete values. We use the Math.sqrt() implementation as the inverse function.

@Test public void squareConcreteValues() {
  double a = 2;
  assertEquals(square(Math.sqrt(a)), a, precission);
}

This is okay but defining input values manually is not very productive, not readable and has not sufficient test coverage. You can instead employ some computing power to generate the values using Quickcheck.

Firstly, the square function is not bijective as square(-x) = square(x). This is a fact we did not express in the example with the concrete values. It simply omitted this fact. To fix this the result is compared to the absolute value of x. Secondly, the function will overflow and test output like this:
java.lang.AssertionError: expected:<1.6482368012418589E307> but was:<Infinity>
is typical.

@Test public void squareWithOverflows() {
  for(double a : someDoubles()) {
    assertEquals(abs(a), Math.sqrt(square(a)), a * precission);
  }
}

Again, this aspect was not expressed in the concrete test. Even if you were not aware of the problem the failing test points to the overflow problem. This is a nice example how Quickcheck can help you to find bugs you did not anticipate. I admit that this is a simple example but give it a try. You'll see that you run into all kinds of problems you did not think of. You have to break your software to know it.

Now we have to fix the overflow problem. Depending on the situation it can be easier to find and test a valid implementation that is more restrictive than theoretically possible but suffices your requirements. This is the trade-off between effort now and potential applicability later.

For this example it is easy to find all legal input arguments. It is the largest double value that can be squared.

@Test public void squareWithBounds() {
  double max = Math.nextAfter(Math.sqrt(Double.MAX_VALUE), 0.0);
  for (double a : someDoubles(-max, max)) {
    assertEquals(abs(a), Math.sqrt(square(a)), a * precission);
  }
}

To finish this example let’s write the test for the illegal input arguments as well. All square arguments that cause an overflow are invalid and should cause an IllegalArgumentException. The invalidArguments double generator defines all invalid values. These are the values greater than the largest valid value max and smaller than the smallest allowed value -max.

@Test public void squareInvalidArguments() {
  double max = Math.sqrt(Double.MAX_VALUE);
  double firstInvalid = Math.nextUp(max);
  Generator<Double> invalidArguments =
    oneOf(doubles(-Double.MAX_VALUE, -firstInvalid))
    .add(doubles(firstInvalid, Double.MAX_VALUE));
    
  for (double a : someEnsureValues(asList(firstInvalid, -firstInvalid), invalidArguments)) {
    try{
      square(a);
      fail();
    }catch(IllegalArgumentException e){ }
  }
}

The implemenation passing the tests is:

public double square(double a) {
  double square = a * a;
  if (Double.isInfinite(square)) { throw new IllegalArgumentException() };
  return square;
}

Testing with inversion functions can solve the dilemma of writing tests without repeating the production code. If you repeat the code in the test you have an additional check that you wrote the code down correctly. You have to repeat an error in both places to introduce a bug. This is all you can get out of such tests. If you test with an inverse function the test and implementation do not share code. This kind of test has the potential to find conceptual problems in your code. (Actually, the reality is not black and white. You can have a test that implements the same operation with a simpler test implementation. This implementation verifies that the more complex production version works. This is the idea of the analogous function test pattern. I will come to later.)

If the inverse function pattern is applicable it can save you a lot of effort. For example the result of an operation can be very costly to verify like encryption functions. The exact representation may not be of interest for the given domain or change frequently leading to high maintenance costs with concrete test values. If you can define valid input values and have an tested inverse function the test effort is to setup the input value generator. The nice side-effect is that you test that the functions you think are inverse functions really are inverse.

The easiest way to get started with Quickcheck

2010-11-10T19:04:00.005+01:00

You may download the Quickcheck zip file from java.net. This zip contains the full Quickcheck distribution. Alternatively, the easiest way to get started is to use the Java.net maven repository.

Add the following definition to your pom.xml file:

<project>
  <repositories>
    <repository>
      <id>maven2-repository.dev.java.net</id>
      <name>Java.net Repository for Maven</name>
      <url>http://download.java.net/maven/2/</url>
      <layout>default</layout>
    </repository>
  </repositories>
  <dependencies>
    <dependency>
      <groupId>net.java</groupId>
      <artifactId>quickcheck</artifactId>
      <version>0.5.1</version>
      <scope>test</scope>
    </dependency>
  </dependencies>
</project>

Have fun.

Alternative test approach: Quickcheck

2010-11-08T18:32:00.002+01:00

With this article I would like to shed some light on the question: Why should I implement tests with the specification-based testing approach proposed by Quickcheck? I will show that the approach yield tests with better readability, more test coverage, helps to omit mock tests and manually maintained test fixtures.

I'll illustrate the approach with an simple example taken from the Guava library to be able to discuss the pros and cons. The example I picked is the test of the com.google.common.base.Splitter class. I present three implementations of the Splitter tests. The test implementation as it can be found in Guava today (translated to TestNG), a test implementation with TestNG @DataProvider and an implementation with Quickcheck for Java.

The following code are tests as they are today. The tests check the behavior of simple split operations for different input values. These tests have a lot of code but are structurally very similar.

@Test public void testCharacterSimpleSplit() {
  String simple = "a,b,c";
  Iterable<String> letters = Splitter.on(',').split(simple);
  assertContentsInOrder(letters, "a", "b", "c");
}

@Test public void testCharacterSplitWithDoubleDelimiter() {
  String doubled = "a,,b,c";
  Iterable<String> letters = Splitter.on(',').split(doubled);
  assertContentsInOrder(letters, "a", "", "b", "c");
}

@Test public void testCharacterSplitWithDoubleDelimiterAndSpace() {
  String doubled = "a,, b,c";
  Iterable<String> letters = Splitter.on(',').split(doubled);
  assertContentsInOrder(letters, "a", "", " b", "c");
}

@Test public void testCharacterSplitWithTrailingDelimiter() {
  String trailing = "a,b,c,";
  Iterable<String> letters = Splitter.on(',').split(trailing);
  assertContentsInOrder(letters, "a", "b", "c", "");
}

@Test public void testCharacterSplitWithLeadingDelimiter() {
  String leading = ",a,b,c";
  Iterable<String> letters = Splitter.on(',').split(leading);
  assertContentsInOrder(letters, "", "a", "b", "c");
}

@Test public void testCharacterSplitWithMulitpleLetters() {
  Iterable<String> testCharacteringMotto =
     Splitter.on('-').split("Testing-rocks-Debugging-sucks");
     assertContentsInOrder(
      testCharacteringMotto, "Testing", "rocks", "Debugging", "sucks");
}
 
private void assertContentsInOrder(Iterable<String> actual,
     String... expected) {
  assertEquals(Arrays.asList(expected), Lists.newArrayList(actual));
}

From the readability perspective the problem with tests specifying concrete values is that the reader has to infer which part of the information is significant and which part is not. For example taking this test in isolation:

@Test public void testCharacterSimpleSplit() {
  String simple = "a,b,c";
  Iterable<String> letters = Splitter.on(',').split(simple);
  assertContentsInOrder(letters, "a", "b", "c");
}

One could come to the result that:
- split works only with one, alphanumeric character (“aa,bb” would not be a legal input string)
- the separator may not be an alphanumeric character
- splits works only for successive char values as the input is a - b - c
- all other characters are undefined

The reader of the tests has to digest all tests to be able to infer the actual properties of the Splitter. While reading he has also to remove the insignificant information and has to eliminate the invalid assumptions. (Actually, the tests say nothing about alphanumeric separators. So this assumption is still open.) As we know what split does this is trivial but for unknown functionality this is much harder.

The test can be implemented with the TestNG DataProviders in a more concise way:

static final String SPLIT = "split";

@DataProvider(name = SPLIT)
public Object[][] split() {
  Object[] simpleSplit = {"a,b,c", ",", new String[] { "a", "b", "c" } };
  Object[] splitWithDoubleDelimiter = {
    "a,,b,c", ",", new String[] { "a", "", "b", "c" } };
  Object[] splitWithDoubleDelimiterAndSpace = {
    "a,, b,c", ",", new String[] { "a", "", " b", "c" } };
  Object[] splitWithTrailingDelimiter = {
    "a,b,c,", ",", new String[] { "a", "b", "c", "" } };
  Object[] splitWithLeadingDelimiter = {
    ",a,b,c", ",", new String[] { "", "a", "b", "c" } };
  Object[] splitWithMulitpleLetters = {
    "Testing-rocks-Debugging-sucks", "-", new String[] { "Testing", "rocks", "Debugging", "sucks" } };
  return new Object[][] {
    simpleSplit, splitWithDoubleDelimiter, splitWithDoubleDelimiterAndSpace,
    splitWithTrailingDelimiter, splitWithLeadingDelimiter, splitWithMulitpleLetters };
}

@Test(dataProvider = SPLIT)
public void simpleSplit(String simple, String separator, String[] expected) {
  Iterable<String> letters = Splitter.on(separator).split(simple);
  assertEquals(Arrays.asList(expected), Lists.newArrayList(letters));
}

This test removes a lot of the boiler-plate in the original version. It tests the split method repeatedly with a set of input values. The more compact representation of the test helps as long as we are keeping test input data and the test in one place. (If you organize your source file in a way that the test data and test is separated the readability decreases significantly.) This test approach still suffers from the readability problems the initial test has: the reader has to derive the property of the Splitter implementation from the input and expected return values. This is like inferring the properties of multiplication from a set of input and return values.

An completely different approach can be implemented using Quickcheck for Java for API. Quickcheck is build on the basic abstraction of the Generator<T>. The only method of the Generator<T> interface is next(). It returns a new value of type T.

The Splitter test uses Quickcheck functionality to create values:
- PrimitiveGenerators.strings() is a Generator<String> for undefined string values
- CombinedGeneratorIterators.someNonEmptyLists() is similar to a Generator<List<T>> but it is adapted to Iterable<List<T>> to be able to use it in a for-each loop. The lists returned have at least one element.

Basic idea is to specify a test as follows: If you take any non empty list of words, join them with a distinct separator and then split the joined string the result will be the input list of words again.

@Test public void simpleSplit() {
  for (List<String> words : someNonEmptyLists(strings())) {
    char separator = anyDistinctCharacter(words);
    String input = Joiner.on(separator).join(words);
    Iterable<String> letters = Splitter.on(separator).split(input);
    assertEquals(words, Lists.newArrayList(letters));
  }
}

The test uses the anyDistinctCharacter helper method to create separators. Separators have to be distinct from the characters used in words otherwise the splitter splits words. The helper uses the PrimitiveGenerators.characters() factory method to create a Generator<Character> for arbitrary characters. To create the separator values CombinedGenerator.excludeValues generator is used. It is build on a input generator but skips all generated values that are equal to the excluded values. (It skips all characters that are in words.)

private char anyDistinctCharacter(List<String> words) {
    char[] notAllowedAsSeperator = Joiner.on("").join(words).toCharArray();
    return excludeValues(characters(), asList(notAllowedAsSeperator)).next();
}

This specification-based test describes the contract and does not enumerate the specific test values. Compared to the two other implementations the way the test is written is more rigid. This is a positive thing, as I already tried to explain that when composing a test of concrete values there is place for misinterpretations. The other effect is that six tests boil down to one test.

This test approach has of course it's trade-offs: it depends on join and is not deterministic.
- Join has to be tested so that this test is working. I think the join test is much easier than the split test. Once join is tested we can depend on it. By testing join/split together we can check that these two are symmetric (f(f-1(x)) = x). Testing symmetry comes for free with this implementation approach.
- The real concern is that we will run the test with randomly generated test data and it is not guaranteed to contain all of the enumerated test cases in every test run.

If non-determinism is your concern there are some ways to address this.
- You can use a different distributions function in your generators. Using different distributions will make certain values more or less likely to occur.
- You can make the values used deterministic by using the CombinedGenerators.ensureValues(ensuredValues). This is still better than the tests with concrete values as you only have to specify the input values and not the expected result values.
- You can combine deterministic and random values. The generator created with CombinedGenerators.ensureValues(ensuredValues, otherValues) uses the enumerated values first and then the otherValues generator after the explicit values are exhausted.
The random nature of the generated values has of course an advantage: you may find bugs that you did not anticipate while writing the test.

Primitive type, enumerations and collection generators alone are not very useful. To test a real world application you have to be able to create values of your custom types. In the Splitter example we already used generators provided by the Quickcheck implementation.

Here is a simple example to get you started.

class Name {
  private final String first;
  private final String last;

  public Name(String first, String last) {
    super();
    this.first = first;
    this.last = last;
  }
  public String getLast() { return last; }
  public String getFirst() { return first; }
}

class NameGenerator implements net.java.quickcheck.Generator<Name>{
  Generator<String> first = PrimitiveGenerators.strings();
  Generator<String> last = PrimitiveGenerators.strings();

  @Override public Name next() {
    return new Name(first.next(), last.next());
  }
}

The code defines the custom type Name and a Generator<Name> using generator implementations provided by the Quickcheck framework. This is analogous to the definition of types in Java you define your own types based on the primitive and other types provided by the JDK.

The test then checks one property of the Name type. This test fails with the current implementation of the Name but this is easily fixed.

public class NameTest {
  @Test public void equals(){
    for(Name name : Iterables.toIterable(new NameGenerator())){
      assertEquals(name, new Name(name.getFirst(), name.getLast()));
    }
  }
}

The test uses an adapter to the Iterable interface to be able to use the generator in a for expression. This is one way to run the test. You can also use an inner class with a more capable runner (QuickCheck.forAll(generator, characteristic)). Using the for expression is the trade-off given that the Java language has no closures yet.

Analogous to your domain object hierarchy you can now build a generator hierarchy that is used to create the domain objects. This clearly adds some overhead as you now have an additional generator for every domain object. But this pays off as you can:
- use generators in unit tests.
- use generated values to replace hard coded fixtures in integration tests (for example tests that you dbunit).
- omit mock tests that are only in place because the object graph to start a test is to hard to setup manually
- use generated values to write inverse functions (f-1(f(x)) = x) and analogous functions (f(x) = g(x) where f or g is simpler) tests (for example zip, encryption, read/write, sorting, searching, etc.).

I hope I could convince you that the approach helps you with writing more expressive tests by leveraging some computing power. You can use specification-based testing approach to test a range of software from the boring business software to more interesting areas like data-structures and algorithms. Maybe you could start by writing a test for the join method using Quickcheck?

Java closures get type inference, hooray!

2010-07-08T09:42:00.000+02:00

According to the latest State of the Lambda document closures in Java will get type inference.

The return type and exception types of a lambda expression are inferred by the compiler; the parameter types may be explicitly specified or they may be inferred from the assignment context.

So this expression will be valid without explicit type annotation:

CallbackHandler cb = { c -> System.out.println("pippo") };

Finally, they seem to have mercy with the humble Java developer.

Talk to me - have fun with your favorite podcasts

2010-06-29T18:29:00.002+02:00

Driving home the other day I listened to a German radio show that made fun of chancellor Angela Merkel. They cut together some of her speeches to let her say the truth about here coalition with the FDP.

I thought: how hard can this be to create? It seems a simple version is not to hard to build using the Java sound API and my favorite podcast.

The idea is simple: take input audio files and create a index of words contained in these files. The index entry is the word, start time and end time. When a new sentence is created it will be stitched together with single words taken from the index.

The file index implementation is straight forward. It reads the index information from a CSV file that is on the classpath. The whole application configuration is done with Guice so the index file name is injected. (I created only a small index from the Java Posse Podcast using Audible.)

The AudioInputStream is the main class to interact with the Java Sound API. You read audio data from it. If you create audio data you do this by creating a AudioInputStream the AudioSystem can read from. The actual encoding is done by the AudioSystem implementation depending on the output audio format.

The Butcher class is the one concerned with audio files. It can read and write audio files and create AudioInputStreams from an input byte array. The other interesting think the Butcher can is cutting samples from a AudioInputStream. The AudioInputStream consists of frames that represent the samples of the PCM signal. Frames have a length of multiple bytes. To cut a valid range of frames from the AudioInputStream one has to take the frame size into account. The start and end time in milliseconds have to be translated to start byte and end bytes of the start frame and end frame. (The start and end data is stored as timestamps to keep them independent from the underlying encoding of the file used.)

The Butcher implementation is simplified. It only supports one WAV file AudioFormat and does no stream processing.

The Composer creates the output file. For a given sentence it takes the audio data for each word from the input files, concatenates the audio data and writes the result to disk. The Composer is currently not very sophisticated and takes the first word from the index it can find.

After building with mvn assembly:assembly the Java application can be run with

java -jar  target/talk-to-me-1.0-SNAPSHOT-jar-with-dependencies.jar [output file] [sentence]

There is still plenty of interesting material to play around with. The current version can be improved in different ways:

Indexing an audio file is quite cumbersome. If the start and end timestamp of a word could be detected from the silence between words indexing would be much easier.
The amplitude of words and the length of silence should be normalized.
Indexing could be even simpler if some speech recognition on the words could be performed.
The output quality could be improved by finding longest sequences of words in an input audio file that match the target sentence (longest common_substring_problem and longest common subsequence problem).

Tuning the Bloom-Filter-based Spelling Corrector

2010-02-22T18:33:00.001+01:00

With the candidate iterators and filter in place the Bloom Filter-based spelling corrector can be implemented and the performance measured.

The base implementation is here. The basic idea is described in the first blog post about the Bloom Filter-based spelling corrector so I won't get into detail about the implementation.

My benchmark is the implementation by David Pollack. As far as I can tell he thought a bit about performance so the comparison is not totally unfair.

The numbers aren't to bad. The Bloom Filter-based implementation is 2.5 times faster. (The performance comparison numbers are based on correcting words of edit distance 0 to 3 derived from the dictionary. The JVM is running with -Xms256m -Xmx256m -server.) My implementation corrects 115 words per seconds.

bloom 182.04358 (115 Hz)
benchmark 466.560114 (45 Hz)
benchmark/bloom 2.562903421257701

But there is still room for improvement. Executing the application with a memory profiler reveals that a lot of java.lang.Integer objects are allocated. The filter function Int => Boolean is translated by the Scala compiler to the generic trait Function1[Integer, Boolean]. This causes boxing of int values to Integer objects. (The boxing of Boolean values is not a problem. There are only two values as long as Boolean.valueOf is used.) Replacing the filter function with a filter trait based on primitive types solves this problem.

trait Filter{
  def contains(x : Int) : Boolean
}

The other source of boxed integers is the partial application of the StringHasher.hashRange method. When the string parameter is applied to the hashRange method a new Function3[Int,Int,Int,Int] is returned. This causes boxing as the previous Function1 object does. The partial application made the code a bit more readable. We have to compromise here on readability and replace the partial application with a normal method that fits well with the JVM.

Implementing these improvements resulted in worse performance at the beginning. The problem was that I used s(idx) instead of s.charAt(idx). The s(idx) converts the String to a RichString and then calls the apply method on it. Both methods are functionally identical but the first will cause conversions from String to RichString whereas the charAt method is a direct method call on the given String. This is a subtle problem the best solution would be able to disable implicit conversions from String to RichString defined in Predef for this file.

With both improvements in place the implementation is 3.7 times faster.

bloom 113.69269 (184 Hz)
benchmark 424.767132 (49Hz)
benchmark/bloom 3.736098881994964

The next step is a bit controversial: basing the candidate production on char Arrays replacing Strings. This yields good performance improvements the final number is 4.9 times faster than the competing implementation but it has clearly a number of drawbacks. The code becomes quite low-level using System.arrayCopy instead of RichString methods. The char[] arrays are mutable so a collaborator may manipulate the array content.

bloom 89.082697 (235 Hz)
benchmark 437.214067 (48 Hz)
benchmark/bloom 4.907957232143522

Some further improvements are still possible. With enough effort the BloomSpeller, Dictionary and CandidateIterators could be based on a CharSequence flyweight implementation. Having this interface in place candidate iterators can return implementations of CharSequence containing only the base string as common state and the individual state of the candidate (index to manipulate, candidate hash value and optionally the alphabet character to use). This would save memory allocation, garbage collection for the candidate char[] array instance and redundant hash value computation. (The candidate hash value is computed a second time when the Speller implementation checks whether the candidate is in the Dictionary.)

The final step is to tune the Bloom Filter configuration. In the first blog entry of this series I calculated expected performance values based on the Bloom Filter worst case (all candidates are contained in the Bloom Filter). The actual numbers differ from the expected results as most candidate checks against the Bloom Filter will abort earlier before k hash functions were executed. Another factor not present in the model is the optimization to compute only hash values for about half of the string length.

The performance is surprisingly stable for an n/m ratio of 4 up to 256. For an n/m up to 4 the production of false candidates dominates the performance characteristics. For n/m ratio greater than 128 the execution of hash functions starts to degrade performance. Over all the configuration of an n/m ratio = 4 is good enough. Only small improvements can be attained with changing this number.

n/m ratio	performance ratio
1	1,85
2	3,07
4	4,05
8	5,07
16	4,75
32	4,83
64	4,93
128	4,69
256	3,89
512	1,78
1024	0,53

Conclusion

Scala is a flexible language. You can write high-level and low-level code as needed. The basic approach to start a high-level implementation and optimizing the hot spots worked out quite well for this example. The byte code emitted by the Scala compiler is good enough in most cases. Some abstractions of the language do not fit to well with the Java platform. This is not a problem for regular code and can be fixed with low-level implementations for hot spots as we've seen. The new @specialized annotation may help here in the future to lower the amount of low-level code.

There are still some areas worth to investigate. How to distribute the candidate production and filtering over multiple cores? Using a join-fork framework or Scala's Future construct seem to fit quite well here. Another idea is to compare the Bloom Filter-based spell checker implementation against a BK-Tree-based implementation.

Producing candidates for a spelling corrector

2010-02-16T20:11:00.002+01:00

The next step to implement the Bloom Filter-based spelling corrector is to create and check hash values for candidates against the filter without actually creating candidate instances. If the filter step succeeds the candidate String instances are created in the next step.

All candidate iterators (for insertion, deletion, transposition and replacement) are based on the CandidateIterator trait. The CandidateIterator can return a hash value for a candidate with the hashValue method and a candidate string with the candidate method. The next method scrolls to the next value.

trait CandidateIterator{
  def next : Boolean
  def candidate : String
  def hashValue : Int
}

An instructive implementation is the replacement CandidateIterator. It replaces each character of the base string with a character from the alphabet to create a candidate.

The candidate method does exactly this for candidate strings. It takes the base string and replaces the character at the idx position with the character from the alphabet at the alphabetIdx position (the alphabet is defined as val alphabet = 'a' to 'z' toArray).

def candidate = (base take idx) + Dictionary.alphabet(alphabetIdx) + (base drop idx + 1)

The hashValue method is not as easily readable as the candidate method. The implementation is based on the insight that the hash function for Strings is the defined in a way that we can reused a base hash value for the a substring base.substring(0, idx). With that in place we can save about half of the hash computations. This has huge performance benefits over an implementation that works directly with Strings where hash values have to be computed from the scratch for every candidate. Analogous to the String copy costs the hashing costs increase nearly linearly with the String length. The performance benefits will be especially relevant for long Strings that will then produce a lot of candidate strings.

The next method takes care of the idx, alphabetIdx to point to valid positions. The baseHash value is calculated iteratively in the next method from the baseHash of the last round if the idx value changes.

The hashValue implementation is now based on the baseHash value. The hash is computed for the character taken from the alphabet and the remaining string base.substring(idx + 1, base.length).

class Replacement(base : String) extends BaseCandidateIterator(base){
  private var idx = 0
  private var alphabetIdx = -1
  private var baseHash = 0
  def next = {
    alphabetIdx += 1
    if(alphabetIdx == Dictionary.alphabet.length){
      idx += 1
      alphabetIdx = 0
      baseHash = hashAt(baseHash, idx - 1)
    }
    idx < base.length
  }
  def candidate = (base take idx) + Dictionary.alphabet(alphabetIdx) + (base drop idx + 1)
  def hashValue = {
    val pivot = hashFor(baseHash, Dictionary.alphabet(alphabetIdx))
    val right = hashRange(pivot, idx + 1, base.length)
    right
  }
}

The CandidateIterator let's us iterate over candidate hash values without creating objects. Externally to the CandidateIterators the filtering takes places calling the candidate to produce an instance method only when the hash value was in the filter. This work is done by the CandidateFilter.

class CandidateFilter(base : CandidateIterator, filter : Int => Boolean) extends Iterator[String]{
  private var more : Boolean = false
  def hasNext : Boolean = {
    def hasMore : Boolean = {
      while(base.next) if(filter(base.hashValue)) return true
      false
    }
    more ||= hasMore
    more
  }

  def next : String = {
    more = false
    base.candidate
  }
}

The class takes a CandidateIterator and a filter. It implements the Iterator trait. Values returned by the CandidateFilter are candidate strings that passed the Bloom Filter test.

Users of the CandidateFilter and CandidateIterator can now use the Iterator convenience methods and for expressions to work with candidate strings as usual.

With the CandidateIterator implementation and the CandidateFilter in place the spelling corrector can be implementation in the final step.

Implementing hash functions in functional style

2010-02-08T18:05:00.001+01:00

The first ability needed to enable filtering with the Bloom Filter-based spell checker is to produce hash values for candidates.

The basic functionality is to hash a character given a base hash value from a preceding invocation. The hashFor function implements this.

def hashFor(h: Int, c: Char) : Int = h * 31 + c

Two further functions help with building candidate hashes: hashAt and hashRange.

HashAt builds the hash for the a character of base string at a index position given a base hash value.

def hashAt(base : String)(h: Int, i: Int) : Int= hashFor(h, base.charAt(i))

The hashAt method is defined in a way to be able to use partial application of parameters. (It's not using clean currying. The Scala language allows to define functions with mixed arity: unary functions and functions with arity greater than 1.)

The motivation to define the function in this way is to be able to use it with fewer parameters than the method definition def hashAt(base : String, h: Int, i: Int) when it is used repeatedly with the same base string parameter.

To get the function signature you can access the function object in the Scala console:

scala> hashAt _
(String) => (Int, Int) => Int

Alternatively the signature can be written as (String) => ((Int, Int) => Int) for better readability. The function takes one parameter and will return a function of type (Int, Int) => Int.

To make any sense of this let's apply the parameters one by one:

scala> val f = hashAt _
f: (String) => (Int, Int) => Int = <function>

scala> val g = f("s")
g: (Int, Int) => Int =  <function>

scala> val h = g(0,0)
h: Int = 115

The parameters are applied left to right. The intermediary function definitions has each parameters bound until there are no parameter left to bind and the function is evaluated. The sequence is equivalent to calling hashAt("s")(0,0).

HashRange hashes characters of a string from a start index to the end index (exclusively) given a base hash value.

def hashRange(base : String)(h: Int, i: Int, end : Int) : Int =
    if(i < end) hashRange(base)(hashAt(base)(h, i), i + 1, end) else h

Using the hashRange method you can produce the same hashValues as the java.lang.String implementation.

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;
            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
    return h;
}

The equivalent definition based on the hashRange function is:

def hash(s : String) = StringHasher.hashRange(s)(0, 0, s.length)

The function is defined as a tail recursive method. A tail recursive function is a function that does only return values from recursive calls and won't manipulate these return values. With a tail recursive definition the Scala compiler is able to translate the recursive call into a loop. Defining a tail recursive function is a bit tricky and you may inadvertently change a tail recursive version into a normal recursive one and even an optimized tail recursive function into a not optimized one. To omit the pitfalls of tail recursive functions Scala 2.8 introduces a @tailrec annotation. This produces a compiler failure if a function cannot be optimized.

With the hash support methods hashAt, hashFor, hashRange in place we can implement hash values for candidates. I'll implement the insertion candidate production to demonstrate the application of the methods. The insert adds a characters from an alphabet at a given index.

It is always good to write some tests (besides the fact that it tests the functionality) to be able to have a look at the API from the user's perspective. Testing the individual methods is not enough to get a feel of the API. Users will always use a combination of the three methods. One concern is that the hash code is calculated incrementally and the user has to define the hash functions in a incremental manner as well. Using the output of preceding execution as an input parameter for succeeding method calls which may be error prone.

The law for the insert candidate hash can be defined with the equivalent hash function of java.lang.String implementation. It can be expressed in specification-based test:

@Test def userSample {
  for{s <- strings
    index <- integers(0, s.length - 1)
    c <- basicLatinCharacters}{
    val insertCandidate = (s take index) + c + (s drop index)
    assertEquals(insertCandidate.hashCode, insertCandidateHash(s, index,c))
  }
}

Three methods of the specification-based test framework Quickcheck are used in the test:
- strings returns an arbitrary string value
- integer(min,max) returns an integer value from min to max (inclusive)
- basicLatinCharacters returns a sample character from the from the Unicode Latin-1 code page.
All three methods return values through the Generator interface that is converted with a implicit type conversion to an Scala Iterator to be able to use it in a for expression.

With the input string, insertion index and character to insert given the actual law is quite simple. We construct a string that is an equivalent insertion candidate and get its hash value. The hash value returned by the insertCandidateHash method under test has to be produce the same value. (This is a testing pattern in the context of specification-based test: testing based on a analogous functions. Stay tuned for a in depth description of the testing patterns.) This example shows that unpleasant tests with classical scenario-based TDD can be expressed in a compact way with specification-based testing. The last piece of the puzzle is the implementation of the insertCandidateHash function.

def insertCandidateHash(s : String, i : Int, c : Char) = {
  val hashRange = StringHasher.hashRange(s) _
  val left = hashRange(0, 0, i)
  val pivot = StringHasher.hashFor(left, c)
  val right = hashRange(pivot, i, s.length)
  right
}

The sample code demonstrates the use partial application of function parameters in the first line. The string parameter is applied to the function returning a function with the signature (Int, Int, Int) => Int. This function object can than be used for all hash values of the same base string. The hash value is calculated for the left, pivot and right characters of the string. The characters for the left and right hash values are unchanged from the base string. The hash value for the pivot element is one from the alphabet as one would expect for an insertion.

In the next blog I'll implement the candidate iterators for insertion, replacement, transposition and delete based on the StringHasher.

The moment electronic paper died

2010-02-07T13:56:00.001+01:00

Perhaps you did not noticed it but last week the electronic paper followed the Maglev and became part of the museum of failed technical innovations. As the Maglev, it started with a brilliant theoretical idea that nobody cared about once it was there.

The Maglev promised faster train travel with a better efficiency. The problem of the Maglev is that is does not fit well into the current infrastructure. New separate tracks have to be build. In the meantime wheeled electric trains are capable to travel at high speeds using and interfacing better with the current infrastructure.

Electronic paper has the advantage that it does not consume electricity while displaying a single page and works without backlight. In theory an electronic paper-based device can be used much longer with recharging. Readability for text is supposed to be better than a LCD as well. But it cannot display charts, tables and photos well. Everything users are used to know on the computer and smart phones. Additionally, they switch slowly from one page to another and the display even flickers annoyingly while changing the page content.

Until the advent of the iPad I thought of buying such a device and fantasized about caring around all my IT-books, classical literature from Project Gutenberg and blogs on this device around while commuting. It was just a matter of the right price. But now I do not see a point anymore. The iPad has proven that it is possible to build a general purpose computing device that includes book reading software. The electronic paper may be better for novels but I don't care. The ability to use all kinds of software and browse the web on such a device is definitely buying me more.

That said the iPad is just the prove that it can be done. It is not platform I would like to develop on.

What's the point off having a general purpose computing device that is controlled by one company? The platform for such a device has to be reasonably open. And I think that will not only be in the interest of application developers but of the provider of such a platform as well. The development and deployment model imposed on developers will stifle innovation. As innovative as the iPad may be a single company won't outperform a whole industry in the long run.

A faster spelling corrector

2010-02-02T20:22:00.014+01:00

The compact spelling corrector implemention showed some of the features of Scala: for expression, higher order functions (fold and map), tuple support and the infix method syntax. The current implementation has terrible performance, so we try to develop a faster corrector implementation.

Let's have a look at it at run-time with the VisualVM memory profiler.

Not very surprising, it creates a lot of objects. To correct 20 words of edit distance 0 to 3 randomly picked from the big.txt file it allocated 15 million char[] arrays and 9 million String instances. Allocation may be cheap but allocating millions of objects is not.

One way to improve the performance of the spelling corrector is to allocate fewer objects. The spelling corrector is based on a brute force approach: calculate all possible candidates for a given edit distance. The most expensive operation is to create candidate string instances. The java.lang.String implementation is immutable. Every single change to a String will force the creation of a new instance.

But we can do better than that. We can capitalize on the knowledge that the Strings won't be random. The candidates can be easily deduced from the base string. A candidate string has some additional private state depending on the operation (insert, transpose, replace, delete) performed. Phrasing it in this way directly leads to the flyweight pattern. Flyweights can be implemented for every operation implementing the CharSequence interface that is already part of the JDK. This will gain quite good performance improvements. No additional char[] arrays will be allocated.

I'll skip the flyweight implementation and leave it as an exercise. There is a better approach.

The flyweight implementation will still create one object per candidate. Even this can be omitted. If we would pick only candidates that are promising the creation of objects would be further reduced and the performance increased. And happy coincidence a data structure can help here: the Bloom Filter.

Additionally to dictionary of word frequencies that is already used in the base implementation of the spelling corrector a Bloom Filter is initialized with all words.

The candidate generation will than be separated in multiple steps: candidate hashing, hash filtering with the Bloom Filter, candidate instantiation and dictionary filtering.

Using the Bloom Filter most of the candidates will not survive the hash generation and hash filtering steps. The hashed candidates can be calculated without instantiating any objects, just using primitive int values that live on the stack. This has super performance characteristics: no memory allocation and garbage collecting needed.

For every type of candidate: deletion, replacement, insertion and transposition an Iterator can be implemented that produces the candidate hash values. The iterator implementations are based on a base string and additional state (positions in the base string and positions in the alphabet) necessary for the candidate hash value production.

All candidate hash values will be checked if they are contained in the Bloom Filter. If so the candidate string will be created and checked against the dictionary. The second check is necessary as the bloom filter produces false positives.

The actual false positive rate can be freely chosen. It will have no impact on the functionality. It could be 100%. The false positive rate can be changed to tune the performance depending on memory consumption requirements, cost of hash functions used in the Bloom Filter implementation and object instantiation cost for candidate strings.

To check on the basic assumption we can measure the performance characteristics of the basic string operations needed and the Bloom Filter. The limited performance test compares the run-time of a character array copy needed to create the base char[] for one insertion candidate string (creating a String candidate won't be faster than this)

arraycopy(stringValue, 0, s, 0, 1) //insertion
s(1) = 'c'
arraycopy(stringValue, 1, s, 2, stringValue.length - 1)

and the Bloom Filter contains method performance.

All presented durations lack an unit of measurement as all measurements are based on the same scale. This is sufficient to compare the values.

The time needed to create the insertion candidate string grows linearly with the base string length.

char[] length	character copy time
2	11,69
4	11,70
8	12,57
16	15,95
32	21,57
64	30,21
128	51,22

The Bloom Filter time grows linearly with the number of hash functions (k) used. The optimal number of hash functions used is determined according to the ration between expected elements (n) and bloom filter size (m).

The measured time is the worst case: an entry (or a false positive) is in the Bloom Filter. In this scenario all k-hash functions are executed.

n/m ratio	k	false positive rate	time filter
1	1	0,62	3,73
2	2	0,39	5,70
3	3	0,24	7,70
4	3	0,14	7,71
5	4	0,09	9,38
6	5	0,05	11,59
7	5	0,03	11,59
8	6	0,02	13,80
9	7	0,01	18,68
10	7	0,01	18,68

In a real world scenario the average run-time of the Bloom Filter will be better as the execution can be aborted for values that are not in the Bloom Filter. The false positive probability another important figure of the Bloom Filter:

False positive causes additional work based on the assumption to work with a valid value. This run-time is wasted as the preceding check against the dictionary will eliminate the false positives.

To get the expected resulting performance of the spelling corrector we construct a small model. The expected run-time is determined by the cost of the filter t_f, the false positives probability p_f the probability p_w that a candidate is a word in the dictionary and the time t_s to construct a candidate string. The time spend to construct strings which are false positives is p_f * t_s. The time spend to construct strings which are words is p_w*t_s. (To simplify the formula a constant string length is assumed.)

The values computed are based on candidate strings with a length of 8 chars (t_s=t_s8) and the probability that 5% of the candidates are words contained in the dictionary (p_w=0.05).

n/m ratio	k	false positive rate (p_f)	time filter (t_f)	*false positive time (p_f t_s)**	expected time (t)
1	1	0,62	3,73	7,84	12,20
2	2	0,39	5,70	4,88	11,21
3	3	0,24	7,70	3,04	11,37
4	3	0,14	7,71	1,76	10,10
5	4	0,09	9,38	1,09	11,09
6	5	0,05	11,59	0,66	12,88
7	5	0,03	11,59	0,39	12,61
8	6	0,02	13,80	0,25	14,68
9	7	0,01	18,68	0,15	19,46
10	7	0,01	18,68	0,09	19,40

By increasing the n/m ratio (and hash functions k executed respectively) of the Bloom Filter we see an increase in the time spent to check if the filter contains a candidates string (time filter). On the other hand the time spent to produce false positives (false positive time) declines with a growing n/m ratio.

For the given model the local minimum of the expected run-time is with a n/m ratio of 4 (false positive rate of 0,14). The expected worst case run-time of the Bloom Filter based implementation is better than the plain array copying run-time (with a of minimum 11,69) and the performance benefits increases dramatically with the string length.

In the next blog entries I'll implement this Bloom Filter-based spelling corrector to see if one can capitalize on the theoretical advantages. The next blog entry will be about the hash function support needed.

Why overrideable tail recursive methods must not be optimized

2010-01-18T21:05:00.002+01:00

Suppose you define a tail recursive method x in a object A. You can use the @tailrec annotation to mark methods you expect optimization of the tail recursive code to happen.

import annotation._
object A{
    @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

Now you move the method x to a trait or class and suddenly the compilation fails.

import annotation._
trait A{
    @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

:8: error: could not optimize @tailrec annotated method
            @tailrec def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s

I had exactly this problem. I defined a perfectly valid tail recursive function but the compiler would not optimize it to a loop. This was in Scala 2.7 that does not support the @tailrec annotation. You have the additional issue of spotting the problem in the first place.

The problem is that overrideable tail recursive methods won't be optimized. If you change the code to

import annotation._
trait A{
    @tailrec final def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

it will compile again. This is the rule. But why?

Performance optimization must not change the behavior at run-time. So overriding an optimized tail recursive method will behave differently from an unoptimized tail recursive method.

Let's define A in a way that it won't be optimized and override the tail recursive method x in the subclass B.

class A{
    def x(i : Int, s : String) : String = if(i > 0) x(i - 1, s + "a:" + i) else s
}

class B extends A{
    override def x(i : Int, s: String) : String = super.x(i, s + "b:")
}

This will produce the output:

scala> new A().x(3, "")
res0: String = a:3a:2a:1

scala> new B().x(3, "")
res1: String = b:a:3b:a:2b:a:1b:

The implementation of the method x in B invokes the method x in A. When the method x defined in A invokes the method x it calls the method x in B (for an instance of B). This behavior is due to late binding of calls to x.

Suppose it was possible to optimize the method x in A. The compiler would define a class similar to this definition of A. The recursive invocation of x is optimized to a loop. With this definition of x there is no possibility to apply late binding to x. The optimization would hard wire the definition of x.

class A{
    def x(i : Int, s : String) : String = {
        var j = i
        var t = s
        while(j > 0){
            t = t + "a:" + j
            j = j - 1
        }
        t
    }
}

class B extends A{
    override def x(i : Int, s: String) : String = super.x(i, "b:" + s)
}

scala> new A().x(3, "")
res0: String = a:3a:2a:1

scala> new B().x(3, "")
res1: String = b:a:3a:2a:1

The early binding of x in A changes the behavior of B. Once the method x in A is called it will never come back to B. This is the reason why the Scala compiler can't optimize overrideable tail recursive methods.

Following this explanation, it should be clear that the @tailrec annotation is worthwhile and should be used in all your Scala 2.8 code you expect the optimization to happen. For Scala 2.7 it's a bit unfortunate that moving a tail recursive method from an object to trait will change the behavior significantly without a compiler error. So be warned.

Lessons from Stackoverflow: missing education should not stop you from being a good developer

2010-01-11T09:01:00.001+01:00

To put this blog into perspective: I've the weakest of all possible computer science degrees you can imagine. It's formally a degree in computer science but half of my curriculum was in communication engineering which is an interesting field (if you want to build a digital hearing aid for your grandma) but does not really help with software development.

I do appreciate the work of Jeff Atwood at Stackoverflow. It's a great site. It is a viable programming resource. Judging based on his results he is a good developer.

Ironically you can build a good product without been a topnotch computer scientist. This is really encouraging for me.

I'd been reading Jeff Atwood's blog for more than two years because it was funny, entertaining, presented a down-to-earth view of IT and provided insights of a different community (.net and Windows) from my Java community. But around the time he started Stackoverflow I quit reading his blog. I cannot say exactly why, but I lost its appeal a bit. I liked to read more computer science related stuff (mostly from the functional programming world). Roughly one year later I'm back again. I really like Stackoverflow.

But time and again listening to the Stackoverflow podcasts makes me wondering how's that possible. How could he write Stackoverlow? In the latest Stackoverflow podcast #79 Joel Spolsky tried to explain that you can parse only regular languages with regexps parser. (Actually, most implementations allow more than that. For example back referencing is more powerful than regular expressions.) This explanation goes on and on. This was like a déjà vu when he tried to explain Jeff and Scott Hanselman Hindley-Milner type inference algorithm used by the Haskell compiler. (He tried to explain that you can deduce the return type of a method from the parameters and the functions called. Let's say he did not get too far.)

Jeff explains why it's great to have his first open-source project. How many bugs he fixed and that he is now at the point where the hairy problems start. Few people seem to be able to help fixing the problems in the C# port of the PHP and Perl implementations. Joel explains again and again that you need a lexer and parser generator to parse Markdown and every student with a parser course can tell you that this is right tool for this kind of problem. That a transformation from an AST is a piece of cake. I never had a parser course so don't expect a scientific explanation here, but I was at least able to parse a subset of SQL with Parser Combinators. The moment Jeff started to explain his open source project. That the parsing is done with regular expressions I though: "Hell, why didn't he use a lexer/parser for that."

But you can learn something from Jeff Atwood's example: Your meager education should not stop you from being a good developer. We can't all have ivy league education. (They wouldn't be ivy league if everyone would get a degree. The system does only work because it discriminates between students.) Let's get over it. Put your enthusiasm in your work and learn the bits and pieces you have to learn to get the jobs done. Try to constantly improve your theoretical knowledge, your tool knowledge, quality of your code and your communication skills. Maintain your critical thinking to spot ways you can improve. You can't known everything but you should known what you don't known:

There are known knowns. These are things we know that we know. There are known unknowns. That is to say, there are things that we know we don't know. But there are also unknown unknowns. There are things we don't know we don't know.

The known unknowns will slow you down, but only the unknown unknowns can hurt you. These are the places where you put to much effort into a problem that is already solved like parsing. But a star maverick developer can only develop so much. There will be times when a Duct Tape Developer is needed and the pure theory boys won't get the job done. This is the one thing you can learn from the Stackoverflow story: It's the motivation, stupid.

By the way, if you have doubts about your abilities, this is probably a good sign.

How to setup a Maven Scala project with IntelliJ IDEA support

2010-01-07T09:07:00.003+01:00

Setting up a Maven and Scala project with IDEA is simple.

Install IntelliJ IDEA Community Edition and the Scala plugin (File -> Settings -> Plugins -> Available).

Generate your maven project using the simple Scala archetype:

mvn org.apache.maven.plugins:maven-archetype-plugin:1.0-alpha-7:create 
    -DarchetypeGroupId=org.scala-tools.archetypes  
    -DarchetypeArtifactId=scala-archetype-simple
    -DarchetypeVersion=1.2
    -DremoteRepositories=http://scala-tools.org/repo-releases
    -DgroupId=group
    -DartifactId=artifact

Add the Scala compiler lib to your project dependencies in the pom.xml file:

<dependencies>
    <dependency>
        <groupId>org.scala-lang</groupId>
        <artifactId>scala-compiler</artifactId>
        <version>${scala.version}</version>
        <scope>compile</scope>
    </dependency>
 </dependencies>

Update the Scala version configuration to a recent release:

<properties>
    <scala.version>2.7.7</scala.version>
</properties>

Open the a new project. Select the pom.xml in the file dialog.

An notification will pop up. Click "Create Scala Facet".

Done.

You can now compile and execute as usual and run the maven build mvn install with the Maven Tool Window. (The M2_HOME environment variable or Maven home settings (File -> Settings -> Maven -> Maven home directory) have to be present.)

The best Scala IDE: IntelliJ IDEA

2010-01-06T17:59:00.005+01:00

After years and years of using Eclipse (after Netbeans, JBuilder, Visual Cafe, Emacs and other spooky Java "editors") IntelliJ IDEA is powerful, convenient and simple to use IDE for Scala development. Oh, yes it's free: IntelliJ IDEA Community edition.

I tried IDEA because the Scala plug-in for Eclipse is so horrible. I works so badly that using good old jEdit with some macros is way better. On a small project I had to clean the whole project for every compile. It's so bad. After several tries (starting sometime in 2008) I've given up on this thing.

Before IDEA I also tried to use Netbeans, but it failed the dump-developer-that-does-not-read-the-manual-test. Basic functionality should be usable without a detailed study of the documentation. That worked for me with IDEA but I could not get the plugin Scala plugin to run in Netbeans. It's probably me and everything is fine with Netbeans. Still I've invested less time to get things done with IDEA. It simply worked.

The simple summary: every basic IDE feature works: syntax high lighting, compiling, debugging, navigation and outline.

If you worried about productivity of Scala development because it was missing IDE support: stop worrying. The support is here.

I'm a heavy short cut user so using a new IDE slows me down naturally. Using the Eclipse key map was not an option for me. This works only 80% of the time. The main problem is that functionality with the same shortcuts behaves slightly different. That's maddening at the long run. So it's better to learn a new set of short cuts. It's like driving in Great Britain. It's easier when you are using a car with the steering wheel on the right. Driving a car with the steering wheel on the left is dangerous. There are the country side hedges where you'll see practically nothing in a left turn and chances are that you're going to start your trip on the right hand side on a calm country road. So better relearn.

Interestingly IDEA has a code analysis tool that does spell checking in comments, methods and variables names. This is already works for Scala. Eclipse does spell checking only in comments. This is a boon for code quality. You do not want to read incorrectly spelled source code. This is plain annoying to read, fix and frankly to get right (camel case does not make it easier). (The code analysis tool for Java is very good. It finds tons and tons of problems after FindBugs. I have not heard about the analysis tool before. It would be nice if it could be integrated in build tools and used in a continuous integration environments.)

The maven support seems to work out of the box. It reads a pom.xml and builds IDEA project files from it. It still uses its internal build infrastructure. With Eclipse you have to manually generate the .project and .classpath files which works but is an extra step and the eclipse specific configuration in pom files can get quite clunky.

The essential things work for Scala. You have code completion without implicit type conversion information. I suppose the support for implicit type conversion is quite hard to implement. There are a lot of callable members with type conversion for a given object. I suppose the best way to implement this would be a 2-step process. First show all directly reachable members and after hitting Ctrl + Shift again show all reachable members. Methods parameters are missing for decompiled Scala classes and as code completion information.

Besides these minor problems IntelliJ IDEA is a wonderful tool to develop Scala with and it does not crash. Go and try it yourself.

Quickcheck 0.5 release

2010-01-02T21:51:00.007+01:00

It's done: Quickcheck version 0.5 is ready. Again one of the nice little releases of Quickcheck.

The 0.5 release added the following features mainly to provide better readability:

Support for an adapter from Generator to Iterable to allow the use of Java's for-expression in tests (replacing the inner classes).
Generated source code for @Iterables and @Samples annotations on generator factories. The @Iterables annotation was added to support for-expression directly with Generators without additional code. The @Samples annotation can be used to generate a factory for sample values from a Generator class.

Minor changes are:

Added a declarative Pojo generator for interfaces.
Implemented excluding generator.
Added Generators.cast utility method. Generator<String> can now be casted to Generator<Object> to provide broader applicability of Generators.
Maven repository support (http://download.java.net/maven/2/net/java/quickcheck)

The version 0.6 of Quickcheck will be a major rework after more than 2 years of experience with the specification-based test approach and development. Mainly to support further development for example shrinking (simplification) of failed test values. A major feature still missing in Quickcheck version 0.5.

When I started Quickcheck I would not have thought that it is possible to develop such a tiny little thing for more than 2 years. Still more ideas and things that could be implemented and written about and so little time.

Recently, I've used the 0.5 version in my Scala projects I blogged about. I did not mention that I tested it in any way, though. It was a pleasant experience given that QuickCheck was not designed with Scala's language features in mind. It works with just a small implicit type conversion and adaption layer (10 lines or so).

Distribution function implementations based on the XorShift random number generator I've already worked with would be nice to have. When I'm at adding new distributions anyway, there are still the distribution functions based on heuristics to implement. For example a distribution function based on a boundary heuristic that starts production of values with minimum value, -epsilon, 0, +epsilon and maximum value before random generation kicks in. Another item on my ever growing list is the description of patterns related to specification-based testing and QuickCheck. Obviously there is still plenty of work left.

Peter Norvig's Spelling Corrector in Scala

2009-12-31T13:55:00.007+01:00

This is a Scala version of Peter Norvig's spelling corrector. Reading his essay I realized that Python is quite a nice language and similar to Scala due to the support of for-expressions in both languages. Before that I've seen Python as a strange language that made you write self in your classes all the time.

I tried to write the shortest version possible without introducing redundancy. The code is definitely not very readable.

import util.matching.Regex.MatchIterator

val alphabet = 'a' to 'z' toArray
def train(features : MatchIterator) = (Map[String, Int]() /: features)((m, f) => m + ((f, m.getOrElse(f, 0) + 1)))
def words(text : String) = ("[%s]+" format alphabet.mkString).r.findAllIn(text.toLowerCase)
val dict = train(words(io.Source.fromFile("big.txt").mkString))

def edits(s : Seq[(String, String)]) = (for((a,b) <- s; if b.length > 0) yield a + b.substring(1)) ++
  (for((a,b) <- s; if b.length > 1) yield a + b(1) + b(0) + b.substring(2)) ++
  (for((a,b) <- s; c <- alphabet if b.length > 0) yield a + c + b.substring(1)) ++
  (for((a,b) <- s; c <- alphabet) yield a + c + b)

def edits1(word : String) = edits(for(i <- 0 to word.length) yield (word take i, word drop i))
def edits2(word : String) = for(e1 <- edits1(word); e2 <-edits1(e1)) yield e2
def known(words : Seq[String]) = for(w <- words; found <- dict.get(w)) yield w
def or[T](candidates : Seq[T], other : => Seq[T]) = if(candidates.isEmpty) other else candidates

def candidates(word: String) = or(known(List(word)), or(known(edits1(word)), known(edits2(word))))

def correct(word : String) = ((-1, word) /: candidates(word))(
  (max, word) => if(dict(word) > max._1) (dict(word), word) else max)._2

List("osters", "musters", "mixters") map correct foreach println

You can run the script directly with the Scala interpreter:

$ scala test.scala
posters
masters
matters

A decent Bloom Filter in Scala

2009-12-20T15:54:00.011+01:00

The Bloom Filter is an interesting probabilistic data structure. Its main advantage is that the Bloom Filter drastically reduces the memory consumption.

It produces false positives. Which means that it falsely states that a value is contained. On the other hand it ensures that it produces no false negatives. This renders it useful for space efficient in-process filtering.

The memory needed is not determined by the size of the object stored but by the number of elements and quality of the Bloom Filter (the false positive rate). Whole cars, houses and star ships fit into this little bloom filter.

My Scala implementation is based on a decent stand-alone Java Bloom Filter by Ian Clarke.

class BloomFilter(val size : Int, val expectedElements : Int ){
  require(size > 0)
  require(expectedElements > 0)

  val bitArray = new BitArray(size)
  val k = ceil((bitArray.size / expectedElements) * log(2.0)).toInt
  val expectedFalsePositiveProbability = pow(1 - exp(-k * 1.0 * expectedElements / bitArray.size), k)

  def add(hash : Int) {
    def add(i : Int, seed : Int) {
      if(i == k) return
      val next = xorRandom(seed)
      bitArray.set(next)
      add(i + 1, next)
    }
    add(0, hash)
  }

  def contains(hash : Int) : Boolean = {
    def contains(i : Int, seed : Int) : Boolean = {
      if(i == k) return true
      val next = xorRandom(seed)
      if (!bitArray.get(next)) return false
      return contains(i + 1, next)
    }
    contains(0, hash)
  }

  private def xorRandom(i : Int) = {
    var y = i
    y ^= y << 13
    y ^= y >> 17
    y ^ y << 5
  }
}

It has some advantages over the base version:
- My implementation replaces java.util.Random with am in-lined Xorshift Random Number Generator that has sufficient randomness for a Bloom Filter. Additionally the java.util.Random is thread-safe which decreases the performance unnecessarily.
- The BitSet implementation is replaced by a simplified bit array implementation. An idea I've borrowed from a Bloom Filter implementation by Kevin Bourrillion. The size of the BitArray is always a power of 2. This allows some performance optimizations. The modulo operations used to transform a hash function result into a bit set index can be replaced with bit shifting: x % size = x & (size – 1) (when size is a power of 2).

class BitArray(bits : Int){
  val size = nextPow2(bits)
  require(isPowerOf2(size))
  private val data = new Array[Long](size >> 6)

  def set(index : Int) = data(idx(index)) |= (1L << index)
  def get(index : Int) = (data(idx(index)) & (1L << index)) != 0

  private val mask = size - 1
  private def idx(index : Int) = (index & mask) >> 6
  private def isPowerOf2(i : Int) = ((i - 1) & i) == 0
  private def nextPow2(i : Int) = {
    def highestBit(remainder : Int, c : Int) : Int = 
       if(remainder > 0) highestBit(remainder >> 1, c + 1) else c
    require(i <= (1 << 30))
    val n = if(isPowerOf2(i)) i else 1 << highestBit(i, 0)
    assert(n >= i && i * 2 > n && isPowerOf2(n))
    n
  }
}

- The bloom filter works directly with hash values. I think that the Set semantics are overstretched when applied to Bloom Filters. A lot of the methods are not supported and the return values of add (and addAll) are misleading. Using the hash values directly is useful if you do not want to create objects to check if they are contained in the filter. The assumption here is that the object instantiation is far more expensive than calculating hash values and create only objects for the values contained in the filter. Normal uses are of course still possible with this interface.

All the changes add up to an increase in performance of at least 300% compared to the base implementation having a similar false positive rate.

Support for generator type conversion in Quickcheck

2009-10-19T14:07:00.002+02:00

A new utility method is now part of Quickcheck that lets you convert a Generator<A> to a Generator<B> given that A extends B.

This is useful when you have a Generator<Integer> and would like to treat it as a generator of type Generator<Object>.

This can now be done using the Generators.cast method:

Generator<Integer> integers = PrimitiveGenerators.integers();
Generator<Object> objects = Generators.<Object> cast(integers);

This is valid as the type Generator is covariant. (It does only produce values but the state of the Generator<T> is not altered.)

The cast is needed as the Java type does only support invariant generic types. Java cannot support the valid implicit type conversion from Generator<Integer> to Generator<Object>. This information is not present in the Java type system. The cast has to be performed explicitly. (If the generic type Generator could be annotated that it is covariant this sort of conversion could be supported. Scala supports the covariant and contravariant type conversion this way.)