Roman numerals via property-based TDD by Mark Seemann
An example of doing the Roman numerals kata with property-based test-driven development.
The Roman numerals kata is a simple programming exercise. You should implement conversion to and from Roman numerals. This always struck me as the ultimate case for example-driven development, but I must also admit that I've managed to get stuck on the exercise doing exactly that: throwing more and more examples at the problem. Prompted by previous successes with property-based testing, I wondered whether the problem would be more tractable if approached with property-based testing. This turned out to be the case.
Single values #
When modelling a problem with property-based testing, you should attempt to express it in terms of general rules, but even so, the fundamental rule of Roman numerals is that there are certain singular symbols that have particular numeric values. There are no overall principles guiding these relationships; they simply are. Therefore, you'll still need to express these singular values as particular values. This is best done with a simple parametrised test, here using xUnit.net 2.1:
[<Theory>] [<InlineData("I", 1)>] [<InlineData("V", 5)>] [<InlineData("X", 10)>] [<InlineData("L", 50)>] [<InlineData("C", 100)>] [<InlineData("D", 500)>] [<InlineData("M", 1000)>] let ``elemental symbols have correct values`` (symbol : string) expected = Some expected =! Numeral.tryParseRoman symbol
The =! operator is a custom operator defined by Unquote (3.1.1), an assertion library. You can read it as must equal; that is, you can read this particular assertion as some expected must equal tryParseRoman symbol.
As you can see, this simple test expresses the relationship between the singular Roman numeral values and their decimal counterparts. You might still consider this automated test as example-driven, but I more think about it as establishing the ground rules for how Roman numerals work. If you look at the Wikipedia article, for instance, it also starts explaining the system by listing the values of these seven symbols.
Round-tripping #
A common technique when applying property-based testing to parsing problems is to require that values can round-trip. This should also be the case here:
let romanRange = Gen.elements [1..3999] |> Arb.fromGen [<Property(QuietOnSuccess = true)>] let ``tryParse is the inverse of toRoman`` () = Prop.forAll romanRange <| fun i -> test <@ Some i = (i |> Numeral.toRoman |> Option.bind Numeral.tryParseRoman) @>
This property uses FsCheck (2.2.4). First, it expresses a range of relevant integers. For various reasons (that we'll return to) we're only going to attempt conversion of the integers between 1 and 3,999. The value romanRange has the type Arbitrary<int>, where Arbitrary<'a> is a type defined by FsCheck. You can think of it as a generator of random values. In this case, romanRange generates random integers between 1 and 3,999.
When used with Prop.forAll, the property states that for all values drawn from romanRange, the anonymous function should succeed. The i argument within that anonymous function is populated by romanRange, and the function is executed 100 times (by default).
The test function is another Unquote function. It evaluates and reports on the quoted boolean expression; if it evaluates to true, nothing happens, but it throws an exception if it evaluates to false.
The particular expression states that if you call toRoman with i, and then call tryParseRoman with the return value of that function call, the result should be equal to i. Both sides should be wrapped in a Some case, though, since both toRoman and tryParseRoman might also return None. For the values in romanRange, however, you'd expect that the round-trip always succeeds.
Additivity #
The fundamental idea about Roman numerals is that they are additive: I means 1, II means (1 + 1 =) 2, XXX means (10 + 10 + 10 =) 30, and MLXVI means (1000 + 50 + 10 + 5 + 1 =) 1066. You simply count and add. Yes, there are special rules for subtractive shorthand, but forget about those for a moment. If you have a Roman numeral with symbols in strictly descending order, you can simply add the symbol values together.
You can express this with FsCheck. It looks a little daunting, but actually isn't that bad. I'll show it first, and then walk you through it:
[<Property(QuietOnSuccess = true)>] let ``symbols in descending order are additive`` () = let stringRepeat char count = String (char, count) let genSymbols count symbol = [0..count] |> List.map (stringRepeat symbol) |> Gen.elements let thousands = genSymbols 3 'M' let fiveHundreds = genSymbols 1 'D' let hundreds = genSymbols 3 'C' let fifties = genSymbols 1 'L' let tens = genSymbols 3 'X' let fives = genSymbols 1 'V' let ones = genSymbols 3 'I' let symbols = [thousands; fiveHundreds; hundreds; fifties; tens; fives; ones] |> Gen.sequence |> Gen.map String.Concat |> Arb.fromGen Prop.forAll symbols <| fun s -> let actual = Numeral.tryParseRoman s let expected = s |> Seq.map (string >> Numeral.tryParseRoman) |> Seq.choose id |> Seq.sum |> Some expected =! actual
The first two lines are two utility functions. The function stringRepeat has the type char -> int -> string. It simply provides a curried form of the String constructor overload that enables you to repeat a particular char value. As an example, stringRepeat 'I' 0 is "", stringRepeat 'X' 2 is "XX", and so on.
The function genSymbols has the type int -> char -> Gen<string>. It returns a generator that produces a repeated string no longer than the specified length. Thus, genSymbols 3 'M' is a generator that draws random values from the set [""; "M"; "MM"; "MMM"], genSymbols 1 'D' is a generator that draws random values from the set [""; "D"], and so on. Notice that the empty string is one of the values that the generator may use. This is by design.
Using genSymbols, you can define generators for all the symbols: up to three thousands, up to one five hundreds, up to three hundreds, etc. thousands, fiveHundreds, hundreds, and so on, are all values of the type Gen<string>.
You can combine all these string generators to a single generator using Gen.sequence, which takes a seq<Gen<'a>> as input and returns a Gen<'a list>. In this case, the input is [thousands; fiveHundreds; hundreds; fifties; tens; fives; ones], which has the type Gen<string> list, so the output is a Gen<string list> value. Values generated could include ["MM"; ""; ""; ""; "X"; ""; ""], [""; "D"; "CC"; "L"; "X"; "V"; ""], and so on.
Instead of lists of strings, you need single string values. These are easy to create using the built-in method String.Concat. You have to do it within a Gen value, though, so it's Gen.map String.Concat. Finally, you can convert the resulting Gen<string> to an Arbitrary using Arb.fromGen. The final symbols value has the type Arbitrary<string>. It'll generate values such as "MMX" and "DCCLXV".
This is a bit of work to ensure that proper Roman numerals are generated, but the rest of the property is tractable. You can use FsCheck's Prop.forAll to express the property that when tryParseRoman is called with any of the generated numerals, the return value is equal to the expected value.
The expected value is the sum of the value of each of the symbols in the input string, s. The string type implements the interface char seq, so you can map each of the characters by invoking tryParseRoman. That gives you a int option values. You can use Seq.choose id to throw away any None values there may be, and then Seq.sum to calculate the sum of the integers. Finally, you can pipe the sum into the Some case constructor to turn expected into an int option, which matches the type of actual.
Now that you have expected and actual values, you can assert that these two values must be equal to each other. This property states that for all strictly descending numerals, the return value must be the sum of the constituent symbols.
Subtractiveness #
The principal rule for Roman numerals is that of additivity, but if you only apply the above rules, you'd allow numerals such as IIII for 4, LXXXX for 90, etc. While there's historical precedent for such notation, it's not allowed in 'modern' Roman numerals. If there are more than three repeated characters, you should instead prefer subtractive notation: IV for 4, XC for 90, and so on.
Subtractive notation is, however, only allowed within adjacent groups. Logically, you could write 1999 as MIM, but this isn't allowed. The symbol I can only be used to subtract from V and X, X can only subtract from L and C, and C can only subtract from D and M.
Within these constraints, you have to describe the property of subtractive notation. Here's one way to do it:
type OptionBuilder() = member this.Bind(v, f) = Option.bind f v member this.Return v = Some v let opt = OptionBuilder() [<Property(QuietOnSuccess = true)>] let ``certain symbols in ascending are subtractive`` () = let subtractive (subtrahend : char) (minuends : string) = gen { let! minuend = Gen.elements minuends return subtrahend, minuend } let symbols = Gen.oneof [ subtractive 'I' "VX" subtractive 'X' "LC" subtractive 'C' "DM" ] |> Arb.fromGen Prop.forAll symbols <| fun (subtrahend, minuend) -> let originalRoman = String [| subtrahend; minuend |] let actual = Numeral.tryParseRoman originalRoman let roundTrippedRoman = actual |> Option.bind Numeral.toRoman let expected = opt { let! m = Numeral.tryParseRoman (string minuend) let! s = Numeral.tryParseRoman (string subtrahend) return m - s } expected =! actual Some originalRoman =! roundTrippedRoman
Like the previous property, this looks like a mouthful, but isn't too bad. I'll walk you through it.
Initially, ignore the OptionBuilder type and the opt value; we'll return to them shortly. The property itself starts by defining a function called subtractive, which has the type char -> string -> Gen<char * char>. The first argument is a symbol representing the subtrahend; that is: the number being subtracted. The next argument is a sequence of minuends; that is: numbers from which the subtrahend will be subtracted.
The subtractive function is implemented with a gen computation expression. It first uses a let! binding to define that a singular minuend is a random value drawn from minuends. As usual, Gen.elements is the workhorse: it defines a generator that randomly draws from a sequence of values, and because minuends is a string, and the string type implements char seq, it can be used with Gen.elements to define a generator of char values. While Gen.elements minuends returns a Gen<char> value, the use of a let! binding within a computation expression causes minuend to have the type char.
The second line of code in subtractive returns a tuple of two char values: the subtrahend first, and the minuend second. Normally, when subtracting with the arithmetic minus operator, you'd write a difference as minuend - subtrahend; the minuends comes first, followed by the subtrahend. The Roman subtractive notation, however, is written with the subtrahend before the minuend, which is the reason that the subtractive function returns the symbols in that order. It's easier to think about that way.
The subtractive function enables you to define generators of Roman numerals using subtractive notation. Since I can only be used before V and X, you can define a generator using subtractive 'I' "VX". This is a Gen<char * char> value. Likewise, you can define subtractive 'X' "LC" and subtractive 'C' "DM" and use Gen.oneOf to define a generator that randomly selects one of these generators, and uses the selected generator to produce a value. As always, the last step is to convert the generator into an Arbitrary with Arb.fromGen, so that symbols has the type Arbitrary<char * char>.
Equipped with an Arbitrary, you can again use Prop.forAll to express the desired property. First, originalRoman is created from the subtrahend and minuend. Due to the way symbols is defined, originalRoman will have values like "IV", "XC", and so on.
The property then proceeds to invoke tryParseRoman. It also uses the actual value to produce a round-tripped value. Not only should the parser correctly understand subtractive notation, but the integer-to-Roman conversion should also prefer this notation.
The last part of the property is the assertion. Here, you need opt, which is a computation builder for option values.
In the assertion, you need to calculate the expected value. Both minuend and subtrahend are char values; in order to find their corresponding decimal values, you'll need to call tryParseRoman. The problem is that tryParseRoman returns an int option. For example, tryParseRoman "I" returns Some 1, so you may need to subtract Some 1 from Some 5. The most readable way I've found is to use a computation expression. Using let! bindings, both m and s are int values, which you can easily subtract using the normal - operator.
expected and actual are both int option values, so can be compared using Unquote's must equal operator.
Finally, the property also asserts that the original value must be equal to the round-tripped value. If not, you could have an implementation that correctly parses "IV" as 4, but converts 4 to "IIII".
Limited repetition #
The previous property only ensures that subtractive notation is used in simple cases, like IX or CD. It doesn't verify that composite numerals are correctly written. As an example, the converter should convert 1893 to MDCCCXCIII, not MDCCCLXXXXIII. The second alternative is incorrect because it uses LXXXX to represent 90, instead of XC.
The underlying property is that any given symbol can only be repeated at most three times. A symbol can appear more than thrice in total, as demonstrated by the valid numeral MDCCCXCIII, in which C appears four times. For any group of repeated characters, however, a character must only be repeated once, twice, or thrice.
This also explain why the maximum Roman numeral is MMMCMXCIX, or 3,999.
In order to express this property in code, you first need a function to group characters. Here, I've chosen to reuse one of my own creation:
// seq<'a> -> 'a list list when 'a : equality let group xs = let folder x = function | [] -> [[x]] | (h::t)::ta when h = x -> (x::h::t)::ta | acc -> [x]::acc Seq.foldBack folder xs []
This function will, for example, group "MDCCCXCIII" like this:
> "MDCCCXCIII" |> group;; val it : char list list = [['M']; ['D']; ['C'; 'C'; 'C']; ['X']; ['C']; ['I'; 'I'; 'I']]
All you need to do is to find the length of all such sub-lists, and assert that the maximum is at most 3:
[<Property(QuietOnSuccess = true)>] let ``there can be no more than three identical symbols in a row`` () = Prop.forAll romanRange <| fun i -> let actual = Numeral.toRoman i test <@ actual |> Option.map (group >> (List.map List.length) >> List.max) |> Option.exists (fun x -> x <= 3) @>
Since actual is a string option, you need to express the assertion within the Maybe (Option) monad. First, you can use Option.map to map any value (should there be one) to find the maximum length of any repeated character group. This returns an int option.
Finally, you can pipe that int option into Option.exists, which will evaluate to false if there's no value, or if the boolean expression x <= 3 evaluates to false.
Input range #
At this point, you're almost done. The only remaining properties you'll need to specify is that the maximum value is 3,999, and the minimum value is 1. Negative numbers, or zero, are not allowed:
[<Property(QuietOnSuccess = true)>] let ``negative numbers and zero are not supported`` i = let i = -(abs i) let actual = Numeral.toRoman i test <@ Option.isNone actual @>
In this property, the function argument i can be any number, but calling abs ensures that it's positive (or zero), and the unary - operator then converts that positive value to a negative value.
Notice that the new i value shadows the input argument of the same name. This is a common trick when writing properties. It prevents me from accidentally using the input value provided by FsCheck. While the input argument is useful as a seed value, it isn't guaranteed to model the particular circumstances of this property. Here, you only care to assert what happens if the input is negative or zero. Specifically, you always want the return value to be None.
Likewise for too large input values:
[<Property(QuietOnSuccess = true)>] let ``numbers too big are not supported`` () = Gen.choose (4000, Int32.MaxValue) |> Arb.fromGen |> Prop.forAll <| fun i -> let actual = Numeral.toRoman i test <@ Option.isNone actual @>
Here, Gen.choose is used to define an Arbitrary<int> that only produces numbers between 4000 and Int32.MaxValue (including both boundary values).
This test is similar to the one that exercises negative values, so you could combine them to a single function if you'd like. I'll leave this as an exercise, though.
Implementation #
The interesting part of this exercise is, I think, how to define the properties. There are many ways you can implement the functions to pass all properties. Here's one of them:
open System let tryParseRoman candidate = let add x = Option.map ((+) x) let rec imp acc = function | 'I'::'X'::xs -> imp (acc |> add 9) xs | 'I'::'V'::xs -> imp (acc |> add 4) xs | 'I'::xs -> imp (acc |> add 1) xs | 'V'::xs -> imp (acc |> add 5) xs | 'X'::'C'::xs -> imp (acc |> add 90) xs | 'X'::'L'::xs -> imp (acc |> add 40) xs | 'X'::xs -> imp (acc |> add 10) xs | 'L'::xs -> imp (acc |> add 50) xs | 'C'::'M'::xs -> imp (acc |> add 900) xs | 'C'::'D'::xs -> imp (acc |> add 400) xs | 'C'::xs -> imp (acc |> add 100) xs | 'D'::xs -> imp (acc |> add 500) xs | 'M'::xs -> imp (acc |> add 1000) xs | [] -> acc | _ -> None candidate |> Seq.toList |> imp (Some 0) let toRoman i = let rec imp acc = function | x when x >= 1000 -> imp ('M':: acc) (x - 1000) | x when x >= 900 -> imp ('M'::'C'::acc) (x - 900) | x when x >= 500 -> imp ('D':: acc) (x - 500) | x when x >= 400 -> imp ('D'::'C'::acc) (x - 400) | x when x >= 100 -> imp ('C':: acc) (x - 100) | x when x >= 90 -> imp ('C'::'X'::acc) (x - 90) | x when x >= 50 -> imp ('L':: acc) (x - 50) | x when x >= 40 -> imp ('L'::'X'::acc) (x - 40) | x when x >= 10 -> imp ('X':: acc) (x - 10) | x when x >= 9 -> imp ('X'::'I'::acc) (x - 9) | x when x >= 5 -> imp ('V':: acc) (x - 5) | x when x >= 4 -> imp ('V'::'I'::acc) (x - 4) | x when x >= 1 -> imp ('I':: acc) (x - 1) | _ -> acc if 0 < i && i < 4000 then imp [] i |> List.rev |> List.toArray |> String |> Some else None
Both functions use tail-recursive inner imp functions in order to accumulate the appropriate answer.
One of the nice properties (that I didn't test for) of this implementation is that the tryParseRoman function is a Tolerant Reader. While toRoman would never create such a numeral, tryParseRoman correctly understands some alternative renderings:
> "MDCCCLXXXXIII" |> tryParseRoman;; val it : int option = Some 1893 > 1893 |> toRoman;; val it : String option = Some "MDCCCXCIII"
In other words, the implementation follows Postel's law. tryParseRoman is liberal in what it accepts, while toRoman is conservative in what it returns.
Summary #
Some problems look, at first glance, as obvious candidates for example-driven development. In my experience, this particularly happen when obvious examples abound. It's not difficult to come up with examples of Roman numerals, so it seems intuitive that you should just start writing some test cases with various examples. In my experience, though, that doesn't guarantee that you're led towards a good implementation.
The more a problem description is based on examples, the harder it can be to identify the underlying properties. Still, they're often there, once you start looking. As I've previously reported, using property-based test-driven development enables you to proceed in a more incremental fashion, because properties describe only parts of the desired solution.
If you're interested in learning more about Property-Based Testing, you can watch my introduction to Property-based Testing with F# Pluralsight course.
