ploeh blog danish software design

An actually useful software metric.

In Humane Code I argue that software development suffers from a lack of useful measurements. While I stand by that general assertion, a few code metrics can be useful. Cyclomatic complexity, while no silver bullet, can be put to good use.

Recap #

I think of cyclomatic complexity as a measure of the number of pathways through a piece of code. Even the simplest body of code affords a single pathway, so the minimum cyclomatic complexity is 1. You can easily 'calculate' the cyclomatic complexity of a method for function. You start at one, and then you count how many times if and for occurs. For each of these keywords you find, you increment the number (which started at 1).

The specifics are language-dependent. The idea is to count branching and looping instructions. In C#, for example, you'd also have to include foreach, while, do, and each case in a switch block. In other languages, the keywords to count will differ.

What's the cyclomatic complexity of this TryParse method?

public static bool TryParse(string candidate, out UserNamePassworCredentials? credentials)
{
    credentials = null;
 
    var arr = candidate.Split(',');
    if (arr.Length < 2)
        return false;
 
    credentials = new UserNamePassworCredentials(arr[0], arr[1]);
    return true;
}

The cyclomatic complexity of this method is 2. You start with the number 1 and then increment it every time you find one of the branching keywords. In this case, there's only a single if, so increment 1 to 2. That's it. If you're in doubt, Visual Studio can calculate metrics for you. (It calculates other metrics as well, but I don't find those useful.)

Guide for unit testing #

