Lots of fine feedback on the Haskell article. Alternative implementations in Java, Ruby, and even Haskell! Much fun! PLUS!! FATAL FLAW DISCOVERED IN RECURSIVE VERSIONS!!

Letters Come Pouring In!

The little Haskell example has triggered a fair amount of email. I’ll summarize some of it here. Thanks to everyone who has chimed in!

Late breaking news: Recursive versions flawed. Details below.

A Ruby Version

Let’s begin with something pretty. Pit Capitain sent along this Ruby version of the game, which matches Dan’s Haskell code rather nicely:

   def score x = 0, y = 0, z = 0, *xs
     case
     when xs.empty?   then x + y + z                   # last frame
     when x == 10     then x + y + z + score(y,z,*xs)  # strike
     when x + y == 10 then x + y + z + score(z,*xs)    # spare
     else                  x + y + score(z,*xs)        # normal
     end
   end

… with test cases …

   require "test/unit"

   class ScoreTest < Test::Unit::TestCase

     def test_all_zero
       assert_equal 0, score(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
     end

     def test_all_ten
       assert_equal 300, score(10,10,10,10,10,10,10,10,10,10,10,10)
     end

     def test_strike
       assert_equal 30, score(10,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
     end

     def test_neither_strike_nor_spare
       assert_equal 60, score(3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)
     end

   end

Pit’s example shows how nicely Ruby’s “splat” operator, also called “unary unarray”, lets us do Haskell’s pattern-matching trick in Ruby. It makes me wonder why I ever program in any other language. Thanks, Pit!

But wait! Pit writes again. Based on something I said, he finds a bug in all these implementations. Watch this …

Recursion Defect

Pit thought about my remarks to the effect that the game has an inherent “ten-ness” about it that the recursive implementations don’t embody. Better yet, he came up with some tests. Here’s the scenario. Whenever the bowling game ends with three rolls, with the first one a ten, Dan’s implementation, Pit’s and my Java one, score those three rolls and end the scoring. But there are two possible ways to end the game with three rolls, starting with a ten, and they get different scores!

If the game consisted of nine empty frames, followed by a strike, 2, 3, the total game score would be 15. But if you roll eight empty frames, then a strike in frame nine, then 2,3 in frame ten, the score is 20! (15 for the strike frame, plus the two-three is scored again as a 5 in the tenth frame! Here are the tests in Java, and sure enough, the second one fails in my code:

   @Test public void pitStrikeFinalFrame() throws Exception {
        assertEquals(15, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,2,3}));
    }

    @Test public void pitStrikeNinthFrame() throws Exception {
        assertEquals(20, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 2,3}));
    }

Pit hypothesizes, and I’m inclined to agree, that you simply must deal with the tenth frame differently in all these recursive versions. He offers this new Ruby version:

   def score r, f=1
     x, y, z, *xs = r
     case
     when f == 10     then x+y + (z or 0)                 # last frame
     when x == 10     then x+y+z + score([y,z,*xs], f+1)  # strike
     when x + y == 10 then x+y+z + score([z,*xs], f+1)    # spare
     else                  x+y   + score([z,*xs], f+1)    # normal
     end
   end

Pit has introduced a new variable, f for frame, where he counts the frames and handles the tenth specially. As you’ll see below, Alistair Bayley created a version that used a similar technique.

My intuition says that all the recursive versions that don’t check the frame number are going to be vulnerable to this same flaw. More important is the discovery that the intuition of all these bright programmers – and me – was wrong in thinking that the recursive versions worked correctly.

Is there a larger lesson to be learned here? Perhaps so. More on this at the bottom. Meanwhile, let’s continue to catch up with the mail:

Alistair's Alternative in Haskell

Alistair Bayley had sent me a Haskell version about a year ago, that I never published, based on my StreamBowling example. Here’s his version:

 scoreGame rolls = scoreFrames rolls 10

 scoreFrames rolls 0 = 0
 scoreFrames rolls frameCnt =
   scoreFrame rolls + scoreFrames (advance rolls) (frameCnt - 1)

 scoreFrame rolls =
   if isMark rolls then scoreMark rolls
   else scoreOpen rolls

 advance rolls = if isStrike rolls then drop 1 rolls else drop 2 rolls

 isStrike  (a:_)     = a == 10
 isSpare   (a:b:_)   = (a + b) == 10
 isMark    rolls     = isStrike rolls || isSpare rolls
 scoreMark (a:b:c:_) = a + b + c
 scoreOpen (a:b:_)   = a + b

Alistair’s version is a bit longer, but also a bit more expressive of what’s going on. In the Agile biz, we’re interested in our programs lasting a long time and being maintainable, so we focus quite a bit on readability, even if it does cost us a little in compactness.

Alistair’s version explicitly includes the ten frame notion. The second parameter to the scoreFrames function is the frame count, and he exits (= 0) when the frame count is down to zero. He uses a separate scoreFrame function to score the individual frames.

This version takes a little untangling to read, as does any program with small methods or functions. But the use of mnemonic names for the functions means that you don’t need to read beyond any point if you don’t want to know more details. I myself admire Dan’s version for its compactness, and Alistair’s for its readability.

Note added later: It also appears that I should admire Alistair’s version for working!!

Tom's Coding Dojo Haskell Version

