Wednesday, December 5, 2007

Using JMock with Scala

While working on the Java version of Jiva earlier this year, I used JMock pretty heavily to test all of the non-deterministic code that is integral to the workings of a Genetic Algorithm.

When I ported Jiva to Scala, I did not really know if I could continue to use JMock for my testing needs. As it turned out, JMock worked out very well for testing Scala code.

I could go in and try to explain some of the ways in which JMock is used within Jiva, but I'm afraid that will introduce a lot of Genetic Algorithms related terminology, and will potentially divert attention from the main point of this post. So I will instead demonstrate the usage of JMock with Scala via a very simple (and contrived) example. If you want to see JMock in action within Jiva, you are welcome to browse the Subversion repository for the project:
http://jiva-ng.googlecode.com/svn/trunk/src/test/scala/net/kogics/jiva/operators/

Back to the simple example...

Let's say we have a Class-under-test (Cut) in our code, and a Helper class that is used by Cut:

class Helper {
def help = "helpfulResult"
def helpWith(problem: String) = problem + " whatever help for String problem"
def helpWith(problem: int) = problem + " whatever help for int problem"
}

class Cut(helper: Helper) {
def doWork: String = {
helper.help + " processed"
}

def doWork(problem: String): String = {
helper.helpWith(problem) + " str processed"
}

def doWork(problem: int): String = {
helper.helpWith(problem) + " int processed"
}
}

The Helper class has three different helper methods with different signatures. Cut also has three methods that delegate to the corresponding Helper methods. The idea here is that we want to test the Cut class by mocking out the helper used by Cut.

Let's jump right into the Test class (you will need to enable Java generics support in Scala for this to work; more on that later):

import junit.framework.TestCase
import junit.framework.Assert._

import org.jmock.Mockery
import org.jmock.lib.legacy.ClassImposteriser
import net.kogics.jiva.util.mock.SExpectations
import org.jmock.Expectations._

class TestCut extends TestCase {

val context = new Mockery() {
{
// we want to be able to mock classes
setImposteriser(ClassImposteriser.INSTANCE);
}
};

def test1 = {
// create the mock
val helper = (context.mock(classOf[Helper])).asInstanceOf[Helper]

// setup mock return values
val noOpHelpReturn = "mockHelp"
val strHelpReturn = "mockHelp stringResult"
val intHelpReturn = "mockHelp intResult"

// set Expectations
context.checking(
new SExpectations {
one(helper).help
will(returnValue(noOpHelpReturn));

exactly(1).of(helper).helpWith(withArg(any(classOf[String])))
will(returnValue(strHelpReturn));

atLeast(1).of(helper).helpWith(withArg(any(classOf[int])))
will(returnValue(intHelpReturn));
})

// setup the class under test with the mock
val cut = new Cut(helper)


// exercise the class under test
// and verify results
val result = cut.doWork
assertEquals(result, noOpHelpReturn + " processed")

val result2 = cut.doWork("task")
assertEquals(result2, strHelpReturn + " str processed")

val result3 = cut.doWork(3)
assertEquals(result3, intHelpReturn + " int processed")

// make sure that the expectations on the mock were satisfied
context.assertIsSatisfied
}
}
This should be pretty straightforward for those of you who are familiar with JMock, except for a couple of things:
  • We set up Expectations using something called SExpectations.
  • We specify method paramater expectations using a method called withArg, as opposed to the more familiar with method provided by JMock
Both of these items are driven by the same reason: with is a reserved word in Scala. To get around this, I created a subclass of Expectations:

package net.kogics.jiva.util.mock;

import org.hamcrest.Matcher;
import org.jmock.Expectations;

public class SExpectations extends Expectations {
public <T> T withArg(Matcher<T> matcher) {
return super.with(matcher);
}
}
SExpectations provides a method called withArg that just calls into the standard with method provided within its superclass by JMock. So essentially this class functions as an adapter that allows JMock parameter matching to be used by code written in Scala.

Update: as pointed out by James Iry in his comment, we can solve this problem right within Scala-land, with the help of identifier quoting using backtics. Here's SExpectations in Scala:

class SExpectations extends Expectations {
def withArg[T](matcher: Matcher[T]): T = super.`with`(matcher)
}
This version of SExpectations can be used in the scala test code in exactly the same way as the Java version. Alternatively, the with method in Expectations can be called directly in the test code with the help of backticks. Both these approaches are shown in the sample code below:

