Haskell Bowling

At the Simple Design and Testing conference, Dan Mead bravely agreed to implement the infamous Bowling Game exercise, TDD style, in Haskell. It was fun and interesting. Here I present some discussion, his program, and a Java program in a similar style.

“New Paradigms”

Chet and I went to the Simple Design and Testing conference in West Chester, PA. Since his wife works at DaimlerChrysler, Chet was able to arrange a brand new Dodge Charger for us to drive to the conference. It was a longer drive than we had thought, especially since last Friday was rainy, and apparently everyone in Pennsylvania was out testing their rain tires or something. But the car was good and the Sirius radio was wonderful.

The conference was run in Open Space style and was a lot of fun. We decided to do mostly the Open Space (Conference Within a Conference (CWAC)) at Agile 2008, and to attend as many more of these little conferences as we can.

One of the sessions was labelled “New Paradigms”, so naturally we went to that. In for a penny, in for a digm or two, that’s our motto. The session turned out to be led by Dan Mead from the university, and he wanted to talk about Haskell. Haskell is a lazy functional programming language with a number of interesting characteristics including static typing, which is quite unusual for such languages. Dan’s basic thought was that in Haskell, programming is easier because the language matches your mind.

The audience, mostly industry types, took the position that the biggest issue in what we called “real world” software development is that the problem doesn’t match anyone’s mind. In particular, the problems we face aren’t particularly mathematical or recursive. At the same time, those of us who had used other functional languages and similarly compact languages agreed that where they apply, they can be very powerful.

Dan wanted to demo Haskell, and we asked him to do an experiment where he would TDD the bowling game. Bravely, he agreed to do it. (I think at the time he didn’t realize that he was facing the evil and Draconian Ron Jeffries. Little did he know …) But I’m a pussycat, as all here know, which is just fine unless you are a mouse or a bird. Anyway, we went down to the lab and Dan started coding. It went pretty well, though we ran out of time before we had the program quite right. Dan sent me his working copy Monday, and it looks like this. The blue part is the actual bowling scoring code — all of it!

{-
Bowling.hs
A haskell implementation of Ron Jeffries' bowling game exercise
By Dan Mead (d.w.mead at gmail dot com)
-}

module Bowling where

{-
Function: score
Desc: score computes the total for a properly formed list 
      that represents a game of bowling
-}

score :: [Int] -> Int --read as "score has the type int list mapped to an int"
score ([]) = 0
score (x:[]) = x 
score (x:y:[]) = x + y 
score (x:y:z:[]) = x + y + z
score (x:y:z:xs) = if  (x == 10)             then x + y + z +  score(y:z:xs) 
                   else if (((x + y) == 10)) then x + y + z +  score(z:xs)
                   else x + y + score(z:xs)

