Table-driven tennis scoring by Mark Seemann
Probably the most boring implementation of the tennis kata I've ever written.
Regular readers of this blog will know that I keep coming back to the tennis kata. It's an interesting little problem to attack from various angles.
The tennis scoring rules essentially describe a finite state machine, and while I was thinking about the state transitions involved, I came across an article by Michael McCandless about scoring tennis using finite-state automata.
This isn't the first time I've thought about simply enumerating all possible states in the state machine, but I decided to spend half an hour on actually doing it. While Michael McCandless shows that an optimisation is possible, his minimised version doesn't enable us to report all intermediary states with the correct labels. For example, he optimises away thirty-all by replacing it with deuce. The end result is still the same, in the sense that the minimised state machine will arrive at the same winner for the same sequence of balls, but it can't correctly report the score while the game is in progress.
For that reason, I decided to use his non-optimised state machine as a launch pad.
I used F# to enumerate all twenty states:
type Score = | LoveAll | FifteenLove | LoveFifteen | ThirtyLove | FifteenAll | LoveThirty | FortyLove | ThirtyFifteen | FifteenThirty | LoveForty | FortyFifteen | ThirtyAll | FifteenForty | GamePlayerOne | FortyThirty | ThirtyForty | GamePlayerTwo | AdvantagePlayerOne | Deuce | AdvantagePlayerTwo
Utterly boring, yes, but perhaps boring code might be good code.
Table-driven methods #
Code Complete describes a programming technique called table-driven methods. The idea is to replace branching instructions such as
switch with a lookup table. The book assumes that the table exists in memory, but in this case, we can implement the table lookup with pattern matching:
// Score -> Score let ballOne = function | LoveAll -> FifteenLove | FifteenLove -> ThirtyLove | LoveFifteen -> FifteenAll | ThirtyLove -> FortyLove | FifteenAll -> ThirtyFifteen | LoveThirty -> FifteenThirty | FortyLove -> GamePlayerOne | ThirtyFifteen -> FortyFifteen | FifteenThirty -> ThirtyAll | LoveForty -> FifteenForty | FortyFifteen -> GamePlayerOne | ThirtyAll -> FortyThirty | FifteenForty -> ThirtyForty | GamePlayerOne -> GamePlayerOne | FortyThirty -> GamePlayerOne | ThirtyForty -> Deuce | GamePlayerTwo -> GamePlayerTwo | AdvantagePlayerOne -> GamePlayerOne | Deuce -> AdvantagePlayerOne | AdvantagePlayerTwo -> Deuce
ballOne function returns the new score when player one wins a ball. It takes the old score as input.
I'm going to leave
ballTwo as an exercise to the reader.
Smoke test #
Does it work, then? Here's a few interactions with the API in F# Interactive:
> ballOne LoveAll;; val it : Score = FifteenLove > LoveAll |> ballOne |> ballTwo;; val it : Score = FifteenAll > LoveAll |> ballOne |> ballTwo |> ballTwo;; val it : Score = FifteenThirty > LoveAll |> ballOne |> ballTwo |> ballTwo |> ballTwo;; val it : Score = FifteenForty > LoveAll |> ballOne |> ballTwo |> ballTwo |> ballTwo |> ballOne;; val it : Score = ThirtyForty > LoveAll |> ballOne |> ballTwo |> ballTwo |> ballTwo |> ballOne |> ballTwo;; val it : Score = GamePlayerTwo
It looks like it's working.
Automated tests #
Should I be writing unit tests for this implementation?
I don't see how a test would be anything but a duplication of the two 'transition tables'. Given that the score is thirty-love, when player one wins the ball, then the new score should be forty-love. Indeed, the
ballOne function already states that.
We trust tests because they are simple. When the implementation is as simple as the test that would exercise it, then what's the benefit of the test?
To be clear, there are still compelling reasons to write tests for some simple implementations, but that's another discussion. I don't think those reasons apply here. I'll write no tests.
Code size #
While this code is utterly dull, it takes up some space. In all, it runs to 67 lines of code.
For comparison, the code base that evolves throughout my Types + Properties = Software article series is 65 lines of code, not counting the tests. When I also count the tests, that entire code base contains around 300 lines of code. That's more than four times as much code.
Preliminary research implies that bug count correlates linearly with line count. The more lines of code, the more bugs.
While I believe that this is probably a simplistic rule of thumb, there's much to like about smaller code bases. In total, this utterly dull implementation is actually smaller than a comparable implementation built from small functions.
Many software problems can be modelled as finite state machines. I find that this is often the case in my own field of line-of-business software and web services.
It's not always possible to exhaustively enumerate all states, because each 'type' of state carries data that can't practically be enumerated. For example, polling consumers need to carry timing statistics. These statistics influence how the state machine transitions, but the range of possible values is so vast that it can't be enumerated as types.
It may not happen often that you can fully enumerate all states and transitions of a finite state machine, but I think it's worthwhile to be aware of such refactoring opportunities. It might make your code dully simple.
Hi Mark, I have had a similar experience whilst coding a Shut the box game, when trying to detect if it was game over or not.
Originally it was a complex set of loops to calculate all the discrete summands for each roll of the dice, then checking if the remaining flaps were in that set. This was done along with a suite of tests for every possible combination set of summands up to 12 (for 2 dice).
Then whilst explaining the pain in writing this to a friend, they simply said, there's only a finite list, why not hard code them?, and that's what I went with, a dictionary with each possible roll from 2 dice, and the possible values from the flaps that could be used to meet that roll. All the tests were removed; as you pointed out, they would just be a reimplmentation of the table.
Dave, thank you for writing. It's good to hear that you have a similar experience. I wonder if it's constrained to game simulation, or if 'real-world' examples exist.