I find cyclomatic complexity useful because it measures the number of pathways through a method. As such, it indicates the minimum number of test cases you ought to furnish. (Edit July 14, 2023: While this tends to work well in practice, it turns out that it's not strictly true in general. See the article Is cyclomatic complexity really related to branch coverage? and the comments for more details.) This is useful when reviewing code and tests.

Sometimes I'm presented with code that other people wrote. When I look through the production code, I consider its cyclomatic complexity. If, for example, a method has a cyclomatic complexity of 5, I'd expect to find at least five test cases to cover that method.

At other times, I start by reading the tests. The number of test cases gives me a rough indication of what degree of complexity to expect. If I see four distinct tests for the same method, I expect it to have a cyclomatic complexity about 4.

I don't demand 100% coverage. Sometimes, people don't write tests for guard clauses, and I usually accept such omissions. On the other hand, I think that proper decision logic should be covered by tests. If I were to stick unwaveringly to cyclomatic complexity, that would make my reviews more objective, but not necessarily better. I could insist on 100% code coverage, but I don't consider that a good idea.

Presented with the above TryParse method, I'd expect to see at least two unit tests, since the cyclomatic complexity is 2.

The need for more test cases #

Two unit tests aren't enough, though. You could write these two tests:

[Fact]
public void TryParseSucceeds()
{
    var couldParse = UserNamePassworCredentials.TryParse("foo,bar", out var actual);
 
    Assert.True(couldParse);
    var expected = new UserNamePassworCredentials("foo", "bar");
    Assert.Equal(expected, actual);
}
 
[Fact]
public void TryParseFails()
{
    var couldParse = UserNamePassworCredentials.TryParse("foo", out var actual);
 
    Assert.False(couldParse);
    Assert.Null(actual);
}

Using the Devil's advocate technique, however, this implementation of TryParse passes both tests:

public static bool TryParse(string candidate, out UserNamePassworCredentials? credentials)
{
    credentials = null;
    if (candidate != "foo,bar")
        return false;
 
    credentials = new UserNamePassworCredentials("foo", "bar");
    return true;
}

This is clearly not the correct implementation, but it has 100% code coverage. It also still has cyclomatic complexity of 2. The metric suggests a minimum number of tests - not a sufficient number.

More test cases #

It often makes sense to cover each branch with a single parametrised test:

[Theory]
[InlineData("foo,bar", "foo", "bar")]
[InlineData("baz,qux", "baz", "qux")]
[InlineData("ploeh,fnaah", "ploeh", "fnaah")]
[InlineData("foo,bar,baz", "foo", "bar")]
public void TryParseSucceeds(string candidate, string userName, string password)
{
    var couldParse = UserNamePassworCredentials.TryParse(candidate, out var actual);
 
    Assert.True(couldParse);
    var expected = new UserNamePassworCredentials(userName, password);
    Assert.Equal(expected, actual);
}
 
[Theory]
[InlineData("")]
[InlineData("foobar")]
[InlineData("foo;bar")]
[InlineData("foo")]
public void TryParseFails(string candidate)
{
    var couldParse = UserNamePassworCredentials.TryParse(candidate, out var actual);
 
    Assert.False(couldParse);
    Assert.Null(actual);
}

Is a total of eight test cases the correct number? Cyclomatic complexity can't help you here. You'll have to rely on other heuristics, such as test-driven development, the transformation priority premise, and the Devil's Advocate.

Humane Code #

I also find cyclomatic complexity useful for another reason. I keep an eye on complexity because I care about code maintainability. In my Humane Code video, I discuss the magic number seven, plus or minus two.

When you read code, you essentially run a little emulator in your brain. You have to maintain state in order to interpret the code you look at. Will this conditional evaluate to true or false? Is the code going to exit that loop now? Is that array index out of bounds? You can only follow the code by keeping track of variables' contents, and your brain can keep track of approximately seven things.

Cyclomatic complexity is a measure of pathways - not how many things you need to keep track of. Still, in my experience, there seems to be a useful correlation. Code with high cyclomatic complexity tends to have many moving parts. There's too much to keep track of. With low cyclomatic complexity, on the other hand, the code involves few moving parts.

I use cyclomatic complexity 7 as an approximate maximum for that reason. It's only a rule of thumb, since I'm painfully aware that I'm transplanting experimental psychology to a context where no conclusions can be scientifically drawn. But like the 80/24 rule I find that it works well in practice.

Complexity of a method call #

Consider the above parametrised tests. Some of the test cases provide enough triangulation to defeat the Devil's attempt at hard-coding return values. This explains test values like "foo,bar", "baz,qux", and "ploeh,fnaah", but why did I include the "foo,bar,baz" test case? And why did I include the empty string as one of the test cases for TryParseFails?

When I write tests, I aspire to compose tests that verify the behaviour rather than the implementation of the System Under Test. The desired behaviour, I decided, is that any extra entries in the comma-separated input should be ignored. Likewise, if there's fewer than two entries, parsing should fail. There must be both a user name and a password.

Fortunately, this happens to be how Split already works. If you consider all the behaviour that Split exhibits, it encapsulates moderate complexity. It can split on multiple alternative delimiters, it can throw away empty entries, and so on. What would happen if you inline some of that functionality?

public static bool TryParse(string candidate, out UserNamePassworCredentials? credentials)
{
    credentials = null;
 
    var l = new List<string>();
    var element = "";
    foreach (var c in candidate)
    {
        if (c == ',')
        {
            l.Add(element);
            element = "";
        }
        else
            element += c;
 
    }
    l.Add(element);
 
    if (l.Count < 2)
        return false;
 
    credentials = new UserNamePassworCredentials(l[0], l[1]);
    return true;
}

This isn't as sophisticated as the Split method it replaces, but it passes all eight test cases. Why did I do this? To illustrate the following point.

What's the cyclomatic complexity now?

Keep in mind that the externally observable behaviour (as defined by eight test cases) hasn't changed. The cyclomatic complexity, however, has. It's now 4 - double the previous metric.

A method call (like a call to Split) can hide significant cyclomatic complexity. That's a desirable situation. This is the benefit that encapsulation offers: that you don't have to worry about implementation details as long as both caller and callee fulfils the contract.

When you calculate cyclomatic complexity, a method call doesn't increment the complexity, regardless of the degree of complexity that it encapsulates.

Summary #

Cyclomatic complexity is one of the rare programming metrics that I find useful. It measures the number of pathways through a body of code.

You can use it to guide your testing efforts. The number is the minimum number of tests you must write in order to cover all branches. You'll likely need more test cases than that.

You can also use the number as a threshold. I suggest that 7 ought to be the maximum cyclomatic complexity of a method or function. You're welcome to pick another number, but keeping an eye on cyclomatic complexity is useful. It tells you when it's time to refactor a complex method.

Cyclomatic complexity considers only the code that directly implements a method or function. That code can call other code, but what happens behind a method call doesn't impact the metric.

Comments

An example showing a refactoring from F# partial application 'dependency injection' to an impure/pure/impure sandwich.

In a comment to Dependency rejection, I wrote:

"I'd welcome a simplified, but still concrete example where the impure/pure/impure sandwich described here isn't going to be possible."

The code in question relates to validationverification of user accounts. You can read the complete description in the linked comment, but I'll try to summarise it here. I'll then show a refactoring to a functional architecture - specifically, to an impure/pure/impure sandwich.

The code is available on GitHub.

Registration flow #

The system in question uses two-factor authentication with mobile phones. When you sign up for the service, you give your phone number. You then receive an SMS, and must use whatever is in that SMS to prove ownership of the phone number. Christer van der Meeren illustrates the flow like this:

He also supplies sample code:

let completeRegistrationWorkflow
    (createProof: Mobile -> Async<ProofId>)
    (verifyProof: Mobile -> ProofId -> Async<bool>)
    (completeRegistration: Registration -> Async<unit>)
    (proofId: ProofId option)
    (registration: Registration)
    : Async<CompleteRegistrationResult> =
    async {
        match proofId with
        | None ->
            let! proofId = createProof registration.Mobile
            return ProofRequired proofId
        | Some proofId ->
            let! isValid = verifyProof registration.Mobile proofId
            if isValid then
                do! completeRegistration registration
                return RegistrationCompleted
            else
                let! proofId = createProof registration.Mobile
                return ProofRequired proofId
    }

While this is F#, it's not functional, since it uses partial application for dependency injection. From the description, I find it safe to assume that we can consider Async as a surrogate for IO.

The code implies the existence of other types. I decided to define them like this:

type Mobile = Mobile of int
type ProofId = ProofId of Guid
type Registration = { Mobile : Mobile }
type CompleteRegistrationResult = ProofRequired of ProofId | RegistrationCompleted

In reality, they're probably more complicated, but this is enough to make the code compile.

Is it possible to refactor completeRegistrationWorkflow to an impure/pure/impure sandwich?

Applicability #

It is possible to refactor completeRegistrationWorkflow to an impure/pure/impure sandwich. You'll see how to do that soon. Before we start that work, however, I'd like to warn against jumping to conclusions. It's possible that the problem statement doesn't capture some subtleties that one would have to deal with in the real world. It's also possible that I've misunderstood the essence of Christer van der Meeren's problem description.

It's (relatively) easy to teach the basics of programming. You teach a beginner about keywords, programming constructs, how to compile or interpret a program, and so on.

On the other hand, it's hard to write about dealing with complicated code. There are ways to make legacy code better, but the moves you have to make depend on myriad details. Complicated code is, by definition, something that's hard to learn. This means that truly complicated legacy code is rarely suitable for instructive examples. One has to strike a delicate balance and produce an example that looks complicated enough to warrant improvement, but on the other hand still be simple enough to be understood.

I think that Christer van der Meeren has struck that balance. With three dependencies, the sample code looks just complicated enough to warrant refactoring. On the other hand, you can understand what it's supposed to do in a few minutes. There's a risk, however, that the example is too simplified. That could weaken the result of the refactoring that follows. Could you still apply that refactoring if the problem was more complicated?

It's my experience that it's conspicuously often possible to implement an impure/pure/impure sandwich.

Fakes #

In the rest of this article, I want to show how to refactor completeRegistrationWorkflow to an impure/pure/impure sandwich. As Refactoring admonishes:

"to refactor, the essential precondition is [...] solid tests"

The tests will need some Test Doubles to stand in for the three dependency functions. If possible, I prefer state-based testing over interaction-based testing. First, then, we need some Fakes.

While completeRegistrationWorkflow takes three dependency functions, it looks as though there's only two architectural dependencies:

• A two-factor authentication service
• A registration database (or service)

type Fake2FA () =
    let mutable proofs = Map.empty
 
    member _.CreateProof mobile =
        match Map.tryFind mobile proofs with
        | Some (proofId, _) -> proofId
        | None ->
            let proofId = ProofId (Guid.NewGuid ())
            proofs <- Map.add mobile (proofId, false) proofs
            proofId
        |> fun proofId -> async { return proofId }
 
    member _.VerifyProof mobile proofId =
        match Map.tryFind mobile proofs with
        | Some (_, true) -> true
        | _ -> false
        |> fun b -> async { return b }
 
    member _.VerifyMobile mobile =
        match Map.tryFind mobile proofs with
        | Some (proofId, _) ->
            proofs <- Map.add mobile (proofId, true) proofs
        | _ -> ()

In F#, I find that the easiest way to model a mutable resource is to use an object. This one just keeps track of a collection of proofs. The CreateProof method fits the function signature of completeRegistrationWorkflow's createProof function argument. It looks for an existing proof for the mobile number so that it can reuse the same proof multiple times. If there's no proof for mobile, it creates a new Guid and returns it after having first added it to the collection.

Likewise, the VerifyProof method fits the type of the verifyProof function argument. Proofs are actually tuples of IDs and a flag that keeps track of whether or not they've been verified. The method returns the flag if it's there, and false otherwise.

The third VerifyMobile method is a test-specific functionality that enables a test to mark a proof as having been verified via two-factor authentication.

Compared to Fake2FA, the Fake registration database is simple:

type FakeRegistrationDB () =
    inherit Collection<Registration> ()
 
    member this.CompleteRegistration r = async { this.Add r }

Again, the CompleteRegistration method fits the completeRegistration function argument to completeRegistrationWorkflow. It just makes the inherited Add method Async.

Fixture creation #

My plan is to add Characterisation Tests so that I can refactor. I do, however, plan to change the API of the System Under Test (SUT). This could break the tests, which would defy their purpose. To protect against this, I'll test against a Facade. Initially, this Facade will be equivalent to the completeRegistrationWorkflow function, but this will change as I refactor.

In addition to the SUT Facade, the tests will also need access to the 'injected' dependencies. You can address this by creating a Fixture Object:

let createFixture () =
    let twoFA = Fake2FA ()
    let db = FakeRegistrationDB ()
    let sut =
        completeRegistrationWorkflow
            twoFA.CreateProof
            twoFA.VerifyProof
            db.CompleteRegistration
    sut, twoFA, db

This function return a triple of values: the SUT Facade and the two Fakes.

The SUT Facade is a partially applied function of the type ProofId option -> Registration -> Async<CompleteRegistrationResult>. In other words, it abstracts away the specifics about how impure actions are executed. It seems reasonable to imagine that the two remaining input arguments, ProofId option and Registration, are run-time values. Regardless of refactoring, the resulting function should be able to receive those arguments and produce the desired outcome.

Characterising the missing proof ID case #

It looks like the cyclomatic complexity of completeRegistrationWorkflow is 3, so you're going to need three Characterisation Tests. You can add them in any order you like, but in this case I found it natural to follow the order in which the branches are laid out in the SUT.

This test case verifies what happens if the proof ID is missing:

[<Theory>]
[<InlineData 123>]
[<InlineData 432>]
let ``Missing proof ID`` mobile = async {
    let sut, twoFA, db = createFixture ()
    let r = { Mobile = Mobile mobile }
 
    let! actual = sut None r
 
    let! expectedProofId = twoFA.CreateProof r.Mobile
    let expected = ProofRequired expectedProofId
    expected =! actual
    test <@ Seq.isEmpty db @> }

All the tests in this article use xUnit.net 2.4.0 with Unquote 5.0.0.

This test calls the sut Facade with a None proof ID and an arbitrary Registration r. Had I used a property-based testing framework such as FsCheck or Hedgehog, I could have made the Registration value itself an arbitrary test argument, but I thought that this was overkill for this situation.

In order to figure out the expectedProofId, the test relies on the behaviour of the Fake2FA class. The CreateProof method is idempotent, so calling it several times with the same number should return the same proof. In this test case, we expect the sut to have done so already, so calling the method once more from the test should return the same value that the SUT received. The test then wraps the proof ID in the ProofRequired case and uses Unquote's =! (must equal) operator to verify that expected is equal to actual.

Finally, the test also verifies that the reservations database remains empty.

Since this is a Characterisation Test it already passes, which makes it untrustworthy. How do I know that I didn't write a Tautological Assertion?

When I write Characterisation Tests, I always try to change the SUT to verify that the test fails for the appropriate reason. In order to fail the first assertion, I can make this change to the None branch of the SUT:

match proofId with
| None ->
    //let! proofId = createProof registration.Mobile
    let proofId = ProofId (Guid.NewGuid ())
    return ProofRequired proofId

This fails the expected =! actual assertion, as expected.

Likewise, you can fail the second assertion with this change:

match proofId with
| None ->
    do! completeRegistration registration
    let! proofId = createProof registration.Mobile
    return ProofRequired proofId

The addition of the completeRegistration statement causes the test <@ Seq.isEmpty db @> assertion to fail, again as expected.

Now I trust that test.

Characterising the valid proof ID case #

Next, you have the case where all is good. The proof ID is present and valid. You can characterise the behaviour with this test:

[<Theory>]
[<InlineData 987>]
[<InlineData 247>]
let ``Valid proof ID`` mobile = async {
    let sut, twoFA, db = createFixture ()
    let r = { Mobile = Mobile mobile }
    let! p = twoFA.CreateProof r.Mobile
    twoFA.VerifyMobile r.Mobile
 
    let! actual = sut (Some p) r
 
    RegistrationCompleted =! actual
    test <@ Seq.contains r db @> }

This test uses CreateProof to create a proof before the sut is exercised. It also uses the test-specific VerifyMobile method to mark the mobile number (and thereby the proof) as valid.

Again, there's two assertions: one against the return value actual, and one that verifies that the registration database db now contains the registration r.

As before, you can't trust a Characterisation Test before you've seen it fail, so first edit the isValid branch of the SUT like this:

if isValid then
    do! completeRegistration registration
    //return RegistrationCompleted
    return ProofRequired proofId

This fails the RegistrationCompleted =! actual assertion, as expected.

Now make this change:

if isValid then
    //do! completeRegistration registration
    return RegistrationCompleted

Now the test <@ Seq.contains r db @> assertion fails, as expected.

This test also seems trustworthy.

Characterising the invalid proof ID case #

The final test case is when a proof ID exists, but it's invalid:

[<Theory>]
[<InlineData 327>]
[<InlineData 666>]
let ``Invalid proof ID`` mobile = async {
    let sut, twoFA, db = createFixture ()
    let r = { Mobile = Mobile mobile }
    let! p = twoFA.CreateProof r.Mobile
 
    let! actual = sut (Some p) r
 
    let! expectedProofId = twoFA.CreateProof r.Mobile
    let expected = ProofRequired expectedProofId
    expected =! actual
    test <@ Seq.isEmpty db @> }

The arrange phase of the test is comparable to the previous test case. The only difference is that the new test doesn't invoke twoFA.VerifyMobile r.Mobile. This leaves the generated proof ID p invalid.

The assertions, on the other hand, are identical to those of the Missing proof ID test case, which means that you can make the same edits to the else branch as you can to the None branch, as described above. If you do that, the assertions fail as they're supposed to. You can also trust this Characterisation Test.

Eta expansion #

While I want to keep the SUT Facade's type unchanged, I do want change the way I compose it. The goal is an impure/pure/impure sandwich: Do something impure first, then call a pure function with the data obtained, and finally do something impure with the output of the pure function.

This means that the composition is going to manipulate the input values to the SUT Facade. To make that easier, I perform an eta conversion on the sut:

let createFixture () =
    let twoFA = Fake2FA ()
    let db = FakeRegistrationDB ()
    let sut pid r =
        completeRegistrationWorkflow
            twoFA.CreateProof
            twoFA.VerifyProof
            db.CompleteRegistration
            pid
            r
    sut, twoFA, db

This doesn't change the behaviour or how the SUT is composed. It only makes the pid and r arguments explicitly visible.

Move proof verification #

When you consider the current implementation of completeRegistrationWorkflow, it seems that the impure actions are interleaved with the decision-making code. How to separate them?

The first opportunity that I identified was that it always calls verifyProof in the Some case. Whenever you want to call a method only in the Some case, but not in the None case, it suggest Option.map.

It should be possible to run Option.map (twoFA.VerifyProof r.Mobile) pid as the initial impure action of the impure/pure/impure sandwich. If that's possible, we could pass the output of that pure function as an argument to completeRegistrationWorkflow. That would already make it simpler:

let completeRegistrationWorkflow
    (createProof: Mobile -> Async<ProofId>)
    (completeRegistration: Registration -> Async<unit>)
    (proof: bool option)
    (registration: Registration)
    : Async<CompleteRegistrationResult> =
    async {
        match proof with
        | None ->
            let! proofId = createProof registration.Mobile
            return ProofRequired proofId
        | Some isValid ->
            if isValid then
                do! completeRegistration registration
                return RegistrationCompleted
            else
                let! proofId = createProof registration.Mobile
                return ProofRequired proofId
    }

Notice that by changing the proof argument to a bool option, you no longer need to call verifyProof, so you can remove it.

There's just one problem. The result of Option.map (twoFA.VerifyProof r.Mobile) pid is an Option<Async<bool>>, but you need an Option<bool>.

You can compose the SUT Facade in an asynchronous workflow, and use a let! binding, but that's not going to solve the problem. A let! binding only works when the outer container is Async. Here, the outermost container is Option. You're going to need to flip the containers around so that you get an Async<Option<bool>> that you can let!-bind:

let sut pid r = async {
    let! p =
        match Option.map (twoFA.VerifyProof r.Mobile) pid with
        | Some b -> async {
            let! b' = b
            return Some b' }
        | None -> async { return None }
    return! completeRegistrationWorkflow
        twoFA.CreateProof
        db.CompleteRegistration
        p
        r
    }

By pattern-matching on Option.map (twoFA.VerifyProof r.Mobile) pid, you can return one of two alternative asynchronous workflows.

Due to the let! binding, p is a bool option that you can pass to completeRegistrationWorkflow.

Traversal #

I know what you're going to say. You'll protest that I just moved complex behaviour out of completeRegistrationWorkflow. The implied assumption here is that completeRegistrationWorkflow is the top-level behaviour that you'd compose in a Composition Root. The createFixture function plays that role in this refactoring exercise.

You'd normally view the Composition Root as a Humble Object - an object that we accept isn't covered by tests because it has a cyclomatic complexity of one. This is no longer the case.

The conversion of Option<Async<bool>> to Async<Option<bool>> is, however, a well-known operation. In Haskell this is known as a traversal, and it's a completely generic operation:

// ('a -> Async<'b>) -> 'a option -> Async<'b option>
let traverse f = function
    | Some x -> async {
        let! x' = f x
        return Some x' }
    | None -> async { return None }

You can put this function in a general-purpose module called AsyncOption and cover it by unit tests if you will. You can even put this module in a separate library; it's perfectly decoupled from the the specifics of the registration flow domain.

If you do that, completeRegistrationWorkflow doesn't change, but the composition does:

let sut pid r = async {
    let! p = AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    return! completeRegistrationWorkflow
        twoFA.CreateProof
        db.CompleteRegistration
        p
        r
    }

You're now back where you'd like to be: One impure action produces a value that you can pass to another function. There's no explicit branching in the code. The cyclomatic complexity remains one.

Change return type #

That first refactoring takes care of one out of three impure dependencies. Next, you can get rid of createProof. This one seems to be more difficult to get rid of. It doesn't seem to be required only in the Some case, so a map or traverse can't work. In both cases, however, the result of calling createProof is handled in exactly the same way.

Here's another common trick in functional programming: Decouple decisions from effects. Return a value that indicates the decision that the function reaches, and then let the second impure action of the impure/pure/impure sandwich act on the decision.

In this case, you can model your decision as a Mobile option. You might want to consider a more explicit type, in order to better communicate intent, but it's best to keep each refactoring step small:

let completeRegistrationWorkflow
    (completeRegistration: Registration -> Async<unit>)
    (proof: bool option)
    (registration: Registration)
    : Async<Mobile option> =
    async {
        match proof with
        | None -> return Some registration.Mobile
        | Some isValid ->
            if isValid then
                do! completeRegistration registration
                return None
            else
                return Some registration.Mobile
    }

Notice that the createProof dependency is no longer required. I've removed it from the argument list of completeRegistrationWorkflow.

The composition now looks like this:

let createFixture () =
    let twoFA = Fake2FA ()
    let db = FakeRegistrationDB ()
    let sut pid r = async {
        let! p = AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
        let! res = completeRegistrationWorkflow db.CompleteRegistration p r
        let! pidr = AsyncOption.traverse twoFA.CreateProof res
        return pidr
            |> Option.map ProofRequired
            |> Option.defaultValue RegistrationCompleted }

Thanks to the let! binding, the result res is a Mobile option. You can now let the twoFA.CreateProof method traverse over res. This produces an Async<Option<ProofId>> that you can let!-bind to pidr - a ProofId option.

You can use Option.map to wrap the ProofId value in a ProofRequired case, if it's there. This step of the final pipeline produces a CompleteRegistrationResult option.

Finally, you can use Option.defaultValue to fold the option into a CompleteRegistrationResult. The default value is RegistrationCompleted. This is the case value that'll be used if the option is None.

Again, the composition has a cyclomatic complexity of one, and the type of the sut remains ProofId option -> Registration -> Async<CompleteRegistrationResult>. This is a true refactoring. The type of the SUT remains the same, and no behaviour changes. The tests still pass, even though I haven't had to edit them.

Change return type to Result #

Consider the intent of completeRegistrationWorkflow. The purpose of the operation is to complete a registration workflow. The name is quite explicit. Thus, the happy path is when the proof ID is valid and the function can call completeRegistration.

Usually, when you call a function that returns an option, the implied contract is that the Some case represents the happy path. That's not the case here. The Some case carries information about the error paths. This isn't idiomatic.

It'd be more appropriate to use a Result return value:

let completeRegistrationWorkflow
    (completeRegistration: Registration -> Async<unit>)
    (proof: bool option)
    (registration: Registration)
    : Async<Result<unit, Mobile>> =
    async {
        match proof with
        | None -> return Error registration.Mobile
        | Some isValid ->
            if isValid then
                do! completeRegistration registration
                return Ok ()
            else
                return Error registration.Mobile
    }

This change is in itself small, but it does require some changes to the composition. Just as you had to add an Option.traverse function when the return type was an option, you'll now have to add similar functionality to Result. Result is also known as Either. Not only is it a bifunctor, you can also traverse both axes. Haskell calls this a bitraversable functor.

// ('a -> Async<'b>) -> ('c -> Async<'d>) -> Result<'a,'c> -> Async<Result<'b,'d>>
let traverseBoth f g = function
    | Ok x -> async {
        let! x' = f x
        return Ok x' }
    | Error e -> async {
        let! e' = g e
        return Error e' }

Here I just decided to call the function traverseBoth and the module AsyncResult.

You're also going to need the equivalent of Option.defaultValue for Result. Something that translates both dimensions of Result into the same type. That's the Either catamorphism, so you could, for example, introduce another general-purpose function called cata:

// ('a -> 'b) -> ('c -> 'b) -> Result<'a,'c> -> 'b
let cata f g = function
    | Ok x -> f x
    | Error e -> g e

This is another entirely general-purpose function that you can put in a general-purpose module called Result, in a general-purpose library. You can also cover it by unit tests, if you like.

These two general-purpose functions enable you to compose the workflow:

let createFixture () =
    let twoFA = Fake2FA ()
    let db = FakeRegistrationDB ()
    let sut pid r = async {
        let! p = AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
        let! res = completeRegistrationWorkflow db.CompleteRegistration p r
        let! pidr =
            AsyncResult.traverseBoth
                (fun () -> async { return () })
                twoFA.CreateProof
                res
        return pidr
            |> Result.cata (fun () -> RegistrationCompleted) ProofRequired }
    sut, twoFA, db

This looks more confused than previous iterations. From here, though, it'll get better again. The first two lines of code are the same as before, but now res is a Result<unit, Mobile>. You still need to let twoFA.CreateProof traverse the 'error path', but now you also need to take care of the happy path.

In the Ok case you have a unit value (()), but traverseBoth expects its f and g functions to return Async values. I could have fixed that with a more specialised traverseError function, but we'll soon move on from here, so it's hardly worthwhile.

In Haskell, you can 'elevate' a value simply with the pure function, but in F#, you need the more cumbersome (fun () -> async { return () }) to achieve the same effect.

The traversal produces pidr (for Proof ID Result) - a Result<unit, ProofId> value.

Finally, it uses Result.cata to turn both the Ok and Error dimensions into a single CompleteRegistrationResult that can be returned.

Removing the last dependency #

There's still one dependency left: the completeRegistration function, but it's now trivial to remove. Instead of calling the dependency function from within completeRegistrationWorkflow you can use the same trick as before. Decouple the decision from the effect.

Return information about the decision the function made. In the above incarnation of the code, the Ok dimension is currently empty, since it only returns unit. You can use that 'channel' to communicate that you decided to complete a registration:

let completeRegistrationWorkflow
    (proof: bool option)
    (registration: Registration)
    : Async<Result<Registration, Mobile>> =
    async {
        match proof with
        | None -> return Error registration.Mobile
        | Some isValid ->
            if isValid then
                return Ok registration
            else
                return Error registration.Mobile
    }

This is another small change. When isValid is true, the function no longer calls completeRegistration. Instead, it returns Ok registration. This means that the return type is now Async<Result<Registration, Mobile>>. It also means that you can remove the completeRegistration function argument.

In order to compose this variation, you need one new general-purpose function. Perhaps you find this barrage of general-purpose functions exhausting, but it's an artefact of a design philosophy of the F# language. The F# base library contains only few general-purpose functions. Contrast this with GHC's base library, which comes with all of these functions built in.

The new function is like Result.cata, but over Async<Result<_>>.

// ('a -> 'b) -> ('c -> 'b) -> Async<Result<'a,'c>> -> Async<'b>
let cata f g r = async {
    let! r' = r
    return Result.cata f g r' }

Since this function does conceptually the same as Result.cata I decided to retain the name cata and just put it in the AsyncResult module. (This may not be strictly correct, as I haven't really given a lot of thought to what a catamorphism for Async would look like, if one exists. I'm open to suggestions about better naming. After all, cata is hardly an idiomatic F# name.)

With AsyncResult.cata you can now compose the system:

let sut pid r = async {
    let! p = AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    let! res = completeRegistrationWorkflow p r
    return!
        res
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

Not only did the call to completeRegistrationWorkflow get even simpler, but you also now avoid the awkwardly named pidr value. Thanks to the let! binding, res has the type Result<Registration, Mobile>.

Note that you can now let both impure actions (db.CompleteRegistration and twoFA.CreateProof) traverse the result. This step produces an Async<Result<unit, ProofId>> that's immediately piped to AsyncResult.cata. This reduces the two alternative dimensions of the Result to a single Async<CompleteRegistrationResult> value.

The completeRegistrationWorkflow function now begs to be further simplified.

Pure registration workflow #

Once you remove all dependencies, your domain logic doesn't have to be asynchronous. Nothing asynchronous happens in completeRegistrationWorkflow, so simplify it:

let completeRegistrationWorkflow
    (proof: bool option)
    (registration: Registration)
    : Result<Registration, Mobile> =
    match proof with
    | None -> Error registration.Mobile
    | Some isValid ->
        if isValid then Ok registration
        else Error registration.Mobile

Gone is the async computation expression, including the return keyword. This is now a pure function.

You'll have to adjust the composition once more, but it's only a minor change:

let sut pid r = async {
    let! p = AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    return!
        completeRegistrationWorkflow p r
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

The result of invoking completeRegistrationWorkflow is no longer an Async value, so there's no reason to let!-bind it. Instead, you can call it and immediately pipe its output to AsyncResult.traverseBoth.

DRY #

Consider completeRegistrationWorkflow. Can you make it simpler?

At this point it should be evident that two of the branches contain duplicate code. Applying the DRY principle you can simplify it:

let completeRegistrationWorkflow
    (proof: bool option)
    (registration: Registration)
    : Result<Registration, Mobile> =
    match proof with
    | Some true -> Ok registration
    | _ -> Error registration.Mobile

I'm not too fond of this style of type annotation for simple functions like this, so I'd like to remove it:

let completeRegistrationWorkflow proof registration =
    match proof with
    | Some true -> Ok registration
    | _ -> Error registration.Mobile

These two steps are pure refactorings: they only reorganise the code that implements completeRegistrationWorkflow, so the composition doesn't change.

Essential complexity #

While reading this article, you may have felt frustration gather. This is cheating! You took out all of the complexity. Now there's nothing left! You're likely to feel that I've moved a lot of behaviour into untestable code. I've done nothing of the sort.

I'll remind you that while functions like AsyncOption.traverse and AsyncResult.cata do contain branching behaviour, they can be tested. In fact, since they're pure functions, they're intrinsically testable.

It's true that a composition of a pure function with its impure dependencies may not be (unit) testable, but that's also true for a Dependency Injection-based object graph composed in a Composition Root.

Compositions of functions may look non-trivial, but to a degree, the type system will assist you. If your composition compiles, it's likely that you've composed the impure/pure/impure sandwich correctly.

Did I take out all the complexity? I didn't. There's a bit left; the function now has a cyclomatic complexity of two. If you look at the original function, you'll see that the duplication was there all along. Once you remove all the accidental complexity, you uncover the essential complexity. This happens to me so often when I apply functional programming principles that I fancy that functional programming is a silver bullet.

Pipeline composition #

We're mostly done now. The problem now appears in all its simplicity, and you have an impure/pure/impure sandwich.

You can still improve the code, though.

If you consider the current composition, you may find that p isn't the best variable name. I admit that I struggled with naming that variable. Sometimes, variable names are in the way and the code might be clearer if you could elide them by composing a pipeline of functions.

That's always worth an attempt. This time, ultimately I find that it doesn't improve things, but even an attempt can be illustrative.

If you want to eliminate a named value, you can often do so by piping the output of the function that produced the variable directly to the next function. This does, however, require that the function argument is the right-most. Currently, that's not the case. registration is right-most, and proof is to the left.

There's no compelling reason that the arguments should come in that order, so flip them:

let completeRegistrationWorkflow registration proof =
    match proof with
    | Some true -> Ok registration
    | _ -> Error registration.Mobile

This enables you to write the entire composition as a single pipeline:

let sut pid r = async {
    return!
        AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
        |> Async.map (completeRegistrationWorkflow r)
        |> Async.bind (
            AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
            >> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired)
    }

This does, however, call for two new general-purpose functions: Async.map and Async.bind:

// ('a -> 'b) -> Async<'a> -> Async<'b>
let map f x = async {
    let! x' = x
    return f x' }
 
// ('a -> Async<'b>) -> Async<'a> -> Async<'b>
let bind f x = async {
    let! x' = x
    return! f x' }

In my opinion, these functions ought to belong to F#'s Async module, but for for reasons that aren't clear to me, they don't. As you can see, though, they're easy to add.

While the this change gets rid of the p variable, I don't think it makes the overall composition easier to understand. The action of swapping the function arguments does, however, enable another simplification.

Eta reduction #

Now that proof is completeRegistrationWorkflow's last function argument, you can perform an eta reduction:

let completeRegistrationWorkflow registration = function
    | Some true -> Ok registration
    | _ -> Error registration.Mobile

Not everyone is a fan of the point-free style, but I like it. YMMV.

Sandwich #

Regardless of whether you prefer completeRegistrationWorkflow in point-free or pointed style, I think that the composition needs improvement. It should explicitly communicate that it's an impure/pure/impure sandwich. This makes it necessary to reintroduce some variables, so I'm also going to bite the bullet and devise some better names.

let sut pid r = async {
    let! validityOfProof = 
        AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    let decision = completeRegistrationWorkflow r validityOfProof
    return!
        decision
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

Instead of p, I decided to call the first value validityOfProof. This is the result of the first impure action in the sandwich (the upper slice of bread).

While validityOfProof is the result of an impure action, the value itself is pure and can be used as input to completeRegistrationWorkflow. This is the pure part of the sandwich. I called the output decision because the workflow makes a decision based on its input, and it's up to the caller to act on that decision.

Notice that decision is bound with a let binding (instead of a let! binding), despite taking place inside an async workflow. This is because completeRegistrationWorkflow is pure. It doesn't return an Async value.

The second impure action acts on decision through a pipeline of AsyncResult.traverseBoth and AsyncResult.cata, as previously explained.

I think that the impure/pure/impure sandwich is more visible like this, so that was my final edit. I'm happy with how it looks now.

Conclusion #

I don't claim that you can always refactor code to an impure/pure/impure sandwich. In fact, I can easily envision categories of software where such an architecture seems impossible.

Still, I find it intriguing that when I find myself in the realm of web services or message-based applications, I can't recall a case where a sandwich has been impossible. Surely, there must cases where it is so. That's the reason that I solicit examples. This article was a response to such an example. I found it fruitful, because it enabled me to discuss several useful techniques for composing behaviour in a functional architecture. On the other hand, it failed to be a counter-example.

I'm sure that some readers are left with a nagging doubt. That's all very impressive, but would you actually write code like that in a piece of production software?

If it was up to me, then: yes. I find that when I can keep code pure, it's trivial to unit test and there's no test-induced damage. Functions also compose in a way objects don't easily do, so there's many advantages to functional programming. I'll take them when they're available.

As always, context matters. I've been in team settings where other team members would embrace this style of programming, and in other environments where team members wouldn't understand what was going on. In the latter case, I'd adjust my approach to challenge, not alienate, other team members.

My intention with this article was to show what's possible, not to dictate what you should do. That's up to you.

This article is the December 2 entry in the F# Advent Calendar in English 2019.

Comments

let completeRegistrationWorkflow
    (createProof: Mobile -> Async<ProofId>)
    (verifyProof: Mobile -> ProofId -> Async<bool>)
    (completeRegistration: Registration -> Async<Result<unit, CompleteRegistrationError>>)
    (proofId: ProofId option)
    (registration: Registration)
    : Async<Result<CompleteRegistrationResult, CompleteRegistrationError>> =
  asyncResult {
    match proofId with
    | None ->
        let! proofId = createProof registration.Mobile
        return ProofRequired proofId
    | Some proofId ->
        let! isValid = verifyProof registration.Mobile proofId
        if isValid then
          do! completeRegistration registration
          return RegistrationCompleted
        else
          let! proofId = createProof registration.Mobile
          return ProofRequired proofId
  }

let complete proofId validReg =
  Workflows.Registration.complete
    Http.createMobileClaimProof
    Http.verifyMobileClaimProof
    Db.completeRegistration
    proofId
    validReg

let completePure reg proofValidity =
  match proofValidity with
  | Some true -> Ok reg
  | Some false | None -> Error reg.Mobile

let complete proofId reg : Async<Result<CompleteRegistrationResult, CompleteRegistrationError>> =
  asyncResult {
    let! proofValidity =
      proofId |> Option.traverseAsync (Http.verifyMobileClaimProof reg.Mobile)

    match completePure reg proofValidity with
    | Ok reg ->
        do! Db.completeRegistration reg
        return RegistrationCompleted
    | Error mobile ->
        let! proofId = Http.createMobileClaimProof mobile
        return ProofRequired proofId
  }

let sut pid r = async {
    let! validityOfProof = 
        AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    let decision = completeRegistrationWorkflow r validityOfProof
    return!
        decision
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

let privateKey = ...
let sut' ciphertext = async {
    let (pid, r) = decrypt privateKey ciphertext
    let! validityOfProof = 
        AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    let decision = completeRegistrationWorkflow r validityOfProof
    return!
        decision
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

let malroyInTheMiddle aliceToMalory = async {
    let maloryToBob = convertIncoming aliceToMalory
    let! bobToMalory = service maloryToBob
    let maloryToAlice = convertOutgoing bobToMalory
    return maloryToAlice
}

let malroyInTheMiddle  =
    Async.fromResult
    >> Async.map convertIncoming
    >> Async.bind service
    >> Async.map convertOutgoing

let completeRegistrationWorkflow
    (createProof: Mobile -> Async<ProofId>)
    (verifyProof: Mobile -> ProofId -> Async<bool>)
    (completeRegistration: Registration -> Async<unit>)
    (proofId: ProofId option)
    (registration: Registration)
    : Async<CompleteRegistrationResult> =
    async {
        match proofId with
        | None ->
            let! proofId = createProof registration.Mobile
            return ProofRequired proofId
        | Some proofId ->
            let! isValid = verifyProof registration.Mobile proofId
            if isValid then
                do! completeRegistration registration
                return RegistrationCompleted
            else
                let! proofId = createProof registration.Mobile
                return ProofRequired proofId
    }

let sut =
    completeRegistrationWorkflow
        twoFA.CreateProof
        twoFA.VerifyProof
        db.CompleteRegistration

let completeRegistrationWorkflow registration = function
    | Some true -> Ok registration
    | _ -> Error registration.Mobile

let sut pid r = async {
    let! validityOfProof = 
        AsyncOption.traverse (twoFA.VerifyProof r.Mobile) pid
    let decision = completeRegistrationWorkflow r validityOfProof
    return!
        decision
        |> AsyncResult.traverseBoth db.CompleteRegistration twoFA.CreateProof
        |> AsyncResult.cata (fun () -> RegistrationCompleted) ProofRequired
    }

You can use a standard string format for TimeSpan values in configuration files.

Sometimes you need to make TimeSpan values configurable. I often see configuration files that look like this:

{
  "SeatingDurationInSeconds": "9000"
}

Code can read such values from configuration files like this:

var seatingDuration = TimeSpan.FromSeconds(Configuration.GetValue<int>("SeatingDurationInSeconds"));

This works, but is abstruse. How long is 9000 seconds?

The idiomatic configuration file format for .NET Core is JSON, which even prevents you from adding comments. Had the configuration been in XML, at least you could have added a comment:

<!--9000 seconds = 2½ hours-->
<SeatingDurationInSeconds>9000</SeatingDurationInSeconds>

In this case, however, it doesn't matter. Use the standard TimeSpan string representation instead:

{
  "SeatingDuration": "2:30:00"
}

Code can read the value like this:

var seatingDuration = Configuration.GetValue<TimeSpan>("SeatingDuration");

I find a configuration value like "2:30:00" much easier to understand than 9000, and the end result is the same.

I haven't found this documented anywhere, but from experience I know that this capability is present in the .NET Framework, so I wondered if it was also available in .NET Core. It is.

Comments

{ "SeatingDuration": "P9000S" }

{ "SeatingDuration": "P2H30M" }

Write small methods. How small? Small enough that any unhandled exception is easy to troubleshoot.

Imagine that you receive a bug report. This one include a logged exception:

System.NullReferenceException: Object reference not set to an instance of an object.
   at Ploeh.Samples.BookingApi.Validator.Validate(ReservationDto dto)
   at Ploeh.Samples.BookingApi.ReservationsController.Post(ReservationDto dto)
   at lambda_method(Closure , Object , Object[] )
   at Microsoft.Extensions.Internal.ObjectMethodExecutor.Execute(Object target, Object[] parameters)
   at Microsoft.AspNetCore.Mvc.Internal.ActionMethodExecutor.SyncActionResultExecutor.Execute(IActionResultTypeMapper mapper, ObjectMethodExecutor executor, Object controller, Object[] arguments)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeActionMethodAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeNextActionFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Rethrow(ActionExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeInnerFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeNextResourceFilter()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Rethrow(ResourceExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeFilterPipelineAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeAsync()
   at Microsoft.AspNetCore.Builder.RouterMiddleware.Invoke(HttpContext httpContext)
   at Microsoft.AspNetCore.Diagnostics.DeveloperExceptionPageMiddleware.Invoke(HttpContext context)
		

Oh, no, you think, not a NullReferenceException.

If you find it hard to troubleshoot NullReferenceExceptions, you're not alone. It doesn't have to be difficult, though. Open the method at the top of the stack trace, Validate:

public static class Validator
{
    public static string Validate(ReservationDto dto)
    {
        if (!DateTime.TryParse(dto.Date, out var _))
            return $"Invalid date: {dto.Date}.";
        return "";
    }
}

Take a moment to consider this method in the light of the logged exception. What do you think went wrong? Which object was null?

Failed hypothesis #

You may form one of a few hypotheses about which object was null. Could it be dto? dto.Date? Those are the only options I can see.

When you encounter a bug in a production system, if at all possible, reproduce it as a unit test.

If you think that the problem is that dto.Date is null, test your hypothesis in a unit test:

[Fact]
public void ValidateNullDate()
{
    var dto = new ReservationDto { Date = null };
    string actual = Validator.Validate(dto);
    Assert.NotEmpty(actual);
}

If you think that a null dto.Date should reproduce the above exception, you'd expect the test to fail. When you run it, however, it passes. It passes because DateTime.TryParse(null, out var _) returns false. It doesn't throw an exception.

That's not the problem, then.

That's okay, this sometimes happens. You form a hypothesis and fail to validate it. Reject it and move on.

Validated hypothesis #

If the problem isn't with dto.Date, it must be with dto itself. Write a unit test to test that hypothesis:

[Fact]
public void ValidateNullDto()
{
    string actual = Validator.Validate(null);
    Assert.NotEmpty(actual);
}

When you run this test, it does indeed fail:

Ploeh.Samples.BookingApi.UnitTests.ValidatorTests.ValidateNullDto
  Duration: 6 ms

  Message: 
    System.NullReferenceException : Object reference not set to an instance of an object.
  Stack Trace: 
    Validator.Validate(ReservationDto dto) line 12
    ValidatorTests.ValidateNullDto() line 36

This looks like the exception included in the bug report. You can consider this as validation of your hypothesis. This test reproduces the defect.

It's easy to address the issue:

public static string Validate(ReservationDto dto)
{
    if (dto is null)
        return "No reservation data supplied.";
    if (!DateTime.TryParse(dto.Date, out var _))
        return $"Invalid date: {dto.Date}.";
    return "";
}

The point of this article, however, is to show that small methods are easy to troubleshoot. How you resolve the problem, once you've identified it, is up to you.

Ambiguity #

Methods are usually more complex than the above example. Imagine, then, that you receive another bug report with this logged exception:

System.NullReferenceException: Object reference not set to an instance of an object.
   at Ploeh.Samples.BookingApi.MaîtreD.CanAccept(IEnumerable`1 reservations, Reservation reservation)
   at Ploeh.Samples.BookingApi.ReservationsController.Post(ReservationDto dto)
   at lambda_method(Closure , Object , Object[] )
   at Microsoft.Extensions.Internal.ObjectMethodExecutor.Execute(Object target, Object[] parameters)
   at Microsoft.AspNetCore.Mvc.Internal.ActionMethodExecutor.SyncActionResultExecutor.Execute(IActionResultTypeMapper mapper, ObjectMethodExecutor executor, Object controller, Object[] arguments)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeActionMethodAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeNextActionFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Rethrow(ActionExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeInnerFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeNextResourceFilter()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Rethrow(ResourceExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeFilterPipelineAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeAsync()
   at Microsoft.AspNetCore.Builder.RouterMiddleware.Invoke(HttpContext httpContext)
   at Microsoft.AspNetCore.Diagnostics.DeveloperExceptionPageMiddleware.Invoke(HttpContext context)

When you open the code file for the MaîtreD class, this is what you see:

public class MaîtreD
{
    public MaîtreD(int capacity)
    {
        Capacity = capacity;
    }
 
    public int Capacity { get; }
 
    public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
    {
        int reservedSeats = 0;
        foreach (var r in reservations)
            reservedSeats += r.Quantity;
 
        if (Capacity < reservedSeats + reservation.Quantity)
            return false;
 
        return true;
    }
}

This code throws a NullReferenceException, but which object is null? Can you identify it from the code?

I don't think that you can. It could be reservations or reservation (or both). Without more details, you can't tell. The exception is ambiguous.

The key to making troubleshooting easy is to increase your chances that, when exceptions are thrown, they're unambiguous. The problem with a NullReferenceException is that you can't tell which object was null.

Remove ambiguity by protecting invariants #

Consider the CanAccept method. Clearly, it requires both reservations and reservation in order to work. This requirement is, however, currently implicit. You can make it more explicit by letting the method protect its invariants. (This is also known as encapsulation. For more details, watch my Pluralsight course Encapsulation and SOLID.)

A simple improvement is to add a Guard Clause for each argument:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    if (reservations is null)
        throw new ArgumentNullException(nameof(reservations));
    if (reservation is null)
        throw new ArgumentNullException(nameof(reservation));
 
    int reservedSeats = 0;
    foreach (var r in reservations)
        reservedSeats += r.Quantity;
 
    if (Capacity < reservedSeats + reservation.Quantity)
        return false;
 
    return true;
}

If you'd done that from the start, the logged exception would instead have been this:

System.ArgumentNullException: Value cannot be null.
Parameter name: reservations
   at Ploeh.Samples.BookingApi.MaîtreD.CanAccept(IEnumerable`1 reservations, Reservation reservation)
   at Ploeh.Samples.BookingApi.ReservationsController.Post(ReservationDto dto)
   at lambda_method(Closure , Object , Object[] )
   at Microsoft.Extensions.Internal.ObjectMethodExecutor.Execute(Object target, Object[] parameters)
   at Microsoft.AspNetCore.Mvc.Internal.ActionMethodExecutor.SyncActionResultExecutor.Execute(IActionResultTypeMapper mapper, ObjectMethodExecutor executor, Object controller, Object[] arguments)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeActionMethodAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeNextActionFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Rethrow(ActionExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ControllerActionInvoker.InvokeInnerFilterAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeNextResourceFilter()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Rethrow(ResourceExecutedContext context)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.Next(State& next, Scope& scope, Object& state, Boolean& isCompleted)
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeFilterPipelineAsync()
   at Microsoft.AspNetCore.Mvc.Internal.ResourceInvoker.InvokeAsync()
   at Microsoft.AspNetCore.Builder.RouterMiddleware.Invoke(HttpContext httpContext)
   at Microsoft.AspNetCore.Diagnostics.DeveloperExceptionPageMiddleware.Invoke(HttpContext context)

It's now clear that it was the reservations argument that was null. Now fix that issue. Why does the CanAccept receive a null argument?

You may now consider examining the next frame in the stack trace: ReservationsController.Post:

public ActionResult Post(ReservationDto dto)
{
    var validationMsg = Validator.Validate(dto);
    if (validationMsg != "")
        return BadRequest(validationMsg);
 
    var reservation = Mapper.Map(dto);
    var reservations = Repository.ReadReservations(reservation.Date);
 
    var accepted = maîtreD.CanAccept(reservations, reservation);
    if (!accepted)
        return StatusCode(
            StatusCodes.Status500InternalServerError,
            "Couldn't accept.");
    var id = Repository.Create(reservation);
    return Ok(id);
}

The Post code only calls CanAccept once, so again, you can unambiguously deduce where the null reference comes from. It comes from the Repository.ReadReservations method call. Now go there and figure out why it returns null.

Notice how troubleshooting is trivial when the methods are small.

Size matters #

How small is a small method? How large does a method have to be before it's no longer small?

A method is small when you can easily troubleshoot it based exclusively on a logged exception.

Until you get the hang of it, it can be hard to predict if a method is going to be easy to troubleshoot. I therefore also follow another rule of thumb:

For languages like C#, methods should have a maximum size of 80x24 characters.

What if you already have bigger methods? Those are much harder to troubleshoot. If you have a method that spans hundreds of lines of code, a logged exception is rarely sufficient for troubleshooting. In order to save space, I'm not going to show en example of such a method, but I'm sure that you can easily find one in the code base that you professionally work with. Such a method is likely to have dozens of objects that could be null, so a NullReferenceException and a stack trace will contain too little information to assist troubleshooting.

I often see developers add tracing or logging to such code in order to facilitate troubleshooting. This makes the code even more bloated, and harder to troubleshoot.

Instead, cut the big method into smaller helper methods. You can keep the helper methods private so that you don't change the API. Even so, a logged exception will now report the helper method in its stack trace. Keep those helper methods small, and troubleshooting becomes trivial.

Conclusion #

Small methods come with many benefits. One of these is that it's easy to troubleshoot a small method from a logged exception. Small methods typically take few arguments, and use few variables. A logged exception will often be all that you need to pinpoint where the problem occurred.

A large method body, on the other hand, is difficult to troubleshoot. If all you have is a logged exception, you'll be able to find multiple places in the code where that exception could have been thrown.

Refactor big methods into smaller helper methods. If one of these helper methods throws an exception, the method name will be included in the stack trace of a logged exception. When the helper method is small, you can easily troubleshoot it.

Keep methods small. Size does matter.

Comments

A diamond kata implementation written in Rockstar

I've previously written about the diamond kata, which has become one of my favourite programming exercises. I wanted to take the Rockstar language out for a spin, and it seemed a good candidate problem.

Rockstar #

If you're not aware of the Rockstar programming language, it started with a tweet from Paul Stovell:

"To really confuse recruiters, someone should make a programming language called Rockstar."

Lyrics #

I'll start with the final result. What follows here are the final lyrics to Diamond rock. As you'll see, it starts with a short prologue after which it settles into a repetitive pattern. I imagine that this might make it useful for audience participation, in the anthem rock style of e.g. We Will Rock You.

After 25 repetitions the lyrics change. I haven't written music to any of them, but I imagine that this essentially transitions into another song, just like We Will Rock You traditionally moves into We Are the Champions. The style of the remaining lyrics does, however, suggest something musically more complex than a rock anthem.

Your memory says  
The way says A

Despair takes your hope
The key is nothing
Your courage is a tightrope
Let it be without it
If your hope is your courage
Let the key be the way

Build your courage up
If your hope is your courage
The key says B

Build your courage up
If your hope is your courage
The key says C

Build your courage up
If your hope is your courage
The key says D

Build your courage up
If your hope is your courage
The key says E

Build your courage up
If your hope is your courage
The key says F

Build your courage up
If your hope is your courage
The key says G

Build your courage up
If your hope is your courage
The key says H

Build your courage up
If your hope is your courage
The key says I

Build your courage up
If your hope is your courage
The key says J

Build your courage up
If your hope is your courage
The key says K

Build your courage up
If your hope is your courage
The key says L

Build your courage up
If your hope is your courage
The key says M

Build your courage up
If your hope is your courage
The key says N

Build your courage up
If your hope is your courage
The key says O

Build your courage up
If your hope is your courage
The key says P

Build your courage up
If your hope is your courage
The key says Q

Build your courage up
If your hope is your courage
The key says R

Build your courage up
If your hope is your courage
The key says S

Build your courage up
If your hope is your courage
The key says T

Build your courage up
If your hope is your courage
The key says U

Build your courage up
If your hope is your courage
The key says V

Build your courage up
If your hope is your courage
The key says W

Build your courage up
If your hope is your courage
The key says X

Build your courage up
If your hope is your courage
The key says Y

Build your courage up
If your hope is your courage
The key says Z

Give back the key

Dream takes a tightrope
Your hope's start'n'stop
While Despair taking your hope ain't a tightrope
Build your hope up

Give back your hope

Raindrop is a wintercrop
Light is a misanthrope
Let it be without raindrop
Darkness is a kaleidoscope
Let it be without raindrop

Diamond takes your hour, love, and your day
If love is the way
Let your sorrow be your hour without light
Put your sorrow over darkness into flight
Put your memory of flight into motion
Put it with love, and motion into the ocean
Whisper the ocean

If love ain't the way
Let ray be your day of darkness without light
Let your courage be your hour without darkness, and ray
Put your courage over darkness into the night
Put your memory of ray into action
Let satisfaction be your memory of the night
Let alright be satisfaction with love, action, love, and satisfaction
Shout alright


Listen to the wind
Let flight be the wind
Let your heart be Dream taking flight
Let your breath be your heart of darkness with light
Your hope's stop'n'start
While your hope is lower than your heart
Let away be Despair taking your hope
Diamond taking your breath, away, and your hope
Build your hope up

Renown is southbound
While your hope is as high as renown
Let away be Despair taking your hope
Diamond taking your breath, away, and your hope
Knock your hope down

Not only do these look like lyrics, but it's also an executable program!

Execution #

If you want to run the program, you can copy the text and paste it into the web-based Rockstar interpreter; that's what I did.

When you Rock! the lyrics, the interpreter will prompt you for an input. There's no instructions or input validation, but the only valid input is the letters A to Z, and only in upper case. If you type anything else, I don't know what'll happen, but most likely it'll just enter an infinite loop, and you'll have to reboot your computer.

If you input, say, E, the output will be the expected diamond figure:

    A    
   B B   
  C   C  
 D     D 
E       E
 D     D 
  C   C  
   B B   
    A    

When you paste the code, be sure to include everything. There's significant whitespace in those lyrics; I'll explain later.

Readable code #

As the Rockstar documentation strongly implies, singability is more important than readability. You can, however, write more readable Rockstar code, and that's what I started with:

Space says  
LetterA says A

GetLetter takes index
If index is 0
Give back LetterA

If index is 1
retVal says B
Give back retVal

If index is 2
retVal says C
Give back retVal


GetIndex takes letter
Index is 0
While GetLetter taking Index ain't letter
Build Index up

Give back Index

PrintLine takes width, l, lidx
If l is LetterA
Let completeSpaceCount be width minus 1
Let paddingCount be completeSpaceCount over 2
Let padding be Space times paddingCount
Let line be padding plus l plus padding
Say line
Else
Let internalSpaceSize be lidx times 2 minus 1
Let filler be Space times internalSpaceSize
Let totalOuterPaddingSize be width minus 2, internalSpaceSize
Let paddingSize be totalOuterPaddingSize over 2
Let padding be Space times paddingSize
Let line be padding plus l, filler, l, padding
Say line

Listen to input
Let idx be GetIndex taking input
Let width be idx times 2 plus 1
Let counter be 0
While counter is lower than idx
Let l be GetLetter taking counter
PrintLine taking width, l, counter
Build counter up

While counter is as high as 0
Let l be GetLetter taking counter
PrintLine taking width, l, counter
Knock counter down

This prototype only handled the input letters A, B, and C, but it was enough to verify that the algorithm worked. I've done the diamond kata several times before, so I only had to find the most imperative implementation on my hard drive. It wasn't too hard to translate to Rockstar.

Although Rockstar supports mainstream quoted strings like "A", "B", and so on, you can see that I went straight for poetic string literals. Before I started persisting Rockstar code to a file, I experimented with the language using the online interpreter. I wanted the program to look as much like rock lyrics as I could, so I didn't want to have too many statements like Shout "FizzBuzz!" in my code.

Obscuring space #

My first concern was whether I could obscure the space character. Using a poetic string literal, I could:

Space says  

The rules of poetic string literals is that everything between says  and the newline character becomes the value of the string variable. So there's an extra space after says !

After I renamed all the variables and functions, that line became:

Your memory says  

Perhaps it isn't an unprintable character, but it is unsingable.

No else #

The keyword Else looks conspicuously like a programming construct, so I wanted to get rid of that as well. That was easy, because I could just invert the initial if condition:

If l ain't LetterA

This effectively switches between the two alternative code blocks.

Obscuring letter indices #

I also wanted to obscure the incrementing index values 1, 2, 3, etcetera. Since the indices are monotonically increasing, I realised that I could use a counter and increment it:

number is 0
If index is number
Let retVal be LetterA

Build number up
If index is number
retVal says B

Build number up
If index is number
retVal says C

The function initialises number to 0 and assigns a value to retVal if the input index is also 0.

If not, it increments the number (so that it's now 1) and again compares it to index. This sufficiently obscures the indices, but if there's a way to hide the letters of the alphabet, I'm not aware of it.

After I renamed the variables, the code became:

Your courage is a tightrope
Let it be without it
If your hope is your courage
Let the key be the way

Build your courage up
If your hope is your courage
The key says B

Build your courage up
If your hope is your courage
The key says C

There's one more line of code in the final lyrics, compared to the above snippet. The line Let it be without it has no corresponding line of code in the readable version. What's going on?

Obscuring numbers #

Like poetic string literals, Rockstar also supports poetic number literals. Due to its modulo-ten-based system, however, I found it difficult to come up with a good ten-letter word that fit the song's lyrical theme. I could have done something like this to produce the number 0:

Your courage is barbershop

or some other ten-letter word. My problem was that regardless of what I chose, it didn't sound good. Some article like a or the would sound better, but that would change the value of the poetic number literal. a tightrope is the number 19, because a has one letter, and tightrope has nine.

There's a simple way to produce 0 from any number: just subtract the number from itself. That's what Let it be without it does. I could also have written it as Let your courage be without your courage, but I chose to take advantage of Rockstar's pronoun feature instead. I'd been looking for an opportunity to include the phrase Let It Be ever since I learned about the Let x be y syntax.

The following code snippet initialises the variable Your courage to 19, but on the next line subtracts 19 from 19 and updates the variable so that its value is now 0.

Your courage is a tightrope
Let it be without it

I had the same problem with initialising the numbers 1 and 2, so further down I resorted to similar tricks:

Raindrop is a wintercrop
Light is a misanthrope
Let it be without raindrop
Darkness is a kaleidoscope
Let it be without raindrop 

Here I had the additional constraint that I wanted the words to rhyme. The rhymes are a continuation of the previous lines' up and hope, so I struggled to come up with a ten-letter word that rhymes with up; wintercrop was the best I could do. a wintercrop is 10, and the strategy is to define Light and Darkness as 11 and 12, and then subtract 10 from both. At the first occurrence of Let it be without raindrop, it refers to Light, whereas the second time it refers to Darkness.

Lyrical theme #

Once I had figured out how to obscure strings and numbers, it was time to rename all the readable variables and function names into idiomatic Rockstar.

At first, I thought that I'd pattern my lyrics after Shine On You Crazy Diamond, but I soon ran into problems with the keyword taking. I found it difficult to find words that would naturally succeed taking. Some options I thought of were:

• taking the bus
• taking a chance
• taking hold
• taking flight
• taking time

Taking a chance sounded too much like ABBA. Taking hold created the derived problem that I had to initialise and use a variable called hold, and I couldn't make that work.

Taking flight, on the other hand, turned out to provide a fertile opening.

I soon realised, though, that my choice of words pulled the lyrical theme away from idiomatic Rockstar vocabulary. While I do get the Tommy and Gina references, I didn't feel at home in that poetic universe.

On the other hand, I thought that the words started to sound like Yes. I've listened to a lot of Yes. The lyrics are the same kind of lame and vapid as what was taking form in my editor. I decided to go in that direction.

Granted, this is no longer idiomatic Rockstar, since it's more prog rock than hair metal. I invoke creative license.

Soon I also conceived of the extra ambition that I wanted the verses to rhyme. Here, it proved fortunate that the form let x be y is interchangeable with the form put y into x. Some words, like darkness, are difficult to rhyme with, so it helps that you can hide them within a put y into x form.

Over the hours(!) I worked on this, a theme started to emerge. I'm particularly fond of the repeated motifs like:

Your hope's start'n'stop

which rhymes with up, but then later it appears again as

Your hope's stop'n'start

which rhymes with heart. Both words, by the way, represent the number 0, since there's ten letters when you ignore the single quotes.

Conclusion #

I spent more time on this that I suppose I ought to, but once I got started, it was hard to stop. I found the translation from readable code into 'idiomatic' Rockstar at least as difficult as writing working software. There's a lesson there, I believe.

Rockstar is still a budding language, so I did miss a few features, chief among which would be arrays, but I'm not sure how one would make arrays sufficiently rock'n'roll.

A unit testing framework would also be nice.

If you liked this article, please endorse my Rockstar skills on LinkedIn so that we can "confuse recruiters."

Write small blocks of code. How small? Here's how small.

One of the most common questions I get is this:

If you could give just one advice to programmers, what would it be?

That's easy:

Write small blocks of code.

Small methods. Small functions. Small procedures.

How small?

Few lines of code #

You can't give a universally good answer to that question. Among other things, it depends on the programming language in question. Some languages are much denser than others. The densest language I've ever encountered is APL.

Most mainstream languages, however, seem to be verbose to approximately the same order of magnitude. My experience is mostly with C#, so I'll use that (and similar languages like Java) as a starting point.

When I write C# code, I become uncomfortable when my method size approaches fifteen or twenty lines of code. C# is, however, a fairly wordy language, so it sometimes happens that I have to allow a method to grow larger. My limit is probably somewhere around 25 lines of code.

That's an arbitrary number, but if I have to quote a number, it would be around that size. Since it's arbitrary anyway, let's make it 24, for reasons that I'll explain later.

The maximum line count of a C# (or Java, or JavaScript, etc.) method, then, should be 24.

To repeat the point from before, this depends on the language. I'd consider a 24-line Haskell or F# function to be so huge that if I received it as a pull request, I'd reject it on the grounds of size alone.

Narrow line width #

Most languages allow for flexibility in layout. For example, C-based languages use the ; character as a delimiter. This enables you to write more than one statement per line:

var foo = 32; var bar = foo + 10; Console.WriteLine(bar);

You could attempt to avoid the 24-line-height rule by writing wide lines. That would, however, be to defeat the purpose.

The purpose of writing small methods is to nudge yourself towards writing readable code; code that fits in your brain. The smaller, the better.

For completeness sake, let's institute a maximum line width as well. If there's any accepted industry standard for maximum line width, it's 80 characters. I've used that maximum for years, and it's a good maximum.

Like all other programmers, other people's code annoys me. The most common annoyance is that people write too wide code.

This is probably because most programmers have drunk the Cool Aid that bigger screens make you more productive. When you code on a big screen, you don't notice how wide your lines become.

There's many scenarios where wide code is problematic:

• When you're comparing changes to a file side-by-side. This often happens when you review pull requests. Now you have only half of your normal screen width.
• When you're looking at code on a smaller device.
• When you're getting old, or are otherwise visually impaired. After I turned 40, I discovered that I found it increasingly difficult to see small things. I still use a 10-point font for programming, but I foresee that this will not last much longer.
• When you're mob programming you're limited to the size of the shared screen.
• When you're sharing your screen via the web, for remote pair programming or similar.
• When you're presenting code at meetups, user groups, conferences, etc.

Notice the red dotted vertical line that cuts through universe. It tells me where the 80 character limit is.

Terminal box #

The 80-character limit has a long and venerable history, but what about the 24-line limit? While both are, ultimately, arbitrary, both fit the size of the popular VT100 terminal, which had a display resolution of 80x24 characters.

A box of 80x24 characters thus reproduces the size of an old terminal. Does this mean that I suggest that you should write programs on terminals? No, people always misunderstand this. That should be the maximum size of a method. On larger screens, you'd be able to see multiple small methods at once. For example, you could view a unit test and its target in a split screen configuration.

The exact sizes are arbitrary, but I think that there's something fundamentally right about such continuity with the past.

I've been using the 80-character mark as a soft limit for years. I tend to stay within it, but I occasionally decide to make my code a little wider. I haven't paid quite as much attention to the number of lines of my methods, but only for the reason that I know that I tend to write methods shorter than that. Both limits have served me well for years.

Example #

Consider this example:

public ActionResult Post(ReservationDto dto)
{
    var validationMsg = Validator.Validate(dto);
    if (validationMsg != "")
        return BadRequest(validationMsg);
 
    var reservation = Mapper.Map(dto);
    var reservations = Repository.ReadReservations(reservation.Date);
 
    var accepted = maîtreD.CanAccept(reservations, reservation);
    if (!accepted)
        return StatusCode(
            StatusCodes.Status500InternalServerError,
            "Couldn't accept.");
 
    var id = Repository.Create(reservation);
    return Ok(id);
}

This method is 18 lines long, which includes the method declaration, curly brackets and blank lines. It easily stays within the 80-character limit. Note that I've deliberately formatted the code so that it behaves. You can see it in this fragment:

return StatusCode(
    StatusCodes.Status500InternalServerError,
    "Couldn't accept.");

Most people write it like this:

return StatusCode(StatusCodes.Status500InternalServerError, "Couldn't accept.");

That doesn't look bad, but I've seen much worse examples.

Another key to writing small methods is to call other methods. The above Post method doesn't look like much, but significant functionality could be hiding behind Validator.Validate, Repository.ReadReservations, or maîtreD.CanAccept. I hope that you agree that each of these objects and methods are named well enough to give you an idea about their purpose.

Code that fits in your brain #

As I describe in my Humane Code video, the human brain can only keep track of about seven things. I think that this rule of thumb applies to the way we read and interpret code. If you need to understand and keep track of more than seven separate things at the same time, the code becomes harder to understand.

This could explain why small methods are good. They're only good, however, if they're self-contained. When you look at a method like the above Post method, you'll be most effective if you don't need to have a deep understanding of how each of the dependencies work. If this is true, the method only juggles about five dependencies: Validator, Mapper, Repository, maîtreD, and its own base class (which provides the methods BadRequest, StatusCode, and Ok). Five dependencies is fewer than seven.

Another way to evaluate the cognitive load of a method is to measure its cyclomatic complexity. The Post method's cyclomatic complexity is 3, so that should be easily within the brain's capacity.

These are all heuristics, so read this for inspiration, not as law. They've served me well for years, though.

Conclusion #

You've probably heard about the 80/20 rule, also known as the Pareto principle. Perhaps the title lead you to believe that this article was a misunderstanding. I admit that I went for an arresting title; perhaps a more proper name is the 80x24 rule.

The exact numbers can vary, but I've found a maximum method size of 80x24 characters to work well for C#.

Comments

This article shows an idiomatic, yet beginner-friendly Haskell solution to a coding exercise.

Mike Hadlow tweeted a coding exercise that involves parsing and evaluating instruction sets. Haskell excels at such problems, so I decided to give it a go. Since this was only an exercise for the fun of it, I didn't want to set up a complete Haskell project. Rather, I wanted to write one or two .hs files that I could interact with via GHCi. This means no lenses, monad transformers, or other fancy libraries.

Hopefully, this makes the code friendly to Haskell beginners. It shows what I consider idiomatic, but basic Haskell, solving a problem of moderate difficulty.

The problem #

Mike Hadlow has a detailed description of the exercise, but in short, you're given a file with a set of instructions that look like this:

1 1 E
RFRFRFRF
1 1 E

The first and last lines describe the position and orientation of a robot. The first line, for example, describes a robot at position (1, 1) facing east. A robot can face in one of the four normal directions of the map: north, east, south, and west.

The first line gives the robot's start position, and the last line the expected end position.

The middle line is a set of instructions to the robot. It can turn left or right, or move forward.

The exercise is to evaluate whether journeys are valid; that is, whether the robot's end position matches the expected end position if it follows the commands.

Imports #

I managed to solve the exercise with a single Main.hs file. Here's the module declaration and the required imports:

module Main where
 
import Data.Foldable
import Data.Ord
import Text.Read (readPrec)
import Text.ParserCombinators.ReadP
import Text.ParserCombinators.ReadPrec (readPrec_to_P, minPrec)

These imports are only required to support parsing of input. Once parsed, you can evaluate each journey using nothing but the functions available in the standard Prelude.

Types #

Haskell is a statically typed language, so it often pays to define some types. Granted, the exercise hardly warrants all of these types, but as an example of idiomatic Haskell, I think that this is still good practice. After all, Haskell types are easy to declare. Often, they are one-liners:

data Direction = North | East | South | West deriving (Eq, Show, Read)

The Direction type enumerates the four corners of the world.

data Robot = Robot {
    robotPosition :: (Integer, Integer)
  , robotDirection :: Direction }
  deriving (Eq, Show, Read)

The Robot record type represents the state of a robot: its position and the direction it faces.

You'll also need to enumerate the commands that you can give a robot:

data Command = TurnLeft | TurnRight | MoveForward deriving (Eq, Show, Read)

Finally, you can also define a type for a Journey:

data Journey = Journey {
    journeyStart :: Robot
  , journeyCommands :: [Command]
  , journeyEnd :: Robot }
  deriving (Eq, Show, Read)

These are all the types required for solving the exercise.

Parsing #

The format of the input file is simple enough that it could be done in an ad-hoc fashion using lines, word, read, and a few other low-level functions. While the format barely warrants the use of parser combinators, I'll still use some to showcase the power of that approach.

Since one of my goals is to implement the functionality using a single .hs file, I can't pull in external parser combinator libraries. Instead, I'll use the built-in ReadP module, which I've often found sufficient to parse files like the present exercise input file.

First, you're going to have to be able to parse numbers, which can be done using the Read type class. You'll need, however, to be able to compose Integer parsers with other ReadP parsers.

parseRead :: Read a => ReadP a
parseRead = readPrec_to_P readPrec minPrec

This turns every Read instance value into a ReadP value. (I admit that I wasn't sure which precedence number to use, but minPrec seems to work.)

Next, you need a parser for Direction values:

parseDirection :: ReadP Direction
parseDirection =
  choice [
    char 'N' >> return North,
    char 'E' >> return East,
    char 'S' >> return South,
    char 'W' >> return West ]

Notice how declarative this looks. The choice function combines a list of other parsers. When an individual parser in that list encounters the 'N' character, it'll parse it as North, 'E' as East, and so on.

You can now parse an entire Robot using the Applicative <*> and <* operators.

parseRobot :: ReadP Robot
parseRobot =
  (\x y d -> Robot (x, y) d) <$>
  (parseRead <* char ' ') <*>
  (parseRead <* char ' ') <*>
   parseDirection

The <*> operator combines two parsers by using the output of both of them, whereas the <* combines two parsers by running both of them, but discarding the output of the right-hand parser. A good mnemonic is that the operator points to the parser that produces an output. Here', the parseRobot function uses the <* operator to require that each number is followed by a space. The space, however, is just a delimiter, so you throw it away.

parseRead parses any Read instance. Here, the parseRobot function uses it to parse each Integer in a robot's position. It also uses parseDirection to parse the robot's direction.

Similar to how you can parse directions, you can also parse the commands:

parseCommand :: ReadP Command
parseCommand =
  choice [
    char 'L' >> return TurnLeft,
    char 'R' >> return TurnRight,
    char 'F' >> return MoveForward]

Likewise, similar to how you parse a single robot, you can now parse a journey:

parseJourney :: ReadP Journey
parseJourney =
  Journey <$>
  (parseRobot <* string "\n") <*>
  (many parseCommand <* string "\n") <*>
   parseRobot

The only new element compared to parseRobot is the use of the many parser combinator, which looks for zero, one, or many Command values.

This gives you a way to parse a complete journey, but the input file contains many of those, separated by newlines and other whitespace:

parseJourneys :: ReadP [Journey]
parseJourneys = parseJourney `sepBy` skipSpaces

Finally, you can parse a multi-line string into a list of journeys:

parseInput :: String -> [Journey]
parseInput = fst . minimumBy (comparing snd) . readP_to_S parseJourneys

When you run readP_to_S, it'll produce a list of alternatives, as there's more than one way to interpret the file according to parseJourneys. Each alternative is presented as a tuple of the parse result and the remaining (or unconsumed) string. I'm after the alternative that consumes as much of the input file as possible (which turns out to be all of it), so I use minimumBy to find the tuple that has the smallest second element. Then I return the first element of that tuple.

Play around with readP_to_S parseJourneys in GHCi if you want all the details.

Evaluation #

Haskell beginners may still find operators like <*> cryptic, but they're essential to parser combinators. Evaluation of the journeys is, in comparison, simple.

You can start by defining a function to turn right:

turnRight :: Robot -> Robot
turnRight r@(Robot _ North) = r { robotDirection = East }
turnRight r@(Robot _  East) = r { robotDirection = South }
turnRight r@(Robot _ South) = r { robotDirection = West }
turnRight r@(Robot _  West) = r { robotDirection = North }

There's more than one way to write a function that rotates one direction to the right, but I chose one that I found most readable. It trades clarity for verbosity by relying on simple pattern matching. I hope that it's easy to understand for Haskell beginners, and perhaps even for people who haven't seen Haskell code before.

The function to turn left uses the same structure:

turnLeft :: Robot -> Robot
turnLeft r@(Robot _ North) = r { robotDirection = West }
turnLeft r@(Robot _  West) = r { robotDirection = South }
turnLeft r@(Robot _ South) = r { robotDirection = East }
turnLeft r@(Robot _  East) = r { robotDirection = North }

The last command you need to implement is moving forward:

moveForward :: Robot -> Robot
moveForward (Robot (x, y) North) = Robot (x, y + 1) North
moveForward (Robot (x, y)  East) = Robot (x + 1, y) East
moveForward (Robot (x, y) South) = Robot (x, y - 1) South
moveForward (Robot (x, y)  West) = Robot (x - 1, y) West

The moveForward function also pattern-matches on the direction the robot is facing, this time to increment or decrement the x or y coordinate as appropriate.

You can now evaluate all three commands:

evalCommand :: Command -> Robot -> Robot
evalCommand   TurnRight = turnRight
evalCommand    TurnLeft = turnLeft
evalCommand MoveForward = moveForward

The evalCommand pattern-matches on all three Command cases and returns the appropriate function for each.

You can now evaluate whether a Journey is valid:

isJourneyValid :: Journey -> Bool
isJourneyValid (Journey s cs e) = foldl (flip evalCommand) s cs == e

The isJourneyValid function pattern-matches the constituent values out of Journey. I named the journeyStart value s (for start), the journeyCommands value cs (for commands), and the journeyEnd value e (for end).

The evalCommand function evaluates a single Command, but a Journey contains many commands. You'll need to evaluate the first command to find the position from which you evaluate the second command, and so on. Imperative programmers would use a for loop for something like that, but in functional programming, a fold, in this case from the left, is how it's done.

foldl requires you to supply an initial state s as well as the list of commands cs. The entire foldl expression produces a final Robot state that you can compare against the expected end state e.

Execution #

Load the input file, parse it, and evaluate each journey in the main function:

main :: IO ()
main = do
  input <- parseInput <$> readFile "input.txt"
  mapM_ print $ isJourneyValid <$> input

I just load the Main.hs file in GHCi and run the main function:

Prelude> :load Main.hs
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.
*Main> main
True
True
True

I used the same input file as Mike Hadlow, and it turns out that all journeys are valid. That's not what I'd expected from an exercise like this, so I cloned and ran Mike's solution as well, and it seems that it arrives at the same result.

Conclusion #

Haskell is a great language for small coding exercises that require parsing and interpretation. In this article, I demonstrated one solution to the robot journeys coding exercise. My goal was to show some beginner-friendly, but still idiomatic Haskell code.

Granted, the use of parser combinators is on the verge of being overkill, but I wanted to show an example; Haskell examples are scarce, so I hope it's helpful.

A simple read-do checklist for test-driven development.

I recently read The Checklist Manifesto, a book about the power of checklists. That may sound off-putting and tedious, but I actually found it inspiring. It explains how checklists empower skilled professionals to focus on difficult problems, while preventing avoidable mistakes.

Since I read the book with the intent to see if there were ideas that we could apply in software development, I thought about checklists one might create for software development. Possibly the simplest checklist is one that describes the red-green-refactor cycle of test-driven development.

Types of checklists #

As the book describes, there's basically two types of checklists:

• Do-confirm. With such a checklist, you perform a set of tasks, and then subsequently, at a sufficient pause point go through the checklist to verify that you remembered to perform all the tasks on the list.
• Read-do. With this type of checklist, you read each item for instructions and then perform the task. Only when you've performed the task do you move on to the next item on the list.

This list is, I think, mostly useful if you're still learning test-driven development. It can be easily internalised. As such, I offer this for inspiration, and as a learning aid.

Red-green-refactor checklist #

Read each of the steps in the list and perform the task.

1. Write a failing test.
   • Did you run the test?
   • Did it fail?
   • Did it fail because of an assertion?
   • Did it fail because of the last assertion?
2. Make all tests pass by doing the simplest thing that could possibly work.
3. Consider the resulting code. Can it be improved? If so, do it, but make sure that all tests still pass.
4. Repeat

I regularly see people write failing tests as an initial step. The reason the test fails, however, is because the implementation throws an exception.

Improperly failing tests #

Consider, as an example, the first test you might write when doing the FizzBuzz kata.

[Fact]
public void One()
{
    string actual = FizzBuzz.Convert(1);
    Assert.Equal("1", actual);
}

I wrote this test first (i.e. before the 'production' code) and used Visual Studio's refactoring tools to generate the implied type and method.

When I run the test, it fails.

Further investigation, however, reveals that the test fails when Convert is called:

Ploeh.Katas.FizzBuzzKata.FizzBuzzTests.One
   Source: FizzBuzzTests.cs line: 11
   Duration: 8 ms

  Message: 
    System.NotImplementedException : The method or operation is not implemented.
  Stack Trace: 
    at FizzBuzz.Convert(Int32 i) in FizzBuzz.cs line: 9
    at FizzBuzzTests.One() in FizzBuzzTests.cs line: 13

This is hardly surprising, since this is the current 'implementation':

public static string Convert(int i)
{
    throw new NotImplementedException();
}

This is what the subordinate do-confirm checklist is for. Did the test fail because of an assertion? In this case, the answer is no.

This means that you're not yet done with the read phase.

Properly failing tests #

You can address the issue by changing the Convert method:

public static string Convert(int i)
{
    return "";
}

This causes the test to fail because of an assertion:

 Ploeh.Katas.FizzBuzzKata.FizzBuzzTests.One
   Source: FizzBuzzTests.cs line: 11
   Duration: 13 ms

  Message: 
    Assert.Equal() Failure
              ↓ (pos 0)
    Expected: 1
    Actual:   
              ↑ (pos 0)
  Stack Trace: 
    at FizzBuzzTests.One() in FizzBuzzTests.cs line: 14

Not only does the test fail because of an assertion - it fails because of the last assertion (since there's only one assertion). This completes the do-confirm checklist, and you're now ready to make the simplest change that could possibly work:

public static string Convert(int i)
{
    return "1";
}

This passes the test suite.

Conclusion #

It's important to see tests fail. Particularly, it's important to see tests fail for the reason you expect them to fail. You'd be surprised how often you inadvertently write an assertion that can never fail.

Once you've seen the test fail for the proper reason, make it pass.

Finally, refactor the code if necessary.

Comments

It's surprisingly easy to write a unit test assertion that never fails.

Recently I was mob programming with a pair of IDQ's programmers. We were starting a new code base, using test-driven development (TDD). This was the first test we wrote:

[Fact]
public async Task HandleObserveUnitStatusStartsSaga()
{
    var subscribers = new List<Guid> { Guid.Parse("{4D093799-9CCC-4135-8CB3-8661985A5853}") };
    var sut = new StatusPolicy
    {
        Data = new StatusPolicyData
        {
            UnitId = 123,
            Subscribers = subscribers
        }
    };
 
    var subscriber = Guid.Parse("{003C5527-7747-4C7A-980E-67040DB738C3}");
    var message = new ObserveUnitStatus(123, subscriber);
    var context = new TestableMessageHandlerContext();
    await sut.Handle(message, context);
 
    Assert.Contains(subscriber, sut.Data.Subscribers);
}

This unit test uses xUnit.net 2.4.0 and NServiceBus 7.1.10 on .NET Core 2.2. The System Under Test (SUT) is intended to be an NServiceBus Saga that monitors a resource for status changes. If a unit changes status, the Saga will alert its subscribers.

The test verifies that when a new subscriber wishes to observe a unit, then its ID is added to the policy's list of subscribers.

The test induced us to implement Handle like this:

public Task Handle(ObserveUnitStatus message, IMessageHandlerContext context)
{
    Data.Subscribers.Add(message.SubscriberId);
    return Task.CompletedTask;
}

Following the red-green-refactor cycle of TDD, this seemed an appropriate implementation.

Enter the Devil #

I often use the Devil's advocate technique to figure out what to do next, so I made this change to the Handle method:

public Task Handle(ObserveUnitStatus message, IMessageHandlerContext context)
{
    Data.Subscribers.Clear();
    Data.Subscribers.Add(message.SubscriberId);
    return Task.CompletedTask;
}

The change is that the method first deletes all existing subscribers. This is obviously wrong, but it passes all tests. That's no surprise, since I intentionally introduced the change to make us improve the test.

False negative #

We had to write a new test, or improve the existing test, so that the defect I just introduced would be caught. I suggested an improvement to the existing test:

[Fact]
public async Task HandleObserveUnitStatusStartsSaga()
{
    var subscribers = new List<Guid> { Guid.Parse("{4D093799-9CCC-4135-8CB3-8661985A5853}") };
    var sut = new StatusPolicy
    {
        Data = new StatusPolicyData
        {
            UnitId = 123,
            Subscribers = subscribers
        }
    };
 
    var subscriber = Guid.Parse("{003C5527-7747-4C7A-980E-67040DB738C3}");
    var message = new ObserveUnitStatus(123, subscriber);
    var context = new TestableMessageHandlerContext();
    await sut.Handle(message, context);
 
    Assert.Contains(subscriber, sut.Data.Subscribers);
    Assert.Superset(
        expectedSubset: new HashSet<Guid>(subscribers),
        actual: new HashSet<Guid>(sut.Data.Subscribers));
}

The only change is the addition of the last assertion.

Smugly I asked the keyboard driver to run the tests, anticipating that it would now fail.

It passed.

We'd just managed to write a false negative. Even though there's a defect in the code, the test still passes. I was nonplussed. None of us expected the test to pass, yet it does.

It took us a minute to figure out what was wrong. Before you read on, try to figure it out for yourself. Perhaps it's immediately clear to you, but it took three people with decades of programming experience a few minutes to spot the problem.

Aliasing #

The problem is aliasing. While named differently, subscribers and sut.Data.Subscribers is the same object. Of course one is a subset of the other, since a set is considered to be a subset of itself.

The assertion is tautological. It can never fail.

Fixing the problem #

It's surprisingly easy to write tautological assertions when working with mutable state. This regularly happens to me, perhaps a few times a month. Once you've realised that this has happened, however, it's easy to address.

subscribers shouldn't change during the test, so make it immutable.

[Fact]
public async Task HandleObserveUnitStatusStartsSaga()
{
    IEnumerable<Guid> subscribers =
        new[] { Guid.Parse("{4D093799-9CCC-4135-8CB3-8661985A5853}") };
    var sut = new StatusPolicy
    {
        Data = new StatusPolicyData
        {
            UnitId = 123,
            Subscribers = subscribers.ToList()
        }
    };
 
    var subscriber = Guid.Parse("{003C5527-7747-4C7A-980E-67040DB738C3}");
    var message = new ObserveUnitStatus(123, subscriber);
    var context = new TestableMessageHandlerContext();
    await sut.Handle(message, context);
 
    Assert.Contains(subscriber, sut.Data.Subscribers);
    Assert.Superset(
        expectedSubset: new HashSet<Guid>(subscribers),
        actual: new HashSet<Guid>(sut.Data.Subscribers));
}

An array strictly isn't immutable, but declaring it as IEnumerable<Guid> hides the mutation capabilities. The test now has to copy subscribers to a list before assigning it to the policy's data. This anti-aliases subscribers from sut.Data.Subscribers, and causes the test to fail. After all, there's a defect in the Handle method.

You now have to remove the offending line:

public Task Handle(ObserveUnitStatus message, IMessageHandlerContext context)
{
    Data.Subscribers.Add(message.SubscriberId);
    return Task.CompletedTask;
}

This makes the test pass.

Summary #

This article shows an example where I was surprised by aliasing. An assertion that I thought would fail turned out to be a false negative.

You can easily make the mistake of writing a test that always passes. If you haven't tried it, you may think that you're too smart to do that, but it regularly happens to me. Other TDD practitioners have told me that it also happens to them.

This is the reason that the red-green-refactor process encourages you to run each new test and see it fail. If you haven't seen it fail, you don't know if you've avoided a tautology.

How do you know when you have enough test cases. The Devil's Advocate technique can help you decide.

When I review unit tests, I often utilise a technique I call Devil's Advocate. I do the same whenever I consider if I have a sufficient number of test cases. The first time I explicitly named the technique was, I think, in my Outside-in TDD Pluralsight course, in which I also discuss the so-called Gollum style variation. I don't think, however, that I've ever written an article explicitly about this topic. The current text attempts to rectify that omission.

Coverage #

Programmers new to unit testing often struggle with identifying useful test cases. I sometimes see people writing redundant unit tests, while, on the other hand, forgetting to add important test cases. How do you know which test cases to add, and how do you know when you've added enough?

I may return to the first question in another article, but in this, I wish to address the second question. How do you know that you have a sufficient set of test cases?

You may think that this is a question of turning on code coverage. Surely, if you have 100% code coverage, that's sufficient?

It's not. Consider this simple class:

public class MaîtreD
{
    public MaîtreD(int capacity)
    {
        Capacity = capacity;
    }
 
    public int Capacity { get; }
 
    public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
    {
        var reservedSeats = reservations.Sum(r => r.Quantity);
 
        if (Capacity < reservedSeats + reservation.Quantity)
            return false;
 
        return true;
    }
}

This class implements the (simplified) decision logic for an online restaurant reservation system. The CanAccept method has a cyclomatic complexity of 2, so it should be easy to cover with a pair of unit tests:

[Fact]
public void CanAcceptWithNoPriorReservations()
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 4
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(new Reservation[0], reservation);
 
    Assert.True(actual);
}
 
[Fact]
public void CanAcceptOnInsufficientCapacity()
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 4
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = 7 } },
        reservation);
 
    Assert.False(actual);
}

These two tests together completely cover the CanAccept method:

You'd think that this is a sufficient number of test cases of the method, then.

As the Devil reads the Bible #

In Scandinavia we have an idiom that Kent Beck (who's worked with Norwegian companies) has also encountered:

"TIL: "like the devil reads the Bible"--meaning someone who carefully reads a book to subvert its intent"

If you think of a unit test suite as an executable specification, you may consider if you can follow the specification to the letter while intentionally introduce a defect. You can easily do that with the above CanAccept method:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Sum(r => r.Quantity);
 
    if (Capacity <= reservedSeats + reservation.Quantity)
        return false;
 
    return true;
}

This still passes both tests, and still has a code coverage of 100%, yet it's 'obviously' wrong.

Can you spot the difference?

Instead of a less-than comparison, it now uses a less-than-or-equal comparison. You could easily, inadvertently, make such a mistake while programming. It belongs in the category of off-by-one errors, which is one of the most common type of bugs.

This is, in a nutshell, the Devil's Advocate technique. The intent isn't to break the software by sneaking in defects, but to explore how effectively the test suite detects bugs. In the current (simplified) example, the effectiveness of the test suite isn't impressive.

Add test cases #

The problem introduced by the Devil's Advocate is an edge case. If the reservation under consideration fits the restaurant's remaining capacity, but entirely consumes it, the MaîtreD class should still accept it. Currently, however, it doesn't.

It'd seem that the obvious solution is to 'fix' the unit test:

[Fact]
public void CanAcceptWithNoPriorReservations()
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 10
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(new Reservation[0], reservation);
 
    Assert.True(actual);
}

Changing the requested Quantity to 10 does, indeed, cause the test to fail.

Beyond mutation testing #

Until this point, you may think that the Devil's Advocate just looks like an ad-hoc, informally-specified, error-prone, manual version of half of mutation testing. So far, the change I made above could also have been made during mutation testing.

What I sometimes do with the Devil's Advocate technique is to experiment with other, less heuristically driven changes. For instance, based on my knowledge of the existing test cases, it's not too difficult to come up with this change:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Sum(r => r.Quantity);
 
    if (reservation.Quantity != 10)
        return false;
 
    return true;
}

That's an even simpler implementation than the original, but obviously wrong.

This should prompt you to add at least one other test case:

[Theory]
[InlineData( 4)]
[InlineData(10)]
public void CanAcceptWithNoPriorReservations(int quantity)
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(new Reservation[0], reservation);
 
    Assert.True(actual);
}

Notice that I converted the test to a parametrised test. This breaks the Devil's latest attempt, while the original implementation passes all tests.

The Devil, not to be outdone, now switches tactics and goes after the reservations instead:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    return !reservations.Any();
}

This still passes all tests, including the new test case. This indicates that you'll need to add at least one test case with existing reservations, but where there's still enough capacity to accept another reservation:

[Fact]
public void CanAcceptWithOnePriorReservation()
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 4
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = 4 } },
        reservation);
 
    Assert.True(actual);
}

This new test fails, prompting you to correct the implementation of CanAccept. The Devil, however, can do this:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Sum(r => r.Quantity);
    return reservedSeats != 7;
}

This is still not correct, but passes all tests. It does, however, look like you're getting closer to a proper implementation.

Reverse Transformation Priority Premise #

If you find this process oddly familiar, it's because it resembles the Transformation Priority Premise (TPP), just reversed.

“As the tests get more specific, the code gets more generic.”

When I test-drive code, I often try to follow the TPP, but when I review code with tests, the code and the tests are already in place, and it's my task to assess both.

Applying the Devil's Advocate review technique to CanAccept, it seems as though I'm getting closer to a proper implementation. It does, however, require more tests. As your next move you may, for instance, consider parametrising the test case that verifies what happens when capacity is insufficient:

[Theory]
[InlineData(7)]
[InlineData(8)]
public void CanAcceptOnInsufficientCapacity(int reservedSeats)
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 4
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = reservedSeats } },
        reservation);
 
    Assert.False(actual);
}

That doesn't help much, though, because this passes all tests:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Sum(r => r.Quantity);
    return reservedSeats < 7;
}

