The Bowling Work Sample

A couple of years ago, I read an interesting book chapter by Robert C. Martin and Robert S. Koss. It demonstrates how pair programming and test driven development works, by implementing a simple program that scores a ten pin bowling game. Although the episode demonstrates the use of these techniques extremely well, I always thought that the resulting libraries design was not optimal, because it would be hard to reuse the code inside a more complex (G)UI application.

Some years later, I was asked to repeat that this exercise as a work sample, while applying for a job.I took the chance to challenge my assumptions and develop the application including a GUI using TDD. I started with the GUI, so that the customer has something to look at and play with. This would also enable me to prove that a different and more versatile design will emerge, when a GUI is present. Of course it was also a possibility to show of bit, by developing UI code using TDD. As anticipated, the UI code proved to be extremely challenging, as the scoring rules of bowling are straight forward on the first view, but have a lot of exceptions and extra ifs, especially on the last frame. I ended with a well crafted, well tested, but rather complex application.

Since then I use this bowling scoring sample to get myself familiar with new technologies and programming environments. The rules of bowling are easy to grasp and still complex enough to write a manageable and simple application. When you start to add applications to track a complete bowling league, the sample can scale even to a small and complete distributed system.

The first version I wrote about was written in C# 3.0 using WindowsForms, Spring.NET, RhinoMocks and NUnit.

I’m currently working on a Java version using Java 1.6, Maven, JUnit 4.x, Spring and Swing. I plan to extend it into a multi tier bowling league tracking application using a SQL Database, Hibernate, and building multiple client and server versions using Wicket, Eclipse RCP, Eclipse RAP, Qooxdoo and JEE.

NSTL 3.0 released

Last Friday I finally managed to get the NSTL 3.0 out of the door. Although most of the features were mature and ready more than 3 Months ago, I never managed to finish the automatic build process for the 3.x branch. Well, until last Friday!

Besides being compiled the first release written using C#3.0 features such as LINQ and extension methods, it offers a lot of functionality to integrate the NSTL and its C++ background seamless into .NET. Actually, using the new extension methods lets you use .NET and NSTL collections and algorithms seamlessly. For instance, you can use .NET collections with iterators in algorithms:

using.NUnit.Framework;
using NStl.Linq;//Import the extensions