--some easy test variables, just enter them into hugs or winhugs
test1 = score [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
test2 = score (replicate 12 10) --replicate 12 10 makes a list of 12 10s
test3 = score (10:5:5: (replicate 17 0))
test4 = score (replicate 20 3)

{-
Test runs from hugs98:
Hugs.Base> :load "/home/dan/Bowling.hs"
Bowling> test1
0
Bowling> test2
300
Bowling> test3
30
Bowling> test4
60 
-}

Discussion

Let’s discuss the scoring code a bit: there are some observations that I think are interesting:

score ([]) = 0
score (x:[]) = x 
score (x:y:[]) = x + y 
score (x:y:z:[]) = x + y + z
score (x:y:z:xs) = if  (x == 10)             then x + y + z +  score(y:z:xs) 
                   else if (((x + y) == 10)) then x + y + z +  score(z:xs)
                   else x + y + score(z:xs)

This is a recursive implementation of bowing scoring, a fairly common approach to list processing that you’ll find in functional languages. The program might begin, if you were thinking of frames of pairs of rolls, with just this bit:

score ([]) = 0
score (x:y:xs) = x + y + score(xs)

This code uses Haskell’s match capability to describe two rules:

  1. If the input to the score function is an empty list, return zero.
  2. If the input to the score function is a list with at least two elements, the score is the sum of the two elements, plus the score of the rest of the list.

This is a pretty straightforward recursive implementation. Now let’s turn our attention back to the code we actually have:

score ([]) = 0
score (x:[]) = x 
score (x:y:[]) = x + y 
score (x:y:z:[]) = x + y + z
score (x:y:z:xs) = if  (x == 10)             then x + y + z +  score(y:z:xs) 
                   else if (((x + y) == 10)) then x + y + z +  score(z:xs)
                   else x + y + score(z:xs)
  1. The first item just stops the recursion, as before.
  2. I believe that the second rule, with the single element, cannot occur with the current rule set. There should be no case where the parsing will result in just one element, assuming the input is correct. (Which is the rule of this exercise.)
  3. The x:y:[] rule handles the case of a final, non-bonus frame. It’s there because of the subsequent rules which work whenever there are three or more elements.
  4. The x:y:z:[] rule handles the case of three rolls at the end of the game, i.e. a bonus roll. This rule is not, in my opinion, obvious or communicative. What it’s relying on is that it happens that if you roll a strike, you get ten + the next two rolls, but the first roll (x) equals ten, and if you roll a spare, the score is ten plus the next one roll, but the first two (x + y) sum to ten. When I observe this truth in my demonstrations, a significant portion of the audience objects, saying that it obscures the rules of the game.
  5. The x:y:z:xs rule does the bulk of the work. Essentially:
    1. If you have a strike, then score three balls, then treat the last two as part of a real frame and score them again: x + y + z + score(y:z:xs)
    2. If you have a spare, then score three balls, then treat the last one as part of a real frame, and score it again: x + y + z + score(z:xs)
    3. Otherwise, score the two rolls, and treat the third as part of a real frame to be stored again: x + y + score(z:xs)

This is all pretty straightforward, I think, except for the obfuscation of the rules of bowling that apperas in the x+y+z, as already mentioned.

Dan’s assertion was that the Haskell programs we get rather directly reflect our thoughts, and that they are compact and easy to understand. I would agree that with what we just figured out fresh in our mind, the code is clear — and it’s certainly compact. However, walking up to it, I do not find it clear. It is recursive, and its rules are a bit odd, mostly due to the need in the x:y:z rules to look for an item that may not be there, resulting in the special ending rules like x:y:[] and x:y:z:[]. And we are left with that tag rule x:[], which appears to be redundant, but it’s really hard to be sure.

Nonetheless, it’s an interesting implementation that seems to get the right answers, in very few lines. And it was quite brave of Dan to sit in front of a bunch of people and try to improvise a solution. I find that scary when I do it, at least. So thanks to Dan for an interesting and thought-provoking session.

A Java Example

As an experiment, I decided to code up an example in Java that follows the style of this Haskell version, insofar as that makes sense. As opposed to my usual style of showing each individual move of the development, this time I’ll present the program as it presently stands. First the tests:

package haskellBowling;

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class BowlingGameTest {
    BowlingGame game;

    @Before public void setUp() throws Exception {
        game = new BowlingGame();
    }

    @Test public void hookup() {
        assertTrue(true);
    }

    @Test public void opens() throws Exception {
        assertEquals(60, game.score(new Integer[] 
          {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}));
    }

    @Test public void spare() throws Exception {
        assertEquals(22, game.score(new Integer[] 
          {6,4,5,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}));
    }

    @Test public void perfect() throws Exception {
        assertEquals(300, game.score(new Integer[] 
          {10,10,10,10,10,10,10,10,10,10,10,10}));
    }

    @Test public void alternatingStrikeSpare() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10}));
    }

    @Test public void alternatingSpareStrike() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5}));
    }

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

These are pretty much the standard tests that one uses, with the addition of the trainingSpare test, which I wrote because I wasn’t sure whether a spare at the end of the game would work. This uncertainty came, I think, from the odd merging of strikes and spares into three-element frames that just add up the three balls, and general uncertainty about whether the recursion stopped correctly.

Now, let’s look at the implementation. I’ll present it bit by bit and discuss each bit.

public class BowlingGame {
    List<Integer> rolls;

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

Above is the class definition, with just one member variable, a list of rolls. The only public method just takes the roll array that the tests use, slams it into the list, and then calls a private score() method, which, together with some helper methods, does all the work, and echos the style of Dan’s Haskell method:

   private Integer score() {
        if (rolls.size() == 0) return 0;
        if (rolls.size() == 3) return thisFrameScore();
        return thisFrameScore() + remainingScore();
    }

Above, we consider three cases. If the list is empty, we are done, and we return zero to stop the recursion. Looking at it now, this first line seems odd: it appears that we would get to the end and always return a total score of zero. That turns out not to be the case, since the tests run, but it’s not clear.

The second line says that if there are three balls left, we can just return the score of that frame. This, too, seems odd to me now, as it appears that when we get to the end of a long series of frames, we’d just return the last one.

The final line is the recursive one. It returns the score for the current frame, PLUS the score of the rest of the game, in the remainingScore() method:

   private Integer remainingScore() {
        setRemainingRolls();
        return score();
    }

    private void setRemainingRolls() {
        rolls =  rolls.subList(frameSize(rolls), rolls.size());
    }

