Here is a short video of the game:

The estimation done by the author reveals a 10% of his time writing tests and 90% writing the actual software :

The number of hours spent on the project is my best estimate, as I have not kept track of these numbers. Also, the 10% breakdown comes from keeping track of my coding habits for the last two weeks of coding. But, these are my best guesses.

Underscore and anonymous parameters

I read some examples that use the Scala wildcard character: _ (the underscore). Here is one:

[java]
val sum = List(1, 2, 3).reduceLeft(_+_)

Note that the reduceLeft method apply a function of two arguments cumulatively to the items of the List. That means _+_ is a function of t two arguments. This example can be translated to:

[java]
val sum = List(1, 2, 3).reduceLeft((x, y) => x + y)

(x) => x is the Scala notation to write anonymous functions. For pythoners, this is the equivalent to lambda x: x.

As described in the Scala language specification. Implicit anonymous functions using underscores in parameter position. Some examples below. The expressions in the left column are each function values which expand to the anonymous functions on their right:

_ + 1                 x => x + 1 
_ * _                 (x1, x2) => x1 * x2 
(_: int) * 2          (x: int) => (x: int) * 2 
if (_) x else y       z => if (z) x else y 
_.map(f)              x => x.map(f) 
_.map(_ + 1)          x => x.map(y => y + 1)

Another example, I think, a bit harder to see where the anonymous function is hidden (note that foreach takes a function of one argument):

[java]
object Test extends Application {
    private def printAddition(a: Int, b: Int)  {
        println(a + b)
    }
 
    List(1, 2, 3).foreach(printAddition(5, _))
}

is equivalent to:

[java]
object Test extends Application {
    private def printAddition(a: Int, b: Int)  {
        println(a + b)
    }
 
    List(1, 2, 3).foreach((x) => printAddition(5, x))
}

Underscore and partially applied function

Let's write a simple function that return a function:

[java]
object Test extends Application {
    private def createAddFunc(a: Int) = {
      (x: Int) => a + x
    }
    
    val add100 = createAddFunc(100) // createAddFunc return a function, 
                                // so add100 references a function
    add100(3) // call add100 method (returns 100 + 3)

    // We can also write this:
    createAddFunc(100)(3)

    // Or affect createAddFunc to another name (note the trailing _)
    var createAddFuncCopy = createAddFunc _
}

In the last line of code of this example, the trailing underscore tells the compiler to look at createAddFunc as a functional, and not invoke it.

Underscore and pattern matching

Scala has a pattern matching mechanism (first-match policy). In this case, the underscore matches everything that has not be matched before:

[java]
object Test extends Application {
    private def cardColor(symbol: String) : String = symbol match {
      case "heart" => "red"
      case "diamond" => "red"
      case "spade" => "black"
      case "club" => "black"
      case _ => "typo ?" 
    }
    
    println(cardColor("club"))
    println(cardColor("clubb"))
}

prints:

black
typo ?

In this case, the Scala underscore is the equivalent to the underscore in OCaml, it matches everything that has not be matched:

let cardColor = function
      "heart" | "diamond" -> "red"
    | "spade" | "club"    -> "black"
    | _       -> "typo ?";;

print_endline (cardColor "club");;
print_endline (cardColor "clubb");;

Note the previous Scala code can also be written à la OCaml using the "|" symbol:

[java]
private def cardColor(symbol: String) : String = symbol match {
    case "heart" | "diamond" => "red"
    case "spade" | "club" => "black"
    case _ => "typo ?" 
}

Underscore and package imports

Another use of the _ is to import all tje classes of a package:

[java]
import scala.io._

THe equivalent of the java syntax:

[java]
import java.util.*;