// set Expectations
context.checking(
new SExpectations {
one(helper).help
will(returnValue(noOpHelpReturn));

exactly(1).of(helper).helpWith(withArg(any(classOf[String])))
will(returnValue(strHelpReturn));

atLeast(1).of(helper).helpWith(`with`(any(classOf[int])))
will(returnValue(intHelpReturn));
})
That's about it, actually. To reiterate: if you know how to use JMock (with Java), it should be pretty straightforward for you to start using it with Scala.

Some additional comments:
  • To work with JMock, you need to use Scala with the -Ygenerics and -target:jvm-1.5 options.
  • I used JUnit 3 for my Scala unit tests because the Scala Eclipse plugin does not quite support annotations. The standalone/command-line version of Scala supports annotations just fine, so it should be very possible to use JMock/JUnit 4 with Scala
  • I suppose I could have used MockObjectTestCase as a base class for my Tests. I just wanted to have more control over things as I worked through the Scala/JMock integration
  • I used the CGLib based Legacy ClassImposteriser because I needed to mock system classes for testing Jiva code
  • Versions used - Scala: 2.6.0, JMock: 2.4.0

Saturday, December 1, 2007

Announcing Jiva, a Genetic Algorithms Toolkit written in Scala

Earlier this week, I put out an initial release (version 0.1.5) of Jiva, a Genetic Algorithms (GA) toolkit that I have been working on.

Jiva is hosted on Google Code:
http://code.google.com/p/jiva-ng/

Jiva is written in Scala, a very powerful OO/Functional hybrid language that runs on the Java Platform:
http://www.scala-lang.org/

Jiva started out life earlier this year as a GA toolkit written in Java. I decided to port it to Scala because I figured that this might be a good way for me to (a) learn Scala, and (b) have some fun in the process. And I think this has turned out to be mostly true (especially the fun part!).