Compared to the initial, 'desired' implementation, there's at least two issues with this code:

• It doesn't consider reservation.Quantity
• It doesn't take into account the Capacity of the restaurant

[Theory]
[InlineData( 1, 10)]
[InlineData( 2,  9)]
[InlineData( 3,  8)]
[InlineData( 4,  7)]
[InlineData( 4,  8)]
[InlineData( 5,  6)]
[InlineData( 6,  5)]
[InlineData(10,  1)]
public void CanAcceptOnInsufficientCapacity(int quantity, int reservedSeats)
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = reservedSeats } },
        reservation);
 
    Assert.False(actual);
}

This makes it harder for the Devil to come up with a malevolent implementation. Harder, but not impossible.

It seems clear that since all test cases still use a hard-coded capacity, it ought to be possible to write an implementation that ignores the Capacity, but at this point I don't see a simple way to avoid looking at reservation.Quantity:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Sum(r => r.Quantity);
    return reservedSeats + reservation.Quantity < 11;
}

This implementation passes all the tests. The last batch of test cases forced the Devil to consider reservation.Quantity. This strongly implies that if you vary Capacity as well, the proper implementation out to emerge.

Diminishing returns #

What happens, then, if you add just one test case with a different Capacity?

[Theory]
[InlineData( 1, 10, 10)]
[InlineData( 2,  9, 10)]
[InlineData( 3,  8, 10)]
[InlineData( 4,  7, 10)]
[InlineData( 4,  8, 10)]
[InlineData( 5,  6, 10)]
[InlineData( 6,  5, 10)]
[InlineData(10,  1, 10)]
[InlineData( 1,  1,  1)]
public void CanAcceptOnInsufficientCapacity(
    int quantity,
    int reservedSeats,
    int capacity)
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = reservedSeats } },
        reservation);
 
    Assert.False(actual);
}

