Algorithmic panic

Last week I read a blog post about an interview for Google and I thought: "Oh my god, I don't know how to do that, I'm lost, I have no idea, I will never find the solution".

Flashback

Two weeks ago, I've ordered and started reading the excellent book, "The Algorithm Design Manual". That book is very good. Teaching algorithms and data structures can be something very dry when you consider it from a very scholar perspective. But it becomes really fun and challenging when you realize that:

• it solves real worthy problems
• no amount of processing power can be overcome a clever algorithm when there is one
• there's often no "right" solution but a combination of different approaches with different trade-offs
  

So the book is filled with "war stories" showing the author investigating some problems, trying to ask relevant questions until there's a "ah-ah" moment where the problem is sufficiently characterized. Then the solution is refined to get a completely satisfying result.

Decode this!

For example, the author and his team had to provide a new way to decrypt DNA fragments, knowing that there was a new technique using small probes returning small fragments of the whole string. Say your DNA is ATGCCTCGATTG, the probes will find AT, TG, GA, TT, TG, all of which are substrings of the initial string. And from all those pieces, you have to find the original DNA string. For this kind of problem, the sheer number of elements kills instantly any brutal-force approach. Originally they had to sequence DNA fragments of 50.000 characters, knowing that more that 1.5 million pieces should be combined to get the answer. Don't try this at home!

Binary tree > HashTable > Suffix Tree

For their algorithm to work they had to set up a dictionary allowing the search of substrings of length k inside strings of length 2k. The question is: how to do that very efficiently? A student proposed a HashTable which would do the job in O(log(k)). But this was still too slow! Hey, what can be faster than a HashTable??!! A Suffix Tree.

In this specific case they were searching elements which looked very close to one another, just being different by one character. And a suffix tree happens to organize the suffixes of a set of strings so that it's easy to search for a string which is just one character away.

Understanding the structure of the problem yielded much better results than a HashTable: for a 8000 characters long DNA, the HashTable time was 2 days against 650 seconds for the SuffixTree (the "compressed" version, because the original one was blowing up the memory!). That was my "ah-ah" moment.

The dreadful interview question

So I thought I was ready for any algorithmic question. Until I read the blog: "find the median of 2 sorted lists in O(log(n))". I don't know why, reading that blog, I imagined myself over the phone, trying to solve this problem and my mind got totally blank. Panic.

The same night, going to bed, I told myself: ok, relax, have a fresh look at it. And I slept happily a few minutes later because the principle of the solution wasn't that difficult.

First of all, the median of a sorted list is the middle element. That's an O(1) search! Then, given the medians for each list, the median of both lists is something like the median of the 2 sublists of all elements between median1 and median2. That's where we get our O(log(n)) from, because with a recursive search, we're pretty sure to cut the problem size by 2 at each step.

I programmed the rest the day after. Again, I think that this is a tribute to Scala. The result is really readable and I used ScalaCheck to verify it by generating lists of same and different sizes. On the other hand, I had hard time figuring out the proper bound conditions (ScalaCheck was very helpful here):

trait Median {
def median(l1: List[Int], l2:List[Int]): Int = {
if (l1.isEmpty || l2.isEmpty || l1.last <= l2.head) (l1 ::: l2).median
else if (l2.last < l1.head) (l2 ::: l1).median
else {
val (m1, m2) = (l1.median, l2.median)
if (m2 < m1) median(l1.takeBetween(m2, m1), l2.takeBetween(m2, m1))
else if (m2 > m1) median(l1.takeBetween(m1, m2), l2.takeBetween(m1, m2))
else m1
}
}
implicit def toExtendedList(list: List[Int]) = ExtendedList(list)
case class ExtendedList(list: List[Int]) {
def takeBetween(a: Int, b: Int) = list.dropWhile(_ <= a).takeWhile(_ <= b)
def median = list(list.size / 2)
}
}

Data structures everywhere

Funnily, yesterday, one of my colleagues asked me if I knew an easy, fast and clever way to access some values classified with 2 keys:

• there's only one value for (key1, key2)
• she wants to get the value for (key1, key2) (fast,...)
  
• she wants to get all values for key1 (fast again,...)
  
• she wants to get all values for key2 (fast also,...)

