2009-07-21

(Dis)Functional Bowling

It is saddening to see people invested so heavily in cargo-cult programming practices that they cannot see natural solutions to simple problems after having their thoughts twisted by object-orientation as an ends and TDD as a fighting technique. Uncle Bob is struggling (and failing) to approach functional programming in the natural way by what seems to be his biases and commercial interests. His Bowling Game Kata (warning, PPT; right-click to download) is to find the score of a 10-frame bowling game:

The game consists of 10 frames as shown above. In each frame the player has two opportunities to knock down 10 pins. The score for the frame is the total number of pins knocked down, plus bonuses for strikes and spares.

A spare is when the player knocks down all 10 pins in two tries. The bonus for that frame is the number of pins knocked down by the next roll. So in frame 3 above, the score is 10 (the total number knocked down) plus a bonus of 5 (the number of pins knocked down on the next roll.)

A strike is when the player knocks down all 10 pins on his first try. The bonus for that frame is the value of the next two balls rolled.

In the tenth frame a player who rolls a spare or strike is allowed to roll the extra balls to complete the frame. However no more than three balls can be rolled in tenth frame.

In order to sidestep the problem of validating games for length, I'll consider a bowling game as an infinite number of balls, a finite prefix of which is non-zero:

let repeat x = let rec l = x :: l in l

let game strikes = strikes @ repeat 0

Scoring a frame according to the rules is a matter of pattern matching on the first few balls. According to the result, a complete frame is removed and the rest of the game returned:

let score_frame = function
| 10 :: (n :: m :: _ as g) -> 10 + n + m, g
| n :: m :: (r :: _ as g) when n + m = 10 -> 10 + r, g
| n :: m :: g -> n + m, g

To score a game, I keep track of how many frames I'm into the game, and stop at the tenth:

let rec score frame g =
 if frame = 10 then 0 else
 let n, g = score_frame g in
 n + score (succ frame) g

The game begins at the zeroth-frame, obviously:

# score 0 (game [1; 4; 4; 5; 6; 4; 5; 5; 10; 0; 1; 7; 3; 6; 4; 10; 2; 8; 6]) ;;
- : int = 133

10 minutes of thinking, and some looking around to realize that I had mistyped the scorecard. What TDD do you need, Uncle Bob?

11 comments:

Anonymous said...

Look the problem was already clearly defined. The definition exists! TDD isn't needed if you already have a clear problem.

TDD is really about a lack of requirements elicitation and using tests to make up for it.

Really you could've just done test first, yet TDD was unnecessary because you even had test cases already made!

assert 133 = somegame

Matías Giovannini said...

@Anonymous: The rules of the actual game were clearly defined, the "modeling of a real-world problem" was not. I had complete design freedom, and that's what TDD is supposed to guide you in. Utterly unnecessary.

Ten lines of code to solve this problem compared to Bob Martin's bumbling is an absolute indictment of OO and TDD, in my book.

Anonymous said...

Ten lines of code to solve this problem compared to Bob Martin's bumbling is an absolute indictment of OO and TDD, in my book.

Don't forget that Clojure lacks pattern matching, which makes a bit less comfortable than members of the ML family (multimethods just don't fit for some problems).

Tim Stewart said...

I'm interested in trying out your code but fsi version 1.9.6.16 is complaining about it:

error FS0191: Recursive values may not appear directly as a construction of the type 'FSharpList`1' within a recursive binding. This feature has been removed from the F# language. Consider using a record instead.

Would you please help an F# noob like me by showing how this might be done in the current CTP release of F#?

Thank you!

Matías Giovannini said...

@Tim: my using an infinite list was more of a show-off than anything. Notice that no bowling game can be longer than 21 balls, hence padding with at most 21 zeros suffice:

let rec repeat n x =

if n = 0 then []

else x :: repeat (n - 1) x



let game strikes = strikes @ repeat 21 0


HTH

Javier said...

well i think tdd was designed for large business apps developed by teams of programmers, not for simple pieces of code. TDD can make the simple code ridiculously complex.

But functional programming is approaching to business and may be TDD could help (or maybe not)

Scot McSweeney-Roberts said...

I've tried doing TDD with Scala, and the one thing I found was that it kept me from programming in a functional style. Maybe it was my lack of experience doing TDD with FP (and I never found any resources on the web - every TDD resource is TDD with OO), but I was left wondering if TDD is really compatible with FP.

Perhaps TDD is all the rage because it papers over some flaws in OO style development and most people are doing OO. If FP doesn't have those flaws, then you're not going to get the same benefits.

dm3 said...

@Scot

For functional testing check out Haskells' QuickCheck (IIRC, it's available in Scala too). There are some examples of its usage in Real World Haskell.

Jonathan said...

To be fair, TDD isn't really meant to help much with any program that can be expressed in 10 lines.

phil tomson said...

I like that infinite list trick... I didn't know you could do this in OCaml. This is the sort of thing that Haskelers brag about, isn't it? Of course they've got nicer syntax for it, but one can imagine a camlp4 extension that would help in that department.

So how exactly do infinite lists work in OCaml? Does OCaml just decide that after some number of recursions to create the list that it must be infinite and just stop there (filling in values later)?

Matías Giovannini said...

@Javier: The Bowling kata is supposed to be a textbook example of TDD. In my opinion, it derails from the moment they decide to model throws in an object-oriented way. But by all means look it up and form your own opinion.

@Scot: Whether TDD is compatible or not with FP is a matter of opinion, I think. Nothing in principle says they cannot go together. The majority of the practitioners in the FP field seem to agree that it is not needed.

@dn3: Note that QuickCheck is an entirely different approach to testing (one that I actually like): throw stuff at the function hoping that something falsifies a postcondition. It doesn't involve any coding beyond thinking about the postcondition itself. I don't, however, like to clutter my code with checks after the exploratory phase.

@Jonathan: Exactly. The idea is that code should be provably correct from inspection, the staple of FP papers: "Proof: by obvious induction." It does become obvious with practice, something that TDD doesn't seem to deliver.

@Phil: OCaml allows for the definition of recursive values. The infinite list is, in effect, a recursive data structure pointing back to itself. For that to work you must go through a type constructor, in this case '::' or List.cons.