Notice that I just added one test case with a Capacity of 1.

You may think that this is about where the Devil ought to capitulate, but not so. This passes all tests:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = 0;
    foreach (var r in reservations)
    {
        reservedSeats = r.Quantity;
        break;
    }
    return reservedSeats + reservation.Quantity <= Capacity;
}

Here you may feel the urge to protest. So far, all the Devil's Advocate implementations have been objectively simpler than the 'desired' implementation because it has involved fewer elements and has had a lower or equivalent cyclomatic complexity. This new attempt to circumvent the specification seems more complex.

It's also seems clearly ill-intentioned. Recall that the intent of the Devil's Advocate technique isn't to 'cheat' the unit tests, but rather to explore how well the test describe the desired behaviour of the system. The motivation is that it's easy to make off-by-one errors like inadvertently use <= instead of <. It doesn't seem quite as reasonable that a well-intentioned programmer accidentally would leave behind an implementation like the above.

You can, however, make it look less complicated:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    var reservedSeats = reservations.Select(r => r.Quantity).FirstOrDefault();
    return reservedSeats + reservation.Quantity <= Capacity;
}

You could argue that this still looks intentionally wrong, but I've seen much code that looks like this. It seems to me that there's a kind of programmer who seems generally uncomfortable thinking in collections; they seem to subconsciously gravitate towards code that deals with singular objects. Code that attempts to get 'the' value out of a collection is, unfortunately, not that uncommon.

