Saturday, December 24, 2011

Where my Scala makes my Zipper Optional

Houdy. 

As told in previous posts, I have read Learn You a Haskell for a great good. The book content, in addition to be humorous and filled with the author drawn-by-hand pictures, is worth while reading for people - who like me - embraced functional programming a few months ago. 
The reading took some time, and in some sense started changing my way of coding. Do not misunderstand me. As a Java developer by day I have no other choice than coding in a Object Oriented approach - as far as Java permits me - and do not specifically reject this approach. I simply found some answers to technical questions and more personal way of looking at code. 

Embracing a new paradigm leverages your ability to constantly make your approach of coding evolves. It is a matter of personal opinion, but I want my own code to evolve, always. Learn you a Haskell was a first shot, and at this very moment Programming Haskell and the Craft of functional programming lays beside me on the desktop while my pdf ordered copy of Real World Haskell patiently wait on my SSD USB key. 

For those who know me, I love both Clojure and Scala, and this is not just an excuse to buy fancy geeky t shirts, I mean it . Practicing so long Haskell, while not doing Scala has been a burden. At some point I had to come back to Scala doing a simple exercise of my own in order to restart coding in the language. I needed a small kata, nothing specific in particular in order to get in Scala again, even a single class. Unfortunately, without current position nor pet project to tease my mind, the ideas were not easy to find. I found amusing considering the last chapter of Learn you a Haskell and started coding a very small zipper. 
Today post is a just a very small rambling on coming back to Scala and trying to feel the code differently.  

In 1997 Gerard Huet from INRIA (even me sometimes have french references), published an interesting article on the Zipper, as a simple approach to tree navigation and modification. Instead of considering a tree as a global context, one can find suitable to focus on a node to work on, to navigate from, or to change a local information to, like some data bound to the node. And this is it . 
A zipper is mainly a magnifying glass focusing a specific branch of a piece of tree bound to a node. In order for us to move locally up, right, left from this branch after manipulating it, we just need to remember the little world around us and the path taken to get to this position (frequently the path issued from the root).
Supposedly having to modify some data bound to nodes - no so far one from another-, having the ability to move from node to node, remembering where we come from is a real bless. No need to seek out for each node from the root each time we want to modify it: let's fire a bunch of moving commands. Using Gerard Huet own words, going down and up through the tree is like zipping and unzipping a piece of cloth, aka the name.
As far as trees are concerned , knowing the world around our branch means knowing the owning node and the other tree branches.

Everything starts with a tree definition. 
After 3 months of Haskell, I could no see a tree definition as class template defining object grapes but as a union of types (You must trust me on this assertion :)). Stephan Boyer post on this point of view is quite explicit. A tree is either an empty leaf or a node. In haskell it is defined as :

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

which becomes in Scala

package com.promindis.data

sealed trait Tree[+A]
object Empty extends Tree[Nothing]  {override def toString = "Empty"}
final case class Node[+A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
The scala definition concedes two lines to the Haskell one (no big deal frankly, a a certain point, the line battle does not mean anything, generally battles around languages do  not mean a lot). 

Why making things complex? A tree definition can be hosted by a simple trait. The parameterized A type define the type of the data bound a tree node. A Tree instance can be Empty or a Node instance.

The Tree value constructors are defined to be co-variant. As so, a node binding a String value is compatible with a node binding a AnyRef value. A leaf by definition must be compatible with anything. In Scala all types have a common lower bound type impersonated by the Nothing type. Then the Empty  object extending Tree[Nothing] will be compatible with Tree instances holding data of any type. Considering the uniqueness of a leaf, I found more natural making an object of it. 

I call the little world around a tree node a Spot (and not a breadcrumb like Miran Lipovaca, I leave to him that cute definition :)). Spot definitions gathered in lists will make a complete path, noticing for each step whether we came from the right or the left. Therefore our  type definition becomes:

package com.promindis.data

sealed trait Spot[+A]
final case class LeftSpot[+A](value: A, right: Tree[A]) extends Spot[A]
final case class RightSpot[+A](value: A, left: Tree[A]) extends Spot[A]
Spot type is defined to be co-variant versus its parameterized type, the meaning attached to this co-variance reflecting the one attached to the Tree type co-variance. So far so good (I told you there would be little code).

 At that point we are ready to play with zippers. What is a zipper ? A friendly (immutable of course) object encompassing the current working Tree node, and a path we are coming from, so:

final case class Zipper[+A](tree: Tree[A], spots: List[Spot[A]])

As explained before, the list of spots makes a path.
By default the tree and spots fields are final (val in scala), so immutable. Good.

Focusing, on the up, right, left and update functions in our tree, we can simply create a new immutable Zipper as a result of invoking each operation. Or can we ? What would happen if by any mean we were rambling too deep in our tree structure ? No doubt that something bad would occur as no one can go left or right from a leaf for example.
This is a potential error case.
Not watching our steps and going too far should lead us nowhere, but we should not suffer from nasty side effect like null pointers or invalid method calls. A nice Scala solution does exist, that would confine our Zipper in a "cotton" context, protecting us from side effects .

We can take back our Zipper whenever we want from the context, but the "cotton" context will not harm us. The Option type is our solution. Our Zipper is simply optional. It can look like Some(Zipper(tree, list)) when existing or None which represent no Zipper. As so, the left() method definition becomes:

 def left(): Option[Zipper[A]]

The right and up methods will return too Option instances. 

Frankly, at that point, we are nearly done. Of course I am going to use a test driven approach. But wait a minute. In order to ramble through my tree, check my values , will I have to extract my zipper at each step?
That can become particularly cumbersome ! Scala provides us with the same tools as with Map or List. One can extract the content of an Option using the tools used for collection iteration, the <- sugar form. So, starting from the following structure

  val leftChild = Node(2,Node(3, Empty, Empty),Node(4, Empty, Empty))

  val rightChild = Node(5, Node(6, Empty, Empty), Empty)

  val updatedChild = Node(7, Node(6, Empty, Empty), Empty)

  val tree = Node(1, leftChild, rightChild)


we can test the zipper expression after going left and up this way :

 def e2() = {for (
      left <- Zipper(tree, List()).left();
      up <- left.up() )
    yield up}.should(beSome(Zipper(tree, List())))

where e2 defines a Specs2 match result. Going to the left, produces an Option context. 

Applying <- to Zipper(tree, List()).left(), binds the extracted value to the local left variable. We then reuse it on the next line in order to go up. The result is again bound into a protecting Option context. At this point Specs2 provides you with the suitable DSL to extract, then challenge the value.

You may have guessed it, the Option type is a Monad, offering you a context to embed your values and manipulate them protecting your code from some side effect. Quoting Miran Lipovaca, the list comprehension for and its <- form provide us with an easy to read syntax gluing together monadic values in sequence. In our case the for comprehension is very similar to the do notation in Haskell.
Of course Monads are not just programmatic applicable design patterns and everyone can learn from category theory their more profound meaning, but you can view them as design patterns very suitable in solving programming problems. The Option monad offers you a possible failure context wrapping around optional values, while a List Monad for example can be assumed as embedding non deterministic values. 
At some point one have to start working with this notions in order to progress and I think possible to start from the application level before leveraging to the more general notions in the category theory domain. The application level offers the advantage of the every day practice. 

So, now before I forget, the testing code I wrote:


package com.promindis.data

import org.specs2.Specification

final class ZipperSpecification extends Specification{def is =

  "Zipper Specification"                      ^
                                              p^
    "Left method in Zipper should"            ^
    "go left from current scope"              !e1^
    "return to root applying up to go Left"   !e2^
                                              p^
    "Right method in Zipper should"           ^
    "go right from root"                      !e3^
    "return to root applying up to go right"  !e4^
                                              p^
    "Navigation should"                       ^
    "prevent me from going too far"           !e5^
                                              p^
    "Update should"                           ^
    "allow me to update right node"           !e6

  val leftChild = Node(2,Node(3, Empty, Empty),Node(4, Empty, Empty))

  val rightChild = Node(5, Node(6, Empty, Empty), Empty)

  val updatedChild = Node(7, Node(6, Empty, Empty), Empty)

  val tree = Node(1, leftChild, rightChild)

  def e1()  =
    Zipper(tree, List()).left()
      .should(beSome(Zipper(leftChild, List(LeftSpot(1, rightChild)))))

  def e2() = {for (
      left <- Zipper(tree, List()).left();
      up <- left.up() )
    yield up}.should(beSome(Zipper(tree, List())))

  def e3() =
    Zipper(tree, List()).right()
      .should(beSome(Zipper(rightChild, List(RightSpot(1, leftChild)))))

  def e4() = {for (
      right <- Zipper(tree, List()).right();
      up <- right.up() )
    yield up}.should(beSome(Zipper(tree, List())))

  def e5 = { for (
      right <- Zipper(tree, List()).right();
      deeperRight <- right.right();
      tooFar <- deeperRight.right()
    ) yield tooFar}.should(beNone)

  def e6 = {for(
    right <- Zipper(tree, List()).right()
  ) yield right.updated(_ => 7)}
    .should(beSome(Zipper(updatedChild, List(RightSpot(1, leftChild)))))
}

leading to the implementation:
package com.promindis.data

final case class Zipper[+A](tree: Tree[A], spots: List[Spot[A]]) {

  def updated[B >: A](f: A => B): Zipper[B] = {
    tree match {
      case Node(value, left, right) => 
        Zipper(Node(f(value), left, right), spots)
      case Empty => this
    }
  }

  def left(): Option[Zipper[A]] = {
    tree match {
      case Node(value, left, right) => 
        Some(Zipper[A](left, LeftSpot(value, right)::spots))
      case Empty => None
    }
  }

  def right(): Option[Zipper[A]] = {
    tree match {
      case Node(value, left, right) => 
        Some(Zipper[A](right, RightSpot(value, left)::spots))
      case Empty => None
    }
  }

  def up(): Option[Zipper[A]] = {
    spots match {
      case LeftSpot(value, right)::xs => 
 Some(Zipper(Node(value, tree, right), xs))
      case RightSpot(value, left)::xs =>  
        Some(Zipper(Node(value, left, tree), xs))
      case Nil => None
    }
  }
}