This looks like a very classical problem for Java programmers but surprisingly I found no existing, open-source, solution for this (if you know that, please tell me. I looked at things like TreeMaps or MultiMaps for example but they don't fit the requirement of a fast 2 key search with either of the keys).

After some research and some thinking we concluded that 3 hashmaps sharing the values and dedicated to answer each different query fast would be the best thing to do. But now that I know that HashTables are not the ultimate solution to everything,...

PDD: Properties Driven Development

Quick quizz: 1 + 2 =? and 1 + 2 + 3 =? and 1 + 2 + 3 + 4 =?

In other words, what is the result of the sumN function, which sums all integers from 1 to n?

If we had to use a "direct" (some would say "naive") TDD approach, we could come with the following code:
[Warning!! The rest of the post assumes that you have some basic knowledge of Scala, specs and Scalacheck,... ]

"the sumN function should" {
def sumN(n: Int) = (1 to n) reduceLeft((a:Int, b:Int) => a + b)
"return 1 when summing from 1 to 1" in {
sumN(1) must_== 1
}
"return 2 when summing from 1 to 2" in {
sumN(2) must_== 3
}
"return 6 when summing from 1 to 3" in {
sumN(3) must_== 6
}
}

But if we browse our mental book of "mathematical recipes" we remember that

sumN(n) = n * (n + 1) / 2

This is actually a much more interesting property to test and Scalacheck helps us in checking that:

"the sumN function should" {
def sumN(n: Int) = (1 to n) reduceLeft((a:Int, b:Int) => a + b)
"return n(n+1)/2 when summing from 1 to n" in {
val sumNInvariant = (n: Int) => sumN(n) == n * (n + 1) / 2
property(sumNInvariant) must pass
}
}

Even better, Scalacheck has no reason to assume that n is strictly positive! So it quickly fails on n == -1 and a better implementation is:

"the sumN function should" {
def sumN(n: Int) = {
assume(n >= 0) // will throw an IllegalArgumentException if the constraint is violated
(1 to n) reduceLeft((a:Int, b:Int) => a + b)
}
"return n(n+1)/2 when summing from 1 to n" in {
val sumNInvariant = (n: Int) => n <= 0 || sumN(n) == n * (n + 1) / 2
property(sumNInvariant) must pass
}
}

This will be ok and tested for a large number of values for n. Using properties is indeed quite powerful. Recreation time! You can now have a look at this movie, where Simon Peyton-Jones shows that Quickcheck (the Haskell ancestor of Scalacheck) detects interesting defaults in a bit packing algorithm.

Fine, fine, but honestly, all those examples look very academic: graph algorithms, mathematical formulas, bits packing,... Can we apply this kind of approach to our mundane, day-to-day development? Tax accounting, DVD rentals, social websites?

I am going to take 2 small examples from my daily work and see how PDD could be used [yes, YAA, Yet Another Acronym,... PDD stands for Properties Driven Development (and not that PDD)].

1. From the lift framework (courtesy of Jamie Webb): a 'camelCase' function which transforms underscored names to CamelCase names
2. From my company software: some pricer extension code for Swaps where fees values have to be subtracted from the NPV (Net Present Value) under certain conditions
   

I'll develop the examples first and try to draw conclusions latter on.

Example 1: camelCase

So what are the properties we can establish for that first example? Can we describe it informally first?

The camelCase function should CamelCase a name which is under_scored, removing each underscore and capitalizing the next letter.

Try this at home, this may not be so easy! Here is my proposal:

def previousCharIsUnderscore(name: String, i: Int) = i > 1 && name.charAt(i - 1) == '_'
def underscoresNumber(name: String, i: Int) = {
if (i == 0) 0
else name.substring(0, i).toList.count(_ == '_')
}
def indexInCamelCased(name: String, i: Int) = i - underscoresNumber(name, i)
def charInCamelCased(n: String, i: Int) = camelCase(n).charAt(indexInCamelCased(n, i))

val doesntContainUnderscores = property((name: String) => !camelCase(name).contains('_'))

val isCamelCased = property ((name: String) => {
name.forall(_ == '_') && camelCase(name).isEmpty ||
name.toList.zipWithIndex.forall { case (c, i) =>
c == '_' ||
indexInCamelCased(name, i) == 0 && charInCamelCased(name, i) == c.toUpperCase ||
!previousCharIsUnderscore(name, i) && charInCamelCased(name, i) == c ||
previousCharIsUnderscore(name, i) && charInCamelCased(name, i) == c.toUpperCase
}
})
doesntContainUnderscores && isCamelCased must pass

This property says that:

• the CamelCased name must not contain underscores anymore
• if the name contains only underscores, then the CamelCased name must be empty
• for each letter in the original name, either:
  
  • it is an underscore
    
  • it is the first letter after some underscores, then it becomes the first letter of the CamelCased word and should be uppercased
  • the previous character isn't an underscore, so it should be unchanged
  • the previous character is an underscore, so the letter should be uppercased
    

Before running Scalacheck, we also need to create a string generator with some underscores:

implicit def underscoredString: Arbitrary[String] = new Arbitrary[String] {
def arbitrary = for { length <- choose(0, 5) string <- vectorOf(length, frequency((4, alphaNumChar), (1, elements('_')))) } yield List.toString(string) }

This works and in the process of working on the properties I observed that:

• the full specification for CamelCasing name is not so easy!


• it is not trivial to relate the resulting name to its original. I had to play with indices and the number of underscores to be able to relate characters before and after. However, if that code is in place, the testing code is almost only 1 line per property to check
  


• the properties above specify unambiguously the function. I could also have specify weaker properties with less code, by not avoiding to specify that some letters should be unchanged or that the CamelCased name contains an uppercased letter without checking its position.
  

Example 2: Pricer extension

The logic for this extension is:

1. to have the NPV (NetPresentValue) being calculated by the Parent pricer
2. to collect all fees labeled "UNDERLYING PREMIUM" for that trade
3. to subtract the fee value from the NPV if the valuation date for the trade is >= the fee settlement date
4. to apply step 3 only if a pricing parameter named "INCLUDE_FEES "is set to true, while another pricing parameter "NPV_INCLUDE_CASH" is set to false

This looks certainly like a lot of jargon for most of you but I guess that it is pretty close to a lot of "Business" requirements. What would a property for those requirements look like (in pseudo Scala code)?

(originalNPV, fees, valuation date, pricing parameters) =>

if (!INCLUDE_FEES || NPV_INCLUDE_CASH)
newNPV == originalNPV
else
newNPV == originalNPV - fees.reduceLeft(0) { (fee, result) => result +
if (fee.isUnderlyingPremium && fee.settlementDate <= valuationDate)
fee.getValue
else
0
}
The most remarkable thing about this property is that it looks very close to the actual implementation. On the other hand, Scalacheck will be able to generate a lot of test cases:

• an empty fee list
• a list with no underlying premium fee
• a list with a fee which settle date is superior to the valuation date
  
• a list with a fees which settle date is inferior to the valuation date
• the 4 possible combinations for the values of the pricing parameters

You can also notice that I use as the first parameter the originalNPV, which doesn't directly come from a generator but which would be the result of the original pricer with the other generated parameters (fees, valuation date, pricing parameters).


Conclusion

As a conclusion, and at the light of the 2 previous examples, I would like to enumerate the result of my recent experiments with Properties-Driven-Development:

• First of all is that PDD is TDD, on steroids. In PDD, we also have data and assertions but data are generated and assertions are more general.

• I don't believe that this replaces traditional TDD in all situations. There are situations where generating even 4 or 5 cases manually is easier and faster. Especially when we consider that making an exact oracle (the savant word for verification of test expectation) is sometimes tedious as in the camelCase function. In that situation developping the cases manually using the == method would have been much faster

• PDD on the other hand allow the specify very clearly what is the rule. This is something that you would have to infer reading several examples when using TDD

• On the other hand having several examples also facilitate the understanding of what's going on. "foo_bar" becomes "FooBar" is more easy to catch than "if a letter is preceded by,..."

• PDD is very good at generating data you wouldn't think of: empty list, negative numbers, a string with underscores only,...

• A tip: sometimes, it is useful to include in the generated parameters the result returned by the function you want to test. For example, in the second example, my parameters could be: (originalNPV, newNPV, fees, valuation date, pricing parameters). That way, when Scalacheck reports an error, it also reports the actual value you got when showing a counter-example

• Sometimes the properties you want to check will almost mimic the implementation (as in example 2). I think that this is may be very often the case with business code if written properly or that this may show that your code is missing a key abstraction
  

• It really gets some time to get your head wrap around finding properties. And soon you'll start thinking things like: "I know that property A, B and C characterize my function, but are they sufficient?" and you realize that you coming close to Programming == Theorem Proving
  

As a summary, PDD is not the long awaited Silver Bullet (sorry ;-) ,...) but it is indeed a wonderful tool to have in your toolbox. It will help you test much more thoroughly your programs while seeing them yet another way.

Better mocks with jMock (and specs)

Now, I don't know how I managed to do without it. Now, I wonder how everyone can do without it. Now, I think that nothing big can be done without it.

I'm not advertising a brand new toy, but I'm talking about mock objects. Whether they are real mocks or just stubs, it is almost impossible to unit test Java components without them. Not that you can't test them but if you really want to isolate a piece of code, mocks show up one way or the other.

One of the best libraries for mock objects in Java is jMock. Yet, Java's verbosity makes it sometimes difficult to understand the intention of the mock expectations. Enter now jMocks with Scala!

Some statistics about my blog

Let's say I want to write another front-end to publish my posts to Blogger. I have encapsulated all Blogger functionalities in a Scala trait:

trait Blogger {
def allPosts: List[Post]
def todayPosts: List[Post]
def post(p: Post, tags: List[Tag]): Unit
...
}

Now I want to test a "Statistics" component which will compute some stats about my posts:

object statsSpecification extends Specification with JMocker {
"a statistics component" should {
"return the number of posts for today" in {
val blogger = mock(classOf[Blogger])
val stats = new Statistics(blogger)
expect {
one(blogger).todayPosts will returnValue(List(Post("...")))
}
stats.numberOfPostsForToday
}
}
}
class Statistics(blogger: Blogger) {
def numberOfPostsForToday: Int = blogger.todayPosts.size
}

In that short specification we:

1. create a mock: blogger = mock(classOf[Blogger]). I would have preferred to write blogger = mock[Blogger] but there is no way in Scala to create an object from its type only


2. Add an expectation in the expect block. Again here the loan pattern makes things a lot clearer than the corresponding "Double-brace block" in Java (even if it is a clever java trick!).


3. Specify what the return value should be in the same expression by defining "will" as Scala infix operator. In the Java equivalent we would have to make a separate method call (which our favorite IDE may insist on putting on the next line!)
   one(blogger).todayPosts; will(returnValue(List(Post("..."))))

Pushing further with nested expectations

There is also a situation where using Scala and jMock could be a real win.
[What follows is extracted from the specs Wiki, talk about reusability!]

You need to mock an object, like a Connection, which is supposed to give you access to a service, that you also want to mock and so on. For example, testing some code accessing the Eclipse platform can be very difficult for that reason.

Using specs you can use blocks to specify nested expectations:

// A workspace gives access to a project and a project to a module
case class Module(name: String)
case class Project(module: Module, name: String)
case class Workspace(project: Project)
val workspace = mock(classOf[Workspace])

expect {
one(workspace).project.willReturn(classOf[Project]) {p: Project =>
// nested expectations on project
one(p).name willReturn "hi"
one(p).module.willReturn(classOf[Module]) {m: Module =>
// nested expectation on module
one(m).name willReturn "module"}
}
}

or