Still, you might think that at this point, you've added enough test cases. That's reasonable.

The Devil's Advocate technique isn't an algorithm; it has no deterministic exit criterion. It's just a heuristic that I use to explore the quality of tests. There comes a point where subjectively, I judge that the test cases sufficiently describe the desired behaviour.

You may find that we've reached that point now. You could, for example, argue that in order to calculate reservedSeats, reservations.Sum(r => r.Quantity) is simpler than reservations.Select(r => r.Quantity).FirstOrDefault(). I'd be inclined to agree.

There's diminishing returns to the Devil's Advocate technique. Once you find that the gains from insisting on intentionally pernicious implementations are smaller than the effort required to add more test cases, it's time to stop and commit to the test cases now in place.

Test case variability #

Tests specify desired behaviour. If the tests contain less variability than the code they cover, then how can you be certain that the implementation code is correct?

The discussion now moves into territory where I usually exercise a great deal of judgement. Read the following for inspiration, not as rigid instructions. My intent with the following is not to imply that you must always go to like extremes, but simply to demonstrate what you can do. Depending on circumstances (such as the cost of a defect in production), I may choose to do the following, and sometimes I may choose to skip it.

If you consider the original implementation of CanAccept at the top of the article, notice that it works with reservations of indefinite size. If you think of reservations as a finite collection, it can contain zero, one, two, ten, or hundreds of elements. Yet, no test case goes beyond a single existing reservation. This is, I think, a disconnect. The tests come not even close to the degree of variability that the method can handle. If this is a piece of mission-critical software, that could be a cause for concern.

