Sunday, September 25, 2011

kinna' stream attitude calling by-name my Clojure and my Scala

Hello, some very simple stuff - cross my heart - this week.

I recently decided to connect to the Project Euler site in order to practice on a regular base mathematics. The website proposes in order to begin some simple problems based on logic and solvable - most of them - by computer implementation.
I found the site problems fitting nicely in the context of execution of regular code kata. The idea being to (re)use some basic concepts of my favorite languages (java included, don't smile). These problems matter to me because some of them involve the use and calculus of prime numbers. Believe me or not I actually use prime numbers almost every day.
In addition to the well known usage of prime numbers in computer science, from a personal point of view, prime numbers are very suitable in writing tests when you find yourself challenging the binding of long properties using range of parameters run by JUnit Theories, but they also can provide unique output results when provided as input to algorithms processes.
Test takes between a fifth to a third of my coding time whether doing TDD or laying test harness around c... sorry legacy code. In order to generate prime numbers, you got to know how to identify them, but also how to generate them.

Why is it so ? Because as with natural integers, working with prime numbers means working with infinite suite, Yeah cool :)
 This is where working with a recursive suite is not really possible because of the nested aspect of methods calls. A function in charge of defining one prime number, then the other and so on would run ad infinitum.
What we would like would be running a little our prime number generator, then use its result in some processing , than run it again and so on. This approach breaks a little bit our habits of thinking in terms of function invoking other functions (or routines invoking subroutines). The astute functional programmer can see clearly now where to this talk is going.
A solution is in delaying the calls. This approach has been nicely exposed in the sicp book but also in the incredible Peter Henderson's book: Functional programming: Application and Implementation. You can also watch H. Abelson lecture 6A here.

Let's take a naive approach. Just imagine we want to generate on will the natural numbers starting from 1. Invoking the recursive:

(defn integers-from [n]
  (cons n [integers-from (+ n 1)]))

using

(first (integers-from 1))

would blow our stack because the function integers-from would call herself , evaluating first the (+ n 1) expression. Calling the function evaluating first (+ n is) is named a call by-value
What if we could delay this evaluation, promising to the function to evaluate herself if necessary (on demand). The implementation would look like

(defn integers-from [n]
  (cons n [(promised (integers-from (+ n 1)))]))

There is one simple way to delay this evaluation using a simple macro:

(defmacro promised [expression]
   `(fn [] ~expression))

The macro evaluation will lead to the creation of a closure holding the  integers-from expression. The example is contrived and only serves our purpose. When needed we could then force the delayed sequence to execute the following evaluation:

(defn fulfilled [promise]
    (promise))

A function getting the ten first natural integers would look like

(defn first-elements [k stream]
  (if (= 0 k)
    []
    (cons (first stream) (first-elements (dec k) (fulfilled (second stream))))))

The example works fine, try it.

algorithms.tools=> (first-elements 10 (integers-from 1))
(1 2 3 4 5 6 7 8 9 10)

but we would have to redefine all the nice higher order functions in Clojure in order to serve our purpose, explicitly forcing the fulfillment of promises .
The generated sequences are named Streams.

Well, Clojure embeds nicely this lazy evaluation mechanics (in clojure.core ) using the force and delay macros, but even more nicely providing the lazy-seq macro, in extenso producing implicitly lazy sequences. Using lazy sequences you don't even deal with force and delay. Quoting Stuart Halloway and Aaron Breda, you pay only for what you need (Programming Clojure 2nd edition is out and covers Clojure 1.3, just released by the way). 

The idea of delegating the evaluation of an expression passed to a function is named the call by-name in opposition to the call by-value.

But wait a minute. This means, that the expression should be evaluated each time it is explicitly used. Nope pals ! Creators of Clojure have inserted a memoization mechanic allowing the lazy sequence to cache the result on its very first invocation. So now we have call by-need invocation, the expression being evaluated once.
But beware. Although lazy sequences can be very valuable to delay the evaluation of big data structures, or very long I/O operations, there can be a memory saturation effect, specifically if you keep a reference to the head of the sequence.A kind of dog tail effect.

Using lazy sequences our number generator becomes:

(defn numbers-from [n]
  (lazy-seq (cons n (numbers-from (+ 1 n)))))

and you can try taking the first ten numbers

algorithms.tools=> (take 10 (numbers-from 1))
(1 2 3 4 5 6 7 8 9 10)

using the nice embedded higher order functions. What about my prime number list so I can solve my first problems ? We only need to create a stream of prime numbers:

(defn prime-stream
  ([] (lazy-seq (cons 2 (lazy-seq (cons 3 (prime-stream 5))))))
  ([from-prime]
    (lazy-seq
      (cons
        from-prime
        (prime-stream (next-prime from-prime))))))

I played with the function variable arity in Clojure and made the stream construction the result of a function instead of a var so no reference to the head is kept, in consequence no memory leak due to caching. Each time you need to manipulate it, you create it.
For reason of symmetry I kept the lazy-seq chain of calls in the empty signature declaration in order to create the beginning of the stream.
Making of (prime-stream 5) a lazy sequences is making the promise of calculating the upcoming prime numbers.
Good...almost.

Now I need to process the primes. My implementation is inspired from well known heuristics taking into consideration known facts like:
  • primes are not even
  • primes are certainly not dividable by five
  • every prime greater than 3 can be written in the form 6k+/-1
  • ...
These known heuristics save the day avoiding a brute force approach consisting in trying to divide each number N by numbers from 1 to N-1, which can become very expensive in terms of CPU consumption and very long versus the time of completion. The algorithm can be refined and its time of execution shortened. A first draft looks like :

(defn prime-form? [number]
  "All primes greater than 3 can be written in the form 6k+/-1."
  (let [sqrt (Math/floor (Math/sqrt number))]
    (loop [f 5 dividable false]
      (if (or (> f sqrt) dividable)
        (not dividable)
        (recur
          (+ f 6)
          (or
            (= 0 (mod number f))
            (= 0 (mod number (+ 2 f)))))))))

(defn prime? [number]
  "1 is not a prime.
  All primes except 2 are odd."
  (cond
    (even? number) false
    (= 0 (mod number 3)) false
    (prime-form? number) true
    :else false
    ))

(defn next-prime [from-prime]
  (loop [current (+ 2 from-prime)]
    (if (prime? current)
      current
      (recur (+ 2 current)))))

where
  • next-prime recursively explore the following numbers matching if they are prime (step 2 is because if we start from a prime, we can go from one odd number to the next odd number)
  • prime? takes in charge the match, first checking modularity versus 2 and 3, then delegating the congruence estimate to prime-from?
  • prime-from? challenges the congruence of the number versus 6k +/-1
Some checks in the prime? function are redundant with the next-prime function implementation, but my prime? function is a shared tool function.
Make a run with something like

(defn prime-at [position]
  (time
      (nth (prime-stream) position)))

and you will get :

algorithms.euler=> (prime-at 10001)
"Elapsed time: 201.724241 msecs"
104759

Congratulation you have solved one of the Project Euler problems. The following problems are harder, believe me :). So take a shot if you have time.

Coming to Scala, streams are implemented as... Stream objects and are nicely exposed by Joshua Suereth in his book. The nice thing with streams in Scala is that methods can be defined or redefined with almost whatever symbols you may like and the cons method is specifically pleasant:

  sealed trait PrimeSuite {
    @annotation.tailrec
    final def nextPrime(value: Long): Long = {
      if (isPrime(value + 2)) (value + 2)
      else nextPrime(value + 2)
    }
  }

  def suite: Stream[Long] = new PrimeSuite {
    def f(value: Long): Stream[Long] = value#::f(nextPrime(value))
    def create: Stream[Long] = cons(2, cons(3, f(5)))
  }.create

The sealed trait exists because of experiments I am achieving. The tail recursive optimization can be marked with the @tail.recur annotation. So far, so good, the other methods are carbon copy of the Clojure code:

 def isPrimeForm(value: Long): Boolean = {
    val square = floor(sqrt(value));
    def findPrime(from: Long = 5): Boolean ={
      from match {
        case current if current > square => true
        case current if ((value % current) == 0) => false
        case current if ((value % (current + 2)) == 0) => false
        case _  => findPrime(from + 6)
      }
    }
    findPrime()
  }

  def isPrime(value: Long): Boolean = {
    value match {
      case 2 => true
      case 3 => true
      case even if ((even & 1) == 0) => false
      case odd if ((odd % 3) == 0) => false
      case _ => isPrimeForm(value)
    }
  }


although this time I preferred using the idiomatic match/case pattern of Scala. The Stream is guaranteed is to cache the values using some internal mechanics. And that is nice because having a look at the #:: method I discovered this:


class ConsWrapper[A](tl: => Stream[A]) {
    def #::(hd: A): Stream[A] = cons(hd, tl)
    def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
  }

This little exploration reveals the Scala form expected to reference a call by-name parameter:

=> Stream[A]

only invoked when explicitly used. That is slightly different from expecting

() => Stream[A]

where the expression is supposed to have been evaluated before the method call. (Nice and clean demo in Martin Odersky's book) Playing a little bit with the call by-name in Scala lead me to confirm that called by-name parameters should always be free from side effect.

Why is it so ? Take the following ugly example:

  def f(assert: => Boolean) {
    println(assert)
    Thread.sleep(5000)
    println(assert)
  }

  def firstShot() {
    var item = 3
    val runner = new Runnable {
      def run() {
        f({
          print("asserting...");
          5 > item
        })
      }
    }

    val thread = new Thread(runner)
    thread.start()
    thread.join()
  }

Basically I fire a runnable in charge of calling by name the method f, passing through a closure, closing onto the variable item (never use mutable values, never). The standard output provides me with:

asserting...true
asserting...true

so in essence the method is invoked twice. Consider now:

 def f(assert: => Boolean) {
    println(assert)
    Thread.sleep(5000)
    println(assert)
  }

 def secondShot() {
    var item = 3
    val runner = new Runnable {
      def run() {
        f({
          print("asserting...");
          5 > item
        })
      }
    }

    val thread = new Thread(runner)
    thread.start()
    Thread.sleep(1000)
    item = 7
    thread.join()
  }

leading to a show stopping side effect:

asserting...true
asserting...false

I volunteerly changed the mutable value and came to an unstable state. And yes indeed the call by-name parameter has been invoked twice, meanwhile the mutable value was altered. We can simulate a call by-need effect using a lazy value:

 def thirdShot() {
    var item = 3

    def f(assert: => Boolean) {
      lazy val asserted = assert
      println(asserted)
      Thread.sleep(5000)
      println(asserted)
    }

    val runner = new Runnable {
      def run() {
        f({
          print("asserting...");
          5 > item
        })
      }
    }

    val thread = new Thread(runner)
    thread.start()
    Thread.sleep(1000)
    item = 7
    thread.join()
  }

which output looks like:

asserting...true
true

Call by-need effect is nice by the way and spare resources so you should always use it and never (never) use mutable variable nor fields.

 Well, I want to understand finger trees so I leave you

Be seeing you :) !!!

Sunday, September 18, 2011

Ruling my expectations with Junit

For once no Clojure, nor Scala in this post.There is no whining in saying that as a java developer by day, I too rarely have the opportunity to learn or teach something, because of the attitude of diletante people more concerned by "making a career" than committing into their developer's job. But last friday a nice thing happened. I went lucky playing with Junit rules.

Let us settle the environment. I am working on the worst project I have ever been working on. By itself the project is very small (less than 70k lines of code).
It does clearly break all the rules of decent architecture reasoning in any way, its internals being deeply rotten by terrible missuses of the already invasive and useless Spring framework, but also tons of other under used dependencies (typically Apache open sources).
I won't debate over the use of Spring because I don't want this blog to be polluted by frameworks advocates sentences without interest. I am an old dog paid for using his brain rather than pressing dumbly on buttons like a monkey. I never had the need to use anything but standards API. I certainly do not need a jackhammer framework invading my perm gen to pass parameters to a constructor. End of debate.

As a TDD advocate, armed with Martin Fowler and Keriewsky books on refactoring, but also Michael Feathers and Meszaros writings, I patiently implement or fix the modules using Junit. Junit is indeed a (really small) framework per se, but above all Junit is a tool (which Spring is not). Junit is a carpenter chisel compared to the cited jackhammer.
One impact of the unfortunate pervasive injection is the difficulty in testing classes, sometime hosting nearly twenty injections. One other common problem dealing with legacy code, is exception testing and resources freeing. These two aspects rarely live in perfect harmony.

I chose to solve the invasive injection problem using (alas) mocks, accessible via seam points, presented by M. Feathers in his book As far as the exceptions are concerned Junit provides us with helpful classes and annotations.

Let see through an example. The following code reproduces a typical recurring pattern in the application but of course I changed names in order not to face copyright problems (who would want to copyright that anyway :)) :

public void invoke() throws GenericException{
    try {
//Do some stuff in database
       if (dbError()) {
           logSomething("dumb");
           throw new TechnicalException(0x01, "something happened");
       }
    } catch (final TechnicalException exception) {
        throw new GenericException(0x10, "someErrorMessage");
    } finally {
        freeReesources();
    }
}

This recurring pattern mixes technical exceptions with generic exceptions, expects some resources freeing, and also some logging. Of course there is also unconventional error code attached to the exceptions.
The translation from one error code to another is one of the strangest things I have ever witnessed. I cannot describe they purpose but take for granted that as a matter of fact an exception in this system is not passive and fires action on creation (yes, who can believe it) 

All the logged information must be tested, and at least the exiting exception code must also be tested before refactoring. It is vital too, to check that resources are released and messages are logged. (The content matters, guess why ;)) 

 The complete demo code I wrote for the purpose of testing, looks like:

 
public final class Controller {
    private boolean resourcesWereFreed;
    private String loggedMessage;

    public void invoke() throws GenericException{
        try {
           if (dbError()) {
               logSomething("dumb");
               throw new TechnicalException(0x01, "something happened");
           }
        } catch (final TechnicalException exception) {
            throw new GenericException(0x10, "someErrorMessage");
        } finally {
            freeReesources();
        }
    }

    private void logSomething(final String dumb) {
        loggedMessage = dumb;
    }

    private boolean dbError() {
        return true;
    }

    private void freeReesources() {
        resourcesWereFreed = true;
    }

    public boolean hasReleasedResources() {
        return resourcesWereFreed;
    }

    public String loggedMessage() {
        return loggedMessage;
    }
}


where I introduced spying flag methods to checks which other methods were called. In real life I found my self needing to create various self tests, God I hate that. The code for the exceptions :

 

public class GenericException extends Exception{
    private int code;

    public GenericException() {
        super();
    }

    public GenericException(final int codeValue, final String message) {
        super(message);
        code = codeValue;
    }

    public int getCodeErreur() {
        return code;
    }
}

public final class TechnicalException extends GenericException{
    public TechnicalException() {
        super();
    }

    public TechnicalException(final int code, final String message) {
        super(code, message);
    }

}


A first approach to challenge the exception throwing in Junit - using the @Test(expected= ...) facility -looks like:

@Test(expected = GenericException.class)
    public void doStuff_WithFailingInvocation_ShouldThrowException() throws GenericException {
        controller().invoke();
    }
This first level approach allows me to only check my exception type. Try the following:

 
@Test(expected = GenericException.class)
    public void doStuff_WithFailingInvocation_ShouldThrowException() throws GenericException {
        controller().invoke();
        assertThat(true, is(false));
        trace("I can't do anything there... :(");
    }


Surprise, test passes although the exception is being thrown. 
Naturally, the code following the challenge is never invoked. 
 We have two problems now. 

We would like to test more on the exception, that these damned resources have been released and that messages have been logged. 

 The first point can be cleared, sort of. Here come the Junit rules. I encourage you to hit Junit rules on Google and you will find deeper explanations than mine (here and there for example). Basically, Junit rules provide you with a nice way to intercept the call to your test,  using a decorating class named a Statement. The statements are ruled, meaning that a rule implementation can choose on which test to apply the statement. 
In the previous links, Dale H. Emery provides a nice detailed explanation of the the sequence of events during the execution of ruled tests. See the order of event as a kind of @InvokeAround like in J2EE 5/6. 

The Junit framework already provides default rules so to create n'delete temporary folders or -guess what - to check thrown expectations. Good. Let's try it then.


    @Rule
    public ExpectedException expected = ExpectedException .none();

    @Test
    public void doStuff_WithFailingInvocation_ShouldThrowExceptionWithCorrectMessage() throws GenericException {
        expected(GenericException.class, withErrorMessage());
        controller().invoke();
        assertThat(true, is(false));
        trace("I can't do anything there... :(");
    }

   private String withErrorMessage() {
        return "someErrorMessage";
    }

   private void expected(final Class<GenericException> genericExceptionClass, final String message) {
        expected.expect(genericExceptionClass);
        expected.expectMessage(is(equalTo(message)));
    }


I used an ExpectedException instance. At the very start I declare an empty expectation, that will be applied to all my tests. An empty expectation expects...nothing. If I do not want to challenge an exception, the behaviour is crystal clear for the test: nothing gets matched. 

 Before firing the tests per se I set my rule expectations using standard Junit matchers (such an elegant DSL...). The ExpectedException definition allows me to challenge both the class and the message content. So far so good, but an exception is still raised and no check is applied onto the system under test (SUT) afterwards. The test is still green while we willingly declared a wrong assertion. 

 Hum, what about making our own rule? 
What do we want? Some contract that would check at least that the resources are freed, something like that:

 
@Rule
public Contract contract = contract().postCheck(resourcesHaveBeenReleased());

But we should be ask for additional checking like:

withContract().postCheck(messageWasLogged());

I propose you a solution implementing the TestRule interface, the MethodRule interface being deprecated as of the 4.9 version. No copyright, till I did the job for the guys in 4.8 using MethodRule ;) :

import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.Callable;

import org.junit.rules.TestRule;
import org.junit.runner.Description;
import org.junit.runners.model.Statement;

public final class Contract implements TestRule {
    private final List<Callable>?<> list;

    private Contract() {
        super();
        list = new LinkedList<>();
    }

    @Override
    public Statement apply(final Statement base, final Description description) {
        return contractedStatement(base);
    }

    private Statement contractedStatement(final Statement base) {
        return new ContractedStatement(base);
    }

    private void postCheck() throws Exception {
        for (final Callable<?> callable : postConditions()) {
            callable.call();
        }
    }

    public Contract postCheck(final Callable<?> callable) {
        postConditions().add(callable);
        return this;
    }

    private List<Callable<?>> postConditions() {
        assert list != null;
        return list;
    }

    public static Contract contract() {
        return new Contract();
    }

    private class ContractedStatement extends Statement {
        private final Statement base;

        public ContractedStatement(final Statement decorated) {
            base = decorated;
        }

        @Override
        public void evaluate() throws Throwable {
            try {
                base().evaluate();
            } finally {
                withContract().postCheck();
            }
        }

        private Contract withContract() {
            return Contract.this;
        }

        private Statement base() {
            return base;
        }
    }
}


The apply method takes as input parameter a statement in charge of invoking the underlaying test method. This base statement is then wrapped by a ContractedStatement that will run the action throwing a Throwable if anything goes wrong. 
The contracted statement always executes the postChecked method hosted by the Contract. In essence postCheck will execute a set of registered blocks of code to apply. 
Unfortunately this is not Scala we are working with, so the Java abstraction that looks like most to a block of code is a Callable, as being able to throw an exception if necessary, and returning some value (although we do not need this feature). 
 From the test all becomes clearer. We only have to create callables on demand, each callable wrapping the expected assertions:

 

 @Rule
   public Contract contract = contract().postCheck(resourcesHaveBeenReleased());


   @Test
    public void doStuff_WithFailingInvocation_ShouldThrowExceptionAndReleaseResources() throws GenericException {
        expected(GenericException.class, withErrorMessage());
        withContract().postCheck(messageWasLogged());
        controller().invoke();
    }


   private Callable<?> messageWasLogged() {
        return new Callable<Object>() {
            public Object call() throws Exception {
                assertThat(controller().loggedMessage(), is(equalTo("dumb")));
                trace("I am there too");
                return null;
            }
        };
    }

    private Callable<?> resourcesHaveBeenReleased() {
        return new Callable<Object>() {
            public Object call() throws Exception {
                assertThat(controller().hasReleasedResources(), is(true));
                trace("Hey I can test that now");
                return null;
            }
        };
    }


Tests are green and you can now insert a wrong assertion. It will fail. 

 My last wish was testing the code value of the raised exception. The code shape for this scenario could be very close to the code shape of the ExpectedException one:

 

 @Test
    public void doStuff_WithFailingInvocation_ShouldThrowGenericExceptionAndReleaseResources() throws GenericException {
        expected(GenericException.class, code(), withErrorMessage());
        withContract().postCheck(messageWasLogged());
        controller().invoke();
    }

    private int code() {
        return 0x10;
    }

    private Contract withContract() {
        return contract;
    }

    private void expected(final Class<GenericException> genericExceptionClass, final int code, final String message) {
        expectedGeneric.expect(is(equalTo(code)), genericExceptionClass, is(equalTo(message)));
    }

    private String withErrorMessage() {
        return "someErrorMessage";
    }

This step, I decided, to make it as a hack of the ExpectedException class creating my own ExpectedGenericException. This test helper would then be specific to the family of tests in my business layer as it targets the whole hierarchy of business/technical exceptions rooted by the same GenericException. The Rule class is the ExpectedGenericException:

 
import com.promindis.sample.GenericException;
import org.hamcrest.Matcher;
import org.hamcrest.StringDescription;
import org.junit.rules.TestRule;
import org.junit.runners.model.Statement;

import static org.hamcrest.CoreMatchers.instanceOf;
import static org.junit.Assert.assertThat;
import static org.junit.matchers.JUnitMatchers.both;
 
 
public final class ExpectedGenericException implements TestRule {
    private Matcher<Object> matcher;

    private ExpectedGenericException() {
        super();
    }

    @Override
    public Statement apply(final Statement base, final org.junit.runner.Description description) {
        return interceptedStatmentBase(base);
    }

    private Statement interceptedStatmentBase(final Statement base) {
        return new Statement() {
            @Override
            public void evaluate() throws Throwable {
                try {
                    base.evaluate();
                } catch (final GenericException e) {
                    assertThat(e, matcher());
                    return;
                }
                if (matcher() != null)
                    throw new AssertionError("Expected exception to comply to was a Generic exception" + StringDescription.toString(matcher()));
            }

        };
    }


    public static ExpectedGenericException expected() {
        return new ExpectedGenericException();
    }


    public <E extends GenericException> void expect(final Matcher<Integer> matching, final Class<E> exceptionClass, final Matcher<String> message) {
       expect(instanceOf(exceptionClass));
        if (message != null)
            expect(hasMessage(message));
        expect(hasCode(matching));
    }



    public void expect(final Matcher<? extends Object> matching) {
        if (matcher == null)
            matcher= (Matcher<Object>)matching;
        else
            matcher= both(matcher).and(matching);
    }


    private Matcher<GenericException> hasCode(final Matcher<Integer> matcher) {
        return new GenericExceptionCodeMatcher(matcher);
    }

    private Matcher<GenericException> hasMessage(final Matcher<String> matcher) {
		return new GenericExceptionMessageMatcher(matcher);
	}

    private Matcher<Object> matcher() {
        return matcher;
    }


As in our previous example the apply method offers a possible entry point where, after decorating the incoming base statement with our own statement, we resend it. Our stament will basically filter a generic exception raise and apply defined Junit matchers. 
The matchers can be registered through the invocation of the expected method from the testing class. The expect method, that reuses the hamcrest both method, chains all the matchers in charge of validating the exception content. We there reuse the code pattern of the default ExpectedException in order to merge the differente matching expectations.

 
public void expect(final Matcher<? extends Object> matching) {
        if (matcher == null)
            matcher= (Matcher<Object>)matching;
        else
            matcher= both(matcher).and(matching);
    }



We basically match a class type, a message content, then a code value. In order to gracefully merge the matchers in a chain of matchers we also decorates each of them into package scoped instances of the classes GenericExceptionMessageMatcher and GenericExceptionCodeMatcher:

 
import com.promindis.sample.GenericException;
import org.hamcrest.Description;
import org.hamcrest.Matcher;
import org.junit.internal.matchers.TypeSafeMatcher;

final class GenericExceptionCodeMatcher extends TypeSafeMatcher<GenericException> {
    private final Matcher<Integer> matcher;

    public GenericExceptionCodeMatcher(final Matcher<Integer> matcher) {
        this.matcher = matcher;
    }

    public void describeTo(final Description description) {
        description.appendText("exception with code ");
        description.appendDescriptionOf(matcher);
    }

    @Override
    public boolean matchesSafely(final GenericException item) {
        return matcher.matches(item.getCodeErreur());
    }
}

//And

import com.promindis.sample.GenericException;
import org.hamcrest.Description;
import org.hamcrest.Matcher;
import org.junit.internal.matchers.TypeSafeMatcher;

final class GenericExceptionMessageMatcher extends TypeSafeMatcher<GenericException> {
    private final Matcher<String> matcher;

    public GenericExceptionMessageMatcher(final Matcher<String> matcher) {
        this.matcher = matcher;
    }

    public void describeTo(final Description description) {
        description.appendText("exception with message ");
        description.appendDescriptionOf(matcher);
    }

    @Override
    public boolean matchesSafely(final GenericException item) {
        return matcher.matches(item.getMessage());
    }
}

so we can add our own descriptions or whatever necessary. 

Let resist to the attempt of "generifying" more than necessary the wrappers and making our ExpectedGenericException more... generic. We are not building a framework. More complexity is not needed (YAGNI principle) 
Test green. We are done ! 

 Soon we will talk again about Clojure and Scala I hope, so be seeing you !!! :)

Sunday, September 11, 2011

Eight Queens in Clojure Land


Hello again. When time flies and you find yourself with your hands full of books and article to read, finding and writing about some subject can become very hard. In such times I try to look in my bag of things I-always-wanted-to-do-but-never-took-time-to-do (you can breath) . I had a little bit more than two hours to kill yesterday before digging again in Clojure in Action and the new chapter edited by Joshua Suereth in Scala in Depth.
There remain few basic algorithmic problems I want to tackle before switching to distributed algorithms. One of them is the famous eight queen problem. Fortunately Martin Odersky presented a Scala version in his book, in order to expose a nice use of the comprehensions in Scala. So, unfortunately for me Scala was not an option to implement a solution.

I wanted it recursive and having committed myself into the study of Clojure for a few months now, the language was an option. Although I am not at the level of expert Lisp and Clojure developers I took the liberty to try my very first personal implementation.
The result is not the result I expected, but as usual any critic will be welcomed: although being french I do like learning from critics as from failures and retries (really need to embrace a new nationality). In conclusion a very brief and relaxing exercise today.

  As a reminder you can get details about the the eight queen puzzle there. Basically our purpose is to dispatch eight queens on a chessboard so that, none of them can attack the others. Applying the basic rules of chess game, two queens cannot be located on the same rows, nor columns nor diagonals. Numerous readers must have stopped there finding that too basic.
For the others let's continue. Indulge me and consider that it would more elegant to provide a solution dealing with the dispatch of n queens on a n sized chessboard (the others should not have left). In order to solve the problem I adopted the same attitude as when solving the Hanoi Tower problem.
Let us consider the problem partially solved - one say - on a four sized chessboard. At step 3, my only partial solutions can be expressed as list of list of ...list:

(   ((3 3) (2 1) (1 4) ()) 
    ((3 4) (2 1) (1 3) ()) 
    ((3 1) (2 4) (1 2) ())
    ((3 2) (2 4) (1 1) ()))

A tuple represents a queen position.
The adopted rules being to index the upper left corner as (1 1) and the lower right as (4 4), the car of the list being the row number and the cdr being the column number.
A list of positions is a partial solution to be completed
And the list of list of list (:)) is the list of solutions.
 No big deal there.

 The solutions are to be read from left to right, the first element being the most recent position found. The annoying empty list at the beginning of the solution is due to my choice of starting from no solution. All I have to do is considering all the possible positions on the fourth row and choose the matching ones that would lead to acceptable solution. The scenario is applicable whatever is the step index value in a n sized chessboard. In the four cell chessboard the two solutions are:

One should notice that the solutions are symmetric and there might be interesting exercises to implement in order to reduce the number of solution to the reduced forms by symmetry considerations.

Considering the eight queen problem we are to find 92 solutions.

 I usually do TDD. And I will present you the unitary tests. But I have to confess that I did not start like that. You generally start implementing some algorithm in pseudo code before writing anything, but the conciseness of Lisp languages (they are homoiconic languages) makes them natural candidates to write the algorithm as-is.

I wrote what came in mind and backwardly tested my methods one after the other adjusting the first shot. Worked nice for me: I worked both with IntelliJ and Leinengen, with the following project.clj configuration:
(defproject states "1.0"
  :description "N-Queens"
  :dependencies [[org.clojure/clojure "1.3.0-beta2"]
  			     [org.clojure/clojure-contrib "1.2.0"]])
although the clojure-contrib is not needed. Just in case ;) .

 The entry point of my algorithm is where I set my intention to match the different positions for a queen at step k , within a n dimension chessboard. Using Abelson and Sussman wishful programming approach lead me to:
(ns algorithms.n-queens)

;.......

(defn place-queens [at-step within-boundaries]
    (if (= 0 at-step)
      (list (list (list)))
      (let [solutions (place-queens (dec at-step) within-boundaries)
             for-positions (possible-positions at-step within-boundaries)]
        (mapcat (possible-solutions for-positions) solutions))))

This is where the little annoying empty list comes from.
As Martin Odersky, I define my no-solution expression as an empty list. In Clojure the empty list is not a bottom form marking the end of a list like Nil. I learned that during the exercise :), but too late.

At the very top we find the working namespace definition (algorithms.n-queens), so my file is located under some algorithms directory and the code implemented in a n-queens.clj file.
Starting, literally at step 0, I do return a (list(list(list))), otherwise I define my set of solutions as the solutions recursively found for a decremented number of steps and the range of positions to be tested.
I then return a list of the possible new solutions as a result from comparing all possible positions versus already found solutions.
 The easier function to be tested is possible-positions in charge to extract all the possible positions in the row at-step. Driven by test we start with something like:

(ns test.algorithms.n-queens-specs
  (:use algorithms.n-queens)
  (:use clojure.test))

(deftest possible-positions-at-defined-step-should-be-generated
    (is (= (list '(1 1) '(1 2)) (possible-positions 1 2))))
Provided at the top is the namespace definition including the clojure.test namespace. At step 1, in a two dimensional chessboard I expect ((1 1) (1 2)) as possible positions. The matching implementation is:
(defn possible-positions [at-row boundary]
  (map #(list at-row %)(range 1 (inc boundary))))

We use a map higher order function in order to apply a #(list at-row %) lambda function taking as parameter all the range from 1 to the boundary limit (upper limit is exclusive so we have to increment the boundary value)
 In the placed-queens method the (possible-solutions for-positions) is surrounded by parenthesis because I decided to use a closure. I found more natural to close onto the set of possible positions, and then find a match for each possible solution. That 's the purpose of
(mapcat (possible-solutions for-positions) solutions)
mapcat allowing me to slice a list of list of solutions into recursive list of solution, and I must confess once more that I found it using TDD. No magic, just the good effect of testing. A typical test scenario for the possible-solutions implementation would be:
 
(deftest possible-solutions-with-positions-for-known-solution-should-complete-solution
  (let [for-positions (possible-positions 4 4)
          from-solution (list '(3 1) '(2 4) '(1,2))]
    (is (= (list (list '(4 3) '(3 1) '(2 4) '(1,2)))
          ((possible-solutions for-positions) from-solution)))))
where starting at row 4 with the already found partial solution ( (3 1) (2 4) (1 2)) we would find ((4 3) (3 1) (2 4) (1 2)) Of course keep warm the test. It won't pass, we do not have the function yet. My function definition can be :
(defn matching [in-solution]
  (fn [position]
      (every? (safe? position) in-solution)))

(defn safe [positions matching-solution]
  (filter #(matching-solution %) positions))

(defn possible-solutions [positions]
  (fn [solution]
    (reduce #(cons (cons %2  solution) %1) nil
      (safe positions (matching solution)))))

with the help of matching and the help of safe.
The expression   (matching solution) defines yet another closure which captures a solution and allows the challenge of a possible position versus all the positions of the captured solution.
This closure is reused in the safe function to filter the possible positions matching, in effect the partial solution. From these filtered positions combined to the en-closed solution we will build new solutions. Take your time, higher order functions and their use is not always simple.

 The function possible-solutions rebuild then a list of new solutions from nil, each new solution appending a filtered position to the en-closed solution. From each solution we can have multiple possible new solutions. We return a list of lists (solutions) of ...lists (positions). The bunch of tests used to qualify this approach are:
(deftest matching-solution-with-matching-position-should-return-true
  (let [solution (list '(3 1) '(2 4) '(1,2))]
    (is (true? ((matching solution) '(4 3))))))

(deftest matching-solution-with-un-matching-position-should-return-false
  (let [solution (list '(3 1) '(2 4) '(1,2))]
    (is (false? ((matching solution) '(4 2))))))

(deftest safe-positions-with-matching-solution-should-return-valid-positions
  (is (= (list '(4 3)) (safe (possible-positions 4 4) (matching (list '(3 1) '(2 4) '(1,2)))))))
trying effective different scenarii on four dimension chessboards...But you can't test'em till the safe? function invoked from matching is implemented.

 The safe function basically creates yet (yet) another closure, closing onto a new possible position. This closure will test all the existing positions in a solution in order to ensure that the enclosed position can be appended to form a new solution. I need tests to challenge the safe? function:
(deftest position-safe-for-not-safe-position-should-return-false
  (is (false? ((safe? '(1 1)) '(2 1))))
  (is (false? ((safe? '(1 1)) '(1 2))))
  (is (false? ((safe? '(1 1)) '(2 2)))))

(deftest position-safe-for-empty-position-should-return-true
  (is (true? ((safe? '(1 1)) '(3 2)))))

(deftest position-safe-for-safe-position-should-return-true
  (is (true? ((safe? '(1 1)) '()))))
You will notice I have also tested the empty starting solution. So, Our solution comes to be
(defn on-diagonal [position previous-position]
   (= (Math/abs (- (second position) (second previous-position)))
              (Math/abs (- (first position) (first previous-position)))))

(defn safe? [position]
  (fn [previous-position]
  (or
    (empty? previous-position)
    (and
      (not (= (first position) (first previous-position)))
      (not (= (second position) (second previous-position)))
      (not (on-diagonal position previous-position))))))
As a summary the whole program is:
(ns algorithms.n-queens)

(defn possible-positions [at-row boundary]
  (map #(list at-row %)(range 1 (inc boundary))))

(defn on-diagonal [position previous-position]
   (= (Math/abs (- (second position) (second previous-position)))
              (Math/abs (- (first position) (first previous-position)))))

(defn safe? [position]
  (fn [previous-position]
  (or
    (empty? previous-position)
    (and
      (not (= (first position) (first previous-position)))
      (not (= (second position) (second previous-position)))
      (not (on-diagonal position previous-position))))))

(defn matching [in-solution]
  (fn [position]
      (every? (safe? position) in-solution)))

(defn safe [positions matching-solution]
  (filter #(matching-solution %) positions))

(defn possible-solutions [positions]
  (fn [solution]
    (reduce #(cons (cons %2  solution) %1) nil
      (safe positions (matching solution)))))

(defn place-queens [at-step within-boundaries]
    (if (= 0 at-step)
      (list (list (list)))
      (let [solutions (place-queens (dec at-step) within-boundaries)
             for-positions (possible-positions at-step within-boundaries)]
        (mapcat (possible-solutions for-positions) solutions))))

(defn placed-queens[for-number]
  (time
    (place-queens for-number for-number)))
Here we are with our Eight Queens. Too many books to read, so be seeing you !!! :)