I should point out that despite its early-release status, Jiva is pretty functional (http://code.google.com/p/jiva-ng/wiki/FeatureSet ). If you are interested in playing with Genetic Algorthms, I encourage you to give Jiva a try. If you run into problems or have questions, please let me know.

Some quick links:
Download, Build and Run Jiva: http://code.google.com/p/jiva-ng/wiki/JivaQuickStart
Defining and Running GA Problems: http://code.google.com/p/jiva-ng/wiki/DefiningAndRunningGAProblems
Samples: http://code.google.com/p/jiva-ng/wiki/SampleProblems

Other tools used by Jiva:
Sant: for builds (http://code.google.com/p/sant/).
JMock: for testing of Scala code (http://www.jmock.org/).
New Scala Eclipse Plugin (http://lamp.epfl.ch/~mcdirmid/scala.update).
Much4.us: for Backlog/Task Management (http://much4.us/much4/).

Many thanks to the authors of these fine tools! I used them pretty heavily while working on Jiva, and they all held up very well and provided extremely useful functionality.

Sunday, July 1, 2007

Java Collections QuickRef

As of version 6.0, Java contains a large number of Collection classes. In this post, I have attempted to categorize a useful subset of these classes on the basis of general usage scenarios:

If you want to manage a Sequence of elements, and the sequence is:

  • Unordered, use a Set
    • If you do not need thread safety - use a HashSet
    • If you need thread safety:
      • Use a CopyOnWriteArraySet (under special conditions: small Set sizes and a very high read/write ratio)
      • Or wrap a HashSet with a lock (Collections.synchronizedSet() can be used for this)
  • Ordered:
    • If the order is External, use a List
      • If you do not need thread safety - use an ArrayList or LinkedList
      • If you need thread safety:
        • Use a CopyOnWriteArrayList (under special conditions: small List sizes and a very high read/write ratio)
        • Or wrap a List with a lock (Collections.synchronizedList() can be used for this)
    • If the order is Internal, use a SortedSet (an internal order is based on a 'natural' order relation defined on the elements of a container)
      • If you do not need thread safety - use a TreeSet
      • If you need thread safety - use a ConcurrentSkipListSet

If you want to manage a Mapping of keys to values, and the mapping needs to be:

  • Unordered, use a Map
    • If you do not need thread safety - use a HashMap
    • If you need thread safety - use a ConcurrentHashMap
  • Ordered (because you need to iterate through the container in a specified order)
    • If the order is External, use a Map
      • If you do not need thread safety - use a LinkedHashMap
      • If you need thread safety - wrap a LinkedHashMap with a lock (Collections.synchronizedMap() can be used for this)
    • If the order is Internal, use a SortedMap (an internal order is based on a 'natural' order relation defined on the elements of a container)
      • If you do not need thread safety - use a TreeMap
      • If you need thread safety - use a ConcurrentSkipListMap

If you want to Hold elements for future processing:

  • If you do not need thread safety, use a Queue or Deque
    • If you want:
      • FIFO/LIFO ordering - use an ArrayDeque
      • Priority based ordering - use a PriorityQueue
  • If you need thread safety in (a producer-consumer situation), use a BlockingQueue or BlockingDeque
    • If you want:
      • FIFO/LIFO ordering - use a LinkedBlockingQueue or LinkedBlockingDeque
      • Priority based ordering - use a PriorityBlockingQueue

The following table presents the Big-Oh time-complexity of common Collection operations for some of the core implementation classes:



add(e)
add(i,e)
contains(e)
get(i)/
get(key)
iterator
.next()
remove(0)
iterator
.remove()
ArrayList
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
LinkedList
O(1)
O(n)
O(n)
O(n)
O(1)
O(1)
O(1)
Hash table based
O(1)

O(1)
O(1)
O(h/n)

O(1)
Tree based
O(log n)

O(log n)
O(log n)
O(log n)

O(log n)
Skip list
based
O(log n)

O(log n)
O(log n)
O(1)

O(log n)


For detailed information on Java Collections - Java Generics and Collections, by Naftalin and Wadler - is a great resource.

Friday, June 22, 2007

Playing with Traits in Scala


Update: A more recent post on traits is also available

Traits in Scala provide a powerful tool for abstraction and class composition. Traits allow you to:
  • Define a type by specifying the signature of supported methods. This is similar to how interfaces work in Java.
  • Provide partial/full implementations that can be mixed-in to classes that use the trait. Why is this different from what abstract classes give you? The big difference is that abstract classes cannot be multiply extended from, while traits can.
This post starts to dig into how Scala traits work. I have used the following version of the Scala compiler for experimentation:
Scala compiler version 2.5.1-final -- (c) 2002-2007 LAMP/EPFL

Traits with only abstract methods get mapped to plain old interfaces by the Scala compiler. But when they contain implementations within non-abstract methods, traits start getting interesting. For such a trait (named, let us say - X), Scala generates two entities:
  • An interface called X with all the methods in the trait.
  • A class called X$class with static versions of all the non-abstract methods in the trait. These methods take one additional parameter (relative to the methods in the trait) of type X . Any code within a non-abstract method in the trait goes into the corresponding static method in X$class. Calls to other trait methods from within this code get translated to calls on the extra parameter of type X.
A class that mixes-in X ends up:
  • Implementing the interface X.
  • Delegating all the non-abstract methods of X to the static methods of X$class, passing itself (this) as a parameter.
So, mixing-in a trait provides (in Java terminology) a concise and powerful way to implement an interface and delegate its implementation to another class.

Let us see some of this in action. But first a detour through Java-land to look at a problem that can be nicely tackled with traits:

Let's say I have the following domain classes in a Java based system:
class Employee {
// etc
}

class Manager extends Employee {
List<Employee> directReports = new ArrayList<Employee>();

// etc
}
Now - let's say that I am given a new business requirement to implement:
whenever a new Employee starts reporting to a Manager, a specified list of departments need to be notified of this change.

Let's also say that I have these infrastructure classes available to me:
interface Observer<T> {
void onChange(Observable<T> source, T notificationData);
}

interface Observable<T> {
void addObserver(Observer<T> observer);
void removeObserver(Observer<T> observer);
void notifyObservers(T notificationData);
}

class ObservableImpl<T> implements Observable<T> {
// manages sequence of observers and notifications to these observers
}
What I really want to do at this point is to make the Manager class Observable. I can then fire a notification to an Observer whenever a direct report is added to the Manager; this Observer can notify the appropriate departments about the change.

Wouldn't it have been great if I could do this:
class Manager extends Employee, ObservableImpl<Employee> {

List<Employee> directReports = new ArrayList<Employee>();

public void addReport(Employee e) {
directReports.add(e);
notifyObservers(e);
}

// etc
}
Alas, we don't have multiple inheritence in Java. So I have to go ahead and implement the Observable interface within the Manager class - and delegate to an ObservableImpl:
class Manager extends Employee implements Observable<Employee> {

List<Employee> directReports = new ArrayList<Employee>();

Observable<Employee> observable = new ObservableImpl<Employee>();

public void addReport(Employee e) {
directReports.add(e);
notifyObservers(e);
}

// etc

// implement Observable methods by delegating to observable

public void notifyObservers(Employee notificationData) {
observable.notifyObservers(notificationData);
}

public void addObserver(Observer<Employee> observer) {
observable.addObserver(observer);
}

public void removeObserver(Observer<Employee> observer) {
observable.removeObserver(observer);
}
}
Traits in Scala give me a short-cut way of doing this. Here's the same functionality implemented in Scala:
trait Observer[T] {
def onChange(source: Observable[T], notificationData: T) : Unit
}

trait Observable[T] {
def addObserver(observer: Observer[T]) = {/*do the right thing*/}
def removeObserver(observer: Observer[T]) = {/*do the right thing*/}
def notifyObservers(notificationData: T) = {/*do the right thing*/}
}

class Employee {}

class Manager extends Employee with Observable[Employee] {

var directReports : List[Employee] = Nil

def addEmployee(employee: Employee) = {
directReports = employee :: directReports
notifyObservers(employee)
}
}
Notice how much more concise the Scala version is! All you need to do is to declare Manager as:
class Manager extends Employee with Observable[Employee]
and this mixes-in the functionality of the Observable trait.

Neat, huh?

I haven't yet talked about a very useful trait pattern - in which a trait defines an abstract method (which needs to be implemented by classes that mix in the trait), and then uses this method to provide higher level value-added methods. A future post will dig into this...

Monday, May 28, 2007

Efficient Concurrency

There are many ways to write thread-safe code for situations where concurrent readers and writers modify a shared data-structure:
  • Using locks: but this is very inefficient under high read-write load, especially because multiple readers interfere with each other.
  • Using read-write locks: this works better, because readers can run concurrently while no writes are taking place.
  • Using non-blocking algorithms based on the Compare-and-Swap (CAS) primitive: this works very well at low to moderate load levels, but makes the application code more complicated.
  • Using striping: where different sections of a large structure are protected with different locks (java.util.concurrent.ConcurrentHashMap uses this technique)
  • Using copy-on-write structures: where a new copy of a structure is made on every write. Reads do not interfere with each other. This works well if the number of reads are much, much higher than the number of writes.
  • Using immutable, functional structures: this is arguably the best way to manage concurrency. Reads do not interfere with each other. Writes need to acquire a lock for a very short time while replacing the root of the structure.

On to some real code. Here's an immutable/functional List that I recently implemented:
http://jiva.googlecode.com/svn/trunk/jiva/src/net/xofar/util/collection/immutable/List.java


The basic ideas behind the implementation of the above class are:
  • The List class is abstract.
  • List has two subclasses: Cons and Nil.
  • Nil stands for an empty list.
  • A Cons has two cells. One holds a value; the other points to the rest of the List. So a Cons essentially implements a singly-linked list.
  • The last entry in a list is a Nil. At this point in the list, the rest of the list is empty.
  • As a user of the List class, you never see Cons and Nil. You create a List using a factory method, and then use List operations to work on the list.
  • The core List operations are:
public List<T> prepend(T elem)
public T head();
public List<T> tail();
public boolean isEmpty();
public List<T> remove(T elem);

Some interesting things to note about these operations are:
  • The only way you can add something to a list is to prepend() to it. This returns a new list with the additional element. Threads that already hold a reference to the list continue to see the list as it was before the prepend.
  • head() and tail() give you a clean way to iterate through the list.
  • isEmpty() allows you to check for the end of the list.
  • As a concession to the need for modification, List supplies a remove(T elem) method. This gives you back a new list that does not contain the supplied element. The implementation of this method uses an optimized form of copy-on-write.
In a future post, I will talk about a good use for immutable/functional lists in a highly concurrent situation. These kinds of lists also lend themselves very well to algorithms that build their results in a bottom-up fashion (this will be the subject of yet another post).

Thursday, May 24, 2007

A FutureResult based on FutureTask

This morning, I was looking within the java.util.concurrent package for something in the spirit of the FutureResult class in Doug Lea's util.concurrent library. Surprisingly enough, I did not find anything (did I miss something?).

So I cooked up my own version:

public class FutureResult<V> {
volatile V result;

volatile Exception problem;

final FutureTask<V> resultSyncer;

public FutureResult() {
Callable<V> resultReturner = new Callable<V>() {
public V call() throws Exception {
if (problem != null) {
throw problem;
} else {
return result;
}
}
};
resultSyncer = new FutureTask<V>(resultReturner);
}

public void set(V result) {
this.result = result;
resultSyncer.run();
}

public void setException(Exception problem) {
this.problem = problem;
resultSyncer.run();
}

public V get() throws InterruptedException, ExecutionException {
return resultSyncer.get();
}
}


The latest code for this class is available at:
http://jiva.googlecode.com/svn/trunk/jiva/src/net/xofar/util/concurrent/FutureResult.java

Functionality of this nature can, of course, also be implemented with the help of plain-old wait/notify or condition variables. But this seemed like a neat way to accomplish what I wanted...