You should add some test cases where there's two, three, or more existing reservations. People often don't do that because it seems that you'd now have to write a test method that exercises one or more test cases with two existing reservations:

[Fact]
public void CanAcceptWithTwoPriorReservations()
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = 4
    };
    var sut = new MaîtreD(capacity: 10);
 
    var actual = sut.CanAccept(
        new[] { new Reservation { Quantity = 4 }, new Reservation { Quantity = 1 } },
        reservation);
 
    Assert.True(actual);
}

While this method now covers the two-existing-reservations test case, you need one to cover the three-existing-reservations test case, and so on. This seems repetitive, and probably bothers you at more than one level:

• It's just plain tedious to have to add that kind of variability
• It seems to violate the DRY principle

What you can do instead is to parametrise the key values of the collection(s) in question. While you can't put collections of objects in [InlineData] attributes, you can put arrays of constants. For existing reservations, the key values are the quantities, so supply an array of integers as a test argument:

[Theory]
[InlineData( 4, new int[0])]
[InlineData(10, new int[0])]
[InlineData( 4, new[] { 4 })]
[InlineData( 4, new[] { 4, 1 })]
[InlineData( 2, new[] { 2, 1, 3, 2 })]
public void CanAcceptWhenCapacityIsSufficient(int quantity, int[] reservationQantities)
{
    var reservation = new Reservation
    {
        Date = new DateTime(2018, 8, 30),
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity: 10);
 
    var reservations = reservationQantities.Select(q => new Reservation { Quantity = q });
    var actual = sut.CanAccept(reservations, reservation);
 
    Assert.True(actual);
}