List<int> list = new List<int>(){0,1,2,3};
ListTIterator<int> it = Algorithm.Find(list.Begin(), list.End(), 2);
Assert.That(it, Is.Not.EqualTo(list.End());

By being able to pimp up .NET BCL objects with extension methods, I was able to deprecate a whole lot of NSTL containers like Vector<T>, DList<T> and bulky adapter utility methods like NStlUtil.Begin(..).

Furthermore this release provides extension methods for the NSTL itself, enabling a smooth transition to .NET collections:

using.NUnit.Framework;
using NStl.Linq;//Import the extensions

List<int> list = new List<int>(){0,1,2,3};
ListTIterator<int> it =
Algorithm.Find(list.Begin(), list.End(), 2);

//range contains 0,1
IEnumerable<int> range = list.Begin().AsEnumerable(it);

Last but not least you will find LINQ overloads for the Cast<T> operators to cast dictionaries.

How would Linq look like in Java (2)

After thinking a bit more about my recent attempt in bringing Linq to Java and looking deeper into the JGA library, one thing starts to bug me: The Queryable<T> interface lets you only adapt specific operations by overriding specific methods. Although this is a powerful possibility, it kind of prevents the main use case to extend the Linq mechanism: An overload for a specific type T of Iterable<T>. In .NET  this is possible through the extension method feature which does not exist in Java. You simple would provide a new method for your specific Iterable<YourType>.

Basically extension methods are static methods that get glued to a type by some compiler magic and look like instance methods. In Java you can use static methods without a qualifying type by importing it statically. They look and feel like global methods in C++. Since I have seen how the hamcrest matchers use this feature in JUnit 4.x to create a somewhat fluent syntax, I’m wondering if this can’t be used to create a Linq like syntax:

import static xox.foo.Queryable.*;//defines select, … 

UnaryFunction<Float, Integer> xform =…;
UnaryFunction<Integer, Boolean> lessThan5 = …;

Iterable<Integer> i2 = 
    from(collection, select(xform, where(lessThan5)));

With this design, a contributor would be able to provide his/her type specific overloaded implementation of the operation. It is really interesting to think about a possible implementation for this. How can the iterators be chained correctly, as the static methods are evaluated in the exact opposite order as the iterator chain is expected to work?

I first experimented passing a LinkedList<Iterable<T>> through the method chain, but it turned out that I had to know the specific Iterable type to link the iterators together. So I switched to provide a simple base class that implements Iterable<T>. It provides service to its inheritors to access the next and previous Iterable.

abstract class LinkedIterable<TIn, TOut> implements Iterable<TOut>{
    LinkedIterable<?, TIn> getPrev() {// … omitted } 
    LinkedIterable<TOut, ?> getNext(){// … omitted }
    public abstract Iterator<TOut> iterator();
}

A typical implementation would  use it like this:

class SelectIterable<TIn, TOut> extends LinkedIterable<TIn, TOut> {
    private final UnaryFunction<TIn, TOut> select;

    public SelectIterable(LinkedIterable<TOut, ?> next,
                          UnaryFunction<TIn, TOut> select) {
        super(next);
        this.select = select;
    }

    public Iterator<TOut> iterator() {
        return new SelectIterator<TIn, TOut>(super.getPrev().iterator(),
                                             select);
    }
}

This linked list liked construct gets passed through the method chain. Each method takes one as input,creates a specific new implementation, adds it to the front and returns the head of the list.

public static <TIn> LinkedIterable<TIn, TIn>
    where(UnaryFunction<TIn, Boolean> sel,
          LinkedIterable<TIn, ?> dec) {

        return new WhereIterable<TIn>(dec, sel);
}

The last method in the method chain to be called is the from function. It simply has to add the input range to the LinkedIterable<T> chain, run to the tail of the tail of the list and return it. As a LinkedIterable<T> is an Iterable<T>, this works seamless.

Now I just have to think about whether this syntax is better to read than my former approach. Especially for longer statements, all the methods and their braces might become unhandy:

Grouping managersBySalary = 
    from(employes, where(isManager, select(toManager, groupBy(salary)));

How would Linq look like in Java

After thinking a while about Linq for Java I started to experiment. My main driver was to find out how Linq would look like in Java. I started with a simple task: From a given range of floats convert ever item to an integer and take those that are less or equal four. In C# this would look like this:

IEnumerable<float> source =
    new []{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

IEnumerable<int> result =
    source.Select(x=>(int)x).Where(x=> x<= 4);

Java has neither delegates nor any lambda syntax, so statements like x=>x<=4 are not possible. So I decided to model the delegates as interfaces:

public interface UnaryFunction<Arg, Result> { 
    Result execute(Arg arg);
}

Linq statements basically are so called extension methods to the IEnumerable<T> and/or IQueryable<T> interface. The Java equivalent is the Iterable<T> interface. However, there is nothing like an extension method in java, so I had to fall back on the OO way of extension: inheritance.

public interface Queryable<T> extends Iterable<T>{
   <U> Queryable<U> select(UnaryFunction<T, U> select); 
   Queryable<T> where(UnaryFunction<T, Boolean> pred);
}

So if every operation returns a new Queryable<T> object, it would be possible to chain the calls very similar to the C# way.

This looked very promising! I decided that the real work should be done on the Iterator<T> level and implemented specific iterators for the select and where operations. Here is the SelectIterator as an example:

class SelectIterator<From, To> implements Iterator<To> {

    private final Iterator<From> inner;
    private final UnaryFunction<From, To> select;

    SelectIterator(Iterator<From> inner,
                          UnaryFunction<From, To> sel) {
        this.inner = inner;
        this.select = sel;
    }
    public boolean hasNext() {
        return inner.hasNext();
    } 
    public To next() {
        return select.execute(inner.next());
    } 
    public void remove() {
        throw new UnsupportedOperationException("");
    }
}

I implemented the Queryable<T> interface with an abstract base class and concrete anonymous inner classes:

abstract class QueryableImpl<T> implements Queryable<T> {  
   <U> Queryable<U> select(final UnaryFunction<T, U> s){
        return new QueryableImpl<U>(){
            @Override
            public Iterator<U> iterator() {
                return new SelectIterator(
                       QueryableImpl.this.iterator(), s
                                         );
            }
        };
    }

    // … and some more
    public abstract Iterator<T> iterator();
}

Last but not least I provided a static adaptor function to convert any Iterable<T> to a Queryable<T>:

static <T> Queryable<T> from(final Iterable<T> range) {
    return new QueryableImpl<T>() { 
        @Override
        public Iterator<T> iterator() {
            return range.iterator();
        }
    };
}

Putting all together allows you to write the following Java code:

Iterable<Float> src=
    Arrays.asList(0f, 1f, 2f, 3f, 4f, 5f, 6f, 7f, 8f);

UnaryFunction<Float, Integer> xform =
    new UnaryFunction<Float, Integer>() {
        public Integer execute(Float arg) {
            return (int) arg.floatValue();
        }
    };

UnaryFunction<Integer, Boolean> less5 =
    new UnaryFunction<Integer, Boolean>() {
        public Boolean execute(Integer arg) {
                return arg < 5;
        }
    };

Iterable<Integer> i2 = 
     from(src).select(xform).where(less5);

This looks pleasant close to the C# original!

Linq for Java

I started to work in Java and I’m really missing a comprehensive set of algorithms and data structures. The google collections in combination with the standard collection framework serves the data structure side very well and JGA looks promising for Algorithms. After all I don't want to do another port of the STL :-).

In the last months working with .NET I started to rely on Linq for my daily work and although it is quite reduced compared to the NSTL, I rarely missed a thing. I especially liked the fluent way that you can manipulate and transform the content any IEnumerable<T>.

I have found nothing comparable that is as fluent as Linq (JGA is close though) in the Java world and I start to wonder if it is possible to port at least some of the aspects?

My first try using Live Writer

Technorati Tags: Live Writer

I have kind of abandoned this blog for a while. Now I have some time and as I came over this Live Writer tool, I decided to try it out. I’m especially interested how easy it is to post source code using the wysiwyg features, because this gave me a hard time with the the build in web editor. So here is some code that was written in the editor:

int[] i = int[]{ 0, 1, 2 };
Algorithm. RandomShuffle(i.Begin(), i.End());

class AClass : BClass, ISomeInterface
{
    void AMethod(){}
}

Ok, it works. But How does it look? And here is some copy/paste code from Visual Studio:

using NUnit.Framework;
using TenPin.Bowling.Shared.Scorecard.Imp;
using NUnit.Framework.SyntaxHelpers;

namespace TenPin.Bowling.Shared.Scorecard.Test
{

    [TestFixture,
     Description("Basic test for the NullFrame class.")]
    public class NullFrameFixture
    {
        [Test]
        public void Ctor()
        {
            NullFrame frame = new NullFrame();

            Assert.That(frame.NextThrow, Is.EqualTo(0));
            Assert.That(frame.NextButOneThrow,
                        Is.EqualTo(0));
            Assert.That(frame.Score, Is.EqualTo(0));
        }
    }
}

Ok, so lets publish it!

Now I’m trying if I can edit the entry after posting. The Posted stuff looks great!