    private int frameSize(List<Integer> rolls) {
        return isStrike()? 1: 2;
    }

The remainingScore() method just shrinks the rolls list by removing whatever rolls have been consumed. In Haskell, we can refer directly to the “rest” of the list, and the Haskell code constructs it on the fly. We don’t have that luxury, so instead we sublist the rolls list, removing however many rolls are in the current frame. That’s always 2, unless the frame is a strike, in which case it’s 1. Then remainingScore returns the result of a recursive call to score.

And this explains why it all works. If we’re on the last frame and it’s a bonus frame, we’ll have been called from the ninth frame, which will be holding the score so far, and adding the frame score of the final frame to it, via line 2. If we’re on an ordinary last frame, we’ll score it without looking for a bonus, remove both rolls, then call recursively to add in the “eleventh” absent frame, which returns zero from the first line, ending the recursion and leaving us with the right final answer.

I still find this a bit obscure, and it has only been about one day since I read this code. We’ll see later about whether we can make it better, but I have my doubts. Recursive methods tend to be confusing, in my opinion. Moving on, let’s look at how the frames are scored in thisFrameScore():

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

Here, we just add up “this frame’s rolls”, which is the sublist of the list containing the rolls referenced by the frame. That’s always either two (for open frame) or three (for strike or spare):

   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;
    }

In thisFrameRolls we just sublist the list, taking from the first roll to as many rolls (2 or 3) we need. We compute the 2 or 3 by deciding if the frame is a “mark”, i.e. a strike or spare, using the standard definition of strike and spare, as a frame where the first (and only) roll is a ten, or where the sum of the two rolls is a ten.

Here, for your convenience, is the whole BowlingGame class as a unit:

package haskellBowling;

import java.util.Arrays;
import java.util.List;

public class BowlingGame {
    List<Integer> rolls;

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

    private Integer score() {
        if (rolls.size() == 0) return 0;
        if (rolls.size() == 3) return thisFrameScore();
        return thisFrameScore() + remainingScore();
    }

    private Integer remainingScore() {
        setRemainingRolls();
        return score();
    }

    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 void setRemainingRolls() {
        rolls =  rolls.subList(frameSize(rolls), rolls.size());
    }

    private int frameSize(List<Integer> rolls) {
        return isStrike()? 1: 2;
    }
}

Assessing the Java, and the Approach

The Java is certainly much more code, and while it expresses some ideas that the Haskell doesn’t, such as strike and spare and mark, the Haskell would be much shorter even if it were extended to address those concerns. And shorter is generally preferable.

The recursive solution, however, is questionable on more fundamental grounds. A game of bowling consists of ten frames, not less or more, and the “ten-ness” of the game is not represented in the recursive solutions at all. Even if we let that slide, the recursive solutions make it a bit hard to understand what’s going on. And, as I also mentioned, the x+y+z trick raises objections from a number of observers, in that the rules of the game do not make clear that the rolls scored for strike and spare are the same rolls, yet the code takes advantage of that fact.

Dan’s assertion, as I recall it, was that Haskell lets us express the program “in the way we think”. On the contrary, what Haskell does in my opinion is let us express the program in the way Haskell thinks, in a concise form. And we learn to think the way Haskell thinks, not because humans normally think in terms of pattern matches and recursion, but because we learn to work that way. And having learned it, it seems natural. Well, having learned Java and C# and SNOBOL and twenty other languages, they all seemed natural too, but I confess that I have liked the expressive ones like LISP and Smalltalk more than I did, say FORTRAN.

I’m certainly not knocking Haskell: it looks like it would be fun, and for some class of problems, perhaps a good way to go. I’m concerned that no one who wasn’t there may ever be able to read another person’s Haskell program, but lord knows it’s not easy to write code in any language that is easy to understand for a new reader.

What we see here is that it is possible to emulate part of the Haskell solution in Java fairly easily, but with lots more code, and that other parts, such as the pattern matching, are quite difficult. It might be amusing to try to do the same solution in, say, Ruby, which would probably be more compact and perhaps would cleave closer to the Haskell style.

And for a real mind-blower, Chet and I were thinking of this: How about writing a recursive Regex solution that works on text strings, taking a text string consisting of all the rolls, and transforming it to a new string where you can convert all the values in it and then just add them up. For example, putting plusses in front of added strings, we might convert a perfect game to a score string this way:

  1. 10 10 10 10 10 10 10 10 10 10 10 10
  2. 10 +10 +10 10 +10 +10 10 +10 +10 10 +10 +10 10 +10 +10
    10 +10 +10 10 +10 +10 10 +10 +10 10 +10 +10 10 10 10

Now THAT would be obscure!

Thanks, and Thanks

Thanks to Dan for calling the session and working the example in public. Thanks to the security guy who asked us if we were allowed to be in the lab after hours and left when we assured him that we were. Thanks to Naresh and everyone involved in the conference. And thanks to you for reading.

Posted on:

Written by: Ron Jeffries

Categorization: Articles

Recent Articles

Codea Calculator

Based on a simple example on the codea.io forums, I decided to write an article showing all the stuff I might do on a production calculator project. Wow.

XProgNew – Working with layout

I’ve been trying to learn some things about how the new implementation will handle the front page. The front page has a top row the most recent articles in two categories, “Beyond Agile” and “The Annals of Kate Oneal”, and …