This single test method replaces the previous three 'happy path' test methods. The first four [InlineData] annotations reproduce the previous test cases, whereas the fifth [InlineData] annotation adds a new test case with four existing reservations.

I gave the method a new name to better reflect the more general nature of it.

Notice that the CanAcceptWhenCapacityIsSufficient method uses Select to turn the array of integers into a collection of Reservation objects.

You may think that I cheated, since I didn't supply any other values, such as the Date property, to the existing reservations. This is easily addressed:

[Theory]
[InlineData( 4, new int[0])]
[InlineData(10, new int[0])]
[InlineData( 4, new[] { 4 })]
[InlineData( 4, new[] { 4, 1 })]
[InlineData( 2, new[] { 2, 1, 3, 2 })]
public void CanAcceptWhenCapacityIsSufficient(int quantity, int[] reservationQantities)
{
    var date = new DateTime(2018, 8, 30);
    var reservation = new Reservation
    {
        Date = date,
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity: 10);
 
    var reservations =
        reservationQantities.Select(q => new Reservation { Quantity = q, Date = date });
    var actual = sut.CanAccept(reservations, reservation);
 
    Assert.True(actual);
}

The only change compared to before is that date is now a variable assigned not only to reservation, but also to all the Reservation objects in reservations.

Towards property-based testing #

