Types + Properties = Software: finite state machine by Mark Seemann
How to compose the tennis game code into a finite state machine.
This article is the seventh in a series of articles that demonstrate how to develop software using types and properties. In the previous article, you saw how to define the initial state of a tennis game. In this article, you'll see how to define the tennis game as a finite state machine.
The source code for this article series is available on GitHub.
Scoring a sequence of balls #
Previously, you saw how to score a game in an ad-hoc fashion:
> let firstBall = score newGame PlayerTwo;;
val firstBall : Score = Points {PlayerOnePoint = Love;
PlayerTwoPoint = Fifteen;}
> let secondBall = score firstBall PlayerOne;;
val secondBall : Score = Points {PlayerOnePoint = Fifteen;
PlayerTwoPoint = Fifteen;}
You'll quickly get tired of that, so you may think that you can do something like this instead:
> newGame |> (fun s -> score s PlayerOne) |> (fun s -> score s PlayerTwo);;
val it : Score = Points {PlayerOnePoint = Fifteen;
PlayerTwoPoint = Fifteen;}
That does seem a little clumsy, though, but it's not really what you need to be able to do either. What you'd probably appreciate more is to be able to calculate the score given a sequence of wins. A sequence of wins is a list of Player values; for instance, [PlayerOne; PlayerOne; PlayerTwo] means that player one won the first two balls, and then player two won the third ball.
Since we already know the initial state of a game, and how to calculate the score for each ball, it's a one-liner to calculate the score for a sequence of balls:
let scoreSeq wins = Seq.fold score newGame wins
This function has the type Player seq -> Score. It uses newGame as the initial state of a left fold over the wins. The aggregator function is the score function.
You can use it with a sequence of wins, like this:
> scoreSeq [PlayerOne; PlayerOne; PlayerTwo];;
val it : Score = Points {PlayerOnePoint = Thirty;
PlayerTwoPoint = Fifteen;}
Since player one won the first two balls, and player two then won the third ball, the score at that point is thirty-fifteen.
Properties for the state machine #
Can you think of any properties for the scoreSeq function?
There are quite a few, it turns out. It may be a good exercise if you pause reading for a couple of minutes, and try to think of some properties.
If you have a list of properties, you can compare them with the ones I though of.
Before we start, you may find the following helper functions useful:
let isPoints = function Points _ -> true | _ -> false let isForty = function Forty _ -> true | _ -> false let isDeuce = function Deuce -> true | _ -> false let isAdvantage = function Advantage _ -> true | _ -> false let isGame = function Game _ -> true | _ -> false
These can be useful to express some properties, but I don't think that they are generally useful, so I put them together with the test code.
Limited win sequences #
If you look at short win sequences, you can already say something about them. For instance, it takes at least four balls to finish a game, so you know that if you have fewer wins than four, the game must still be on-going:
[<Property>] let ``A game with less then four balls isn't over`` (wins : Player list) = let actual : Score = wins |> Seq.truncate 3 |> scoreSeq test <@ actual |> (not << isGame) @>
The built-in function Seq.truncate returns only the n (in this case: 3) first elements of a sequence. If the sequence is shorter than that, then the entire sequence is returned. The use of Seq.truncate 3 guarantees that the sequence passed to scoreSeq is no longer than three elements long, no matter what FsCheck originally generated.
Likewise, you can't reach deuce in less than six balls:
[<Property>] let ``A game with less than six balls can't be Deuce`` (wins : Player list) = let actual = wins |> Seq.truncate 5 |> scoreSeq test <@ actual |> (not << isDeuce) @>
This is similar to the previous property. There's one more in that family:
[<Property>] let ``A game with less than seven balls can't have any player with advantage`` (wins : Player list) = let actual = wins |> Seq.truncate 6 |> scoreSeq test <@ actual |> (not << isAdvantage) @>
It takes at least seven balls before the score can reach a state where one of the players have the advantage.
Longer win sequences #
Conversely, you can also express some properties related to win sequences of a minimum size. This one is more intricate to express with FsCheck, though. You'll need a sequence of Player values, but the sequence should be guaranteed to have a minimum length. There's no built-in in function for that in FsCheck, so you need to define it yourself:
// int -> Gen<Player list> let genListLongerThan n = let playerGen = Arb.generate<Player> let nPlayers = playerGen |> Gen.listOfLength (n + 1) let morePlayers = playerGen |> Gen.listOf Gen.map2 (@) nPlayers morePlayers
This function takes an exclusive minimum size, and returns an FsCheck generator that will generate Player lists longer than n. It does that by combining two of FsCheck's built-in generators. Gen.listOfLength generates lists of the requested length, and Gen.listOf generates all sorts of lists, including the empty list.
Both nPlayers and morePlayers are values of the type Gen<Player list>. Using Gen.map2, you can concatenate these two list generators using F#'s built-in list concatenation operator @. (All operators in F# are also functions. The (@) function has the type 'a list -> 'a list -> 'a list.)
With the genListLongerThan function, you can now express properties related to longer win sequences. As an example, if the players have played more than four balls, the score can't be a Points case:
[<Property>] let ``A game with more than four balls can't be Points`` () = let moreThanFourBalls = genListLongerThan 4 |> Arb.fromGen Prop.forAll moreThanFourBalls (fun wins -> let actual = scoreSeq wins test <@ actual |> (not << isPoints) @>)
As previously explained, Prop.forAll expresses a property that must hold for all lists generated by moreThanFourBalls.
Correspondingly, if the players have played more than five balls, the score can't be a Forty case:
[<Property>] let ``A game with more than five balls can't be Forty`` () = let moreThanFiveBalls = genListLongerThan 5 |> Arb.fromGen Prop.forAll moreThanFiveBalls (fun wins -> let actual = scoreSeq wins test <@ actual |> (not << isForty) @>)
This property is, as you can see, similar to the previous example.
Shortest completed game #
Do you still have your list of tennis game properties? Let's see if you thought of this one. The shortest possible way to complete a tennis game is when one of the players wins four balls in a row. This property should hold for all (two) players:
[<Property>] let ``A game where one player wins all balls is over in four balls`` (player) = let fourWins = Seq.init 4 (fun _ -> player) let actual = scoreSeq fourWins let expected = Game player expected =! actual
This test first defines fourWins, of the type Player seq. It does that by using the player argument created by FsCheck, and repeating it four times, using Seq.init.
The =! operator is a custom operator defined by Unquote, an assertion library. You can read the expression as expected must equal actual.
Infinite games #
The tennis scoring system turns out to be a rich domain. There are still more properties. We'll look at a final one, because it showcases another way to use FsCheck's API, and then we'll call it a day.
An interesting property of the tennis scoring system is that a game isn't guaranteed to end. It may, theoretically, continue forever, if players alternate winning balls:
[<Property>] let ``A game where players alternate never ends`` firstWinner = let alternateWins = firstWinner |> Gen.constant |> Gen.map (fun p -> [p; other p]) |> Gen.listOf |> Gen.map List.concat |> Arb.fromGen Prop.forAll alternateWins (fun wins -> let actual = scoreSeq wins test <@ actual |> (not << isGame) @>)
This property starts by creating alternateWins, an Arbitrary<Player list>. It creates lists with alternating players, like [PlayerOne; PlayerTwo], or [PlayerTwo; PlayerOne; PlayerTwo; PlayerOne; PlayerTwo; PlayerOne]. It does that by using the firstWinner argument (of the type Player) as a constant starting value. It's only constant within each test, because firstWinner itself varies.
Using that initial Player value, it then proceeds to map that value to a list with two elements: the player, and the other player, using the other function. This creates a Gen<Player list>, but piped into Gen.listOf, it becomes a Gen<Player list list>. An example of the sort of list that would generate could be [[PlayerTwo; PlayerOne]; [PlayerTwo; PlayerOne]]. Obviously, you need to flatten such lists, which you can do with List.concat; you have to do it inside of a Gen, though, so it's Gen.map List.concat. That gives you a Gen<Player list>, which you can finally turn into an Arbitrary<Player list> with Arb.fromGen.
This enables you to use Prop.forAll with alternateWins to express that regardless of the size of such alternating win lists, the game never reaches a Game state.
Summary #
In this article, you saw how to implement a finite state machine for calculating tennis scores. It's a left fold over the score function, always starting in the initial state where both players are at love. You also saw how you can express various properties that hold for a game of tennis.
In this article series, you've seen an extensive example of how to design with types and properties. You may have noticed that out of the six example articles so far, only the first one was about designing with types, and the next five articles were about Property-Based Testing. It looks as though not much is gained from designing with types.
On the contrary, much is gained by designing with types, but you don't see it, exactly because it's efficient. If you don't design with types in order to make illegal states unrepresentable, you'd have to write even more automated tests in order to test what happens when input is invalid. Also, if illegal states are representable, it would have been much harder to write Property-Based Tests. Instead of trusting that FsCheck generates only valid values based exclusively on the types, you'd have to write custom Generators or Arbitraries for each type of input. That would have been even more work than you've seen in this articles series.
Designing with types makes Property-Based Testing a comfortable undertaking. Together, they enable you to develop software that you can trust.
If you're interested in learning more about Property-Based Testing, you can watch my introduction to Property-based Testing with F# Pluralsight course.