Here is a video I captured from the iPhone Simulator (that doesn't support accelerometer, so the all the game features are not showed):

Maker Faire Africa (MFA), a celebration of African ingenuity, innovation and invention, will take place August 13-15 at the Ghana-India Kofi Annan Centre of Excellence in ICT in Ghana's capital, Accra.

You also should check out the Afrigadget website:

dedicated to showcasing African ingenuity. A team of bloggers and readers contribute their pictures, videos and stories from around the continent. The stories of innovation are inspiring. It is a testament to Africans bending the little they have to their will, using creativity to overcome life’s challenges.

In an old post I wrote about a metaheuristic: particle swarm optimization (PSO). It was the simplest code to demonstrate what PSO looks like. Today I'm writing about genetic algorithm, another metaheuristic inspired by evolution of species. You can read the description of the algorithm on the genetic algorithm article on Wikipedia.

I applied the algorithm to a problem that is not really one: trying to help lazy programmers to write file converters. I had to write file converters to unify all (more or less) formated input files into one kind of CSV file. Each of these converters is made using the right combination of filtering / regexp matching / line splitting.

So I wrote a program based on genetic algorithm where an individual is composed by 3 "genes":

• a list of filters (remove consecutive spaces, replace tabs by spaces, ...)
• a list of basics regexp (int, float, date, line separator, ...)
• a list of cleaning functions (remove empty cell, merge cells, ...)

The fitness of an individual is calculated using a sample file to parse that goes through the genes (filters / regexp / cleaning functions). The result of this process is a CSV file that can be compared to the expected sample result (that I wrote manually). The comparison uses the SequenceMatcher of the difflib Python stantard module, it returns the fitness: a float. A fitness close to 1.0 means the results is close to the expected CSV format. When the fitness is exaclty 1.0, that means the converter works perfectly for the sample.

Here is a sample file I wanted to convert:

08/12   	 Hello world 06/12
Paris 121231231 	  	- 22,29
08/12 	Something something ... 04/12
1111 1111 1111 1111 	  	- 14,35
08/12 	something else
	  	- 12,96
26/11 	Vir AAAAA
AAAAAA 2008	  	264,51

into this csv file:

"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

The program prints for each generation the 5 bests individual (I'm using elitism, so the best individual is always kept from a generation to the next one). A sample run:

$ python ga.py tests/sample1.txt tests/sample1.expected result1.pickled
Generation: 0 (mutation rate=10)
0.53772
0.42507
0.30406
0.28598
0.26389
Generation: 1 (mutation rate=10)
0.53772
0.42507
0.32684
0.30406
0.26799

...

Generation: 271 (mutation rate=15)
1.0
0.96025
0.95107
0.91779
0.87886
"08/12","Hello world 06/12","Paris 121231231","-22,29"
"08/12","Something something ... 04/12","1111 1111 1111 1111","-14,35"
"08/12","something else","","-12,96"
"26/11","Vir AAAAA","AAAAAA 2008","264,51"

filters: str_remove_consecutive_spaces, str_remove_somespaces, str_strip, str_remove_consecutive_spaces
regex: ([0-9]{2}/[0-9]{2})(.+?)(
)(.+?)(-?[0-9]+[.,]+[0-9]+)
cleaners: clean_strip, _in, _in, _in

Conclusion

The good:

• It's fun to see your program evolve ;)
• You are lazy and don't want to write _many_ of this kind of file converters
• With a good interface and if the basic functions and genes size are well defined, a non-programmer can create his own parser (I think this is the only argument to use it).

The bad:

• The resulted parsers are not optimal

The ugly:

• Of course it's quite easy to write such genes by hand
• It may never converge to 1.0 and generated parsers of fitness != 1.0 are useless (this may not be the case for other kind of GA applications)
• You need many well chosen primitives to cover a wide set of solutions

Download

gaparser-0.1.tar.bz2: source code and examples.

OpenCalais is a free web service that can perform semantic analysis on any English text. It processes the text sent in your request and respond with extracted concepts and relationships. It's a great tool if you want to play with semantics and if you want to add some nice features to your website / blog.

As an example, I tried to send the text from a this small article about Ruby and Python. Note : For readability I kept only interesting data from the response :

[xml]
<!-- 
Relations: 
ProgrammingLanguage: Python, Ruby
--> 
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:c="http://s.opencalais.com/1/pred/">
  <rdf:Description rdf:about="...">
    <!-- ProgrammingLanguage: Python; --> 
    <c:detection>[similarities and differences between Ruby and ]Python[ but I didn't find any idioms list in Ruby, so if]</c:detection> 
    <c:prefix>similarities and differences between Ruby and</c:prefix> 
    <c:exact>Python</c:exact> 
    <c:suffix>but I didn't find any idioms list in Ruby, so if</c:suffix> 
    <c:relevance>0.543</c:relevance> 
  </rdf:Description>

  <rdf:Description rdf:about="...">
    <!-- ProgrammingLanguage: Ruby; --> 
    <c:detection>[ list in Ruby, so if you know one or if you are a ]Ruby[ programmer, please post a]</c:detection> 
    <c:prefix>list in Ruby, so if you know one or if you are a</c:prefix> 
    <c:exact>Ruby</c:exact> 
    <c:suffix>programmer, please post a</c:suffix> 
    <c:relevance>0.386</c:relevance> 
  </rdf:Description>
</rdf:RDF>

The analyzed text is quite small but the results seems OK : 2 programming languages detected here, no animal, no gemtone...

If you like semantics or if you work on NLP projects, you should already know DBPedia. Database plus a set of tools that allow you to ask sophisticated queries against Wikipedia. Some days ago, DBPedia 3.2 was released and now, it includes DBpedia Ontology, a manually created cross-domain ontology based on the most commonly used infoboxes within Wikipedia.

Read more on the official announcement

Note: I'm a bit late on this news, I will try to update the blog more often.