Tom Moertel wrote a Haskell version of Bowling in response to a meeting the Pittsburgh Coding Dojo had on the subject. It goes like this:

     -- | Compute the score for the list of rolls 'rs'

     score rs = sc 0 1 rs

     sc s 11 _  = s
     sc s f rs  = case rs of
         10:rs'                -> sc' 3 rs'  -- strike
         x:y:rs' | x + y == 10 -> sc' 3 rs'  -- spare
                 | otherwise   -> sc' 2 rs'  -- normal
         _                     -> error "ill-formed sequence of rolls"
       where
         sc' n rs' = sc (s + sum (take n rs)) (f + 1) rs'

Tom has more discussion, and some very compact tests in HUnit, on his blog entry about this. Tom also offers a reference to QuickCheck, an automated testing tool for Haskelll and other languages.

Tom also pointed to Dave Thomas’s “Sorting It Out” kata, and to his solution. Check them out.

Tom’s version doesn’t have the Pit bug. The reason is, basically, that it is processing ten frames always, rather than relying on a characteristic in the roll stream to decide when to stop.

Anthony Takes Me to Task

Anthony Williams objects strongly to my Java version as being “hideous”, on a discussion on the testdrivendevelopment and extremeprogramming Yahoo groups. (The xp list discussion goes on a bit longer than the other: they’re identical up until the TDD one stops.)

Anthony’s primary objection is my use of the member variable rolls to avoid passing the sublists around as a parameter. It’s a valid objection. He refers to Martin Fowler’s code smell, “Temporary Field”, p. 84 of Refactoring.

Now, I don’t mind an object where every method looks at a field, and the field changes value over time as the object’s methods run. In this case, the variable basically counts down what’s going on, and there is no intermediate point where an outsider ever sees the object in an intermediate state. Anthony disagrees, which is certainly a valid position. To nail down his point, he offers an untested Java version that looks better than mine:

public class BowlingGame {
    final List<Integer> rolls;

    public BowlingGame(Integer[] rollsArray) {
        rolls = Arrays.asList(rollsArray);
    }

    public BowlingGame(List<Integer> rolls_) {
        rolls = rolls_;
    }

    public Integer score() {
        if (rolls.size() == 0) return 0;
        if (rolls.size() == 3) return thisFrameScore();
        return thisFrameScore() + new BowlingGame(remainingRolls()).score();
    }

    private List<Integer> remainingRolls() {
        return rolls.subList(frameSize(), rolls.size());
    }

    private Integer thisFrameScore() {
        Integer frameScore = 0;
        for (Integer roll : thisFramesRolls()) 
            frameScore += roll;
        return frameScore;
    }

    private List<Integer> thisFramesRolls() {
        return rolls.subList(0, numberOfRollsToScore());
    }

    private int numberOfRollsToScore() {
        return (isMark()) ? 3: 2;
    }

    private boolean isMark() {
        return isStrike() || isSpare();
    }

    private boolean isStrike() {
        return rolls.get(0) == 10;
    }

    private boolean isSpare() {
        return rolls.get(0) + rolls.get(1) == 10;
    }

    private int frameSize() {
        return isStrike()? 1: 2;
    }
}

This version certainly shows that I could have done better. No surprise to me, I’m sure it’s generally possible to do better than I do. In Anthony’s proposed solution, I’m not entirely comfortable with creating a new instance of BowlingGame on every cycle, but that’s probably an inappropriate fear on my part. The recursion line, highlighted above, is a bit more complex than I like to see. It was the complexity of my corresponding line that pushed me in the direction I went. Mine was worse than his, though, and I like his better.

It appears, as well, that I would have done well to show my work on coming up with the Java version I displayed. The one that’s there is refactored quite a bit from where it began as a simple transcription of the Haskell code.

Anthony and I have exchanged three or four public mails on this topic, on the lists. You might find them interesting to look at. I believe that all the Java versions we’ve discussed are just a few refactorings away from each other. Anthony’s not so sure.

Pit’s discovered bug renders all this discussion somewhat moot. Recall that Kent Beck’s definition of Simple Code begins with “Runs all the tests”, which ought to translate into “Works”. My program doesn’t work, and Anthony’s almost certainly has the same defect. How many angels can dance on the point of a program that doesn’t work?

Summing Up

This little example has caused a lot of conversation. I’ve tried to summarize the private notes here, and to point to the public ones. It’s a delight to know that people look at this stuff, and to see different viewpoints coming out. It often seems to me that we will benefit from displaying more code, and discussing it, as part of learning better what we think and how to do this work. That’s why I publish these things … thanks for looking at them and for helping out!

Added After Pit's Defect Discovery

This is fascinating! Dan’s original version seems to have an obscure but fatal flaw that was inherited by all the various descendents in Java and Ruby. The flaw is hard to see, and occurs where such things often do, when trying to unwind the recursion in a recursive solution. I’m not inclined to try to “fix” my Java version, but I’ll look at it for a bit before finally deciding. I am more inclined to rewrite the top part of it, changing it to have an explicit loop of ten, which is what all the procedural versions we’ve ever seen wind up with. I’ll leave it open to my other correspondents to decide whether it’s worth chasing this problem further, or not.

My conclusion is that while languages like Haskell are very powerful and compact, it’s still quite easy to have subtle defects in the code we write. This leads me to think that, were I working in such a language again, I’d continue to follow the TDD discipline, and would continue to try to make the code more expressive, even at cost in compactness. And I’ll be a bit more careful with recursive solutions for a while, since this one has burned my fingers badly. Not the first time, I might add, since I wrote my first recursive program somewhere back around 1963 or 1964. And, sadly, probably not the last, since I hope to continue programming well into this century, and I expect to make quite a few mistakes along the way.

Thanks for tuning in. I’ll be interested to see what reaction this article gets, with its discovery of a flaw, and its various alternate versions.