// a workspace is a list of projects
case class Project(name: String)
case class Workspace(projects: List[Project])
val workspace = mock(classOf[Workspace])
expect {
// the workspace will return project mocks with different expectations
one(workspace).projects willReturnIterable(classOf[Project],
{p: Project => one(p).name willReturn "p1" },
{p: Project => one(p).name willReturn "p2" })
}

I haven't yet tested this capability on a real project but I clearly remember having had that kind of requirement.

I hope that this short post can make you feel that using mocks can be easy and elegant, especially if you use them with Scala! (and specs,....)

PS: Thanks again to Lalit Pant for showing the way with Scala and jMock

Better unit tests with ScalaCheck (and specs)

Writing unit tests can seem tedious sometimes.

Some people tell you: "Hey, don't write unit tests only! Do Test-Driven Development". You write the test first, then the code for it. This way:

• you end-up writing only the code that's necessary to deliver some concrete value for your customer/user
• you drive the design of your system
• you add frequent refactorings to the mixture to ensure your code stays clean

Or even better, "Do Behaviour-Driven Development!". With BDD, you get nice executable specifications for your system, which can almost read like English.

While I fully adhere to the above principles, I also think that there is a continuum between specifications and tests. And at the end of this continuum, it's all about testing that your software works. Even given silly inputs. Your unit tests should provide that kind of coverage.

And it's not that easy. A single line of code can go wrong in so many different ways. Try copying a file. Here comes ScalaCheck to the rescue!

Introducing ScalaCheck

Using ScalaCheck, you define:

• properties which should always be true
• random data to exercise the property

and ScalaCheck generates the test cases for you. Isn't it great?

Let's take a concrete example to illustrate this, because I feel I almost lost my only reader here (thanks bro, you're a real brother).

If you want, you Can

Last week I started specifying and testing the famous Can class from the lift framework. The Can class is the Option class from Scala library, on steroids. [To Scala newcomers: there are many good posts on Option, Maybe (in Haskell), Either and all this monad folkore but I will send you to a concrete example here].

Basically, a Can is either Empty (it contains nothing) or Full (it contains a value). This is a fairly common situation in software or elsewhere: the user with name "Smith" exists in the database (Full) or not (Empty), I got the power (Full) or I haven't (Empty).

When a Can is empty, it can be enhanced with an error message explaining why it is empty. In that case, it will be a Failure object.

Now, if you want to test an "equals" method working for all different cases you have to specify a lot of test cases:

1. 2 Full objects which are equal
2. 2 Full objects which are not equal
3. 2 Empty objects which are equal
4. 2 Empty objects which not equal
5. 2 Failure objects which are equal
6. 2 Failure objects which not equal
7. A Full object and an Empty object (not equal)
8. A Full object and an Failure object (not equal)
9. A Failure object and an Empty object (not equal)

When I said it could be tedious,... And I'm even simplifying the situation since Failures can be chained, optionally contain an Exception, etc,...

Properties

Here is the solution, implemented using specs and ScalaCheck, with the support of Rickard Nillson, author of the ScalaCheck project:

object CanUnit extends Specification with CanGen {
"A Can equals method" should {
"return true when comparing two identical Can messages" in {
val equality = (c1: Can[Int], c2: Can[Int]) => (c1, c2) match {
case (Empty, Empty) => c1 == c2
case (Full(x), Full(y)) => (c1 == c2) == (x == y)
case (Failure(m1, e1, l1),
Failure(m2, e2, l2)) => (c1 == c2) == ((m1, e1, l1) == (m2, e2, l2))
case _ => c1 != c2
}
property(equality) must pass
}
}
}

How does it read?

"equality" is a function taking 2 Cans. Then, depending on the Can type, it says that the result from calling the equals method on the Can class should be equivalent to calling equals on the content of the Can if it is a Full Can for instance.

Create a "property" with this function and declare that the property must pass. That's all.

Well, you may want to have a look at what's generated. Add the display parameter:

import org.specs.matcher.ScalacheckParameters._
...
property(equality) must pass(display)

Then you should see in the console:

....
Tested: List(Arg(,Failure(cn,Full(net.liftweb.util.CanGen$$anon$0$UserException),List()),0),... Tested: ...
Tested: ...
....
+ OK, passed 100 tests.

And if one test fails:

A Can equals method should
x return true when comparing two identical Can messages
A counter-example is 'Full(0)' (after 1 try) (CanUnit.scala line 21)

But you may have, at this point, the following nagging question: "Where does all this test Data come from?". Let's have a look below.

Generating data

Data generators are defined "implicitly". You define a function which is able to generate random data and you mark it as "implicit". When ScalaCheck tries to generate a given of object, it's looking for any implicit definition providing this. Like:

implicit def genCan[T](dummy: Arb[Can[T]])
(implicit a: Arb[T] => Arbitrary[T]) = new Arbitrary[Can[T]] {
def getArbitrary = frequency(
(3, value(Empty)),
(3, arbitrary[T].map(Full[T])),
(1, genFailureCan)
)
}

This code says that generating a Can, optionally full of an element of type T, which has its own implicit Arbitrary generator, is like choosing between:

• an Empty object, 3 times out of 7
  
• an arbitrary object of type T, put in a Full object, 3 times out of 7
  
• a Failure object (which has its own way of being generated via another function), 1 time out of 7
  

[The "dummy" parameter is here to help Scala type inferencer, AFAIK. The world is not perfect, I know]

Here is the Failure generator, which make heavy use of ScalaCheck predefined generation functions:
def genFailureCan: Gen[Failure] = for {
msgLen <- choose(0, 4)
msg <- vectorOf(msgLen, alphaChar)
exception <- arbitrary[Can[Throwable]]
chainLen <- choose(1, 5)
chain <- frequency((1, vectorOf(chainLen, genFailureCan)), (3, value(Nil)))} yield Failure(msg.mkString, exception, chain.toList)

In the above method,

• choose returns a random int number inside a range
• vectorOf returns a collection of arbitrary object, with a specified length
• alphaChar returns an arbitrary alphanumeric character
• arbitrary[Can[Throwable]] returns an arbitrary Can, making all this highly recursive!

Random thoughts

I hope this sparked some interest in trying to use ScalaCheck and specs to define real thorough unit tests on your system.

The added value is similar to BDD, you will see "properties" emerge and this will have a better chance at producing rock-solid software.

From now on, you too can be a ScalaCheck man! (see lesson 4)

2008, a Scala year

I apologize to Scala-interested readers, you'll have to scroll down to find something vaguely related to Scala! The first part is a pseudo-retrospective on my personal objectives for the past two years.

[non-scala]
"There's always a missing quote" - me

I was looking for a way to open this post with a brilliant quote about setting up personal objectives but after spending several seconds (at least) searching the web, I found none which meant precisely what I wanted to convey about having personal objectives. So I may just tell my own story.

First year

Two years ago, I had this so original New Year idea of choosing 2 personal objectives for the year to come. Notice that I didn't say "resolution". This wasn't something I wanted to drop after half an agonizing month. My choice was: "Learn Ruby" and "Learn Japanese".

"Learn Ruby" was very obvious considering my Java monotheism at that time and the relentless voice in my head moaning: "Leaaarnnn a new language each yeaaaar".

"Learn Japanese" was less obvious. I wanted to work in Asia and having just a little bit of Vietnamese on my resume didn't seem very professional. But why Japanese? Because it looked very far from what I knew, and I thought: cool, I will read imported mangas! (If you told me that I would actually end up in Tokyo 1 year later, I would have swallowed my chopsticks!).

Besides that, having 2 Japanese languages as "The objective of the year" look damn cool (Hey, you know that Ruby is also a Japanese language?)

Verdict, one year later. I had done a nice immersion in Ruby, touching Rails, Camping, doing code katas, using it for mundane scripting, bugging my coworkers,...

Japanese, on the other hand was embarrassing. A friend of mine told me: "Ah ah, you learn Japanese, good. Ohayo gozaimas'!". I said "What?". He had just told me "Good morning".

My conclusion was: it's funny to have objectives, especially if you only have to fulfill the ones you fancy for real.

Second year

I tried the same experiment for the following year. But that time I was really leaving for Japan! With a job in finance, which I hadn't done for some time, using a thousands-of-java-classes software. Since I am a sensible person, I thought: don't put too much pressure on your shoulders: new life, new challenges, do something reasonable.

My official and much touted objectives for 2007 were: "Learn Japanese" (and start with "Good morning" maybe this time) and "Learn my new company's product and succeed in my company".

Where are we, one year later?

• "Learning Japanese" was a self-sustaining objective since I had company-provided lessons starting from August. It's much easier with a teacher than alone. Go to the class, do your "Shukudai" (homework) and it should be fine
  

• "Learning my company product and succeed in my company" is well,... a terrible objective per se. It was more a way of saying: focus on your job, not on something else. A non-objective, not very motivating in itself, I'm addicted to my job anyway. Besides, this is not something I totally own. There are so many things which are truly out of my control (like not being authorized to blast atrocious code or organize projects in a truly agile mode)
  

Half-way through the year, I realized that having a motivating objective was like having something making you go the extra mile, diffusing energy and enthusiasm on the rest of your existence. I decided to finish the open-source project I had started as an experiment: specs.

This year

So what's in for this year? If I choose objectives for 2008, I:

1. authorize myself to change my mind anytime. Life's too short and anyway my experience shows me that this cannot work if it's not pure pleasure


2. select something which is deeply motivating, like learning something intriguing and new for the learning freak that I am (though I wish I was motivated by more cooler things to show-off in parties. Monads are hot on reddit but try that during a diner)


3. try not to put too much on my shoulders, because sleeping should not be Option[Sleep]
   

Which brings me to the quote of the day:

"I can't do everything,..., today" - my wife, pretty submerged
[non-scala]

Now, dear Scala readers, here are my objectives for this year:

1. continue to support specs, fixing issues and listening to users. I don't plan any major feature excepted maybe having another go at integrating JMock. However I will certainly add a myriad of small stuff (like a "skip" method, in 1.1.5)
   


2. contribute to the lift project by adding documentation, specs and tests. I expect to get a deep knowledge of that awesome web framework, quality interactions with the community, personal satisfaction from contributing to others work, improvements for specs
   


3. [as time permits] keep an eye on LiteralSpecifications with specs by creating a front-end wiki allowing you to write your specifications using a Markup language annotated with Scala code. The long-term objective is described in this paper
   

My dream would be to meet you all during the next Scala lift off conference. I have to see if I can combine this with a SF assignment in my company's headquarters!

Happy New Year 2008, I have no doubt that it is going to be a great "Scala year" despite the unavoidable hype and FUD!

Software design is like a magic trick

There's something I love at least as much as software development: my wife (Hey!! Give me back that keyboard, will ya?. I love you *more* than software development of course,...). So, what was I saying, ah, yes. There's something I love at least as much as software development: magic.

And there are some interesting similarities between the design of a magic trick and the design of software. Let's take, as an example, the last functionality I have designed for specs (but not released yet).

The effect

When you start thinking about a magic trick, you just try to be creative, to focus on what will really make other peoples brain explode. Or, and I find this even more impressive, transport them emotionally in a real magic world. To that respect David Copperfield is an incredible magician, and there are lesser known magicians whose creativity and talent are as amazing: Jay Sankey, Juan Tamariz, Michael Ammar, Jean-Pierre Vallarino, Vito Lupo,... The list is long. All of them have spent hours just thinking: "Why is this magic?", "How can I make it more magic?". They think about the spectator and the effect first and before any consideration of how it could be done.

In my case, it's a lot less romantic,... I just want the developer to be able to:

• create a table containing data rows
  
• have a header of Strings labeling each column
• have the rows being typechecked so that the type of the elements in a given column is always the same
• apply a function to each row and have the function parameters being typechecked against the row types
  
• have a light syntax allowing the table to look like a table as much as possible (not a list of lists,...)

Something like that:
|"a"|"b"|"c = a + b"|
| 1 | 1 | 2 |
| 1 | 2 | 3 |
| 2 | 2 | 4 | {(a:Int, b: Int, c: Int) => (a + b) must_== c }

How can I use my target language, Scala, to do that? Without loosing the ideal representation above; I want to keep my effect as magical as possible!

The method

Let's say I want to make the Statue of Liberty disappear, this would be baffling, wouldn't it? But even with an incredible budget, will the New-York authorities allow me to place a huge trap below Ellis Island? No? So how did he do it ?!

Here are 3 things I noticed with great magicians:

• They have an incredible magic culture. They know every obscure method to make a coin disappear or a card change its color, including the name of the inventor, the year of publication and the thousands of tricks using it
  

• They are always open to new stuff. Anything. Okito was just playing with a pill box when he invented the "Okito box". Michael Ammar actually listened to every single "great new idea" we had at our local magic club!
  

• They can invest an incredible amount of time and energy to preserve the magic of the effect: exercise for hours for a single "invisible" move, research chemical catalogs, learn the order of 6 decks of cards by heart (you can find a Hollywood version of that in "The Prestige")
  

That's what I tried to do with the DataTable feature: use all the Scala wizardry I knew of, be opened to new ideas and invest the maximum of energy so the feature is as simple as can be for the developer.

Here was my first attempt:
("a", "b", "c = a + b") |
( 1 , 1 , 2 ) |
( 1 , 2 , 3 ) |
( 2 , 2 , 4 ) | { t => val (a, b, c) = t
(a + b) must_== c }In that version, I used the following features:

• Tuples have a litteral notation ( , , , )
• You can create new operators, like | on tuples using implicit definitions
• The definition of the | operator can make sure that I will always add Tuples having the same types for their elements
  
• A tuple can be deconstructed as 3 values using "val"
  

This was mostly what I wanted but not quite, so I searched again and eventually got to this:
"a"| "b"| "c = a + b" |
1 ! 1 ! 2 |
1 ! 2 ! 3 |
2 ! 2 ! 4 | {(a: Int, b: Int, c: Int) => c must_== calc.add(a, b) }

Yes, almost my original intention! The most notable difference is the use of ! instead of | as a separator for the cells in the data rows. This is because operators beginning with | have a lower precedence over those beginning with ! in the Scala specification (6.12.3). So if I use |, I will have difficulties delimiting rows. I learned a new trick!

Frankly, it's not as good as the ideal version but it's ok if you read | as a delimiter for the table boundaries (including the header) and ! for the actual data. Sometimes in a magic trick you change a line, bend the story a little and it is still a pretty good trick.

And what about the rest of the magic? The first version only allowed to define a function taking a tuple as a parameter. Well, I worked a lot behind the scene to obtain that new version:

• The DataTable class takes 20 type parameters. 20 is a limitation but should act like a warning anyway. Why would you seriously need more that 20 columns in your table? Can't it be refactored?
  

• There are 20 DataRow classes, having from 1 to 20 type parameters. Each DataRow object can only be joined with a similar DataRow object using the | operator
  

• The DataTable class has 20 methods to apply functions having 1 to 20 parameters. Applying each row to the function parameters is done in each of these methods. A nice side-effect of that is that I can use a function with less parameters than the row size
  

• All that code is produced with a Ruby script to ease the work of the magician developer
  

You can have a look at the current code, which may actually be clearer than the points above.

Design and magic

This comparison with Magic can add more credits to the "Design is a craft" theory. I'm pretty sure that you could do the same kind of comparison with some craft you're fond of. So what's next: "Software design is like Origami", "Software design is like Wood carving"?

PS: for the Statue of Liberty trick, just Google for the explanation, you should get a glimpse of the kind of creativity those darn magicians can have!

Scala to heaven, second step: anatomy of a scala script

This objective of this post is to contrast some java and scala code aimed at accomplishing the same scripting task: cleaning-up my garbage system.

I want to be able to count old items in a database and archive them (through my system API). Of course, if anything goes wrong, I want to be able to restore them.

I'll show what is the approach I took using java then the corresponding scala-way of doing things.

The Java way: connect to the server

First things first: get a server connection. Typically, this is how I do it in java:

DataServerConnection connection = ConnectionUtil.connect("me", "my password", "my environment file");
// I do my stuff here

Of course, when my job is over, I have to close the connection:

connection.disconnect();

But in this situation, and in plenty others like writing to an OutputStream, I may just forget to close your resource. So, here's:

The Scala way: connect to the server

There is, among a gazillion things, a very useful feature in Scala: the possibility to have parameters of a method evaluated lazily. This means that the parameter you pass to a method will be evaluated only when the method body requires it, and not as the method is called, as it is the case in Java.

This way, I can write a better connect method:

def connect(user: String, password: String, env: String, actions: => Any) = {
  val connection = ConnectionUtil.connect(user, password, env)
  actions
  connection.disconnect
}

And use it like that:

connect("me", "my password", "my env. file", actions())

The actions are only performed once the connection is open, and the connection is closed without having to think about it. And for even more readability, I can even use the following syntax:

def connect(user: String, password: String, env: String)(actions: => Any) = {
  val connection = ConnectionUtil.connect(user, password, env)
  actions
  connection.disconnect
}
connect("me", "my password", "my env. file"){
  actions
}

Nice Ruby/blocks feel, isn't it? [for a better implementation of this pattern with try/catch and all, please check the Loan Pattern].

The Java way: processing stuff

For this script, the overall process is the same:

• get some "Market data items" for some "type" and "currency"
• count/archive/restore the oldest ones

The usual way to do that in Java is to nest some for loops and do the job inside the most inner loop:

for (String type : types) {
  for (String currency : currencies(type)) {
    for (String name : getMarketDataItemNames(type, currency)) {
      final int id = market().getMarketDataItemId(type, currency, name);
      doAction(action, type, id);
    }
  }
}

This buries deep inside the "selection" logic, the "action" logic. One alternative would be to construct first the list of elements to process, then process them. But in my case, this would mean dragging a very big chunk of the database in memory.

The Scala way: processing stuff

Scala offers the possibility to cleanly separate the selection logic from the action logic:

// select items
def items = for (itemType <- market.getMarketDataItemTypes.toStream;                   
                 currency <- currencies(itemType);
                 name     <- market.getMarketDataItemNames(itemType, currency);                       
                 itemId   =  getItemId(itemType, currency, name))                                       
                   yield (itemType, itemId, name)  

// archive items 
def archive(items: Iterable[Item]) = 
  for ((itemType, itemId, itemName) <- items)
    archive(itemType, itemId, itemName)

archive(items)

The for/yield construct returns ("yields") a list composed of "items" (type, id, name), ready to be processed by the archive function. The interesting thing is that this list doesn't have to be build in memory at once. It is a Stream, i.e. a list whose elements are being fetched as they are needed.

The Java way: aggregating results

The last step in my script is to display the current number of processed elements as well as their total number. I did it very simply with Java:

final int totalProcessed = 0;
for (String type : types) {
  for (String currency : currencies(type)) {
    for (String name : getMarketDataItemNames(type, currency)) {
      final int id = market().getMarketDataItemId(type, currency, name);
      System.out.println(action + " item: " + name);
      int processed = doAction(action, type, id);
      totalProcessed += processed;
      System.out.println("Done: " + processed + " Total: " + totalProcessed);
    }
  }
}

Again, the reporting logic is buried inside the loops, and this may fine indeed for a simple script. In other circumstances, you may want to be able to achieve a bit more independence between the functionalities:

The Scala way: aggregating results

The idea here is to be able to write:

report(count(items))
report(archive(items))
report(restore(items))

With the same report function which will:

• take a list of Report resulting from each action,
  
• print the current Report
• cumulate the current Report with a running total Report
• without having to process everything, then do the reporting,...
  

I will not go in every detail of the exact solution (which is a bit complex to my taste in fact, see below) but here are the principles. First of all, each action yields its result as a Report object, containing the name of the processed item and the result of the processed action:

def archive(items: Iterable[Item]) =
  for ((itemType, itemId, itemName) <- items)     
    yield Report(itemName, archive(itemType, itemId, itemName)) 

Then, the report function judiciously uses the reduce function to do the sum and report each element:

def report(reports : Iterable[Report]) = {
  reports.reduceLeft {(x:Report, y: Report) =>
    (x + y).report
  }
}

Not so readable for the non-expert eye, right?! Press F1:

• report iterates over a list of Reports
• it sums all elements 2 by 2 until we have a final result. List("h", "e", "l", "l", "o").reduceLeft((a: String, b: String) => a + b) would produce: "hello"
• before returning the summed element, it calls the report function to allow the aggregated report to print itself to the console:

class Report(itemName: String, processed: Int) {
  var total: Int = 0
  def +(c: Report) = { c.total = total + c.processed; c }
  def report = { reportItem; reportTotal; this }
  def reportItem  = println("Item " + itemName + ": " + processed)
  def reportTotal = println("total number: " + total)
}

Conclusion

The sad truth is that my real-world solution is a tad more complex that the one presented above. In the "real-life", I have different types of Reports because each action doesn't bring the same kind of results.

count only returns counted elements, archive and restore return deleted elements + processed elements (to double-check that the action is ok). Abstracting over this and defining a Summable interface to provide addition over both Int and Tuples proved a bit more challenging than using the plain Java solution.

But the good news is that as long as you're not looking for too much abstraction, you will find really neat ways to write common programming logic in Scala.

Scala to heaven, first step

Now let's start with our first step with Scala.

In the next posts, I'll be certainly assuming that you come to Scala from Java, however everybody is welcome!

I want first to demonstrate the use of a wonderful idea, borrowed from Haskell, the Option class. And this will be used with pattern matching. Said like that, this looks like advanced Computer Science stuff, but it's not.

This will help us manage something that plagues a lot of java applications: the dreaded NullPointerException.

An Option to parse options

Yes, I admit it. Parsing "options" on a command line is not the better way to introduce the "Option" class. So I'll try to go slow enough to reduce the confusion I have introduced in the first place,...

Anyway, this is a "real" example ("real" as "I'm using it", not as "the space shuttle runs with that"). I wrote a small utility in Scala to analyse the options passed on a command line. It can be used that way:

val action = getOptionValue("-action", "generateQuotes", args)

where

• "-action" is the name of the option on the command line: -action generateQuotes for instance
• generateQuotes is the default action if no "-action" option has been specified
• args is an array of string containing all the options passed on the command line (typically through the main static method)
  

The Java way

How can I implement this getOptionValue method? Let's first provide a parseOption function taking only the name of the option and the arguments (args) as parameters. This function should return the value of the option if such a thing exists on the command line. What could be a Java implementation of that?

public String getOptionValue(String name, String defaultValue, Array[String] args) {
final String option = parseOption(name, args);
  if (option == null)
    return defaultValue;
  else
    return option;
}

public String parseOption(String name, Array[String] args) {
  for (int i=0; i < args.length - 1; i++)
    if (args[i].equalsIgnoreCase(name) && i < args.length - 1 && args[i+1] != null) 
       return args[i+1];
  return null;
}

Please don't stare too much at the for loop, it is very naive but it was as YAGNI as I needed. Let's focus instead on the return value of the parseOption function. This function can either return a String or a null pointer meaning "I have not found an option value corresponding to the name you were asking for".

Unfortunately, if I don't look at the parseOption code, I have no way to tell what the return value when the option is not found. Is it null, is it an empty string? Many times, in real life, this can be pretty much hard to tell, because the value comes from another function which comes from,... and so on.

So in presence of a large codebase, you may eventually add a superflous check:

if (option == null || option.equals("")) return defaultValue;

Better be safe than sorry,...

The Scala way

Now what does Scala offers in that situation?

The Option class provides 2 subclasses:

• None, which represents "I have found nothing"
• Some, which represents "I have found something, and you can get it"

The parseOption function in Scala is defined like this:

def parseOption(name:String, args:Array[String]): Option[String] = {
  for (i <- List.range(0, args.length - 1))
    if (args(i).equalsIgnoreCase(name) && i < args.length -1 && args(i+1) != null)
      return Some(args(i+1))
  return None
}

And the getOptionValue function is defined with:

def getOptionValue(name:String, defaultValue:String, args:Array[String]): String = {
  parseOption(name, args) match {
      case None => defaultValue
      case Some(value) => value
  }
}

which reads like:

1. parse the option with the name 'name'
2. if you find nothing, return the defaultValue
3. if you find some(thing), designated by 'value', return that value

Pattern matching in 3 sentences

In Scala, the "object match {case xxx => ...}" construct implements the "pattern matching" idea. Given an object, if its "structure" matches a given pattern, you can use parts of this object to do your job. In that case, I get an object 'Some', which was constructed from a 'value', so I can de-construct the object and access the value.

The death of the NPE?

I find this in itself quite useful and elegant, but this is not all! What if you forgot to add a None clause to your match construct? You get a compiler warning! So, not only you can infer from the parseOption signature that you will have to deal with None values, but you are even reminded to do so!

Now, if you add the Option class to the fact that Scala encourages you to declare final variables (with the "val" modifier, a bit shorter that "final" in Java) and forces you to assign a value to modifiable ones, you can really think twice when you have to write the word "null" in a Scala program.

And even more to the point

And there are other jewels, too. You can convey this idea of a "defaultValue" in an even more concise way. The Option class has a "getOrElse" method, so the code above can be rewritten as:

def getOptionValue(name:String, defaultValue:String, args:Array[String]) = {
parseOption(name, args).getOrElse(defaultValue)
}

You can also do it the other way around. You can define an action that will be done only if the value exists. The Option class implements Iterable, so you can write:

parseOption(name, args).foreach(Console.println _)

In that example foreach iterates on every value contained in the Option (designated by "_") and print it. So the value is printed only if it exists. Of course, here, I would really prefer a more meaningful term (such as "do") but you know what? There is also a technique that allow you to add methods to scala library classes, so it is possible to write that too! More on that later,...

References

To the interested reader, here are some more references:

• This is how David Pollak uses options, in the lift web framework, written in Scala
• The ancestor: Maybe in Haskell (you will also notice the presence of an Either structure which can be very convenient too)
  

Never ending debate

As a conclusion I will add another layer at the dynamic typing vs static typing debate. One of the goal I follow by using Scala is to experiment when and how static typing is better than dynamic typing. My current observations are:

• If you are to use static typing, let your compiler do a maximum of work for you. Emitting a warning if you forget an Option alternative looks like a good example to me, but there are some reaaaaally advanced used of typing (for software configuration or prevention of SQL injection attacks): “make illegal states impossible to represent” is certainly a good ideal in those cases
  

• Sometimes it can be irritating to get the types right, and you have to be quite aware about things such as co-variance, contra-variance, dependent types and all the folklore. I will certainly write a post about that to give another "real-life" example, otherwise it can look pretty esoteric. The way I see it is that static typing is a way to encode some business constraints so that they can be checked before you even run the program. Sometimes it is possible and clean, sometimes the translation from your domain constraints to type constraints is a bit clumsy but it works, sometimes it is downright impossible and you need some "programming"

• There are some things I can do with dynamic typing that I can not do with static typing, such as generating some classes with repetitive attributes and methods, depending on the content of a file. The dynamic solution is very concise and provide "just good enough" objects
  

Longer post than I thought for a "first step" but I really hope this will give you some drive to try Scala out and then you'll get the virus!

Scala to heaven, ground

Selecting one "Programming language of the year", yes but which one?

The contenders

I pre-selected several contenders:

1. An ML language, such as OCaml
2. A "purely" functional language such as Haskell
3. A language designed for concurrency such as Erlang

Those 3 languages looked very interesting to me, each of them addressing fundamental software considerations. Well that's the rational pitch. But what was anedoctically exciting?

Observation round

Erlang was the promise to venture in a domain where I feel seriously weak, concurrent programming, with a brand new paradigm, very different from what I know. OCaml was a bit unknown to me, the only references I had were a colleague telling me that he gave up with OCaml one day the type inferencer was as lost as him and a financial company actually using it.

Haskell was perhaps the most appealing, for 2 reasons: QuickCheck (I loved Tom's Moertel description of his participation to IFCP) and the promise of mind-bending ideas baked in the language.

In order to shed more light on the subject I started reading.

"A history of Haskell, being lazy with class", is a wonderful way to introduce the language and give great insights on the "why" more than the "what" and "how". I also read "The little MLer" to become more familiar to the ML kind. And I was waiting for Joe Armstrong's book on Erlang.

But then I noticed something. Yes, that little language, there, hidden behind the others, come here!

I have a winner

What's your name? Scala
What do you know about concurrent programming? I, I have a clever actors library which may help get those performances
What about functional programming? Well, I unify the object and function approaches so you can get best of both worlds
How useful are you? I can play well with your existing java infrastructure
Do you do pattern matching and gadt? Yep
Isn't static typing to tiring? No, you just have to declare the bare minimum. The rest is inferred. By the way, this should allow me to get a top-level IDE with refactoring and code completion soon.
What about some cool stuff I have in Haskell? You mean Options, Parsers/Combinators and QuickCheck? Can do that too.
Are you system-engineering friendly? Some even pretend that dependency injection is part of me
Can you ease XML processing? I have XML literals and pattern matching against xml structures
Can I write DSLs with you? I am not Ruby but I have clever tricks that can help you a lot for that.

And the list goes on. I haven't discovered the least of what can be done with Scala and it is funny to see on the mailing list that even the language designers seems to think that there will be unexpected and surprising uses of scala features in the future.

First steps

The next steps in the "Scala to heaven" series will try to demonstrate the use of day-to-day Scala features to solve my own programming issues. As a beginner, I feel this is missing. We have good examples in the documentation, but abundance of examples won't be bad.

Scala to heaven, under the surface

Selecting one "Programming language of the year", yes but which one?

At school

First, let's have a look at my abysmal lack of culture on the subject. I think my first programming language must have been Basic. The only mental image I keep from that time is a linear sequence of instructions, with the ability to go back in time or to jump in the "future" to do something else.

Then I played with the Turtle a bit (Logo), I was much more comfortable with recursion, the way function reuse was presented to me and the interactivity with the environment.

At the Engineering school

But they told me that I should structure my programs, encapsulate, and there came Pascal and (later) ADA. In the meantime, I was shown enough Scheme to understand that recursion must be a fundamental thing, at least to return change in a vending machine.

My first internship

C++ and object-orientation sparked a bit more my interest in programming languages, as I first worked on a library for algorithmic geometry. Now I have "objects" I can manipulate, turn up and down, shuffle around. My language eventually supported a wonderful abstraction. "Hello, Mr Object, I am also an object, how can I help you?".

Most of my professional life

Java was a natural move from C++. No more nasty memory bugs, pointers and de-reference. Yes, that kind of profound analysis,... But to my credit, I was more interested by finding efficient ways to understand business concepts and map them properly to a programming language than by the language itself.

The last 2 years

On the road to languages zen, I had several "enlightments". First, the Pragmatic Programmers book gave me an advice: learn a new language each year. Well yes, nice advice, but I have JAVA, the quintessential power of a modern object-language at the tip of my fingers. Why in hell would I be interested in something else?

But damn, it was a conspiracy. Paul Graham, chanting the virtues of Lisp, Steve Yegge executing the nouns (what! my favourite thinking tool?!), even my favourite platform was growing new groovy languages.

Cool! Good place to start. I happened to imagine that, for the product we developed at the time, programing was required here and there to help users describe exactly what they wanted. So I embedded Groovy in our application and started appreciate some nice features:

myList.join(", ") or myList.each { x -> doStuffWith(x) }

Wow, this makes a difference. I can express my mind much more precisely than before! Projecting my ideas on a editor is much more straightforward.

Yes, but can we do better?

Let's go: "Programming with Ruby". Seems cool, Ruby has inspired Groovy (blocks, some of it early syntax), it's recommended by the gurus and there's even this thing, making a lot of noise, there, Rails. Not a bad idea, java for webapps is such a stack.

Of course, I appreciated that I was able to build my first useless website with just a few lines of code and an editor (not to mention my further use of Camping). But I was really blown away by Ruby. So many features that can really make your life easier and say more with less.

One month ago

Time to move on, now I know I don't know. Even if I appreciate that Ruby can "steal" features from other languages, I want something new and useful this year.

Let's go hunting for the language of the year!

Less is more, slow is fast (expensive is cheap?)

Dear Joel,...

Here's a letter I just received from Joel Spolsky's company, FogCreek Software. One year and a half later, they've sent me, for the second time, a DVD I had ordered. Good customer service, you would say: my first package was lost in the wild so they graciously sent me another one. But I really didn't expect that they would resend me the initial DVD that was miraculously returned to them after more than a year! Is that exceptional service or what?

Why did they do that? I was already pretty much satisfied the first time when they quickly sent me another DVD after the first one was lost (I've even heard about some companies doing that on purpose, just to show how good their support was afterwards). But what could they gain by over-satisfying me? Well, I assume, they just didn't miss that wonderful opportunity to show me how much they actually care about me. Not that I felt so miserable and alone on earth, but I was really touched by the attention. Now I really can say that this company has something special.

Ok, ok. How can they afford that? How can they sustain a double-digit growth each year by wasting so much time? Well, they simply don't ("Fog Creek is focused on growing slowly and carefully and staying profitable"). However if they pay so much attention to each of their customer, which I think they do, they are certainly here to stay.

Less is more

There is some kind of "less is more" pattern here. Less market growth, conquest, expansion,... but also more satisfied customers, upgraded installations, license extensions (anyway, Joel thinks that it takes ten years). And guess what, I think that the people working at the customer service are happier too. They certainly prefer 1000 times receive congratulations than coping with angry clients.

In a sense, this is also a "political" decision. Deliberately choosing to do less but to do better shows how you care for others: your customers, your co-workers. It is some kind of "idealist" choice. But is it also a "pragmatic" choice? Is it also a good economic choice for your company, especially for a software company (yes, I don't speculate often about fashion,...)?

Just wondering

Unfortunately, I don't have an answer with elaborate studies. But I am wondering,...

1. Are there times when you should choose "speed" against "quality"?

From the moment you select a feature to implement in your next release what do you get from delivering it faster but buggy? One more customer, of course! The one who is craving for this new feature. The one who's considering that not having it is a deal-breaker, the one,... who will be so mad to discover that it doesn't work!

[Unless he's just a golf player, he's a close buddy of the CEO, and he doesn't care so much as long as your software is buzzword-compliant. But this is another discussion]

Even when prototyping a new idea, we should be careful with "speed", because the frontier between "rapid prototyping" and "semi-chaos" is pretty thin (not to talk about the frontier between "prototype done" and "let's call it 1.0"?)

2. Is it so expensive to focus on the user-interface?

Yes, this can be pretty expensive. You may have to hire a usability engineer for the sole purpose. And I say that because I know what's the big gap between the half-baked interfaces I will ever produce and the interfaces that are carefully crafted by professionals. But this is not only for the beauty of the game. How many hours are going to be lost by: your helpdesk, your consultants, your newly-hired engineers, your partners? Oh, yes, and your customers,...

3. Why not set-up an "aggressive plan"?

This one really makes me wonder,... I guess that for any project, if you could start it over a thousand times, you may discover the most efficient way to order and parallelize activities so that the least amount of time is lost. But you can't do better, can you?

What are the variables you can play with when starting a project?

1. deadlines
2. quantity of people
3. motivation
4. quality of people
5. customer expectations

So far, an "aggressive plan":

1. fixes deadlines using ballpark estimates of the project estimates and insists that the target can't be missed. Time lines being then the only success criteria, this usually compromises any chance of success before the project even begun.

2. throws in between a moderate amount of people ("we can do it") and a big crowd ("we'll do the maximum")

There are strong suspicions that throwing more people on a project can only make it worse (Brooke's law and this study). Anyway, I am not sure there's much "aggressiveness" to have here. The "right" number of people will do. The good question is not: "is it aggressive enough?" whatever it means, but "are we properly staffed for this?"

3. motivates highly everybody

By either: insisting on the "heroic" aspect of the venture or reminding that "aggressive" concerns each one personally,...

4. tries to gather talented individuals,..

As far as 2 or 3 weeks allow it (because the preparation phase was also "aggressive")

5. decides bravely to deliver only one single feature.

No, just kidding!

Quality, ergonomic user-interfaces, sustainable project pace and even slack, why not go slow?

"less is slow, slow is fast, fast is more" (or the other way around ;-) )

One place where it makes the most sense in certainly when coding:

• less is slow: you need time to find the right abstractions, the proper structure, the proper names. You need time to remove the unessential (the famous StExupery word about perfection)
  

• slow is fast: you worked hard to produce less, but you get more value because code is a liability, and less allow you to move things around faster
  

• fast is more: there is a tipping point when you can add much more ideas to your software because you just play with the right legos

Why does it sound so paradoxical? A is ContraryOf(A). I believe strongly this is a matter of perceptions.

Perceptions

Try this at home. As an experiment:

• crank out code (I mean "crank" if you don't religiously follow the red-green-refactor mantra)
• take time to refactor it
• add some meaningful comments (the why, not the how)
• add some user doc (it can be a document or a few comments in a header)
• take note of the additional time taken
• forget all that for a few months (2 will usually do)
• try to estimate how much time was saved -just for you- when you read that code again

Seems simple and obvious, so why don't we do that all the time? Because we're so focused on the here and now that we don't perceive the poor chap that will read the code in 2 months. He's not here now, to cry in anger [This is why pair programming helps. He's sitting next to you,...]

Same idea, different context: why don't we do TDD all the time? Because we don't perceive the difficulty of what we're doing. If you'd realize that each line of code can bear many different and subtle bugs, you would just want to secure it before coding the rest. [And there are plenty of other benefices too].

I am ashamed to confess this, but 2 days ago I wrote a simple "Table" class, taking a list of n row names, a list of m column names and an array of n x m values. I had to create a method that returned the value for a given row name and column name. Can you do it with you eyes closed? Good for you. I was inspired enough to write a few specs before using the class,...

Those are 2 examples showing that we should be careful with our perceptions and ask ourselves:

• Can we really "not afford" to refactor?
• Can we really "not afford" to give more time to a project?
• Can we really "not afford" to hire a usability engineer?
• Can we really "not afford" to look for better tools and practices?
  

My theory is that the reality of what we do is so complex that we can be easily fooled by our perceptions [Or we choose to see things this way!]

Higher-order ideas

In my next post, I'll go slow again. I'll have a look at a language I just started learning. Yes, there's going to be a substantial learning curve, desperate evenings just trying to understand why this f*****g line doesn't work. But I am pretty sure this will pay off, allowing me to get more with less, to go fast because I was slow.

I've chosen Scala as my "Programming language of the year". Scala is not even in the 50 most popular programming languages, but I think it really embodies higher-order ideas, ideas that let you express other ideas with less words, doing more with less.

Stay tuned for the "Scala to Heaven"!

Net pearls

Reading tons and tons of internet stuff, I often find some posts or some documents I find interesting or funny: some net pearls.

As usual I would like to share this with the rest of the world and present those collected pearls as a post.

Pearl n. 1

This historical document by Dr. Winston Royce presents the waterfall model. The interesting sentence in this document is:

I believe in this concept, but the implementation described above is risky and invites failure.

This line must not have been quoted very often by waterfall proponents,...

Pearl n. 2

The next pearl comes from a study of the productivity of several languages. This story is interesting because it compares the use of different types of languages, static or dynamic, through different axes: productivity, length, memory consumption, speed,... Whatever my love for programming languages, the pearl is in the following conclusion:

Interpersonal variability, that is the capability and
behavior differences between programmers using the
same language, tends to account for more differences
between programs than a change of the programming
language.

Pearl n. 3

This one is both funny and interesting (read the whole thread): do we need a "might-equal" operator?

How about adding a "might-equal" operator?  I recommend useng
 the characters "=?".  I hav implemented my hone programming 
language, incubating the might-equal operater.  It works 
somthing like this:

if (x =? y)
  print ("x might equal y");
else
  print ("x might not equal y");

Acording to my studys, the might-eqqul operatir is 299834%
 more useful than the standerd ekwal operator.  For
 testing porposes, I have usd the mighty-kwal operatyr 
in severul custom sofware packages, including spell 
chex and statistics soffy-soff.  I hope that you ull can 
make yous of it in yore own pergroomink lunkishes. 

Pearl n. 4

This presentation from Michael Feathers introduces some coaching patterns and suggests visualizing the group as an individual, "Pat", even if one-on-one action is the privileged interaction medium:

‘Pat’ does not embody an organizational goals, ‘Pat’ is an amalgam of the team

Pearl n. 5

A little bit of history here. Here's a snapshot of notes taken during the meeting that led to the Agile Manifesto.

Pearl n. 6

Acceptance tests is one area that is still not very well covered by software vendors, despite their great usefullness (in terms of executable specifications). This may not be true anymore with Greenpepper software.

Pearl n. 7

Do you like programming quizzes? Here's a nice puzzle from John McCarthy (Lisp's inventor), solved with Haskell:

We pick two numbers a and b, so that a>=b and both 
numbers are within the range [2,99]. We give Mr.P 
the product a*b and give Mr.S the sum a+b. The 
following dialog takes place:

Mr.P: I don't know the numbers
Mr.S: I knew you didn't know. I don't know either.
Mr.P: Now I know the numbers
Mr.S: Now I know them too

Can we find the numbers a and b?

This puzzle is solved by encoding the facts in a few statements.

Pearl n. 8

You can still do funny stuff with Java! Check this out and turn the page.

Pearl n. 9

What's hot, what are the next technologies you should keep an eye on? This conference program proposes some answers:

• Services (SOA, web services, composition, mashup)
  
• Web frameworks (Rails, Tapestry) and Ajax
• Application frameworks (Spring, OSGi)
• Build systems (Maven) and automation
• AOP
• Open-source (use, participation)
• Collaborative, open webapps (Web 2.0)
  

Pearl n. 10

I like concrete examples when it comes to describe concurrencies issues, the next big question in our industry (not in the previous list, which also shows that is it far from complete). But fortunately, humans do distributed computing!

Bob. Alice calls Bob: "Could you get me those numbers?"

Bob jots Alice's request on his to-do list. "Sure thing, Alice, I promise I'll get them for you after I solve this engineering problem."

Bob has handed Alice a promise for the answer. He has not handed her the answer. But neither Bob nor Alice sits on their hands, blocked, waiting for the resolution.

Rather, Bob continues to work his current problem. And Alice goes to Carol, the CFO: "Carol, when Bob gets those numbers, plug 'em into the spreadsheet and give me the new budget,okay?"

Carol: "No problem." Carol writes Alice's request on her own to-do list, but does not put it either first or last in the list. Rather, she puts it in the conditional part of the list, to be done when the condition is met--in this case, when Bob fulfills his promise.

Conceptually, Alice has handed to Carol a copy of Bob's promise for numbers, and Carol has handed to Alice a promise for a new integrated spreadsheet. Once again, no one waits around, blocked. Carol ambles down the hall for a contract negotiation, Alice goes back to preparing for the IPO.

When Bob finishes his calculations, he signals that his promise has been fulfilled; when Carol receives the signal, she uses Bob's fulfilled promise to fulfill her own promise; when Carol fulfills her promise, Alice gets her spreadsheet. A sophisticated distributed computation has been completed so simply that no one realizes an advanced degree in computer science should have been required.

Conclusion

Here we are. I didn't mean at all to reach 10 pearls exactly but this came to be precisely the number of pearls I wanted to share. This must be a proof of the profound wisdom they embody.

See you for Net pearls 2! (Sooooo handy when I have nothing to say ;-) )

Pattern matching with Ruby

How do you know you got it all in your toolbox? Short answer: you never have it all. Long answer: you may add more, a lot more,...

I was reading one of Steve Yegge's old posts lately: "Choosing languages". This article introduced me to the pattern matching capabilities of a language such as Haskell. Wow,... Yes we can't do that in Ruby. But can't we really?

Indeed, this triggered my memory like a mantra: "if it's not nailed down, steal it... if it's not nailed down, steal it,..." Here's the article: If it's not nailed down, steal it. The author presents a "theft" in Ruby: the implementation of pattern matching.

So using the 'multi' gem, you are able to express the Fibonacci function as:

multi (:fib, 0) { 1 }
multi (:fib, 1) { 1 }
multi (:fib, Integer) { |n| fib(n-1) + fib(n-2) }

This may not be very impressive here, but later on in Steve's article, Steve tells us that pattern matching can really be a huge win when dealing with complex structured data. Here's an example from a contest in the Amazon's developer journal.

=============================================================

bad [[_,fs],[_,ds],[_,cs],[_,gs]] = (cs /= fs) && (cs == ds || cs == gs)

Here, the bad function gets a list as its argument. But instead of naming the list, it specifies a pattern that it expects the list to match: a list of 2-item sublists. It ignores the first element of each sublist, and assigns the second element to fs (farmer side), ds (dog side), etc. The variables then become available for use in the body of the function, after the "=" sign, where we check if if the chicken's alone with the dog or the grain.

=============================================================

For sure, writing the same thing in Java, or even in plain Ruby would be a pain. So I rolled up my sleeves and tried to enhance the 'multi' gem with the ability to use Arrays and variables in Arrays. So I allowed to write things such as:

multi(:foo, [String, Integer]) {|x, y| x; y}
multi(:foo, [:p1, :p2])  { |symbols| symbols[:p1]; symbols[:p2]}
multi(:foo, [:p1, [Integer, :p3]]) { |symbols, x| symbols[:p1]; symbols[:p3]; x}
multi(:foo, [:p1, [:_, :p2]]) { |symbols| symbols[:p1]; symbols[:p2]}

I also added some support for a 'multi' block, which is closer to a Haskell definition (though the 'let' name will be certainly shock a lisper,...):

multi(:foo) do
let(String) {|x| x.should eql "hello"}
let(String, String) {|x, y| x.should eql "hello"; y.should eql "world"}
end

My conclusion on that little experiment was:

• The use of a "symbols" map is a bit awkward, even if it uses the symbols declared in the pattern. It looks like a trick compared to a Haskell definition
  
• It is possible to reproduce Steve's examples in an easy way (I didn't say efficient!)
• The limitations mentioned in the article regarding the use of 'multi' methods in classes still hold: they are not inherited. 'multi' is not the 'def' keyword
  

What I am really interested in is: will I use it? Steve says that once you've tasted Pattern matching, you start seeing it everywhere (design patterns, anyone?). I still don't see it in my daily java programming, nor in my nightly ruby programming.

Now, let's say I start seeing it ("Yes, I got it! I am in the Matrix!!"). Should I use it in my ruby code? And should I use the rest? Let's see:

• we can do some pattern matching in ruby
• we can compose functions
• we can have lazy lists (and list comprehension)
• we can use statemachines
• we can do high-order messaging: [0, 1, 2].where.nonzero? => [1, 2]


Is it still Ruby? Will other people still understand what I write?

Hey, why not? I am truly amazed by the Ruby's capacities to be benefit from ideas from other languages or paradigms. Indeed, I think it still feels quite Ruby-like with functions and blocks, and those features allow me to write more concise code, at the right abstraction level.

However, capturing an animal and putting him in a zoo is not the same as watching him in its environment. Haskell, Lisp, Erlang and others are quite unique and they each provide different ways to blow your mind.

By the way, is it possible to do concurrency programming "a la" Erlang in Ruby? The challenge is opened,...