Progressively coming back to Scala, more determined than ever you walked by my side creating a small Zipper finally making use of the Option Monad. Not bad for a Christmas day. Merry Christmas to all. Be seeing you !!! :)

Sunday, December 18, 2011

Where we apply destructuring, pre check and decorate data

Hello again.

I just ended reading Learn you a Haskell for a great good and trying to find some example to set on the blog in order to explore (applicative)functors an monads on the blog. As these things take time, the blog is still empty.
But this kind colleague of mine always insists in the way I should produce thoughts on a more regular base even when they are just remainders or basics. So Adrian, I fulfill your request.

Having switched back to my SICP lecture (stuck on chapter 2) , I did the data symbol part (almost, as exercise 2.58 is still waiting for me). For the first time I bumped into a wall with Scheme, as I don't know the language very well. All things being equal I came back to Clojure, as trying to practice the book with both languages.
I found then myself using some little Clojure forms I was not expecting there, like pattern matching, meta data and pre condition testing. Abelson and Sussman present us a small differentiation program aiming to derive so simple equations. Of course the program is extremely limited, the purpose being to make the student work with symbol data. A typical example of differentiation is :

sicp.data-symbol=> (deriv '(* x y (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

where the first parameter of the deriv function is the expression and the second, the free parameter used in the differentiation process
Although there is room here for macro kata, I adopted the authors approach, not feeling completely at ease with macros.
 The interesting stuff here is that we start with a "symbolic" expression very Clojure idiomatic and get as a result too a symbolic expression. At some point in the book, the reader must extend the differentiation program in order to allow for differentiation of multiplications and additions accepting both multiple parameters.

In my humble opinion the exercise should be achieved using the ideas from the previous paragraphs specifically when dealing with stratified design, ergo the notion that a system should be implemented versus a sequence of layered languages. Each level is built up upon a lower level combining the latter functions so providing a new mean of abstraction. I found my Scheme version violating this rule.

Coming back to Clojure, how are we going to express the symbolic data ? Well, we will use the quote special form. That one simply prevents its arguments from being evaluated. So you can try the following in the REPL:

sicp.data-symbol=> 'a
a
sicp.data-symbol=> '(1 2 3)
(1 2 3)

A symbol is equal to himself, so in the first example, 'a will always mean 'a. The second example exposes the strengh of the quote (') symbol as a powerful way to construct self explicitly lists avoiding the cluttering noise of a list keyword. Following the writers indication I produced a first set of basic functions allowing me to challenge my symbolic expressions. Expressions will be idiomatically expressed as list like structure:

 
'(* x y (+ x 3))

Checking the nature per se of the expressions becomes then very easy, as we will check for the first symbolic item in a list:

(defn variable? [expression]
  (symbol? expression))

(defn sum? [expression]
  (= '+ (first expression)))

(defn product? [expression]
  (= '* (first expression)))

(defn exponentiation? [expression]
  (= '** (first expression)))

(defn same-variable? [expression variable]
  (and (variable? expression) (= expression variable)))

challenged using :

(deftest sum?-should-recognize-input-expression
  (is (= true (sum? '(+ x 3))))
  (is (not= true (sum? '(* x 3)))))

(deftest product?-should-recognize-input-expression
   (is (= true (product? '(* x 3))))
   (is (not= true (product? '(+ x 3)))))

(deftest exponentiation?-should-identify-operation
  (is (= true (exponentiation? '( ** x 3))))
  (is (= false (exponentiation? '( * x 3)))))

Of course I did not challenge Clojure native number? and symbol? forms. A lot of the job was done without using tests but walking side by side with the authors' wishful thinking approach, but I I will provide info when I produced it.

The next level of abstraction includes constructors and selectors, respectively creating the operation expressions, than selecting operands on them. For example in order to create a sum one need a make-sum function as constructor. The selectors aim to extract the addend - the first operand - of the sum expression and the augend, the second operand. Working on the sum, we expect our constructor and selectors to handle all the dirty process of manipulating multiple arguments. The intent is to keep the piggy stuff at a lower level so the main function in charge of the main process might be kept clean and unaware of the lower stuff like structure of a sum , products etc...
Of course in the SICP book, the main function has already been written by wishful thinking. In essence our sum constructor should comply to something like this:

(deftest make-sum-with-simple-arguments-should-produce-expression
  (is (= '(+ x 3) (make-sum 'x 3))))

(deftest make-sum-with-simple-arguments-should-produce-expression
  (is (= '(+ x y z) (make-sum '(x y z)))))

(deftest make-sum-with-one-zero-argument-should-produce-symbol
  (is (= 'x (make-sum 'x 0))))

(deftest make-sum-with-two-zero-argument-should-produce-operation-symbol
  (is (= '(+ x y) (make-sum '(x 0 y 0)))))

(deftest make-sum-with-two-numbers-should-produce-number
  (is (= 3 (make-sum '(1 2)))))

We introduced, like in the book, smooth reduction operations allowing to get rid of the identity operands when possible. The result expression are complex enough so we can try to reduce a little bit of that complexity.
The quality of solution I provided is debatable and as usual I am opened to critics. Not at ease with wishful thinking, I tempted to guard my functions with small contracts on my input functions (stack overflow being very close) and explored function variable arity in order to satisfy both my main function invocations and my selectors'invocations:

(defn make-sum
  ([x y] (make-sum [x y]))
  ([[_ :as expression]]
    (cond
      (= 1 (count expression)) (first expression)
      (all-numbers? expression) (apply + expression)
      (:simplified (meta expression)) (cons '+ expression)
      :else (make-sum
              (with-meta
                (filter (fn [x] (not= 0 x)) expression)
                {:simplified true})))))

(defn addend [expression]
  {:pre [(>= (count expression) 3)]}
  (second expression))

(defn augend [[op _ & cdr :as expression]]
  {:pre [(>= (count expression) 3)]}
  (make-sum cdr))

The SICP book strongly suggests to make of a '(+ x y z) expression a '(+ x (+ y z)) expression while looking for augend (so far, the interpretation is mine).
 So now we are talking.

In less than 20 lines I used a lot Clojure idiomatic stuff. As told earlier, my main function already exists (check at the end of the blog) and expects my make-sum function to expose a two variable signature. While extracting the augend parameter from my sum expression I don't want to clutter the code of the augend function with expression re-composition.
Composing a new sum from an existing one is the purpose of the make-sum constructor. I can isolate the sub set of the list I want my constructor to use in order to create a new sum expression. So my make-sum function will expose two function signatures, one with two parameters, and a second with a sequence.

Isolating the rest of the expression in order to crate a new sum expression can become annoying, specifically when mangling a let form sub level with combinations of first and rest functions applied to the input expression. Then comes destructuring. As noted by one of the readers (see comments), destructuring slightly differs from pattern matching  (one  may find interesting discussions here and there).
Let's say on a first approximation that destructuring allows to bind inner elements of an input sequence or map to input function variables. As so, appying :

[op _ & cdr :as expression]

will
  • bind op to the first parameter
  • ignore the second parameter as idiomatically expressed with the _ wild card 
  • and using the & separator will isolate all the remaining elements in a sequenced referred by the cdr expression
The :as keyword allows for the aliasing of the complete input collection using the expression parameter name.

My intent , aliasing the whole input expression, was to provide meat to a pre condition checking (yes like in design by contract). Pre-condition checking are a bless specifically when they stop you before your blindness fires a stack overflow :).
 Back to the make-sum function variable arity, one can see that I delegate all the work to the version accepting sequences as parameters. I could have not used destructuring into the second signature. I found it an idiomatic way to express that the function was specifically expecting a sequence.

As the tests showed earlier, I had to take into account various scenarii like the identity element for the sum, that can lead to a single element expression, the fact that all the list operands are pure numbers etc...

Filtering identity elements induces a recursion step after the filter step. We should memoize some ...state (?) in order to not indefinitely filter zeros from the input expression.But state is bad, we all know it. Decorating the filtered list with a meta information can be a smooth way to proceed. Once the immutable filtered sequence created, we do not alter its content or use a third method signature. We attach to the data a meta information:

 (with-meta
   (filter (fn [x] (not= 0 x)) expression)
   {:simplified true})

informing the function that no more recursion is necessary:

(:simplified (meta expression)) (cons '+ expression)

and the construction of the sum expression can be achieved.
The set of operations is similar when it comes to the product expression constructors and selectors.

 The whole code is given by:

(defn variable? [expression]
  (symbol? expression))

(defn sum? [expression]
  (= '+ (first expression)))

(defn product? [expression]
  (= '* (first expression)))

(defn exponentiation? [expression]
  (= '** (first expression)))


(defn same-variable? [expression variable]
  (and (variable? expression) (= expression variable)))

(defn all-numbers? [in-list]
  (letfn [
           (iter [still-number remaining]
             (cond
               (not still-number) still-number
               (empty? remaining) true
               :else (recur
                       (and still-number (number? (first remaining)))
                       (rest remaining))))]
    (iter true in-list)))

(defn make-sum
  ([x y] (make-sum [x y]))
  ([[_ :as expression]]
    (cond
      (= 1 (count expression)) (first expression)
      (all-numbers? expression) (apply + expression)
      (:simplified (meta expression)) (cons '+ expression)
      :else (make-sum
              (with-meta
                (filter (fn [x] (not= 0 x)) expression)
                {:simplified true})))))

(defn addend [expression]
  {:pre [(>= (count expression) 3)]}
  (second expression))

(defn augend [[op _ & cdr :as expression]]
  {:pre [(>= (count expression) 3)]}
  (make-sum cdr))

(defn make-product
  ([x y] (make-product [x y]))
  ([[_ :as expression]]
    (cond
      (= 1 (count expression)) (first expression)
      (> (count (filter (fn [x] (= 0 x)) expression)) 0) 0
      (all-numbers? expression) (apply * expression)
      (:simplified (meta expression)) (cons '* expression)
      :else (recur
              (with-meta
                (filter (fn [x] (not (= 1 x))) expression)
                {:simplified true})))))

(defn multiplier [expression]
  {:pre [(>= (count expression) 3)]}
  (second expression))

(defn multiplicand [[op _ & cdr :as expression]]
  {:pre [(>= (count expression) 3)]}
  (make-product cdr))

(defn make-exponentiation [base exponent]
  (cond
    (= 0 exponent) 1
    (= 1 exponent) base
    (and (number? base) (= 1 base)) 1
    (and (number? base) (= 0 base)) 0
    :else (list '** base exponent)))

(defn base [from-exponentiation]
  {:pre [(= 3 (count from-exponentiation))]}
  (second from-exponentiation))

(defn exponent [from-exponentiation]
  {:pre [(= 3 (count from-exponentiation))]}
  (second (rest from-exponentiation)))


(defn deriv [expression variable]
  (println expression " derived by " variable)
  (cond
    (number? expression)
    0
    (variable? expression)
    (if (same-variable? expression variable) 1 0)
    (sum? expression)
    (make-sum
      (deriv (addend expression) variable)
      (deriv (augend expression) variable))
    (product? expression)
    (make-sum
      (make-product
        (multiplier expression)
        (deriv (multiplicand expression) variable))
      (make-product
        (deriv (multiplier expression) variable)
        (multiplicand expression)))
    (exponentiation? expression)
    (do
      (make-product
        (make-product
          (exponent expression)
          (make-exponentiation (base expression) (dec (exponent expression))))
        (deriv (base expression) variable)))
    :else (println "Invalid expression")))

I am working on a Github account, so next time I will give you a link I hope :)

We have been using destructuring, meta data, and function variable arity, all Clojure's idiomatic forms, in one small program, not so unrealistic (shoot me if you never had to write a small interpreter in your real coder's life. If not, you have been lucky)

 PS: For Schemers , why did not I find my solution satisfactory ? Because my first shot is:

(define (make-sum x y) 
  (cond ((=number? x 0) y)
        ((=number? y 0) x)
        ((and (number? x) (number? y)) (+ x y))
        ( else (list '+ x y))))

(define (augend sum-expr) 
  (let ((rest (cddr sum-expr)))
    (if (= 1 (length rest))
        (car rest)
        (cons '+ rest))))

From my own point of view, the augend function should not build a new sum, the make-sum function taking that in charge. But I will find solution using the '.' notation in input parameters.

 Be seeing you !!! :)

Saturday, December 10, 2011

A day at Clojurex

Hello again and sorry for not coming back on a more regular base.

I guess next time I will have to pull some of my exercises from SICP studies or Euler project exploration in order to expose new code. Cross my heart I will try to produce one more code block before the end of the year.

So what happened ?
Three nice things happened.

I am reading Learn you a Haskell for a great good in order to progress in Scala while exploring type system through the nearly perfect Haskell language.
I am doing each exercise of the sicp both in Scheme and Clojure.

As a matter of fact these things take time, so we have a small blog black out issue. In order to have a cool break I decided to try a third exploration like going to a Skillsmater exchange on Clojure. Maybe this was the best idea of the year.
The Clojurex event happened on December 1st. Before having forgotten everything let's talk about that No code. Just talk (not too long, I swear)

London's calling

I went twice to London in forty years, once when I was twelve and another time for Clojurex. I won't wait so long as I registered for Scala days in April.
London has changed of course and from a more adult point of view I really felt like home. First of all, I found welcoming and smiling people everywhere. Undoubtedly, sharing a little of their lives two day was a joy, a hundred of times more pleasant than sharing the lives of french people.
This reinforced my wish to work over there.


At Skillsmatter

The skillsmatter staff is awesome. I cannot find any other words in order to describe the organisation and the welcoming.
They did manage to change the organisation of the event after Uncle Bob misadventure with custom officers and shame on me for hesitating one single second when this happened.
Special thanks to the kind lady who managed to catch a cab so I could get my Eurostar just an hour before departure: perfect timing.

I could not summarize all the locations where the attendees were coming from, but in essence, there was a real community spirit of curious open minded people, from older experienced Lispers to young fascinating skilled people, practicing Java, Scala and alternate languages.
My friend won't understand (:)) but I chose to remain quiet and listen the different conversations taking benefit from the everyday experience of every one. When I was near a group, people naturally included me as if I were a longtime friend. Thanks to all of them.

The presentations

Leaving about 3pm, I watched the morning presentations, unfortunately missing the afternoon brain storming and Uncle Bob Skype conference (yes he finally made it via internet). I will not detail the presentations advocating more the reader to both check the matching podcasts and then check each library/framework web site in order to try the stuff. My involuntary freedom in January will give me some time to try each of them and feedback when possible.

Knowing my reluctance to use frameworks in favor of patterns and algorithms application, why the hell did I attend framework presentations? Because the creators were there in order to discuss the purpose of tools, advocating more for better knowledge of Clojure and how to carefully depends on libraries without breaking language idioms. 
Obviously nobody attended the presentation in order to critic other languages or promote this or that technology like we often read or hear from some Java framework extremists (guess who am I talking about). The collective spirit was turned to better programming, paradigm adoption, and use of one's brain  rather than to framework propaganda and dumb assembly of bricks.
For that thanks again pals :)

Bruce Durling presented Incanter,a platform for statistical computing (including inter alia as committers David Edgar Liebke, Bradford Cross, Michael Fogus, Mark Fredrickson,...). The online presentation, available on line - like all the others - is very impressive as Bruce cleary demonstrated that developers committing into data driven application could find in Incanter a valuable asset, very respectful of Clojure idioms in its DSL forms and expressions target data sets manipulation. I personally was impressed by the ease of use of higher order operations like joining, filtering, grouping by columns and other similar facilities. And guess what, there is also a plotter :)

Robert Rees like some of us tried to get Clojure into a live environment having it stay there. He succeeded proceeding carefully, starting with  tasks which simplicity could easily reveal the strength of Clojure power, incrementally increasing the space of the language, baby steps by baby steps.   So Clojure can be used in production with no harm, on the contrary.

Another data flow oriented category of applications is the web applications. I gave up on pure web development years ago because of my ignorance of functional programming, as not being a genuine computer scientist. I was always frustrated by the complexity of setting up suitable patterns matching both my domain and business problems. From time to time the OOP model did not fit. Specifically when dealing only with flow of data to be handed, filtered and manipulated with basic business rules. 
Like Lift in Scala, Webnoir (written by Chris Granger)  and introduced here by John Stevenson allows you to rapidly develop websites in Clojure using a pure functional oriented approach. Looking at the presentation, I could not help thinking of two or three projects I have been working on years ago, and how much this non MVC approach would have answered myriads of problems we had to face.
I enjoy adopting the MVC approach, but from time to time, MVC does not fit. Functional programming does, ergo webnoir does too. I will try Webnoir as I will try Lift or Play! . And why not coming back to web application ? :)

As I started working with early versions of Swing years ago , Stathis Sideris presentation about Clarity, a new Clojure framework addressing some aspects of GUI programming, specifically shook me. It is possible indeed to (very) easily create Swing application from Clojure thanks to the Clarity layer. I foresee possibilities in this product for a good GUI testing environment. The fluency of the DSL Stathis developed could favor the emergence of very efficient and idiomatic testing API, like UISpec4J in Java. Exploring all the available forms interfacing Clojure with Java, like reification and protocols, Clarity allows for a declarative way of building up GUI (smartly proposing a stylesheet like functionality). No need to explore the code in order to understand the shape or the purpose of a pane or frame. The whole code layout clearly expresses the intents.

Being very quiet during the whole day was not a good strategy to find a freelance contract in UK :). I am sorry for that but frankly not going to Clojurex would have been a big mistake. I got richer in knowledge and had the opportunity to cross the path of a bunch of cool passionate guys. I earned some followers on Twitter and started following others my self, gaining access to a rich set of technical information since then.

If fate does not behave badly next year I will  come back to another Clojurex session, the early bird having already ordered a seat for 2012 December 6th.

Be seeing you !!! :)






Sunday, November 6, 2011

My Clojure being mean with my regressing dataset

Hello again.

 Today we are going to work on the least square exercise number 3 from Andrew Ng Machine learning classroom.
Last time, we challenged our least square method (applied to linear regression), using only single input data. The input data was composed of the ages of young pupils which height was sampled.
Today, we try to find the helpful parameter values required into the prediction of house pricing given for each house, the living area and the number of bedrooms. As exposed by Professor Ng during its lectures, the values of the areas being a 1000 times greater than the number of room some scaling of the input data must be applied.

Being formally a physicist in my youth, I would call this step a normalization. We will scale both types of inputs by their standard deviations and set their means to zero. As a reminder, the mean of a x-data set can be expressed as:

μ =(1/n) ∑in Xi

where n is the total number of data, and Xi each data value.
The standard deviation is expressed by

 σ =  √(1/n) ∑in( Xi - μ)2

(Yes the little symbol behind is a square root :)) This time we must go a little bit further than using the function raw-data as in the previous exercise.
We will reuse our file-reader module from last session:

(ns ml.file-reader
  (:use [clojure.string :only [split trim-newline trim]])
  (:import [java.io File BufferedInputStream BufferedReader FileReader]))

(defn read-lines [from-file]
  (let [reader (BufferedReader. (FileReader. (File. from-file)))]
      (letfn [(flush-content [line]
                (lazy-seq
                  (if line
                    (cons line (flush-content (.readLine reader)))
                    (.close reader))))]
      (flush-content (.readLine reader)))))

(defn parseDouble [x] 
  (Double/parseDouble x))

(defn to-number [data]
  (map #(vec (map parseDouble %)) data))


(defn not-empty? [data]
  (not (empty? data)))

(defn raw-data[from-file]
  (map #(filter not-empty? (split % #" "))
    (map #(trim (trim-newline %))
      (read-lines from-file))))

naturally starting collecting the file contents :

(ns ml.sample-two
  (:use [ml.file-reader])
  (:use [ml.least-square]))

(def from-x-sample "/dev/projects/clojure/leinengen/ml/ex3x.dat")
(def from-y-sample "/dev/projects/clojure/leinengen/ml/ex3y.dat")

(defn x-raw-data[]
  (to-number (raw-data from-x-sample)))

(defn y-raw-data[]
  (to-number (raw-data from-y-sample)))

You will notice I am working in a new namespace, referencing both the file-reader and least-square namespaces from the previous blog entry. Having browsed to Andrew Ng open classroom lecture you might recognize the file names bound to the from-x-sample and from-y-sample variables.
Before going any further I know I will have to process:
  • mean of a data set
  • standard deviation of a data set
  • normalization of data
These tiny steps are suitable for test driven development and the Wikipedia reminding link provides us with a useful sample for tests. I propose you the following set of test functions:

(ns ml.test.sample-two-spec
  (:use ml.sample-two)
  (:use clojure.test))

(def sample [2 4 4 4 5 5 7 9])

(deftest mean-test-sample-should-be-equal-to-five
  (is (= 5 (mean-of sample))))

(deftest deviation-test-sample-should-be-equal-to-two
  (is (= 2.0 (deviation sample (mean-of sample)))))

(deftest normalised-datas-sample-should-have-mean-of-zero
  (is (= 
    [-1.5 -0.5 -0.5 -0.5 0.0 0.0 1.0 2.0] 
    (normalised-datas sample)))
  (is (= 0.0
    (mean-of (normalised-datas sample)))))

The extrapolated implementation came to be:

(defn deviation [dataset mean]
  (let [squares (map #(square (- % mean)) dataset)]
    (Math/sqrt (/  (reduce + squares) (count dataset)))))

(defn mean-of [dataset]
  (let [nb-data (count dataset)]
    (/ (reduce + dataset) nb-data)))

(defn normalised-datas [dataset]
  (let [
    mean (mean-of dataset)
    sigma (deviation dataset mean)]
    (vec (map #(/ (- % mean) sigma) dataset))))

This is where we can see that anonymous functions (prefixed by the '#' symbol) should not be long as the '#' and  '%' symbols may quickly clutter the readability of the code. The formulas remaining simple in this situation, the anonymous functions purposes remain clear.
Our tool methods are ready. But one minute. The raw-data function from my file-reader module helps me to produce a list of vectors for both the x-data and y-data sets:

ml.file-reader=> (to-number (raw-data "/dev/projects/clojure/leinengen/ml/ex3x.dat"))
([2104.0 3.0] [1600.0 3.0] [2400.0 3.0] [1416.0 2.0] [3000.0 4.0] [1985.0 4.0] [1534.0 3.0]
...

In order to normalize the x-data, I will have collect the columns of data referring the living area values, and the column of values referring the number of rooms values. This step is easy meanwhile gathering again on the same list of vectors from the two individual sets will be a little trickier.
I am sure some kind soul will point out to me the useful method that allow to zip vectors in Clojure. After one week of reading and practicing the recursion part of my brain while reading the first part of SICP, I immediately wrote a (tail) recursive solution for the problem.
One of the beautiful aspects of Lisp languages being the easiness of developing one's adapted solution here and now for a given problem. What we expect is:

(deftest zip-datas-with-sample-vectors-should-produce-vector-of-vectors
  (is (= 
    [[1 4] [2 5] [3 6]]
    (zip-datas [1 2 3] [4 5 6]))))

That we can easily solve with :

(defn zip-datas [x y]
  (letfn [
    (zip-iteration [result partial-x partial-y]
      (if (empty? partial-x)
        result
        (recur
          (conj result (vector (first partial-x) (first partial-y)))
          (rest partial-x)
          (rest partial-y))))]
    (zip-iteration [] x y)))

There, we find a local scoped function calling itself recursively. The final result is accumulated in a result variable while we iterate, working on a more and more reduced tail of the vectors being processed. A typical recursive procedure generating an iterative process (check first part of SICP). The complete file content is :

(ns ml.sample-two
  (:use [ml.file-reader])
  (:use [ml.least-square]))

(def from-x-sample "/dev/projects/clojure/leinengen/ml/ex3x.dat")
(def from-y-sample "/dev/projects/clojure/leinengen/ml/ex3y.dat")

(defn x-raw-data[]
  (to-number (raw-data from-x-sample)))

(defn y-raw-data[]
  (to-number (raw-data from-y-sample)))

(defn deviation [dataset mean]
  (let [squares (map #(square (- % mean)) dataset)]
    (Math/sqrt (/  (reduce + squares) (count dataset)))))

(defn mean-of [dataset]
  (let [nb-data (count dataset)]
    (/ (reduce + dataset) nb-data)))

(defn normalised-datas [dataset]
  (let [
    mean (mean-of dataset)
    sigma (deviation dataset mean)]
    (vec (map #(/ (- % mean) sigma) dataset))))


(defn zip-datas [x y]
  (letfn [
    (zip-iteration [result partial-x partial-y]
      (if (empty? partial-x)
        result
        (recur
          (conj result (vector (first partial-x) (first partial-y)))
          (rest partial-x)
          (rest partial-y))))]
    (zip-iteration [] x y)))

(defn load-datas[]
  (let [
    x (x-raw-data) 
    y  (y-raw-data)
    norm-first-x (normalised-datas (map first x))
    norm-second-x (normalised-datas (map second x))]
  (create-samples (zip-datas norm-first-x norm-second-x) (y-raw-data))))

(defn sample-two[iterations learning-rate]
  (find-parameters (load-datas) iterations learning-rate))  


At the bottom, the load-datas function, takes in charge the reading, normalization and construction of the x input data, while the sample-two function will allow us to fire the regression using Andrew parameters: the number of iterations steps, and the learning rate.

 Done. After 100 iterations for a learning rate value of 1, we get:

({:value 340412.6595744681, :at 0}
 {:value 109447.7964696418, :at 1}
 {:value -6578.354854161278, :at 2})

...which is close to Andrew Ng result with a precision of 1 to 2%. This bias from the Octave/Matlab result should encourage us to work on the error amplitude estimation while working on numerical data. In a near future I hope.

Thank you very much to the people who have kindly followed these last three articles, and thank you for the feedback.

I have to pack my things in order to come back to the muddy and smelly suburb of Paris, but now that SICP reading has been seriously started, Haskell and Erlang discovery are in progress, I won't be disturbed by that environment. As a matter of fact, I won't have to bear this situation very long as I am looking for new positions in Europe :)

 Be seeing you !!! :)

Thursday, November 3, 2011

Where I regress with my Clojure thanks to Andrew

Hello again, this time for the "big" entry.

One promise I took was seriously reading the SICP book. I started reading it on vacation in parallel to other exciting activities activities like watching Cesarini and Thompson videos on Erlang, and starting learning a Haskell... for my great good (aficionados will understand).
Joining the reading of Michealson book with these other activities shook me in a positive way as all this functional programming stuff started to rearrange nicely in a flow of coherent concepts. Road is still long, but at least things are getting clearer.
Having read the first part of SICP (practicing the exercises in Scheme and Clojure) helped me in changing my approach of playing with higher order function, recursion, meanwhile re-learning nice mathematical stuff.
Of course I am far from mastering functional programming but it becomes more natural facing some problems to start writing something in Clojure or Scala (and soon in Erlang and Haskell I hope). This functional programming sympathy showed itself when I started watching Andrew Ng lectures on machine learning Stanford lecture CS 229), lectures kindly pointed out to me by Debashish Gosh (thank you Sir).

 In addition to the Stanford video resources, Andrew Ng, also presents short lectures nicely supporting and detailing the concepts exposed during the classroom sessions. I did not have much time yet to set an Octave installation, but quickly felt a lot of frustration while watching some examples.
As a matter of fact I had a hunch,  I could code adopting a functional language because of their mathematical expression so suitable in functional programming languages. I found the least square method applied to linear regression modelling demonstration so appealing that I did not resist in trying something.
After a first shot I was not satisfied with, I read the first part of SICP. As some concepts became clearer I took the problem again and rewrote it, faster and better. Naturally I am far from perfection, but at least, I can understand the code each time I come back to it. So there have been improvements :)

Here we go. I strongly recommend you make your self familiar with the least square method before starting reading the explanations in the open classroom.
Roughly speaking we are going to be provided a set of so-called training samples, we will use to fit a prediction model.
Typically a data set can be the measurements of heights of children versus their age, or prices of houses versus their areas etc... We will try to model a behavior using these training data sets in order to predict new values.
We will label as Y the data to be predicted and X the data provided as input in order to support our prediction attempt. More precisely, there can be multiple data inputs X for a given Y. Some given input data can be then detailed as X1, X2 etc.. depending on the number of inputs for given Y value. X is then a vector.
This aspect leads to very elegant matrices calculus we are not concerned with today.

We can come up with a starting hypothesis for our prediction model represented by the formula

 hθ(X)

where in a linear regression approach, the expression takes the form:

hθ(X) = θ0X0 + θ1X1 +X2θ2 etc...

In vector representation,  θ is also assumed a vector with components θk. Traditionally X0 is added as an additional virtual input and set to 1.
Model fitting can be achieved starting up with a cost function expression that will be minimized versus our model parameters. In essence the values predicted by our model must be as close as possible to the real sample values. A way of formulating this difference between model and reality can be expressed as:

J(θ) =(1/2n) ∑in(hθ(Xi) - Yi)2

where n is the total number of training samples The variable part in the formula being the θk parameters, we are going to look for converging values of these parameters. Grossly the algorithm can be summarized as:

Start with a given set of θk values, like 0 for example
keep changing the values until we have convergence

At each step of the algorithm  will changed the hypothetical θk values applying the following formula:

θk: = θk - α∂θJ(θ)

Where α is called the learning rate. Naturally its value influences the speed of convergence of the process. Regarding a linear regression approach , the last expression can be simplified into:

θk : = θk - (α/n)∑in(hθ(Xi) - Yi)Xki

I tried to keep things simple, sorry for the invasive formulas.

I tempted a rewriting of my first shot solution using both the wishful thinking advocated by Abelson and Sussman, and testing. This is to not-open the debate of understanding what you are doing versus TDD. Both served my purpose, no discussion about that.

Let's get driven by wishful thinking, at least once. My entry point function tries to replicate the generic algorithm :

(defn find-parameters[datas nb-try learning-rate]
    (let [
        nb-datas (count (:input (first datas))) 
        thetas (create-thetas nb-datas)]
        (letfn [
            (improve [parameters remaining]
                (println remaining " " parameters)
                (let [hypothesis (hypothesis-on parameters)]
                    (if (= 0 remaining)
                        parameters
                    (recur 
                        (new-parameters-from 
                             parameters datas hypothesis learning-rate)
                        (dec remaining)))))]
 (improve thetas nb-try))))

In order to mimic Andrew Ng approach while dealing with the exercises, find-parameters functions take as input
  • The datas
  • the number of iterations
  • the learning rate
Taking the number of iterations as input greatly helps in writing the iterative process as a recursion call (Check the sicp part one for type of processes generated by procedures). The local function improve, recures on itself in order to refine the input parameters until reaching the number of iterations.
On each loop, we create a new hypothesis expression using the more recently processed parameters. So the definition of the hypothesis is abstracted in an external function. 


The θ's parameters get created in the create-thetas method. By convention we always start with all parameters values set to 0.We use the number of input data in a sample in order to set the parameters.
The creation functions for data samples and parameter generation where implemented using TDD. 
We expect the input data sets to be created using the data sample creation functions: create-sample. The driving tests:


(deftest create-sample-with-tests-value-should-rpoduce-expected-structure
    (is (= {:input [1 2] :output 3} (create-sample [[2] [3]]))))

(deftest create-theta-should-create-expected-structure
    (is (= [{:value 0.0 :at 0} {:value 0.0 :at 1}] (create-thetas 2)))
    (is (= [{:value 0.0 :at 0} {:value 0.0 :at 1} {:value 0.0 :at 2}] (create-thetas 3))))


lead to the creation functions:

(defn create-sample[[input output]]
    {:input (vec (cons 1 input)) :output (first output)})

(defn create-samples[from-x from-y]
    (map create-sample (zipmap from-x from-y)))

(defn create-theta [parameter position]
    {:value parameter :at position})
  
(defn create-thetas [for-number]
    (letfn [
        (create-thetas-rec [thetas remaining]
            (if (= 0 remaining)
                thetas
                (recur 
                    (cons (create-theta 0.0 (dec remaining)) thetas)
                    (dec remaining))))]
         (create-thetas-rec [] for-number)))

The astute reader will notice we have prep-ended the imaginary sample value 1 (aka X0) to the input data as explained before, in the create-sample function.
Y and Xi data sets being taken from two different files, the create-samples function has been introduced so to zip data incoming from both files.

A hash map represents each sample, indexing the input values with the :input symbol, and the output with the :output symbol.
A hash map structure also represents the θ parameters, referencing in each parameter the value with a :value symbol (hurray !) and the parameter index with the :at symbol.

Good, we have data structures. Remains, the foundation of our model, the hypothesis, hθ(X). I also called bias the difference between the model predicted values and the real model value (hθ(Xi) - Yi) as it is also a recurring structure. Both the hypothesis and the bias are mathematical functions. Using a predefined (simple) set of test values I came with :


(deftest hypothesis-with-null-parameters-should-bring-zero
    (is (= 0.0 ((hypothesis-on (create-thetas 3)) {:input [1 2 3] :output 4})))
    (is (= 6.0
        ((hypothesis-on [(create-theta 1.0 0) (create-theta 1.0 1) (create-theta 1.0 2)]) 
        {:input [1 2 3] :output 4}))))

(deftest bias-for-with-zero-parameter-should-provide-output
    (let [
        parameters (create-thetas 3) 
        hypothesis (hypothesis-on parameters)
        data {:input [1 2 3] :output 4}]
        (is (= -4.0 ((bias-for hypothesis) data)))))

(deftest bias-for-with-unitary-parameter-should-provide-output
(let [
    parameters [(create-theta 1.0 0) (create-theta 1.0 1) (create-theta 1.0 2)]
    hypothesis (hypothesis-on parameters)
    data {:input [1 2 3] :output 4}]
    (is (= 2.0 ((bias-for hypothesis) data)))))

where the bias function is challenged using both (0 0 0) θ values and (1 1 1) θ values. Both implementations are given by

(defn hypothesis-on [parameters]
    (fn[data]
        (let [values (:input data)]
            (reduce + 
                (map #(* (:value %) (values (:at %))) parameters)))))

(defn bias-for [hypothesis]
    (fn[data] 
        (- (hypothesis data) (:output data))))

being higher order functions as returning functions taking respectively as input , the thetas values for the hypothesis and a data sample for the bias. From my point of view this is where functional programming nicely fit the algorithm modeling, abstracting the mathematical functions as basic bricks in our construction.

Going back to the find-parameters function, we now need to implement the new-parameters-from function, in charge of processing the next parameters values, extracted for a previous set of parameter values. This time I must confess I fully decomposed the problem in wishful thinking splitting from top to down the problem in smaller pieces, testing only two of the methods, when there was doubt. The obtained implementation

(defn data-correction[at-index bias]
    (fn [data] 
    (* (bias data) ((:input data) at-index))))

(defn correction-for[parameter datas bias]
    (let [
        at-index (:at parameter) 
        correction-per-data (data-correction at-index bias)]
        (reduce + 
            (map correction-per-data datas))))

(defn corrected-value[parameter nb datas bias learning-rate]
    (- 
        (:value parameter) 
        (* learning-rate (/ (correction-for parameter datas bias) nb))))

(defn new-parameters-from[parameters datas hypothesis learning-rate]
    (let [nb (count datas) bias (bias-for hypothesis)]
        (map 
            #(create-theta 
                (corrected-value % nb datas bias learning-rate) 
                (:at %)) 
            parameters)))

where
  • the new-parameters-from function simply maps onto the list of parameters in order to set up the next list of parameters,
  • the corrected-value function really does the job of altering an input parameter value.
  • The correction-for function then processes the correction for a given parameter without the scaling learning rate, and this using all the data samples (logical, thinking about that), delegating the task of processing the correction on a per data sample base to the data-correction function...and that's all.
The summarized version:

(ns ml.least-square)

(defn square [x] (* x x))

(defn create-sample[[input output]]
  {:input (vec (cons 1 input)) :output (first output)})

(defn create-samples[from-x from-y]
  (map create-sample (zipmap from-x from-y)))

(defn create-theta [parameter position]
  {:value parameter :at position})
    
(defn create-thetas [for-number]
  (letfn [
    (create-thetas-rec [thetas remaining]
      (if (= 0 remaining)
        thetas
        (recur 
          (cons (create-theta 0.0 (dec remaining)) thetas)
          (dec remaining))))]
    (create-thetas-rec [] for-number)))

(defn hypothesis-on [parameters]
  (fn[data]
    (let [values (:input data)]
    (reduce + 
      (map #(* (:value %) (values (:at %))) parameters)))))

(defn bias-for [hypothesis]
  (fn[data] 
    (- (hypothesis data) (:output data))))

(defn data-correction[at-index bias]
  (fn [data] 
    (* (bias data) ((:input data) at-index))))

(defn correction-for[parameter datas bias]
  (let [
    at-index (:at parameter) 
    correction-per-data (data-correction at-index bias)]
    (reduce + 
      (map correction-per-data datas))))

(defn corrected-value[parameter nb datas bias learning-rate]
  (- (:value parameter) (* learning-rate (/ (correction-for parameter datas bias) nb))))

(defn new-parameters-from[parameters datas hypothesis learning-rate]
  (let [nb (count datas) bias (bias-for hypothesis)]
    (map 
      #(create-theta (corrected-value % nb datas bias learning-rate) (:at %)) 
      parameters)))

(defn find-parameters[datas nb-try learning-rate]
  (let [
    nb-datas (count (:input (first datas))) 
    thetas (create-thetas nb-datas)]
    (letfn [
      (improve [parameters remaining]
        (println remaining " " parameters)
        (let [hypothesis (hypothesis-on parameters)]
          (if (= 0 remaining)
            parameters
            (recur 
              (new-parameters-from parameters datas hypothesis learning-rate)
              (dec remaining)))))]
    (improve thetas nb-try))))

The code has been written into a least_square.clj file located in a ml directory under the source root. The Leinengen project definition is:

(defproject practice "1.0.0-SNAPSHOT"
  :description "Essays on Machine Learning"
  :dependencies[[org.clojure/clojure "1.3.0"]]
  :repositories {"sonatype-oss-public" "https://oss.sonatype.org/content/groups/public/"})

In a sample_one.clj file, still under the ml directory the code was challenged using exercise2 samples:

(ns ml.sample-one
  (:use [ml.file-reader])
  (:use [ml.least-square]))

(def from-x-sample "/dev/projects/clojure/leinengen/ml/ex2x.dat")
(def from-y-sample "/dev/projects/clojure/leinengen/ml/ex2y.dat")

(defn x-raw-data[]
    (to-number (raw-data from-x-sample)))

(defn y-raw-data[]
    (to-number (raw-data from-y-sample)))

(defn load-datas[]
    (create-samples (x-raw-data) (y-raw-data))) 

(defn sample-one[iterations learning-rate]
    (find-parameters (load-datas) iterations learning-rate))

reusing the previous blog entry file_reader.clj file:

(ns ml.file-reader
 (:use [clojure.string :only [split trim-newline trim]])
 (:import [java.io File BufferedInputStream BufferedReader FileReader]))

(defn read-lines [from-file]
  (let [reader (BufferedReader. (FileReader. (File. from-file)))]
      (letfn [(flush-content [line]
                (lazy-seq
                  (if line
                    (cons line (flush-content (.readLine reader)))
                    (.close reader))))]
      (flush-content (.readLine reader)))))

(defn parseDouble [x] 
 (Double/parseDouble x))

(defn to-number [data]
 (map #(vec (map parseDouble %)) data))


(defn not-empty? [data]
 (not (empty? data)))

(defn raw-data[from-file]
 (map #(filter not-empty? (split % #" "))
  (map #(trim (trim-newline %))
   (read-lines from-file))))

Executing

(sample-one 1500 0.07)

for 1500 iterations and a learning rate value of 0.07, provides us with the exercise expected result

({:value 0.7501503917693574, :at 0} {:value 0.0638833754997108, :at 1})

which matches Andrew Ng results.

 This settles a personal story I had with least square method while I was a physicist. These times are buried, the least square problem is tackled too and that's nice.

 For the people who were not bored, I will briefly present the content of the sample_two.clj file I used to challenge the exercise three, as it is necessary to apply a little scaling processing onto the input datas in order to proceed with a set of two inputs per sample. The solution works fine though.


 Pffew!!!!!!!!! Going back to Haskell and Michaelson book.


 Be seeing you !!! :)

Wednesday, November 2, 2011

Where are the lines of my Clojure ?

Houdy again.

 Once again a very (very) short one in... Clojure this time. As a matter of fact this is a short one before the longer one up to come :). 


In order to challenge the code displayed in the upcoming post, I had again this problem of reading data from a file before converting it. Thanks to an astute reader in a previous post, I dropped the use of the clojure contrib 1.2 while using the 1.3 version of Clojure.
As I did not took the time to explore the new Clojure contributions I found my self a little bit upset while needing to load data from a file. The older Clojure contributions library hosted a suitable read-lines method in the clojure.contrib.io module. And I liked it. 


 Fortunately LISP languages always invite you in a nice way to develop your tools and build upon them. Of course I could not resist. At that point the do-not-reinvent-the-wheel conservationist's  will have left the building.
Thank you to the others for staying :) The following harsh test renders what I needed:


(def from-test-file "/dev/projects/clojure/leinengen/ml/myfile.txt")

(deftest read-lines-from-file-should-take-back-all
  (is (= 50 (count (read-lines from-test-file)))))

The read-lines takes as input the exact file location expression and returns a sequence (lazy if possible). Having explored lazy sequences in a previous post , I came to the working following solution:

(ns tools.file-reader
    (:import [java.io File BufferedInputStream BufferedReader FileReader]))

(defn read-lines [from-file]
  (let [reader (BufferedReader. (FileReader. (File. from-file)))]
      (letfn [(flush-content [line]
                (lazy-seq
                  (if line
                    (cons line (flush-content (.readLine reader)))
                    (.close reader))))]
      (flush-content (.readLine reader)))))

One will recognize the invocations of the BufferedReader, FileReader, and File java constructors recognizable by the appended "." at the end of the class name. The imports have been achieved through the use of the :import form at the top of the file. 

The function body hosts a recursive inner function flush-content, in charge of
  • taking the decision to stop the recursion when no more line has been found
  • recur again using the readLine method from the BufferedReader.
each new found line becomes an element of the lazy sequence using the standard cons form. The lazy sequence end clause is reached when no more line has been found. Works nicely for small files.


And that's all folks. The big interesting part is in the next post.

Must write it now, so be seeing you !!! :)


Saturday, October 29, 2011

One ring to rule my Akka actors

Hello again.

 On vacation with my hands full of books to read, I found myself committed on a serious SICP reading that takes longer than predicted (specifically while doing the exercises in Clojure in the mean time).
The promise I made was also to start learning Erlang, while starting learning a Haskell for my great good (fans will understand:)). On the edge of opening the Haskell book this weekend, I already watched Francesco Cesarini and Simon Thompson videos on Erlang which provided me with some meat for Akka.

A very short project, indeed but food for the mind, still being with no pet project, nor Scala or Clojure Master for guidance. One of the exercises proposed by Cesarini and Thompson consists in the creation of a ring of actors, one creating the following, then sending an acknowledgement message. The last created actor sends an actor to the source actor, notifying the end of the ring process. The implementation can be summarized into the following diagram:



The sbt build.scala file used for the project is contained into the following template:

import sbt._
import sbt.classpath._
import Keys._
import Process._
import System._

object BuildSettings {
  val buildSettings = Defaults.defaultSettings ++ Seq (
    fork in run         := true,
    javaOptions in run += "-server",
    javaOptions in run += "-Xms384m",
    javaOptions in run += "-Xmx512m",
    organization        := "com.promindis",
    version             := "0.1-SNAPSHOT",
    scalaVersion        := "2.9.1",
    scalacOptions       := Seq("-unchecked", "-deprecation")
  )
}


object Resolvers {
  val typesafeReleases = "Typesafe Repo" at "http://repo.typesafe.com/typesafe/releases/"
  val scalaToolsReleases = "Scala-Tools Maven2 Releases Repository" at "http://scala-tools.org/repo-releases"
  val scalaToolsSnapshots = "Scala-Tools Maven2 Snapshots Repository" at "http://scala-tools.org/repo-snapshots"
}

object TestDependencies {
  val specs2Version = "1.6.1"
  val testDependencies = "org.specs2" %% "specs2" % specs2Version % "test"
}

object AKKADependencies {
  val akkaVersion = "1.2"
  val actorDependencies = "se.scalablesolutions.akka" % "akka-actor" % akkaVersion
}

object MainBuild extends Build {
  import Resolvers._
  import TestDependencies._
  import AKKADependencies._
  import BuildSettings._

  lazy val algorithms = Project(
    "Ring",
    file("."),
    settings = buildSettings ++ Seq(resolvers += typesafeReleases) ++  
              Seq (libraryDependencies ++= Seq(testDependencies, actorDependencies))
  )

}

The BuildSettings object flags the execution of the scala main methods as forked processes so there will be no interference between the sbt process and the execution of the ring. I added memory sizing info for the execution in order not to be constrained by undersized estimates and imposed the flag server as running a 32bits old dual core laptop (yes, shame on me, but a good laptop can reach far more than 2000 euros).

The addition of the server flag revealed to be a nice idea dividing the time of execution by two.

 While achieving this small kata, I felled into a few traps. One of them, I was not expecting, was the chained creation of the Node in the ring one after the other. I could not chain them on construction unless generating an expected big stack overflow. So, on a first try, I overrode the preStart method, naively expecting for some asynchronous invocation of the method. The stack overflow took me by surprise. I then cheated and asynchronously ordered, via message sending, the creation of the next actor. The idea was to reproduce the following Erlang BIF invocation:
NPid = spawn(ring, start_proc, [Num - 1, Pid])

The Node class template is a classic:

 
  class Node(source: ActorRef, number: Int) extends Actor{

    protected def receive = {
      case 'start =>
        source ! 'ping
        if (number == 1)  {
          source ! 'ok
          self ! PoisonPill
        } else {
          Node(source, number - 1)  ! 'ok
        }
      case 'ok =>
        self ! PoisonPill
    }
  }

  object Node {

    def apply (source: ActorRef, number: Int) = {
      val actor: ActorRef = Actor.actorOf(new Node(source, number)).start()
      actor ! 'start
      actor
    }
  }


As one can see, I tried to reduce the volume of exchanged message, using only literal symbols during exchanges. The 'start and 'ok reproduces the Start, OK symbols on the ring schema.

While receiving a 'start message, a Node actor, creates a new Node actor, after notifying the source of all nodes that it has been created. It allowed to check all my actors where created.
On receiving an 'ok message, the actor poisons herself so to free the resources. The reference to the source and the number of expected actors are communicated as constructor parameters. On receiving a 'start message, a Node actor, creates her follower decreasing the number of Node to be created., the last Node, matching the number 1, sends the 'ok message to the source. 


 The Node companion object, takes in charge the creation and start of new actors. 


 The Source actor, is slightly different as collecting the ping notifications from the ring, tracing the complete execution of the ring and relaunching a ring execution. The ability to relaunch a ring process was important as the JVM warm up can take one or two ring processes before exposing a stable time of execution.


 class Source(number: Int, maximum: Int) extends Actor{
    var start: Long = _
    var total: Int = _

    var counter = maximum

    override def preStart() {
      start = currentTimeMillis()
      Node(self, number) ! 'ok
    }

    override def postStop() {
    }

    def decreaseCounter () {
      counter = counter - 1
    }

    protected def receive = {
      case 'ping => total = total + 1
      case 'ok =>
        println(currentTimeMillis() - start + " for " + total)
        decreaseCounter()
      if (counter != 0) {
        println("Retrying... " + counter + " times")
        start = currentTimeMillis()
        total = 0
        Node(self, number) ! 'ok
      } else {
        self ! PoisonPill
      }
    }
  }

  object Source {
    def apply (number: Int, maximum: Int) = Actor.actorOf(new Source(number, maximum)).start()
  }

On receiving a 'ping message,the (missnamed ) total number of created actors is incremented
On receiving an 'ok message, that flags the end of the ring execution, a new ring process is initiated again until reaching the expected number of ring executions. Here is the complete code content:

import akka.actor.{PoisonPill, ActorRef, Actor}
import System._
import Integer._

object Ring {

  class Node(source: ActorRef, number: Int) extends Actor{

    protected def receive = {
      case 'start =>
        source ! 'ping
        if (number == 1)  {
          source ! 'ok
          self ! PoisonPill
        } else {
          Node(source, number - 1)  ! 'ok
        }
      case 'ok =>
        self ! PoisonPill
    }
  }

  object Node {

    def apply (source: ActorRef, number: Int) = {
      val actor: ActorRef = Actor.actorOf(new Node(source, number)).start()
      actor ! 'start
      actor
    }
  }

  class Source(number: Int, maximum: Int) extends Actor{
    var start: Long = _
    var total: Int = _

    var counter = maximum

    override def preStart() {
      start = currentTimeMillis()
      Node(self, number) ! 'ok
    }

    override def postStop() {
    }

    def decreaseCounter () {
      counter = counter - 1
    }

    protected def receive = {
      case 'ping => total = total + 1
      case 'ok =>
        println(currentTimeMillis() - start + "ms for " + total)
        decreaseCounter()
      if (counter != 0) {
        println("Retrying... " + counter + " times")
        start = currentTimeMillis()
        total = 0
        Node(self, number) ! 'ok
      } else {
        self ! PoisonPill
      }
    }
  }

  object Source {
    def apply (number: Int, maximum: Int) = Actor.actorOf(new Source(number, maximum)).start()
  }

  def  main(arguments: Array[String]) {
    Source(parseInt(arguments(0)), parseInt(arguments(1)))
 }

}

where the Ring object main method takes as input parameters respectively the number of node in a ring, and the number of ring processes to execute. With an underlying jdk7 the kind of sampling I got are typically :

> run 1000 5
[info] 201ms for 1000
[info] Retrying... 4 times
[info] 127ms for 1000
[info] Retrying... 3 times
[info] 203ms for 1000
[info] Retrying... 2 times
[info] 90ms for 1000
[info] Retrying... 1 times
[info] 74ms for 1000
[success] Total time: 3 s, completed 29 oct. 2011 15:05:16
> run 10000 5
[info] 1079ms for 10000
[info] Retrying... 4 times
[info] 511ms for 10000
[info] Retrying... 3 times
[info] 94ms for 10000
[info] Retrying... 2 times
[info] 85ms for 10000
[info] Retrying... 1 times
[info] 108ms for 10000
[success] Total time: 5 s, completed 29 oct. 2011 15:05:26
> run 100000 5
[info] 2289ms for 100000
[info] Retrying... 4 times
[info] 967ms for 100000
[info] Retrying... 3 times
[info] 754ms for 100000
[info] Retrying... 2 times
[info] 739ms for 100000
[info] Retrying... 1 times
[info] 752ms for 100000
[success] Total time: 8 s, completed 29 oct. 2011 15:05:45
> run 1000000 5
[info] 9184ms for 1000000
[info] Retrying... 4 times
[info] 7834ms for 1000000
[info] Retrying... 3 times
[info] 8163ms for 1000000
[info] Retrying... 2 times
[info] 7470ms for 1000000
[info] Retrying... 1 times
[info] 7585ms for 1000000
[success] Total time: 43 s, completed 29 oct. 2011 15:06:34

Where the performances seems weaker compared to the Erlang one:


2> timer:tc(ring, start, [1000]).
{5000,ok}
3> timer:tc(ring, start, [10000]).
{52000,ok}
4> timer:tc(ring, start, [100000]).
{246000,ok}
5> timer:tc(ring, start, [1000000]).
{1535000,ok}

The execution time unit in Erlang is microseconds,

As I do not have enough knowledge (yet !!) about the Akka internals nor the Erlang one, I don't want to bring on the scene any conclusion in favor of one of the experiments or the other.

I would rather both welcome explanations and critics about the code sample in order to increase my knowledge of the framework, and understand better why the performances should be better for one or the other.

 In addition, one should remember that

 the machine is under sized for this kind of experiments
the number of messages exchanged during the Akka ring experiment (3000000) is greater that the number of messages exchanged during the Erlang test (1000000)
after all creating 1000000 actors, exchanging around 3000000 messages in about 7s could be considered a good performance on a three year old laptop

So what are the results on your machines ? Certainly better than mine ?

Be seeing you !!! :)

Sunday, October 23, 2011

A "snaky" tribute to Stuart in Scala with Akka

Hello again.

Today a little bit of Scala. My Clojure current algorithm not being complete, I found myself with the same recurring dilemma. What  am I going to talk about? This is a commitment in trying to understand, then expose a little subject, whatever it is, so to learn how to transfer ideas.

The subject came to me while reading Stuart Halloway book, programming Clojure. Nice book, full of interesting exercises. One of the exercises aims to picture some very amusing use of STM (aka Software Transactional Memory) in the form of a simple Snake game.
A very entertaining part and potentially a nice code kata. One must steer a moving snake in a rectangular area. Some Apple(s) is(are) dispatched in the game area while the snake is rambling. The purpose is to catch apples in order to make the snake grow. One can control the snake using the arrow keys. Once the snake has grown enough you win. But beware the head of the snake must never hit the snakes body . Simple.
Although I do not play game, programming Stuart Halloway example was quite fun and the game may be in implementing the solution.  Stuart Halloway presents a nice simple  architecture separating the purely functional aspect from the mutable state and the GUI. The mutable part of the game can evolve in three ways
  • A game can be reset to its initial state.
  • Every turn, the snake updates its position. If it eats an apple, a new apple
  • is placed.
  • A snake can turn.
My (small !!) Scala brain started yelling : "God, You can do that in Scala" with actors. The game state can be managed by some actor that can reinforce the serialisation of the change. My Scala mind tortures me enough, so I do not want to upset her....but let spice the idea with some Akka.

Having not found a pet project yet in Scala and no Scala Master for guidance, this is the only opportunity I have to bring Akka into the game (may I say). Naturally, I would not recommand using Akka in order to program a little game, the Scala genuine actors being self sufficient in order to manage this kind of implementation.
In the large set of Akka modules we can also find a STM module, and I will not resist in using it. Before starting, I provide here the sbt build.scala project content, sbt being a nice tool, not always very easy to start with:
import sbt._
import sbt.classpath._
import Keys._
import Process._
import System._

object BuildSettings {
  val buildSettings = Defaults.defaultSettings ++ Seq (
    organization        := "com.promindis",
    version             := "0.1-SNAPSHOT",
    scalaVersion        := "2.9.1",
    scalacOptions       := Seq("-unchecked", "-deprecation")
  )
}


object Resolvers {
  val typesafeReleases = "Typesafe Repo" at "http://repo.typesafe.com/typesafe/releases/"
  val scalaToolsReleases = "Scala-Tools Maven2 Releases Repository" at "http://scala-tools.org/repo-releases"
  val scalaToolsSnapshots = "Scala-Tools Maven2 Snapshots Repository" at "http://scala-tools.org/repo-snapshots"
}

object TestDependencies {
  val specs2Version = "1.6.1"
  val testDependencies = "org.specs2" %% "specs2" % specs2Version % "test"
}

object AKKADependencies {
  val akkaVersion = "1.2"
  val actorDependencies = "se.scalablesolutions.akka" % "akka-actor" % akkaVersion
  val stmDependencies = "se.scalablesolutions.akka" % "akka-stm" % akkaVersion
}

object SwingDependencies {
  val swingDependencies = "org.scala-lang" % "scala-swing" % "2.9.1"
}


object MainBuild extends Build {
  import Resolvers._
  import TestDependencies._
  import AKKADependencies._
  import BuildSettings._
  import SwingDependencies._

  lazy val algorithms = Project(
    "Snake",
    file("."),
    settings = buildSettings ++ Seq(resolvers += typesafeReleases) ++  
              Seq (libraryDependencies ++= Seq(testDependencies, actorDependencies, stmDependencies, swingDependencies))
  )

}

Why not following Stuart Halloway path in reusing idioms from the language? Scala being a multi-paradigm language, we could use actors of course, and object oriented approach, colored by some functional treatment into the pattern matching implemented in the actors' bodies .

I wanted the stuff to be simple. The approach can be resumed by the following scheme:

 

The global state lays into an Entities Actor in charge of handling all events incoming from the graphic interface. I voluntarily split the Game board (a swing panel) from the entities actor using a second actor called a board driver.The board driver plays the part of a single access point to the game board, both sending and receiving events in coordination with the entities actor.
The entities actor will send notification concerning the model update to the board driver while the board driver will send direction update notifications and refresh notifications.
Basically, a timer will issue the periodic update to the board driver that will convert it into some actor message. No big stuff.

 Like Stuart Halloway we need useful tools in order to help us swapping from the model world to the screen world. First of all, the Game world must be described by abstractions like positions , dimensions etc... For the sake of simplicity, I introduced the following tool class:
import scala.util.Random._

case class WorldLocation(x: Int, y:Int) {
  def + (location: WorldLocation) : WorldLocation ={
    WorldLocation(x + location.x, y + location.y)
  }
}

object World {
  def winLength = 5

  object Direction {
    val Left = WorldLocation(-1, 0)
    val Right = WorldLocation(1, 0)
    val Down = WorldLocation(0, 1)
    val Up = WorldLocation(0, -1)
  }

  def origin: WorldLocation = WorldLocation(0,0)

  def randomLocation(): WorldLocation = WorldLocation(nextInt(width), nextInt(heigth))

  def heigth: Int = 75
  def width: Int = 100

}

where a position into our small universe can be pointed out by a WorldLocation. The randomLocation method provides us a simple mean to pop an apple in a different location on need. The + operation has been implemented in order to provide more fluent expressions during WorldLocation manipulations. winLength defines the size a snake must grow up to in order for the player to win the game  Describing a small universe serves no purpose unitl we convert our desription into a screen world language. 
Here comes the GraphConverters object, very helpful when dealing with transformations from model to screen:

 
case class ScreenLocation(x: Int, y:Int, width: Int, height: Int)

object GraphicConverters {
  val factor = 10

  def converted(length: Int): Int = length * factor

  def converted(location: WorldLocation): ScreenLocation = diplayPointFrom(location)

  def converted(segment: List[WorldLocation]): List[ScreenLocation] = segment.map(diplayPointFrom(_))


  def diplayPointFrom(location: WorldLocation): ScreenLocation = {
    ScreenLocation(location.x * factor, location.y * factor, factor, factor)
  }

}


A scale factor of value 10 will provide a visible graphical panel surface delimited by a 750 * 1000 rectangle. The diplayPointFrom method takes in charge the basic conversion processe from the game World to the screen World, so it will be reused from the converted methods in charge of handling simple coordinates or list of coordinates. 

 Nice. The game started. We need a entities actor managing our entities. The entities are classified in two sub classes definitions: a snake and an apple. So two object abstractions:

 
 sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

case class Apple(location: WorldLocation) extends Entity

I found case classes to be natural implementations of board entities Some of you, dear pals, are going to yell at me. Yes, the Snake entity is a real object, taking in charge its own growth, like a real adult snake, being capable of changing its direction on demand etc...Or does it. As a matter of fact snake instances are immutable, so real "value objects". Every object invocation consists in a pure read access, like head position or leads to the creation of a new snake like moved, grown or go. Can it be more functional ? The location of the methods into the snake definition serves a modular purpose only. Precisely the methods purpose:

 
methodpurpose
gochange direction
movedchange snake position
growngrow snake
aheadprovides next location of head
headlocation of head


We have our two objects.

Good, we need an actor behavior to manage the transformations induced by the incoming events. An akka actor receives its event notifications via the ...receive method:
protected def receive =  {
    case Refresh() => updatePositions(snake,  apple)
    case UpdateDirection(to) => updateDirectionOf(snake, to)
  }

where we recognize the Refresh and UpdateDirection messages set earlier in the model graphic . Starting with  the easiest of all, the snake direction update:
 var snake: Snake = _

 def updateDirectionOf(withSnake: Snake, to : WorldLocation) {
    snake = withSnake.go(to)
  }


The internal actor mutable reference to the snake is basically updated . The updatePosition invocation involves a little bit more of trickery:

 
var snake: Snake = _
  var apple: Apple = _

 def reset() {
    snake = Snake(List(origin), Direction.Right)
    apple = Apple(randomLocation())
  }


 def updatePositions(fromSnake: Snake, fromApple: Apple) {
    fromSnake.body match {
      case head::tail if head == fromApple.location =>
        apple = Apple(randomLocation())
        snake = fromSnake.grown
      case head::tail if tail.contains(head) =>
        Game.displayMessage("You lose")
        reset()
      case head::tail if tail.size == World.winLength  =>
        Game.displayMessage("You win")
        reset()
      case _ => snake = fromSnake.moved
    }

    display ! Updated(snake.body, apple.location)
  }


If the snake eats the apple, in essence , if the the snake head meets the apple location, then a new apple is re-created and the snake grown.
If coincidentally the snake head location meets the snake body, the game is lost, so restarted after notifying the main game board (Game.displayMessage
If hopefully the size of the snake is enough the game is won, so restarted after notifying the main game board (Game.displayMessage
...else we move the snake in its current direction. 

 So suitable is pattern matching dealing with our update !! 

 The Updated message, wraps around locations only and not entities that do belong to the model world. And that's all. Our model is safe, thanks to a containing actor:

package com.promindis.games.snake

import com.promindis.games.snake.World._
import akka.actor.{ActorRef, Actor}

sealed trait StateMessage
case class Refresh() extends StateMessage
case class UpdateDirection(to: WorldLocation) extends StateMessage
case class Updated(snake: List[WorldLocation], apple: WorldLocation) extends StateMessage


class Entities(display: ActorRef) extends Actor {

  sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

case class Apple(location: WorldLocation) extends Entity


  var snake: Snake = _
  var apple: Apple = _
  reset()

  def reset() {
    snake = Snake(List(origin), Direction.Right)
    apple = Apple(randomLocation())
  }

  def updatePositions(fromSnake: Snake, fromApple: Apple) {
    fromSnake.body match {
      case head::tail if head == fromApple.location =>
        apple = Apple(randomLocation())
        snake = fromSnake.grown
      case head::tail if tail.contains(head) =>
        Game.displayMessage("You lose")
        reset()
      case head::tail if tail.size == World.winLength  =>
        Game.displayMessage("You win")
        reset()
      case _ => snake = fromSnake.moved
    }

    display ! Updated(snake.body, apple.location)
  }

  def updateDirectionOf(withSnake: Snake, to : WorldLocation) {
    snake = withSnake.go(to)
  }

  protected def receive =  {
    case Refresh() => updatePositions(snake,  apple)
    case UpdateDirection(to) => updateDirectionOf(snake, to)
  }
}

object Entities {
 def apply(display: ActorRef): ActorRef = Actor.actorOf(new Entities(display)).start()
}


We provided a companion object to the actor in order to simplify both creation and start of the actor. A reset action is fired while instantiating the actor. The second part concerns the board and its driver. 
There, we fall into Scala Swing. The Game extends the standard SimpleSwingApplication while gathering the three elements:

val driver = BoardDriver()
val board = new Board(handleFor(driver))
val state = Entities(driver)

where the handle notifying the board of key press events will look like:

def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
    (key: Value) => boardDriver ! ReceivedPressed(key)
  }

Call me a nit-picker if you want, but I did not want the display to know about the driver, although they do lay into the same Game class (making my own bakery of doom ?). So notification of key pressure is blindly fired through a function closing onto the driver. 
 The board by itself (not my favorite part), embeds some DSL's from the the Scala Swing layers:

 
class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }

As of Scala Swing the listenTo(keys) and reactions += {...} expressions elegantly set the environment as key event listener. We just added the constructor handle method to the list of reactions to be fired on key press event reception. 
The apply method provides us with an idiomatic way to drive the panel repaint from the board driver. The apply methods receives ScreenLocation infornation immediately converted into a closure that will be invoked during the next paint action, issued from the repaint invocation. As a matter of fact I don't like the idea of storing a reference to the closure on a variable, although the driver board is an actor so serialises its incoming events treatment. 

The board driver implementation remains very simple as a single entry point. Its purpose being only the translation of timer/user inputs into actor messages and actor messages into actions onto the main board:  

class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        state ! UpdateDirection(directions(key))
       case ShowMessage(text) => showMessage(parent = board, message = text)

    }
  }

As in all actors, the main purpose is implemented into its receive method. An incoming Updated message implies the invocation of the board after conversion of WorldLocation abstractions into ScreenLocation abstraction. The reception of a KeyPressed message will fire an update order to the entities model and finally a show message will display the dialog box. 
The periodic timer is started into the Game definition. Here it is at the bottom of the whole Game class definition:

 
package com.promindis.games.snake
import java.awt.{Dimension, Graphics2D}
import swing.event.KeyPressed
import swing._
import java.awt.event.{ActionEvent, ActionListener}
import event.Key._
import akka.actor.{ActorRef, Actor}
import swing.Dialog._

object Game extends SimpleSwingApplication {
  val driver = BoardDriver()
  val board = new Board(handleFor(driver))
  val state = Entities(driver)


  def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
    (key: Value) => boardDriver ! ReceivedPressed(key)
  }

  class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }


  case class ShowMessage(text: String)
  case class ReceivedPressed(keyCode: Value)

  class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        state ! UpdateDirection(directions(key))
       case ShowMessage(text) => showMessage(parent = board, message = text)

    }
  }

  object BoardDriver {
    def apply() = Actor.actorOf(new BoardDriver()).start()
  }

  def displayMessage(text: String) {
    driver ! ShowMessage(text)
  }

  def top = new MainFrame {
    title = "Snake"
    contents = new FlowPanel() {
      val timer = new javax.swing.Timer(100, new ActionListener() {
        def actionPerformed(e: ActionEvent) {
          state ! Refresh()
        }
      }).start();
      contents += board
    }
    pack()
  }
}

One minute pals. Didn't I promise for a STM implementation ? Well, the Game, its board and board drivers remaining almost unchanged, the stuff that do really changes is the Entities class. No more actor involved in this template.

package com.promindis.game.snake.stm
import com.promindis.game.snake.stm.World._
import akka.stm._


object Entities {
  sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

  case class Apple(location: WorldLocation) extends Entity

  val snake: Ref[Snake] = Ref(Snake(List(origin), Direction.Right))
  var apple: Ref[Apple] = Ref(Apple(randomLocation()))

  private def reset() {
    snake.set(Snake(List(origin), Direction.Right))
    apple.set(Apple(randomLocation()))
  }

  def updatePositions() {
     atomic{
       val fromSnake: Snake = snake.get()
       val fromApple: Apple = apple.get()
       fromSnake.body match {
          case head::tail if head == fromApple.location =>
              apple.set(Apple(randomLocation()))
              snake.set(fromSnake.grown)
          case head::tail if tail.contains(head) =>
            Game.displayMessage("You lose")
            reset()
          case head::tail if tail.size == World.winLength  =>
            Game.displayMessage("You Win")
            reset()
          case _ => snake.set(fromSnake.moved)
        }
       Game.update(snake.get().body, apple.get().location)
     }
  }

  def updateSnakeDirection(to : WorldLocation) {
    atomic {
      snake.alter(fromPrevious => fromPrevious.go(to))
    }
  }
}

The global state of game, consisting in a snake and an apple will be updated atomically in one transaction. The code will look familiar to Clojure developers. And it is, quoting Jonas Boner, "Refs (transactional references) are mutable references to values and through the STM allow the safe sharing of mutable data. Refs separate identity from value." 
A transaction is delimited using the atomic keyword. The snake and apple definitions remaining the same, the snake and apple object "values" will be identified by two immutable reference fields:

val snake: Ref[Snake] = Ref(Snake(List(origin), Direction.Right))
val apple: Ref[Apple] = Ref(Apple(randomLocation()))

The updatePositions method implementation makes use of the atomic keyword, using then the get/set methods of references in order to modify the references value. Invoked from the Game, the updateSnakeDirection method uses the alternate alter method which accepts a function that takes the old value while creating a new value of the same type, still in the scope of a transaction. 
We used a closure for the purpose of our implementation. The reset method is made private as being exclusively invoked from an atomic scope. Coming back to the Game class, we provide a version very close to the previous one:

 
package com.promindis.game.snake.stm
import java.awt.{Dimension, Graphics2D}
import swing.event.KeyPressed
import swing._
import java.awt.event.{ActionEvent, ActionListener}
import event.Key._
import akka.actor.{ActorRef, Actor}
import swing.Dialog._

object Game extends SimpleSwingApplication {
  val driver = BoardDriver()
  val board = new Board(handleFor(driver))


  class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }

  def displayMessage(text: String) {
    driver ! ShowMessage(text)
  }


  def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
                          (key: Value) => boardDriver ! ReceivedPressed(key)
  }

  case class ShowMessage(text: String)

  case class ReceivedPressed(keyCode: Value)

  case class Updated(snake: List[WorldLocation], apple: WorldLocation)
  class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        Entities.updateSnakeDirection(directions(key))
      case ShowMessage(text) => showMessage(parent = board, message = text)
    }
  }

  object BoardDriver {
    def apply() = Actor.actorOf(new BoardDriver()).start()
  }

  def update(list: List[WorldLocation], location: WorldLocation) {
    driver ! Updated(list, location)
  }

  def top = new MainFrame {
    title = "Snake"
    contents = new FlowPanel() {
      val timer = new javax.swing.Timer(100, new ActionListener() {
        def actionPerformed(e: ActionEvent) {
          Entities.updatePositions()
        }
      }).start();
      contents += board
    }
    pack()
  }
}


Hurray, we have did it !!!!!!! 

Okay the game's very simple, the boundary positions are not controlled, but the kata is worth while. Thank you Stuart Halloway. Must go to fix my next blog code...in Clojure this time. Very strange bug indeed. 

 Be seeing you !!! :)