Looking at a test method like CanAcceptWhenCapacityIsSufficient it should bother you that the capacity is still hard-coded. Why don't you make that a test argument as well?

[Theory]
[InlineData(10,  4, new int[0])]
[InlineData(10, 10, new int[0])]
[InlineData(10,  4, new[] { 4 })]
[InlineData(10,  4, new[] { 4, 1 })]
[InlineData(10,  2, new[] { 2, 1, 3, 2 })]
[InlineData(20, 10, new[] { 2, 2, 2, 2 })]
[InlineData(20,  4, new[] { 2, 2, 4, 1, 3, 3 })]
public void CanAcceptWhenCapacityIsSufficient(
    int capacity,
    int quantity,
    int[] reservationQantities)
{
    var date = new DateTime(2018, 8, 30);
    var reservation = new Reservation
    {
        Date = date,
        Quantity = quantity
    };
    var sut = new MaîtreD(capacity);
 
    var reservations =
        reservationQantities.Select(q => new Reservation { Quantity = q, Date = date });
    var actual = sut.CanAccept(reservations, reservation);
 
    Assert.True(actual);
}

The first five [InlineData] annotations just reproduce the test cases that were already present, whereas the bottom two annotations are new test cases with another capacity.

How do I come up with new test cases? It's easy: In the happy-path case, the sum of existing reservation quantities, plus the requested quantity, must be less than or equal to the capacity.

It sometimes helps to slightly reframe the test method. If you allow the collection of existing reservations to be the most variable element in the test method, you can express the other values relative to that input. For example, instead of supplying the capacity as an absolute number, you can express a test case's capacity in relation to the existing reservations:

[Theory]
[InlineData(6,  4, new int[0])]
[InlineData(0, 10, new int[0])]
[InlineData(2,  4, new[] { 4 })]
[InlineData(1,  4, new[] { 4, 1 })]
[InlineData(0,  2, new[] { 2, 1, 3, 2 })]
[InlineData(2, 10, new[] { 2, 2, 2, 2 })]
[InlineData(1,  4, new[] { 2, 2, 4, 1, 3, 3 })]
public void CanAcceptWhenCapacityIsSufficient(
    int capacitySurplus,
    int quantity,
    int[] reservationQantities)
{
    var date = new DateTime(2018, 8, 30);
    var reservation = new Reservation
    {
        Date = date,
        Quantity = quantity
    };
    var reservedSeats = reservationQantities.Sum();
    var capacity = reservedSeats + quantity + capacitySurplus;
    var sut = new MaîtreD(capacity);
 
    var reservations =
        reservationQantities.Select(q => new Reservation { Quantity = q, Date = date });
    var actual = sut.CanAccept(reservations, reservation);
 
    Assert.True(actual);
}

Notice that the value supplied as a test argument is now named capacitySurplus. This represents the surplus capacity for each test case. For example, in the first test case, the capacity was previously supplied as the absolute number 10. The requested quantity is 4, and since there's no prior reservations in that test case, the capacity surplus, after accepting the reservation, is 6.

Likewise, in the second test case, the requested quantity is 10, and since the absolute capacity is also 10, when you reframe the test case, the surplus capacity, after accepting the reservation, is 0.

This seems odd if you aren't used to it. You'd probably intuitively think of a restaurant's Capacity as 'the most absolute' number, in that it's often a number that originates from physical constraints.

When you're looking for test cases, however, you aren't looking for test cases for a particular restaurant. You're looking for test cases for an arbitrary restaurant. In other words, you're looking for test inputs that belong to the same equivalence class.

Property-based testing #

I haven't explicitly stated this yet, but both the capacity and each reservation Quantity should be a positive number. This should really have been captured as a proper domain object, but I chose to keep these values as primitive integers in order to not complicate the example too much.

If you look at the test parameters for the latest incarnation of CanAcceptWhenCapacityIsSufficient, you may now observe the following:

• capacitySurplus can be an arbitrary non-negative number
• quantity can be an arbitrary positive number
• reservationQantities can be an arbitrary array of positive numbers, including the empty array

[Property]
public void CanAcceptWhenCapacityIsSufficient(
    NonNegativeInt capacitySurplus,
    PositiveInt quantity,
    PositiveInt[] reservationQantities)
{
    var date = new DateTime(2018, 8, 30);
    var reservation = new Reservation
    {
        Date = date,
        Quantity = quantity.Item
    };
    var reservedSeats = reservationQantities.Sum(x => x.Item);
    var capacity = reservedSeats + quantity.Item + capacitySurplus.Item;
    var sut = new MaîtreD(capacity);
 
    var reservations =
        reservationQantities.Select(q => new Reservation { Quantity = q.Item, Date = date });
    var actual = sut.CanAccept(reservations, reservation);
 
    Assert.True(actual);
}

This refactoring takes advantage of FsCheck's built-in wrapper types NonNegativeInt and PositiveInt. If you'd like an introduction to FsCheck, you could watch my Introduction to Property-based Testing with F# Pluralsight course.

By default, FsCheck runs each property 100 times, so now, instead of seven test cases, you now have 100.

Limits to the Devil's Advocate technique #

There's a limit to the Devil's Advocate technique. Unless you're working with a problem where you can exhaust the entire domain of possible test cases, your testing strategy is always going to be a sampling strategy. You run your automated tests with either hard-coded values or randomly generated values, but regardless, a test run isn't going to cover all possible input combinations.

For example, a truly hostile Devil could make this change to the CanAccept method:

public bool CanAccept(IEnumerable<Reservation> reservations, Reservation reservation)
{
    if (reservation.Quantity == 3953911)
        return true;
 
    var reservedSeats = reservations.Sum(r => r.Quantity);
    return reservedSeats + reservation.Quantity <= Capacity;
}

Even if you increase the number of test cases that FsCheck generates to, say, 100,000, it's unlikely to find the poisonous branch. The chance of randomly generating a quantity of exactly 3953911 isn't that great.

The Devil's Advocate technique doesn't guarantee that you'll have enough test cases to protect yourself against all sorts of odd defects. It does, however, still work well as an analysis tool to figure out if there's 'enough' test cases.

Conclusion #

The Devil's Advocate technique is a heuristic you can use to evaluate whether more test cases would improve confidence in the test suite. You can use it to review existing (test) code, but you can also use it as inspiration for new test cases that you should consider adding.

The technique is to deliberately implement the system under test incorrectly. The more incorrect you can make it, the more test cases you'll be likely to have to add.

When there's only a few test cases, you can probably get away with a decidedly unsound implementation that still passes all tests. These are often simpler than the 'intended' implementation. In this phase of applying the heuristic, this clearly demonstrates the need for more test cases.

At a later stage, you'll have to go deliberately out of your way to produce a wrong implementation that still passes all tests. When that happens, it may be time to stop.

The intent of the technique is to uncover how many test cases you need to protect against common defects in the future. Thus, it's not a measure of current code coverage.

Comments

public static string Foo(int i)
{
    return "foo";
}

public static string Foo(int i)
{
    if (i < -1000)
        return "bar";
    return "foo";
}