ploeh blog danish software design

Is TDD white-box testing or black-box testing?

Surely you're aware of the terms black-box testing and white-box testing, but have you ever wondered where test-driven development (TDD) fits in that picture?

The short answer is that TDD as a software development practice sits somewhere between the two. It really isn't black and white, and exactly where TDD sits on the spectrum changes with circumstances.

If the above diagram indicates that TDD can't occupy the space of undiluted black- or white-box testing, that's not my intent. In my experience, however, you rarely do neither when you engage with the TDD process. Rather, you find yourself somewhere in-between.

In the following, I'll examine the two extremes in order to explain why TDD rarely leads to either, starting with black-box testing.

Compartmentalization of knowledge #

If you follow the usual red-green-refactor checklist, you write test code and production code in tight loops. You write some test code, some production code, more test code, then more production code, and so on.

If you're working by yourself, at least, that makes it almost impossible to treat the System Under Test (SUT) as a black box. After all, you're also the one who writes the production code.

You can try to 'forget' the production code you just wrote whenever you circle back to writing another test, but in practice, you can't. Even so, it may still be a useful exercise. I call this technique Gollum style (originally introduced in the Pluralsight course Outside-In Test-Driven Development as a variation on the Devil's advocate technique). The idea is to assume two roles, and to explicitly distinguish the goals of the tester from the aims of the implementer.

Still, while this can be an illuminating exercise, I don't pretend that this is truly black-box testing.

Pair programming #

If you pair-program, you have better options. You could have one person write a test, and another person implement the code to pass the test. I could imagine a setup where the tester can't see the production code. Although I've never seen or heard about anyone doing that, this would get close to true black-box TDD.

To demonstrate, imagine a team doing the FizzBuzz kata in this way. The tester writes the first test:

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

Either the implementer is allowed to see the test, or the specification is communicated to him or her in some other way. In any case, the natural response to the first test is an implementation like this:

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

In TDD, this is expected. This is the simplest implementation that passes all tests. We imagine that the tester already knows this, and therefore adds this test next:

[Fact]
public void Two()
{
    var actual = FizzBuzzer.Convert(2);
    Assert.Equal("2", actual);
}

The implementer's response is this:

public static string Convert(int number)
{
    if (number == 1)
        return "1";
    return "2";
}

The tester can't see the implementation, so may believe that the implementation is now 'appropriate'. Even if he or she wants to be 'more sure', a few more test cases (for, say, 4, 7, or 38) could be added; it doesn't make any difference for the following argument.

Next, incrementally, the tester may add a few test cases that cover the "Fizz" behaviour:

[Fact]
public void Three()
{
    var actual = FizzBuzzer.Convert(3);
    Assert.Equal("Fizz", actual);
}
 
[Fact]
public void Six()
{
    var actual = FizzBuzzer.Convert(6);
    Assert.Equal("Fizz", actual);
}

Similar test cases cover the "Buzz" and "FizzBuzz" behaviours. For this example, I wrote eight test cases in total, but a more sceptical tester might write twelve or even sixteen before feeling confident that the test suite sufficiently describes the desired behaviour of the system. Even so, a sufficiently adversarial implementer might (given eight test cases) deliver this implementation:

public static string Convert(int number)
{
    switch (number)
    {
        case  1: return "1";
        case  2: return "2";
        case  5:
        case 10: return "Buzz";
        case 15:
        case 30: return "FizzBuzz";
        default: return "Fizz";
    }
}

To be clear, it's not that I expect real-world programmers to be either obtuse or nefarious. In real life, on the other hand, requirements are more complicated, and may be introduced piecemeal in a fashion that may lead to buggy, overly-complicated implementations.

Under-determination #

Remarkably, black-box testing may work better as an ex-post technique, compared to TDD. If we imagine that an implementer has made an effort to correctly implement a system according to specification, a tester may use black-box testing to poke at the SUT, using both randomly selected test cases, and by explicitly exercising the SUT at boundary cases.

Even so, black-box testing in reality tends to run into the problem of under-determination, also known from philosophy of science. As I outlined in Code That Fits in Your Head, software testing has many similarities with empirical science. We use experiments (tests) to corroborate hypotheses that we have about software: Typically either that it doesn't pass tests, or that it does pass all tests, depending on where in the red-green-refactor cycle we are.

Similar to science, we are faced with the basic epistemological problem that we have a finite number of tests, but usually an infinite (or at least extremely big) state space. Thus, as pointed out by the problem of under-determination, more than one 'reality' fits the available observations (i.e. test cases). The above FizzBuzz implementation is an example of this.

As an aside, certain problems actually have images that are sufficiently small that you can cover everything in total. In its most common description, the FizzBuzz kata, too, falls into this category.

"Write a program that prints the numbers from 1 to 100."

This means that you can, in fact, write 100 test cases and thereby specify the problem in its totality. What you still can't do with black-box testing, however, is impose a particular implementation. An adversarial implementer could write the Convert function as one big switch statement. Just like I did with the Tennis kata, another kata with a small state space.

This, however, rarely happens in the real world. Example-driven testing is under-determined. And no, property-based testing doesn't fundamentally change that conclusion. It behoves you to look critically at the actual implementation code, and not rely exclusively on testing.

Working with implementation code #

It's hardly a surprise that TDD isn't black-box testing. Is it white-box testing, then? Since the red-green-refactor cycle dictates a tight loop between test and production code, you always have the implementation code at hand. In that sense, the SUT is a white box.

That said, the common view on white-box testing is that you work with knowledge about the internal implementation of an already-written system, and use that to design test cases. Typically, looking at the code should enable a tester to identify weak spots that warrant testing.

This isn't always the case with TDD. If you follow the red-green-refactor checklist, each cycle should leave you with a SUT that passes all tests in the simplest way that could possibly work. Consider the first incarnation of Convert, above (the one that always returns "1"). It passes all tests, and from a white-box-testing perspective, it has no weak spots. You can't identify a test case that'll make it crash.

If you consider the test suite as an executable specification, that degenerate implementation is correct, since it passes all tests. Of course, according to the kata description, it's wrong. Looking at the SUT code will tell you that in a heartbeat. It should prompt you to add another test case. The question is, though, whether that qualifies as white-box testing, or it's rather reminiscent of the transformation priority premise. Not that that's necessarily a dichotomy.

Overspecified software #

Perhaps a more common problem with white-box testing in relation to TDD is the tendency to take a given implementation for granted. Of course, working according to the red-green-refactor cycle, there's no implementation before the test, but a common technique is to use Mock Objects to let tests specify how the SUT should be implemented. This leads to the familiar problem of Overspecified Software.

Here's an example.

Finding values in an interval #

In the code base that accompanies Code That Fits in Your Head, the code that handles a new restaurant reservation contains this code snippet:

var reservations = await Repository
    .ReadReservations(restaurant.Id, reservation.At)
    .ConfigureAwait(false);
var now = Clock.GetCurrentDateTime();
if (!restaurant.MaitreD.WillAccept(now, reservations, reservation))
    return NoTables500InternalServerError();
 
await Repository.Create(restaurant.Id, reservation)
    .ConfigureAwait(false);

The ReadReservations method is of particular interest in this context. It turns out to be a small extension method on a more general interface method:

internal static Task<IReadOnlyCollection<Reservation>> ReadReservations(
    this IReservationsRepository repository,
    int restaurantId,
    DateTime date)
{
    var min = date.Date;
    var max = min.AddDays(1).AddTicks(-1);
    return repository.ReadReservations(restaurantId, min, max);
}

The IReservationsRepository interface doesn't have a method that allows a client to search for all reservations on a given date. Rather, it defines a more general method that enables clients to search for reservations in a given interval:

Task<IReadOnlyCollection<Reservation>> ReadReservations(
    int restaurantId, DateTime min, DateTime max);

As the parameter names imply, the method finds and returns all the reservations for a given restaurant between the min and max values. A previous article already covers this method in much detail.

I think I've stated this more than once before: Code is never perfect. Although I made a genuine attempt to write quality code for the book's examples, now that I revisit this API, I realize that there's room for improvement. The most obvious problem with that method definition is that it's not clear whether the range includes, or excludes, the boundary values. Would it improve encapsulation if the method instead took a Range<DateTime> parameter?

At the very least, I could have named the parameters inclusiveMin and inclusiveMax. That's how the system is implemented, and you can see an artefact of that in the above extension method. It searches from midnight of date to the tick just before midnight on the next day.

The SQL implementation reflects that contract, too.

SELECT [PublicId], [At], [Name], [Email], [Quantity]
FROM [dbo].[Reservations]
WHERE [RestaurantId] = @RestaurantId AND
      @Min <= [At] AND [At] <= @Max

Here, @RestaurantId, @Min, and @Max are query parameters. Notice that the query uses the <= relation for both @Min and @Max, making both endpoints inclusive.

Interactive white-box testing #

Since I'm aware of the problem of overspecified software, I test-drove the entire code base using state-based testing. Imagine, however, that I'd instead used a dynamic mock library. If so, a test could have looked like this:

[Fact]
public async Task PostUsingMoq()
{
    var now = DateTime.Now;
    var reservation =
        Some.Reservation.WithDate(now.AddDays(2).At(20, 15));
    var repoTD = new Mock<IReservationsRepository>();
    repoTD
        .Setup(r => r.ReadReservations(
            Some.Restaurant.Id,
            reservation.At.Date,
            reservation.At.Date.AddDays(1).AddTicks(-1)))
        .ReturnsAsync(new Collection<Reservation>());
    var sut = new ReservationsController(
        new SystemClock(),
        new InMemoryRestaurantDatabase(Some.Restaurant),
        repoTD.Object);
 
    var ar = await sut.Post(Some.Restaurant.Id, reservation.ToDto());
 
    Assert.IsAssignableFrom<CreatedAtActionResult>(ar);
    // More assertions could go here.
}

This test uses Moq, but the example doesn't hinge on that. I rarely use dynamic mock libraries these days, but when I do, I still prefer Moq.

Notice how the Setup reproduces the implementation of the ReadReservations extension method. The implication is that if you change the implementation code, you break the test.

Even so, we may consider this an example of a test-driven white-box test. While, according to the red-green-refactor cycle, you're supposed to write the test before the implementation, this style of TDD only works if you, the test writer, has an exact plan for how the SUT is going to look.

An innocent refactoring? #

Don't you find that min.AddDays(1).AddTicks(-1) expression a bit odd? Wouldn't the code be cleaner if you could avoid the AddTicks(-1) part?

Well, you can.

A tick is the smallest unit of measurement of DateTime values. Since ticks are discrete, the range defined by the extension method would be equivalent to a right-open interval, where the minimum value is still included, but the maximum is not. If you made that change, the extension method would be simpler:

internal static Task<IReadOnlyCollection<Reservation>> ReadReservations(
    this IReservationsRepository repository,
    int restaurantId,
    DateTime date)
{
    var min = date.Date;
    var max = min.AddDays(1);
    return repository.ReadReservations(restaurantId, min, max);
}

In order to offset that change, you also change the SQL accordingly:

SELECT [PublicId], [At], [Name], [Email], [Quantity]
FROM [dbo].[Reservations]
WHERE [RestaurantId] = @RestaurantId AND
      @Min <= [At] AND [At] < @Max

Notice that the query now compares [At] with @Max using the < relation.

While this is formally a breaking change of the interface, it's entirely internal to the application code base. No external systems or libraries depend on IReservationsRepository. Thus, this change is a true refactoring: It improves the code without changing the observable behaviour of the system.

Even so, this change breaks the PostUsingMoq test.

To make the test pass, you'll need to repeat the change you made to the SUT:

[Fact]
public async Task PostUsingMoq()
{
    var now = DateTime.Now;
    var reservation =
        Some.Reservation.WithDate(now.AddDays(2).At(20, 15));
    var repoTD = new Mock<IReservationsRepository>();
    repoTD
        .Setup(r => r.ReadReservations(
            Some.Restaurant.Id,
            reservation.At.Date,
            reservation.At.Date.AddDays(1)))
        .ReturnsAsync(new Collection<Reservation>());
    var sut = new ReservationsController(
        new SystemClock(),
        new InMemoryRestaurantDatabase(Some.Restaurant),
        repoTD.Object);
 
    var ar = await sut.Post(Some.Restaurant.Id, reservation.ToDto());
 
    Assert.IsAssignableFrom<CreatedAtActionResult>(ar);
    // More assertions could go here.
}

If it's only one test, you can probably live with that, but it's the opposite of a robust test; it's a Fragile Test.

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

A common problem with interaction-based testing is that even small refactorings break many tests. We might see that as a symptom of having too much knowledge of implementation details. We might view this as related to white-box testing.

To be clear, the tests in the code base that accompanies Code That Fits in Your Head are all state-based, so contrary to the PostUsingMoq test, all 161 tests easily survive the above refactoring.

Greyscale-box TDD #

It's not too hard to argue that TDD isn't black-box testing, but it's harder to argue that it's not white-box testing. Naturally, as you follow the red-green-refactor cycle, you know all about the implementation. Still, the danger of being too aware of the SUT code is being trapped in an implementation mindset.

While there's nothing wrong with getting the implementation right, many maintainability problems originate in insufficient encapsulation. Deliberately treating the SUT as a grey box helps in discovering a SUT's contract. That's why I recommend techniques like Devil's Advocate. Pretending to view the SUT from the outside can shed valuable light on usability and maintainability issues.

Conclusion #

The notions of white-box and black-box testing have been around for decades. So has TDD. Even so, it's not always clear to practitioners whether TDD is one or the other. The reason is, I believe, that TDD is neither. Good TDD practice sits somewhere between white-box testing and black-box testing.

Exactly where on that greyscale spectrum TDD belongs depends on context. The more important encapsulation is, the closer you should move towards black-box testing. The more important correctness or algorithm performance is, the closer to white-box testing you should move.

You can, however, move position on the spectrum even in the same code base. Perhaps you want to start close to white-box testing as you focus on getting the implementation right. Once the SUT works as intended, you may then decide to shift your focus towards encapsulation, in which case moving closer to black-box testing could prove beneficial.

Are IO expressions really referentially transparent programs?

Sometimes, when I discuss functional architecture or the IO container, a reader will argue that Haskell IO really is 'pure', 'referentially transparent', 'functional', or has another similar property.

The argument usually goes like this: An IO value is a composable description of an action, but not in itself an action. Since IO is a Monad instance, it composes via the usual monadic bind combinator >>=, or one of its derivatives.

Another point sometimes made is that you can 'call' an IO-valued action from within a pure function, as demonstrated by this toy example:

greet :: TimeOfDay -> String -> String
greet timeOfDay name =
  let greeting = case () of
        _ | isMorning timeOfDay -> "Good morning"
          | isAfternoon timeOfDay -> "Good afternoon"
          | isEvening timeOfDay -> "Good evening"
          | otherwise -> "Hello"
 
      sideEffect = putStrLn "Side effect!"
 
  in if null name
     then greeting ++ "."
     else greeting ++ ", " ++ name ++ "."

This is effectively a Haskell port of the example given in Referential transparency of IO. Here, sideEffect is a value of the type IO (), even though greet is a pure function. Such examples are sometimes used to argue that the expression putStrLn "Side effect!" is pure, because it's deterministic and has no side effects.

Rather, sideEffect is a 'program' that describes an action. The program is a referentially transparent value, although actually running it is not.

As I also explained in Referential transparency of IO, the above function application is legal because greet never uses the value 'inside' the IO action. In fact, the compiler may choose to optimize the sideEffect expression away, and I believe that GHC does just that.

I've tried to summarize the most common arguments as succinctly as I can. While I could cite actual online discussions that I've had, I don't wish to single out anyone. I don't want to make this article appear as though it's an attack on anyone in particular. Rather, my position remains that IO is special, and I'll subsequently try to explain the reasoning.

Reductio ad absurdum #

While I could begin my argument stating the general case, backed up by citing some papers, I'm afraid I'll lose most readers in the process. Therefore I'll flip the argument around and start with a counter-example. What would happen if we accept the claim that IO is pure or referentially transparent?

It would follow that all Haskell code should be considered pure. That would include putStrLn "Hello, world." or launchMissiles. That I find that conclusion absurd may just be my subjective opinion, but it also seems to go against the original purpose of using IO to tackle the awkward squad.

Furthermore, and this may be more objective, it seems to allow writing everything in IO, and still call it 'functional'. What do I mean by that?

Functional imperative code #

If we accept that IO is pure, then we may decide to write everything in procedural style. We could, for example, implement rod-cutting by mirroring the imperative pseudocode used to describe the algorithm.

{-# LANGUAGE FlexibleContexts #-}
module RodCutting where
 
import Control.Monad (forM_, when)
import Data.Array.IO
import Data.IORef (newIORef, writeIORef, readIORef, modifyIORef)
 
cutRod :: (Ix i, Num i, Enum i, Num e, Bounded e, Ord e)
       => IOArray i e -> i -> IO (IOArray i e, IOArray i i)
cutRod p n = do
  r <- newArray_ (0, n)
  s <- newArray_ (1, n)
  writeArray r 0 0  -- r[0] = 0
  forM_ [1..n] $ \j -> do
    q <- newIORef minBound  -- q = -∞
    forM_ [1..j] $ \i -> do
      qValue <- readIORef q
      p_i <- readArray p i
      r_j_i <- readArray r (j - i)
      when (qValue < p_i + r_j_i) $ do
        writeIORef q (p_i + r_j_i)  -- q = p[i] + r[j - i]
        writeArray s j i            -- s[j] = i

      qValue' <- readIORef q
      writeArray r j qValue'  -- r[j] = q

  return (r, s)

Ironically, the cutRod action remains referentially transparent, as is the original pseudocode from CLRS. This is because the algorithm itself is deterministic, and has no (external) side effects. Even so, the Haskell type system can't 'see' that. This implementation is intrinsically IO-valued.

Functional encapsulation #

You may think that this just proves the point that IO is pure, but it doesn't. We've always known that we can lift any pure value into IO using return: return 42 remains referentially transparent, even if it's contained in IO.

The reverse isn't always true. We can't conclude that code is referentially transparent when it's contained in IO. Usually, it isn't.

Be that as it may, why do we even care?

The problem is one of encapsulation. When an action like cutRod, above, returns an IO value, we're facing a dearth of guarantees. As users of the action, we may have many questions, most of which aren't answered by the type:

• Does cutRod modify the input array p?
• Is cutRod deterministic?
• Does cutRod launch missiles?
• Can I memoize the return values of cutRod?
• Does cutRod somehow keep a reference to the arrays that it returns? Can I be sure that a background thread, or a subsequent API call, doesn't mutate these arrays? In other words, is there a potential aliasing problem?

At best, such lack of guarantees lead to defensive coding, but usually it leads to bugs.

If, on the other hand, we were to write a version of cutRod that does not involve IO, we'd be able to answer all the above questions. The advantage would be that the function would be safer and easier to consume.

Referential transparency is not the same as purity #

This leads to a point that I failed to understand for years, until Tyson Williams pointed it out to me. Referential transparency is not the same as purity, although the overlap is substantial.

Of course, such a claim requires me to define the terms, but I'll try to keep it light. I'll define referential transparency as the property that allows replacing a function with the value it produces. Practically, it allows memoization. On the other hand, I'll define purity as functions that Haskell can distinguish from impure actions. In practice, this implies the absence of IO.

Usually this amounts to the same thing, but as we've seen above, it's possible to write referentially transparent code that nonetheless is embedded in IO. There are also examples of functions that look pure, although they may not be referentially transparent. Fortunately these are, in my experience, more rare.

That said, this is a digression. My agenda is to argue that IO is special. Yes, it's a Monad instance. Yes, it composes. No, it's not referentially transparent.

Semantics #

From the point of encapsulation, I've previously argued that referential transparency is attractive because it fits in your head. Code that is not referentially transparent usually doesn't.

Why is IO not referentially transparent? To repeat the argument that I sometimes run into, IO values describe programs. Every time your Haskell code runs, the same IO value describes the same program.

This strikes me as about as useful an assertion as insisting that all C code is referentially transparent. After all, a C program also describes the same program even if executed multiple times.

But you don't have to take my word for it. In Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell Simon Peyton Jones presents the semantics of Haskell.

"Our semantics is stratified in two levels: an inner denotational semantics that describes the behaviour of pure terms, while an outer monadic transition semantics describes the behaviour of IO computations."

Over the next 20 pages, that paper goes into details on how IO is special. The point is that it has different semantics from the rest of Haskell.

Pure rod-cutting #

Before I close, I realize that the above cutRod action may cause distress with some readers. To relieve the tension I'll leave you with a pure implementation.

{-# LANGUAGE TupleSections #-}
module RodCutting (cutRod, solve) where
 
import Data.Foldable (foldl')
import Data.Map.Strict ((!))
import qualified Data.Map.Strict as Map
 
seekBetterCut :: (Ord a, Num a)
              => [a] -> Int -> (a, Map.Map Int a, Map.Map Int Int) -> Int
              -> (a, Map.Map Int a, Map.Map Int Int)
seekBetterCut p j (q, r, s) i =
  let price = p !! i
      remainingRevenue = r ! (j - i)
      (q', s') =
        if q < price + remainingRevenue then
          (price + remainingRevenue, Map.insert j i s)
        else (q, s)
 
      r' = Map.insert j q' r
  in (q', r', s')
 
findBestCut :: (Bounded a, Ord a, Num a)
            => [a] -> (Map.Map Int a, Map.Map Int Int) -> Int
            -> (Map.Map Int a, Map.Map Int Int)
findBestCut p (r, s) j =
  let q = minBound  -- q = -∞
      (_, r', s') = foldl' (seekBetterCut p j) (q, r, s) [1..j]
  in (r', s')
 
cutRod :: (Bounded a, Ord a, Num a)
       => [a] -> Int -> (Map.Map Int a, Map.Map Int Int)
cutRod p n = do
  let r = Map.fromAscList $ map (, 0) [0..n]  -- r[0:n] initialized to 0
  let s = Map.fromAscList $ map (, 0) [1..n]  -- s[1:n] initialized to 0
  foldl' (findBestCut p) (r, s) [1..n]
 
solve :: (Bounded a, Ord a, Num a) => [a] -> Int -> [Int]
solve p n =
  let (_, s) = cutRod p n
      loop l n' =
        if n' > 0 then
          let cut = s ! n'
          in loop (cut : l) (n' - cut)
        else l
      l' = loop [] n
  in reverse l'

This is a fairly direct translation of the imperative algorithm. It's possible that you could come up with something more elegant. At least, I think that I did so in F#.

Regardless of the level of elegance of the implementation, this version of cutRod advertises its properties via its type. A client developer can now trivially answer the above questions, just by looking at the type: No, the function doesn't mutate the input list p. Yes, the function is deterministic. No, it doesn't launch missiles. Yes, you can memoize it. No, there's no aliasing problem.

Conclusion #

From time to time, I run into the claim that Haskell IO, being monadic and composable, is referentially transparent, and that it's only during execution that this property is lost.

I argue that such claims are of little practical interest. There are other parts of Haskell that remain referentially transparent, even during execution. Thus, IO is still special.

From a practical perspective, the reason I care about referential transparency is because the more you have of it, the simpler your code is; the better it fits in your head. The kind of referential transparency that some people argue that IO has does not have the property of making code simpler. In reality, IO code has the same inherent properties as code written in C, Python, Java, Fortran, etc.

Just because it's possible. Don't do this at work.

This is the last article in a series named Alternative ways to design with functional programming. In it, you've seen various suggestions on how to model a non-trivial problem with various kinds of functional-programming patterns. The previous two articles showed how to use free monads to model the problem in Haskell and F#. In this article, I'll repeat the exercise in C#. It's not going to be pretty, but it's possible.

What is the point of this exercise? Mostly to supply parity in demo code. If you're more familiar with C# than F# or Haskell, this may give you a better sense of what a free monad is, and how it works. That's all. I don't consider the following practical code, and I don't endorse it.

The code shown here is based on the free branch of the DotNet Git repository available with this article series.

Functor #

A free monad enables you to define a monad from any functor. In this context, you start with the functor that models an instruction set for a domain-specific language (DSL). The goal is to replace the SongService interface with this instruction set.

As a reminder, this is the interface:

public interface SongService
{
    Task<IReadOnlyCollection<User>> GetTopListenersAsync(int songId);
    Task<IReadOnlyCollection<Scrobble>> GetTopScrobblesAsync(string userName);
}

I'll remind the reader that the code is my attempt to reconstruct the sample code shown in Pure-Impure Segregation Principle. I don't know if SongService is a base class or an interface. Based on the lack of the idiomatic C# I prefix for interfaces, one may suppose that it was really intended to be a base class, but since I find interfaces easier to handle than base classes, here we are.

In any case, the goal is to replace it with an instruction set, starting with a sum type. Since C# comes with no native support for sum types, we'll need to model it with either Church encoding or a Visitor. I've been over the Visitor territory enough times already, so here I'll go with the Church option, since it's a tad simpler.

I start by creating a new class called SongInstruction<T> with this method:

public TResult Match<TResult>(
    Func<(int, Func<IReadOnlyCollection<User>, T>), TResult> getTopListeners,
    Func<(string, Func<IReadOnlyCollection<Scrobble>, T>), TResult> getTopScrobbles)
{
    return imp.Match(getTopListeners, getTopScrobbles);
}

If you squint sufficiently hard, you may be able to see how the getTopListeners parameter corresponds to the interface's GetTopListenersAsync method, and likewise for the other parameter.

I'm not going to give you a very detailed walkthrough, as I've already done that earlier in a different context. Likewise, I'll skip some of the implementation details. All the code is available in the Git repository.

To be a functor, the class needs a Select method.

public SongInstruction<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return Match(
        t => SongInstruction.GetTopListeners(
            t.Item1, // songId
            users => selector(t.Item2(users))),
        t => SongInstruction.GetTopScrobbles(
            t.Item1, // userName
            songs => selector(t.Item2(songs))));
}

The name t is, in both cases, short for tuple. It's possible that more recent versions of C# finally allow pattern matching of tuples in lambda expressions, but the version this code is based on doesn't. In both cases Item2 is the 'continuation' function.

Monad #

The next step is to wrap the functor in a data structure that enables you to sequence the above instructions. That has to be another sum type, this time called SongProgram<T>, characterized by this Match method:

public TResult Match<TResult>(
    Func<SongInstruction<SongProgram<T>>, TResult> free,
    Func<T, TResult> pure)
{
    return imp.Match(free, pure);
}

A SelectMany method is required to make this type a proper monad:

public SongProgram<TResult> SelectMany<TResult>(
    Func<T, SongProgram<TResult>> selector)
{
    return Match(
        i => SongProgram.Free(i.Select(p => p.SelectMany(selector))),
        selector);
}

The code is already verbose enough as it is, so I've used i for instruction and p for program.

Lifted helpers #

Although not strictly required, I often find it useful to add a helper method for each case of the instruction type:

public static SongProgram<IReadOnlyCollection<User>> GetTopListeners(int songId)
{
    return Free(SongInstruction.GetTopListeners(songId, Pure));
}
 
public static SongProgram<IReadOnlyCollection<Scrobble>> GetTopScrobbles(string userName)
{
    return Free(SongInstruction.GetTopScrobbles(userName, Pure));
}

This just makes the user code look a bit cleaner.

Song recommendations as a DSL #

Using the composition from Song recommendations from C# combinators as a starting point, it doesn't take that many changes to turn it into a SongProgram-valued function.

public static SongProgram<IReadOnlyList<Song>> GetRecommendations(string userName)
{
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    return SongProgram.GetTopScrobbles(userName)
        .SelectMany(scrobbles => UserTopScrobbles(scrobbles)
            .Traverse(scrobble => SongProgram
                .GetTopListeners(scrobble.Song.Id)
                .Select(TopListeners)
                .SelectMany(users => users
                    .Traverse(user => SongProgram
                        .GetTopScrobbles(user.UserName)
                        .Select(TopScrobbles))
                    .Select(Songs)))
        .Select(TakeTopRecommendations));
}

Notice how much it resembles the original GetRecommendationsAsync method on the RecommendationsProvider class. Instead of songService.GetTopScrobblesAsync it just has SongProgram.GetTopScrobbles, and instead of songService.GetTopListenersAsync it has SongProgram.GetTopListeners.

To support this composition, however, a traversal is required.

Traverse #

The traversal needs a Select function on SongProgram, so we'll start with that.

public SongProgram<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return SelectMany(x => SongProgram.Pure(selector(x)));
}

This is the standard implementation of a functor from a monad.

It turns out that it's also useful to define a function to concatenate two sequence-valued programs.

private static SongProgram<IEnumerable<T>> Concat<T>(
    this SongProgram<IEnumerable<T>> xs,
    SongProgram<IEnumerable<T>> ys)
{
    return xs.SelectMany(x => ys.Select(y => x.Concat(y)));
}

This could, perhaps, be a public function, but in this situation, I only need it to implement Traverse, so I kept it private. The Traverse function, on the other hand, is public.

public static SongProgram<IEnumerable<TResult>> Traverse<T, TResult>(
    this IEnumerable<T> source,
    Func<T, SongProgram<TResult>> selector)
{
    return source.Aggregate(
        Pure(Enumerable.Empty<TResult>()),
        (acc, x) =>
            acc.Concat(selector(x).Select(xr => new[] {xr}.AsEnumerable())));
}

Given a sequence of values, Traverse applies selector to each, and collects all resulting programs into a single sequence-valued program. You see it in use in the above GetRecommendations composition.

Interpreter #

That last missing piece is an interpreter that can evaluate a program. Since I already have a class called FakeSongService, adding an Interpret method was the easiest implementation strategy.

public T Interpret<T>(SongProgram<T> program)
{
    return program.Match(
        i => i.Match(
            t => Interpret(t.Item2(GetTopListernes(t.Item1))),
            t => Interpret(t.Item2(GetTopScrobbles(t.Item1)))),
        x => x);
}

Here, GetTopListernes and GetTopScrobbles are two private helper functions:

private IReadOnlyCollection<User> GetTopListernes(int songId)
{
    var listeners =
        from kvp in users
        where kvp.Value.ContainsKey(songId)
        select new User(kvp.Key, kvp.Value.Values.Sum());
 
    return listeners.ToList();
}
 
private IReadOnlyCollection<Scrobble> GetTopScrobbles(string userName)
{
    var scrobbles = users
        .GetOrAdd(userName, new ConcurrentDictionary<int, int>())
        .Select(kvp => new Scrobble(songs[kvp.Key], kvp.Value));
 
    return scrobbles.ToList();
}

The implementation closely mirrors the original Fake interface implementation, where users and songs are class fields on FakeSongService. This class was first shown in Characterising song recommendations.

It's now possible to rewrite all the tests.

Refactoring the tests #

Since the original GetRecommendationsAsync method was task-based, all tests had to run in task workflows. This is no longer necessary, as this simplified FsCheck property demonstrates:

[<Property>]
let ``One user, some songs`` () =
    gen {
        let! user = Gen.userName
        let! songs = Gen.arrayOf Gen.song
        let! scrobbleCounts =
            Gen.choose (1, 100) |> Gen.arrayOfLength songs.Length
        return (user, Array.zip songs scrobbleCounts) }
    |> Arb.fromGen |> Prop.forAll <| fun (user, scrobbles) ->
        let srvc = FakeSongService ()
        scrobbles |> Array.iter (fun (s, c) -> srvc.Scrobble (user, s, c))
 
        let actual =
            RecommendationsProvider.GetRecommendations user |> srvc.Interpret
 
        Assert.Empty actual

Originally, this test had to be defined in terms of the task computation expression, but now it's a pure function. In the act phase the test calls RecommendationsProvider.GetRecommendations user and pipes the returned program to srvc.Interpret. The result, actual, is a plain IReadOnlyCollection<Song> value.

Similarly, I was able to migrate all the example-based tests over, too.

[<Fact>]
let ``One verified recommendation`` () =
    let srvc = FakeSongService ()
    srvc.Scrobble ("cat", Song (1, false, 6uy),     10)
    srvc.Scrobble ("ana", Song (1, false, 5uy),     10)
    srvc.Scrobble ("ana", Song (2,  true, 5uy), 9_9990)
 
    let actual =
        RecommendationsProvider.GetRecommendations "cat" |> srvc.Interpret
 
    Assert.Equal<Song> ([ Song (2, true, 5uy) ], actual)

Once all tests were migrated over to the new GetRecommendations function, I deleted the old RecommendationsProvider class as well as the SongService interface, since none of them were required any longer.

Conclusion #

The lack of proper syntactic sugar, similar to do notation in Haskell, or computation expressions in F#, means that free monads aren't a useful design option in C#. Still, perhaps the last three articles help a reader or two understanding what a free monad is.

With an extensive computation expression.

This article is part of a series called Alternative ways to design with functional programming. As the title suggests, it examines alternative functional-programming architectures. It does so by looking at the same overall example problem: Calculating song recommendations from a large data set of 'scrobbles'; records of playback data for many users. In the previous article, you saw how to implement the desired functionality using a free monad in Haskell. In this article, you'll see how to use a free monad in F#.

If you are following along in the accompanying Git repository, the code shown here is from the fsharp-free branch. The starting point is fsharp-port.

Functor #

A free monad enables you to define a monad from any functor. In this context, you start with the functor that models an instruction set for a domain-specific language (DSL). The goal is to replace the SongService interface with this instruction set.

As a reminder, this is the interface:

type SongService =
    abstract GetTopListenersAsync : songId : int -> Task<IReadOnlyCollection<User>>
    abstract GetTopScrobblesAsync : userName : string -> Task<IReadOnlyCollection<Scrobble>>

I'm following the F# free monad recipe, which, I'm happy to report, turned out to be easy to do.

First, the sum type:

type SongInstruction<'a> =
    | GetTopListeners of songId : int * (IReadOnlyCollection<User> -> 'a)
    | GetTopScrobbles of userName : string * (IReadOnlyCollection<Scrobble> -> 'a)

If you check with the F# free monad recipe and compare the SongService interface methods with the SongInstruction cases, you should be able to spot the similarity, and how to get from interface to discriminated union.

As shown in the previous article, in Haskell you can declaratively state that a type should be a Functor instance. In F# you have to implement it yourself.

module SongInstruction =
    let map f = function
        | GetTopListeners (  songId, next) -> GetTopListeners (  songId, next >> f)
        | GetTopScrobbles (userName, next) -> GetTopScrobbles (userName, next >> f)

Here I've put it in its own little module, in order to make it clear which kind of data the map function handles.

Monad #

The next step is to wrap the functor in a data structure that enables you to sequence the above instructions.

type SongProgram<'a> =
    | Free of SongInstruction<SongProgram<'a>>
    | Pure of 'a

A bind function is required to make this type a proper monad:

module SongProgram =
    let rec bind f = function
        | Free inst -> inst |> SongInstruction.map (bind f) |> Free
        | Pure inst -> f inst

Again, I'm slavishly following the F# free monad recipe; please refer to it for more details.

Computation expression #

Technically, that's all it takes to make it possible to write programs in the little DSL. Doing it exclusively with the above bind function would, however, but quite cumbersome, so you'll also appreciate some syntactic sugar in the form of a computation expression.

As you will see shortly, I needed to (temporarily) support some imperative language constructs, so I had to make it more involved than usually required.

type SongProgramBuilder () =
    member _.Bind (x, f) = SongProgram.bind f x
    member _.Return x = Pure x
    member _.ReturnFrom x = x
    member _.Zero () = Pure ()
    member _.Delay f = f
    member _.Run f = f ()
    member this.While (guard, body) =
        if not (guard ())
        then this.Zero ()
        else this.Bind (body (), fun () -> this.While (guard, body))
    member this.TryWith (body, handler) =
        try this.ReturnFrom (body ())
        with e -> handler e
    member this.TryFinally (body, compensation) =
        try this.ReturnFrom (body ())
        finally compensation ()
    member this.Using (disposable : #System.IDisposable, body) =
        let body' = fun () -> body disposable
        this.TryFinally (body', fun () ->
            match disposable with
            | null -> ()
            | disp -> disp.Dispose ())
    member this.For (sequence : seq<_>, body) =
        this.Using (sequence.GetEnumerator (), fun enum ->
            this.While (enum.MoveNext, this.Delay (fun () -> body enum.Current)))
    member _.Combine (x, y) = x |> SongProgram.bind (fun () -> y ())

I had to do quite a bit of yak shaving before I got the For method right. Not surprisingly, Scott Wlaschin's series on computation expressions proved invaluable.

As you always do with computation expressions, you leave a builder object somewhere the rest of your code can see it:

let songProgram = SongProgramBuilder ()

You'll soon see an example of using a songProgram computation expression.

Lifted helpers #

Although not strictly required, I often find it useful to add a helper function for each case of the instruction type:

let getTopListeners songId = Free (GetTopListeners (songId, Pure))
 
let getTopScrobbles userName = Free (GetTopScrobbles (userName, Pure))

This just makes the user code look a bit cleaner.

Imperative-looking program #

With all that machinery in place, you can now write a referentially transparent function that implements the same algorithm as the original class method.

let getRecommendations userName = songProgram {
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    let! scrobbles = getTopScrobbles userName
 
    let scrobblesSnapshot =
        scrobbles
        |> Seq.sortByDescending (fun s -> s.ScrobbleCount)
        |> Seq.truncate 100
        |> Seq.toList
 
    let recommendationCandidates = ResizeArray ()
    for scrobble in scrobblesSnapshot do
        let! otherListeners = getTopListeners scrobble.Song.Id
 
        let otherListenersSnapshot =
            otherListeners
            |> Seq.filter (fun u -> u.TotalScrobbleCount >= 10_000)
            |> Seq.sortByDescending (fun u -> u.TotalScrobbleCount)
            |> Seq.truncate 20
            |> Seq.toList
 
        for otherListener in otherListenersSnapshot do
            // Impure
            let! otherScrobbles = getTopScrobbles otherListener.UserName
 
            // Pure
            let otherScrobblesSnapshot =
                otherScrobbles
                |> Seq.filter (fun s -> s.Song.IsVerifiedArtist)
                |> Seq.sortByDescending (fun s -> s.Song.Rating)
                |> Seq.truncate 10
                |> Seq.toList
 
            otherScrobblesSnapshot
            |> List.map (fun s -> s.Song)
            |> recommendationCandidates.AddRange
 
    let recommendations =
        recommendationCandidates
        |> Seq.sortByDescending (fun s -> s.Rating)
        |> Seq.truncate 200
        |> Seq.toList
        :> IReadOnlyCollection<_>
 
    return recommendations }

Notice how much it resembles the original GetRecommendationsAsync method on the RecommendationsProvider class. Instead of songService.GetTopScrobblesAsync it just has getTopScrobbles, and instead of songService.GetTopListenersAsync it has getTopListeners. The whole computation is wrapped in songProgram, and the return type is SongProgram<IReadOnlyCollection<Song>>.

Perhaps you're wondering how the local state mutation (of recommendationCandidates) squares with my claim that this function is referentially transparent, but consider what referential transparency means. It means that you could replace a particular function call (say, getRecommendations "cat") with the value it returns. And you can. That the function used local mutation to arrive at that return value is of no concern to the caller.

Even so, later in this article, we'll refactor the code to something that looks more like a pure function. For now, however, we'll first see how to evaluate programs like the one returned by getRecommendations.

Interpreter #

Again, I follow the F# free monad recipe. Since I already have a class called FakeSongService, adding an Interpret method was the easiest implementation strategy. A private recursive function takes care of the implementation:

let rec interpret = function
    | Pure x -> x
    | Free (GetTopListeners (songId, next)) ->
        users
        |> Seq.filter (fun kvp -> kvp.Value.ContainsKey songId)
        |> Seq.map (fun kvp -> user kvp.Key (Seq.sum kvp.Value.Values))
        |> Seq.toList
        |> next
        |> interpret
    | Free (GetTopScrobbles (userName, next)) ->
        users.GetOrAdd(userName, ConcurrentDictionary<_, _> ())
        |> Seq.map (fun kvp -> scrobble songs[kvp.Key] kvp.Value)
        |> Seq.toList
        |> next
        |> interpret

The implementation closely mirrors the original Fake interface implementation, where users and songs are class fields on FakeSongService. This class was first shown in Characterising song recommendations.

Since I added the interpret function in the class, we need a method that enables client code to call it:

member _.Interpret program = interpret program

It's now possible to rewrite all the tests.

Refactoring the tests #

Since the original GetRecommendationsAsync method was task-based, all tests had to run in task workflows. This is no longer necessary, as this simplified FsCheck property demonstrates:

[<Property>]
let ``One user, some songs`` () =
    gen {
        let! user = Gen.userName
        let! songs = Gen.arrayOf Gen.song
        let! scrobbleCounts =
            Gen.choose (1, 100) |> Gen.arrayOfLength songs.Length
        return (user, Array.zip songs scrobbleCounts) }
    |> Arb.fromGen |> Prop.forAll <| fun (user, scrobbles) ->
        let srvc = FakeSongService ()
        scrobbles |> Array.iter (fun (s, c) -> srvc.Scrobble (user, s, c))
 
        let actual = getRecommendations user |> srvc.Interpret
 
        Assert.Empty actual

Originally, this test had to be defined in terms of the task computation expression, but now it's a pure function. In the act phase the test calls getRecommendations user and pipes the returned program to srvc.Interpret. The result, actual, is a plain IReadOnlyCollection<Song> value.

Similarly, I was able to migrate all the example-based tests over, too.

[<Fact>]
let ``One verified recommendation`` () =
    let srvc = FakeSongService ()
    srvc.Scrobble ("cat", song 1 false 6uy,     10)
    srvc.Scrobble ("ana", song 1 false 5uy,     10)
    srvc.Scrobble ("ana", song 2  true 5uy, 9_9990)
 
    let actual = getRecommendations "cat" |> srvc.Interpret
 
    Assert.Equal<Song> ([ song 2 true 5uy ], actual)

Once all tests were migrated over to the new getRecommendations function, I deleted the old RecommendationsProvider class as well as the SongService interface, since none of them were required any longer. Notice how I managed to move in smaller steps than in the previous article. As described in Code That Fits in Your Head, I used the Strangler pattern to move incrementally. I should also have done that with the Haskell code base, but fortunately I didn't run into trouble.

With all the tests migrated to pure functions, it's time to go back to getRecommendations to give it some refactoring love.

Traverse #

The local mutation in the above incarnation of getRecommendations is located within a doubly-nested loop. You typically need a traversal if you want to refactor such loops to expressions.

The traversal needs a map function, so we'll start with that.

let map f = bind (f >> Pure)

This function is included in the SongProgram module shown above. That's the reason it can call bind without a prefix. The same is true for the traverse function.

let traverse f xs =
    let concat xs ys = xs |> bind (fun x -> ys |> map (Seq.append x))
    Seq.fold
        (fun acc x -> concat acc (f x |> map Seq.singleton))
        (Pure (Seq.empty))
        xs

The local concat function concatenates two SongProgram values that contain sequences to a single SongProgram value containing the concatenated sequence. The traversal uses this helper function to fold over the xs.

Refactored program #

You can now go through all the usual motions of replacing the nested loops and the local mutation with traversal, extracting helper functions and so on. If you're interested in the small steps I took, you may consult the Git repository. Here, I only present the getRecommendations function in the state I decided to leave it.

let getRecommendations userName = songProgram {
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    let! scrobbles = getTopScrobbles userName
 
    let! otherlListeners =
        getUsersOwnTopScrobbles scrobbles
        |> SongProgram.traverse (fun s -> getTopListeners s.Song.Id)
 
    let! otherScrobbles =
        otherlListeners
        |> Seq.collect getOtherUsersWhoListenedToTheSameSongs
        |> SongProgram.traverse (fun u -> getTopScrobbles u.UserName)
 
    return
        otherScrobbles
        |> Seq.collect getTopScrobblesOfUsers
        |> aggregateTheSongsIntoRecommendations }

Notice the two applications of traverse, which replace the twice-nested loop.

The type of getRecommendations is unchanged, and all tests still pass.

Conclusion #

As expected, it required more boilerplate code to refactor the GetRecommendationsAsync method to a design based on a free monad, than the corresponding refactoring did in Haskell. Even so, following the F# free monad recipe made it was smooth sailing. I did, however, hit a snag, mostly of my own manufacture, when implementing support for for loops in the computation expression builder, but that problem turned out to be unrelated to the free monad.

Again, you may wonder what the point is. First, I'll refer you to the decision flowchart in the F# free monad recipe, as well as remind you that these articles are all intended to be descriptive rather than prescriptive. They only present what is possible. It's up to you to decide which option to choose.

Second, a SongProgram<'a> may look similar to an interface, but consider how much more restricted it is. A method that uses dependency injection is inherently impure; in such a method, everything may happen, including every kind of bug.

The F# type system does not check whether or not unconstrained side effects or non-determinism takes place, but still, a type like SongProgram<'a> strongly suggests that only SongProgram-related actions take place.

I think that free monads still have a place in F#, although mostly as a niche use case. In C#, on the other hand, free monads aren't useful because the language lacks features to make this kind of programming workable. Still, for demonstration purposes only, it can be done.

Next: Song recommendations with C# free monads.

A surprisingly easy refactoring.

This article is part of a larger series titled Alternative ways to design with functional programming. In short, it uses Haskell, F#, and C# to present various internal architectures to deal with an example problem. Please refer to the table of contents included with the first article to get a sense of what has already been covered.

In this article, you'll see how a free monad may be used to address the problem that when data size is sufficiently large, you may need to load it piecemeal, based on the results of previous steps in an algorithm. In short, the problem being addressed is to calculate a list of song recommendations based on so-called 'scrobble' data from a multitude of other users' music playback history.

If you want to follow along with the Git repository, the code presented here is from the Haskell repository's free branch.

Starting point #

Instead of starting from scratch from the code base presented in Porting song recommendations to Haskell, I'll start at what was an interim refactoring step in Song recommendations from Haskell combinators:

getRecommendations :: SongService a => a -> String -> IO [Song]
getRecommendations srvc un = do
  -- 1. Get user's own top scrobbles
  -- 2. Get other users who listened to the same songs
  -- 3. Get top scrobbles of those users
  -- 4. Aggregate the songs into recommendations

  -- Impure
  scrobbles <- getTopScrobbles srvc un
 
  -- Pure
  let scrobblesSnapshot = take 100 $ sortOn (Down . scrobbleCount) scrobbles
 
  -- Impure
  recommendations <-
    join <$>
    traverse (\scrobble ->
      fmap join $
      traverse (\otherListener ->
        fmap scrobbledSong .
        take 10 .
        sortOn (Down . songRating . scrobbledSong) .
        filter (songHasVerifiedArtist . scrobbledSong) <$>
        getTopScrobbles srvc (userName otherListener)) .
      take 20 <$>
      sortOn (Down . userScrobbleCount) .
      filter ((10_000 <=) . userScrobbleCount) =<<
      getTopListeners srvc (songId $ scrobbledSong scrobble))
    scrobblesSnapshot
 
  -- Pure
  return $ take 200 $ sortOn (Down . songRating) recommendations

The reason I wanted to start here is that with the IORef out of the way, the only IO-bound code remaining involves the SongService methods.

The plan is to replace the SongService type class with a free monad. Once that's done, there's no more IO left; it will have been replaced by the free monad. That's why it's easiest to first get rid of everything else involving IO. If I didn't, the refactoring wouldn't be as easy. As Kent Beck wrote,

"for each desired change, make the change easy (warning: this may be hard), then make the easy change"

Starting from the above incarnation of the code makes the change easy.

Functor #

As a reminder, this type class is the one I'm getting rid of:

class SongService a where
  getTopListeners :: a -> Int -> IO [User]
  getTopScrobbles :: a -> String -> IO [Scrobble]

Converting such an 'interface' to a sum type of instructions is such a well-defined process that I think it could be automated (if it were worth the effort). You take each method of the type class and make it a case in the sum type.

data SongInstruction a =
    GetTopListeners Int ([User] -> a)
  | GetTopScrobbles String ([Scrobble] -> a)
  deriving (Functor)

I usually think of such a type as representing possible instructions in a little domain-specific language (DSL). In this case, the DSL allows only two instructions: GetTopListeners and GetTopScrobbles.

If you've never seen a free monad before, you may be wondering: What's the a? It's what we may call the carrier type. If you haven't worked with, say, F-Algebras, this takes some time getting used to, but the carrier type represents a 'potential'. As presented here, it may be anything, but when you want to evaluate or 'run' the program, the a turns out to be the return type of the evaluation.

Since SongInstruction is a Functor, it's possible to map a to b, or one concrete type to another, so that the a type parameter can take on more than one concrete type during a small 'program' written in the DSL.

In any case, at this point, SongInstruction a is only a Functor, and not yet a Monad.

Free monad #

You may, if you want to, introduce a type alias that makes SongInstruction a (or, rather, its Free wrapper) a Monad.

type SongProgram = Free SongInstruction

The Free wrapper comes from Control.Monad.Free.

In the rest of the code listings in this article, I make no use of this type alias, so I only present it here because it's the type the compiler will infer when running the test. In other words, while never explicitly stated, this is going to be the de-facto free monad in this article.

From action to function #

Changing the getRecommendations action to a function that returns (effectively) Free (SongInstruction [Song]) turned out to be easier than I had expected.

Since I've decided to omit type declarations whenever possible, refactoring is easier because the type inferencing system can allow changes to function and action types to ripple through to the ultimate callers. (To be clear, however, I here show some of the code with type annotations. I've only added those in the process of writing this article, as an aid to you, the reader. You will not find those type annotations in the Git repository.)

First, I added a few helper methods to create 'program instructions':

getTopListeners sid = liftF $ GetTopListeners sid id
 
getTopScrobbles un = liftF $ GetTopScrobbles un id

The liftF function wraps a Functor (here, SongInstruction) in a free monad. This makes it easer to write programs in that DSL.

The only changes now required to getRecommendations is to remove srvc in four places:

getRecommendations :: MonadFree SongInstruction m => String -> m [Song]
getRecommendations un = do
  -- 1. Get user's own top scrobbles
  -- 2. Get other users who listened to the same songs
  -- 3. Get top scrobbles of those users
  -- 4. Aggregate the songs into recommendations

  -- Impure
  scrobbles <- getTopScrobbles un
 
  -- Pure
  let scrobblesSnapshot = take 100 $ sortOn (Down . scrobbleCount) scrobbles
 
  -- Impure
  recommendations <-
    join <$>
    traverse (\scrobble ->
      fmap join $
      traverse (\otherListener ->
        fmap scrobbledSong .
        take 10 .
        sortOn (Down . songRating . scrobbledSong) .
        filter (songHasVerifiedArtist . scrobbledSong) <$>
        getTopScrobbles (userName otherListener)) .
      take 20 <$>
      sortOn (Down . userScrobbleCount) .
      filter ((10_000 <=) . userScrobbleCount) =<<
      getTopListeners (songId $ scrobbledSong scrobble))
    scrobblesSnapshot
 
  -- Pure
  return $ take 200 $ sortOn (Down . songRating) recommendations

It's almost the same code as before. The only difference is that srvc is not longer a parameter to either getRecommendations, getTopListeners, or getTopScrobbles.

Again, I'll point out that I've only added the type annotation for the benefit of you, the reader. We see now, however, that the return type is m [Song], where m is any MonadFree SongInstruction.

Interpreter #

As described in Porting song recommendations to Haskell I use a FakeSongService as a Test Double. SongService is now gone, but I can repurpose the instance implementation as an interpreter of SongInstruction programs.

interpret :: FakeSongService -> Free SongInstruction a -> a
interpret (FakeSongService ss us) = iter eval
  where
    eval (GetTopListeners sid next) =
      next $
      uncurry User <$>
      Map.toList (sum <$> Map.filter (Map.member sid) us)
    eval (GetTopScrobbles un next) =
      next $
      fmap (\(sid, c) -> Scrobble (ss ! sid) c) $
      Map.toList $
      Map.findWithDefault Map.empty un us

Compare that code to the previous SongService instance shown in Porting song recommendations to Haskell. The functions are nearly identical, only return is replaced by next, and a few other, minute changes.

Test changes #

The hardest part of this refactoring was to adjust the tests. As I've described in Code That Fits in Your Head, I don't like when I have to change the System Under Test and the test code in the same commit, but in this case I lacked the skill to do it more incrementally.

The issue is that since SongService methods were IO-bound, the tests ran in IO. Particularly for the QuickCheck properties, I had to remove the ioProperty and monadicIO combinators. This also meant adjusting some of the assertions. The "One user, some songs" test now looks like this:

testProperty "One user, some songs" $ \
  (ValidUserName user)
  (fmap getSong -> songs)
  -> do
  scrobbleCounts <- vectorOf (length songs) $ choose (1, 100)
  let scrobbles = zip songs scrobbleCounts
  let srvc = foldr (uncurry (scrobble user)) emptyService scrobbles
 
  let actual = interpret srvc $ getRecommendations user
 
  return $ counterexample "Should be empty" (null actual)

Notice the interpreter in action, to the left of the application of getRecommendations. Since interpret reduces any Free SongInstruction a to a, it evaluates Free SongInstruction [Song] to [Song]; that's the type of actual.

The change represents a net benefit in my view. All tests are now pure, instead of running in IO. This makes them simpler.

Final refactoring #

The above version of the code was only a good starting point for making the changeover to a free monad. Extracting the usual helper functions, you can arrive at this variation of the getRecommendations function:

getRecommendations un = do
  -- 1. Get user's own top scrobbles
  -- 2. Get other users who listened to the same songs
  -- 3. Get top scrobbles of those users
  -- 4. Aggregate the songs into recommendations

  userTops <- getTopScrobbles un <&> getUsersOwnTopScrobbles
  otherListeners <- 
    traverse (getTopListeners . (songId . scrobbledSong)) userTops <&>
    getOtherUsersWhoListenedToTheSameSongs . join
  songs <-
    traverse (getTopScrobbles . userName) otherListeners <&>
    getTopScrobblesOfOtherUsers . join
  return $ aggregateTheSongsIntoRecommendations songs

Again, it looks a lot like one of the variations shown in Porting song recommendations to Haskell, just without the srvc parameter.

Conclusion #

Refactoring from a type class, which in other languages could be an interface, is so easy that you may rightfully ask what the point is. To me, the most important benefit is that you restrict your options. As I discussed in a podcast episode some years ago, constraints liberate. Here, we move from allowing anything (IO) to only allowing a limited set of instructions.

You could argue that a 'real' interpreter (rather than a test-specific interpreter) might run in IO, such as the interpreter shown here. Still, I would argue that most interpreters are smaller, and more stable, than the programs you may write with free monads. Thus, the amount of code you have to review that's allowed to do anything is smaller than it otherwise would have been.

In any case, refactoring to a free monad wasn't too difficult in Haskell. How easy is it in F#?

Next: Song recommendations with F# free monads.

A Golden Hammer.

This article is part of a larger article series about alternative ways to design with functional programming, particularly when faced with massive data loads. In previous articles in the series, you've seen various alternatives that may or may not enable you to solve the example problem using functional programming. Each of the previous alternatives, applying the Recawr Sandwich pattern, employing functional combinators, or using pipes and filters, came with some trade-offs. Either there were limits to the practicality of the architecture, or it wasn't really functional after all.

In this, and the following three articles, we finally reach for a universal solution: Free monads.

By universal I mean: It's always possible to do this (if your language supports it). It doesn't follow that it's always a good idea.

So there are trade-offs here, too.

As is usually the case, although sometimes I forget to write it, this and the following articles are descriptive, not prescriptive. In no way do I insist that things must be done this way. I only present examples as options.

The last resort #

If using a free monad is a universal possibility, then why is that not the default option? Why have I waited this long in the article series before covering it?

For more than a single reason.

It's an 'advanced' technique, and I predict that to many programmers, it looks like black magic. If you're working with a team unready for free monads, foisting it upon them are unlikely to lead to anything good.

The following story may illustrate the problem. It's not about free monads, but rather about Dependency Injection (DI) Containers. A specific one, actually. I was consulting with a team, working as a temporary lead developer for about half a year. I made a number of technical decisions, some of them good and others not so much. Among the latter was the decision to use the Castle Windsor DI Container.

Not that Castle Windsor was a bad library. After having done the research and written a book, I considered it the best DI Container available.

The problem, rather, was that the rest of the team considered it 'automagical'. Not that they weren't sophisticated programmers, but they had no interest learning the Castle Windsor API. They didn't consider it part of their core work, and they didn't think it provided enough benefit compared to the maintenance burden it imposed.

They humoured me as long as I stayed on, but also explicitly told me that they'd rip it out as soon as I was gone. In the meantime, I became the Castle Windsor bottleneck. Everything related to that piece of technology had to go through me, since I was the only person who understood how it worked.

A few years later, I returned to that team and that code base on a new project, and they'd kept their word. They'd removed Castle Windsor in favour of Pure DI, bless them.

This experience was crucial in making me realize that, despite their intellectual attraction, DI Containers are rarely the correct choice.

Free monads look to me as though they belong to the same category. While I don't have a similar story to tell, I'm wary of recommending them unless other options are played out. I'll refer you to the decision flowchart in the article F# free monad recipe.

Language support #

Another concern about free monads is whether your language of choice supports them. They fit perfectly in Haskell, which is also the reason I start this sub-series of articles with a Haskell example.

• Song recommendations with Haskell free monads
• Song recommendations with F# free monads
• Song recommendations with C# free monads

In F# you'll have to do some more legwork, but once you've added the required infrastructure, the 'user code' based on free monads is perfectly fine.

C#, on the other hand, doesn't have all the language features that will make free monads a good experience. I wouldn't suggest using a free monad in C#. I include the article with the C# free monad for demonstration purposes only.

These articles will not introduce free monads to novice readers. For a gentler introduction, see the article series Pure interactions.

Conclusion #

When all else fails, and you just must write pure functions, reach for free monads. They are not for everyone, or every language, but they do offer a functional solution to problems with large data sets or rich interaction with users or the environment.

Next: Song recommendations with Haskell free monads.

Synchronized database reads for testing purposes.

In a previous article, you saw how to use a slow Decorator to test for race conditions. Towards the end, I discussed how that solution is only near-deterministic. In this article, I discuss a technique which is, I think, properly deterministic, but unfortunately less elegant.

In short, it works by letting a Decorator synchronize reads.

The problem #

In the previous article, I used words to describe the problem, but really, I should be showing, not telling. Here's a variation on the previous test that exemplifies the problem.

[Fact]
public async Task NoOverbookingRace()
{
    var date = DateTime.Now.Date.AddDays(1).AddHours(18.5);
    using var service = new RestaurantService();
    using var slowService =
        from repo in service
        select new SlowReservationsRepository(TimeSpan.FromMilliseconds(100), repo);

    var task1 = slowService.PostReservation(new ReservationDtoBuilder()
        .WithDate(date)
        .WithQuantity(10)
        .Build());
    await Task.Delay(TimeSpan.FromSeconds(1));
    var task2 = slowService.PostReservation(new ReservationDtoBuilder()
        .WithDate(date)
        .WithQuantity(10)
        .Build());
    var actual = await Task.WhenAll(task1, task2);

    Assert.Single(
        actual,
        msg => msg.StatusCode == HttpStatusCode.InternalServerError);
    var ok = Assert.Single(actual, msg => msg.IsSuccessStatusCode);
    // Check that the reservation was actually created:
    var resp = await service.GetReservation(ok.Headers.Location);
    resp.EnsureSuccessStatusCode();
    var reservation = await resp.ParseJsonContent<ReservationDto>();
    Assert.Equal(10, reservation.Quantity);
}

Apart from a single new line of code, this is is identical to the test shown in the previous article. The added line is the Task.Delay between task1 and task2.

What's the point of adding this delay there? Only to demonstrate a problem. That's one of the situations I described in the previous article: Even though the test starts both tasks without awaiting them, they aren't guaranteed to run in parallel. Both start as soon as they're created, so task2 is going to be ever so slightly behind task1. What happens if there's a delay between the creation of these two tasks?

Here I've explicitly introduced such a delay for demonstration purposes, but such a delay could happen on a real system for a number of reasons, including garbage collection, thread starvation, the OS running a higher-priority task, etc.

Why might that pause matter?

Because it may produce false negatives. Imagine a situation where there's no transaction control; where there's no TransactionScope around the database interactions. If the pause is long enough, the tasks effectively run in sequence (instead of in parallel), in which case the system correctly rejects the second attempt.

This is even when using the SlowReservationsRepository Decorator.

How long does the pause need to be before this happens?

As described in the previous article, with a configured delay of 100 ms for the SlowReservationsRepository, creating a new reservation is delayed by 300 ms. This bears out. Experimenting on my own machine, if I change that explicit, artificial delay to 300 ms, and remove the transaction control, the test sometimes fails, and sometimes passes. With the above one-second delay, the test always passes, even when transaction control is missing.

You could decide that a 300 ms pause at just the worst possible time is so unlikely that you're willing to simply accept those odds. I would probably be, too. Still, what to test, and what not to test is a function of context. You may find yourself in a context where that's not good enough. What other options are there?

Synchronizing Decorator #

What you really need to reproduce the race condition is to synchronize the database reads. If you could make sure that the Repository only returns data when enough reads have been performed, you can deterministically reproduce the problem.

Again, start with a Decorator. This time, build into it a way to synchronize reads.

internal sealed class SynchronizedReaderRepository : IReservationsRepository
{
    private readonly CountdownEvent countdownEvent = new CountdownEvent(2);

    public SynchronizedReaderRepository(IReservationsRepository inner)
    {
        Inner = inner;
    }

    public IReservationsRepository Inner { get; }

Here I've used a CountdownEvent object to ensure that reads only progress when the countdown reaches zero. It's possible that more appropriate threading APIs exist, but this serves well as a proof of concept.

The method you need to synchronize is ReadReservations, so you can leave all the other methods to delegate to Inner. Only ReadReservations is special.

public async Task<IReadOnlyCollection<Reservation>> ReadReservations(
    int restaurantId,
    DateTime min,
    DateTime max)
{
    var result = await Inner .ReadReservations(restaurantId, min, max);
    countdownEvent.Signal();
    countdownEvent.Wait();
    return result;
}

This implementation also starts by delegating to Inner, but before it returns the result, it signals the countdownEvent and blocks the thread by waiting on the countdownEvent. Only when both threads have signalled it does the counter reach zero, and the methods may proceed.

If we assume that, while the test is running, no other calls to ReadReservations is made, this guarantees that both threads receive the same answer. This will make both competing threads come to the answer that they can accept the reservation. If no transaction control is in place, the system will overbook the requested time slot.

Testing with the synchronizing Repository #

The test that uses SynchronizedReaderRepository is almost identical to the previous test.

[Fact]
public async Task NoOverbookingRace()
{
    var date = DateTime.Now.Date.AddDays(1).AddHours(18.5);
    using var service = new RestaurantService();
    using var syncedService =
        service.Select(repo => new SynchronizedReaderRepository(repo));

    var task1 = syncedService.PostReservation(new ReservationDtoBuilder()
        .WithDate(date)
        .WithQuantity(10)
        .Build());
    var task2 = syncedService.PostReservation(new ReservationDtoBuilder()
        .WithDate(date)
        .WithQuantity(10)
        .Build());
    var actual = await Task.WhenAll(task1, task2);

    Assert.Single(
        actual,
        msg => msg.StatusCode == HttpStatusCode.InternalServerError);
    var ok = Assert.Single(actual, msg => msg.IsSuccessStatusCode);
    // Check that the reservation was actually created:
    var resp = await service.GetReservation(ok.Headers.Location);
    resp.EnsureSuccessStatusCode();
    var reservation = await resp.ParseJsonContent<ReservationDto>();
    Assert.Equal(10, reservation.Quantity);
}

Contrary to using the slow Repository, this test doesn't allow false negatives. If transaction control is missing from the System Under Test (SUT), this test fails. And it passes when transaction control is in place.

Disadvantages #

That sounds great, so why not just do this, instead of using a delaying Decorator? Because, as usual, there are trade-offs involved. This kind of solution comes with some disadvantages that are worth taking into account.

In short, this could make the test more fragile. As shown above, SynchronizedReaderRepository makes a specific assumption. It assumes that it needs to synchronize exactly two parallel readers. One problem with this is that this may be coupled to exactly one test. If you had other tests, you'd need to write a new Decorator, or generalize this one in some way.

Another problem is that this makes the test sensitive to changes in the SUT. What if a code change introduces a new call to ReadReservations? If so, the countdownEvent may unblock the threads too soon. One such change may be that the SUT decides to also query for surrounding times slots. You might be able to make SynchronizedReaderRepository robust against such changes by keeping a dictionary of synchronization objects (such as the above CountdownEvent) per argument set, but that clearly complicates the implementation.

And even so, it doesn't protect against identical 'double reads', even though these may be less likely to happen.

This Decorator is also vulnerable to caching. If you have a read-through cache that wraps around SynchronizedReaderRepository, only the first query may get to it, which would then cause it to block forever. Perhaps, again, you could fix this with the Wait overload that takes a timeout value.

That said, if you cache reads, the pessimistic locking that TransactionScope uses isn't going to work. You could, perhaps, address that concern with optimistic concurrency, but that comes with its own problems.

Conclusion #

You can address race conditions in various ways, but synchronization has been around for a long time. Not only can you use synchronization primitives and APIs to make your code thread-safe, you can also use them to deterministically reproduce race conditions, or to test that such a bug is no longer present in the system.

I don't want to claim that this is universally possible, but if you run into such problems, it's at least worth considering if you could take advantage of synchronization to reproduce a problem.

Of course, the implication is that you understand what the problem is. This is often the hardest part of dealing with race conditions, and the ideas described in this article don't help with that.

Comments

                public class ReservationTests(Xunit.Abstractions.ITestOutputHelper output)
                {
                    [Fact]
                    public void ReservationSystem_Parallel_Test()
                    {
                        Check.SampleParallel(
                            // initial state
                            Gen.Const(() => new ReservationSystem()),
                            // parallel operations
                            Gen.Int[1, 10].Operation((rs, q) =>
                                rs.PostReservation(new ReservationDtoBuilder().WithQuantity(q))),
                            // equality check parallel vs sequential
                            equal: (rs1, rs2) => rs1.AllBookings().Equals(rs2.AllBookings()),
                            // string representation of the bookings state for when the test fails
                            print: rs => rs.AllBookings().ToTableString(),
                            // display output in test results
                            writeLine: output.WriteLine
                        );
                    }
                }

            

MailboxProcessors as small Recawr Sandwiches.

This article is part of a series named Alternative ways to design with functional programming. As the title implies, over a multitude of articles, I present various alternatives for applying functional programming to a particular problem. When I present the Impureim Sandwich design pattern, the most common reaction is: What if you need to make additional, impure reads in the middle of an algorithm?

This article series looks at alternatives when this (in my experience rare) requirement seems inescapable. A previous article outlined a general alternative: Use some kind of pipes-and-filters architecture to turn an undisciplined Transaction Script into a composition of 'filters', where each filter is a self-contained Recawr Sandwich.

Depending on the specific technology choices you make, you may encounter various terminology related to this kind of architecture. Filters may also be called actors, message handlers, or, as is the case in this article, agents. For a consistent pattern language, see Enterprise Integration Patterns.

The code shown here is taken from the fsharp-agents branch of the example code Git repository.

Async instead of Task #

The F# base library comes with a class called MailboxProcessor, often called an agent. It's an in-memory message handler that can run in the background of other tasks, pulling messages off an internal queue one at a time.

It's been around for such a long time that its API is based on Async<T>, which precedes the now-ubiquitous Task<TResult>. While conversions exist, I thought it'd make the example code simpler if I first redefined the SongService interface to return Async-based results.

type SongService =
    abstract GetTopListenersAsync : songId : int -> Async<IReadOnlyCollection<User>>
    abstract GetTopScrobblesAsync : userName : string -> Async<IReadOnlyCollection<Scrobble>>

Keep in mind that, despite lack of the idiomatic I prefix, this is an interface, not an abstract class. (It would have had to have the [<AbstractClass>] attribute to be an abstract class.)

This is minor change that only affected a few lines of code where I had to change from task expressions to async expressions.

Gather own scrobbles #

As was also the case in the previous article, we may as well start at the beginning of the algorithm. Given a user name, we'd like to find that user's top scrobbles. Once we've found them, we'd like to post them to an agent. Since F# agents are message-based, we must define an appropriate message type.

type private ScrobbleMessage = Scrobble of Scrobble | EndOfStream

If you recall the previous article, with Reactive Extensions for .NET, you can use the OnCompleted method to signal the end of a stream. Such a method isn't available for an F# agent, because an agent is a consumer of messages, rather than a stream of values. For that reason, a ScrobbleMessage may either be a Scrobble or an EndOfStream.

With the message definition in place, you can define the first step of the algorithm like this:

// string -> SongService -> MailboxProcessor<ScrobbleMessage> -> Async<unit>
let private gatherOwnScrobbles
    userName (songService : SongService) (channel : MailboxProcessor<_>) =
    async {
        // Impure
        let! scrobbles = songService.GetTopScrobblesAsync userName
 
        // Pure
        let scrobblesSnapshot =
            scrobbles
            |> Seq.sortByDescending _.ScrobbleCount
            |> Seq.truncate 100
            |> Seq.map Scrobble
 
        // Impure
        Seq.iter channel.Post scrobblesSnapshot
        channel.Post EndOfStream }

The gatherOwnScrobbles action isn't itself an agent. Rather, it takes one as input, to which it posts messages. Notice that the operation returns an Async<unit> value. In other words, it doesn't really return anything, but rather posts messages to the injected channel.

Like in the previous article, once all scrobbles are posted, gatherOwnScrobbles indicates the end of the stream by posting a final EndOfStream message. This still works in this implementation, since F# agents (as far as I've been able ascertain) handle messages in order. If you're using a distributed messaging framework based on a message bus, and possibly handlers running on multiple machines, you can't always assume this to be the case. As I wrote in Song recommendations with pipes and filters, you'll need to extrapolate from both this and the previous article in such cases. This is where a pattern language as presented in Enterprise Integration Patterns may come in handy. Perhaps you need a Message Sequence in this case.

Be that as it may, the gatherOwnScrobbles action is a small Recawr Sandwich with clearly delineated steps.

The natural next step is to implement a MailboxProcessor that can receive those scrobble messages.

Gather other listeners #

To handle the messages posted by gatherOwnScrobbles we'll create an agent. This one, however, isn't going to complete the algorithm. Rather, it's going to publish even more messages that yet another agent may deal with. For that, we need another message type:

type private UserMessage = User of User | EndOfStream

We see what starts to look like a pattern: A 'payload' case, and a case to indicate that no more message will be coming.

The following action creates an agent that handles scrobble messages and publishes user messages:

// SongService -> MailboxProcessor<UserMessage> -> MailboxProcessor<ScrobbleMessage>
let private gatherOtherListeners
    (songService : SongService) (channel : MailboxProcessor<_>) =
    MailboxProcessor.Start <| fun inbox ->
        let rec loop () = async {
            let! message = inbox.Receive ()
            match message with
            | Scrobble scrobble ->
                // Impure
                let! otherListeners =
                    songService.GetTopListenersAsync scrobble.Song.Id
 
                // Pure
                let otherListenersSnapshot =
                    otherListeners
                    |> Seq.filter (fun u -> u.TotalScrobbleCount >= 10_000)
                    |> Seq.sortByDescending _.TotalScrobbleCount
                    |> Seq.truncate 20
                    |> Seq.map User
 
                // Impure
                Seq.iter channel.Post otherListenersSnapshot
                return! loop ()
            | ScrobbleMessage.EndOfStream -> channel.Post EndOfStream }
        loop ()

If you can look past some of the infrastructure required to initialize and implement the agent (MailboxProcessor), the main message handler is, once again, a small Recawr Sandwich. The other case in the match expression maps one EndOfStream case to another EndOfStream case. Notice that this case does not recursively call loop. This means that once the agent receives an EndOfStream message, it stops all further message processing.

You may have noticed that the loop starts with an 'unmarked' impure step to receive a message. Once a message arrives, it matches on the message. You may argue that there seems to be more than one impure step in the sandwich, but as I've previously outlined, sometimes a sandwich has more that three layers.

I could have compressed the code that receives and dispatches the message to a single line of code:

match! input.Receive () with

I felt, however, that for readers who aren't familiar with F# agents, it would help to instead make things more explicit by having a named message value in the code. It's an example of using an explicit variable for readability purposes.

A third agent, created by gatherOtherScrobbles, handles the messages published by gatherOtherListeners by publishing even more song messages. We'll get back to that message type in a moment, but the agent looks similar to the one shown above. You may consult the Git repository if you're curious about the details.

Collecting the recommendations #

The final agent is a bit different, because it needs to do two things:

• Handle song messages
• Return the recommendations once they're ready

Because of that extra responsibility, the message type isn't a two-way discriminated union. Instead, it has a third case that we haven't yet seen.

type private SongMessage =
    | Song of Song
    | EndOfStream
    | Fetch of AsyncReplyChannel<Option<IReadOnlyCollection<Song>>>

The Song and EndOfStream cases are similar to what we've already seen. These are the two messages that the gatherOtherScrobbles agent publishes.

What does the third case, Fetch, do? It looks odd, with its AsyncReplyChannel payload. In a moment, you'll see how it's used, but essentially, this is how F# agents support the Request-Reply pattern. Let's see it all in action:

// unit -> MailboxProcessor<SongMessage>
let private collectRecommendations () =
    MailboxProcessor.Start <| fun input ->
        let rec loop recommendations isDone = async {
            let! message = input.Receive ()
            match message with
            | Song song -> return! loop (song :: recommendations) false
            | SongMessage.EndOfStream ->
                let recommendations =
                    recommendations
                    |> List.sortByDescending _.Rating
                    |> List.truncate 200
                return! loop recommendations true
            | Fetch replyChannel ->
                if isDone then
                    replyChannel.Reply (Some recommendations)
                else
                    replyChannel.Reply None
                return! loop recommendations isDone }
        loop [] false

The purpose of this agent is to collect all the songs that the previous agent recommended. Once it receives an EndOfStream message, it sorts the songs and keeps only the top 200.

Note that the recursive loop action takes two parameters, recommendations and isDone. The loops starts with an empty song list and the flag set to false. When a new Song arrives, the loop prepends the song onto the song list and recurses. Notice that in that case, the flag remains false.

Only when an EndOfStream message arrives does the agent calculate the final recommendations. Afterwards, it recursively calls loop with the flag raised (set to true). Notice, however, that the agent doesn't stop handling messages, like the other agents do when encountering an EndOfStream message.

At any time during execution, a Fetch message may arrive. This is a request to return the recommendations, if they're ready. In that case, the recommendations are wrapped in a Some case and returned. If the recommendations are not yet ready, None is returned instead.

This enables the overall, blocking method to poll for the recommendations until they are ready. You'll see how this works in a moment.

Polling for results #

The MailboxProcessor class defines a PostAndAsyncReply method that does, indeed, fit the Fetch case of the above SongMessage type. This enables us to implement a polling mechanism like this:

let rec private poll (agent : MailboxProcessor<_>) = task {
    match! agent.PostAndAsyncReply Fetch with
    | Some result -> return result
    | None -> return! poll agent }

This recursive action uses PostAndAsyncReply to keep polling its agent until it receives a useful reply. Since this code is mostly meant for illustration purposes, I've allowed myself a few shortcuts.

First, this effectively implements a busy loop. Whenever it receives a None reply, it immediately recurses to try again. A more reasonable implementation may put a small delay there, but I think that finding the optimal delay time may be a matter of experimentation. After all, if you're concerned with performance, race your horses. Given that this is demo code, I don't have any real horses to race, so I'm not going to try. From observation, however, it doesn't seem as though the tests, at least, run any slower despite the tight loop.

Secondly, the poll loop keeps going until it receives a useful response. What if that never happens? A more robust implementation should implement some kind of timeout or ceiling that enables it to give up if it's been running for too long.

Apart from all that, how does the poll action even type-check? On a MailboxProcessor<'Msg> object, the PostAndAsyncReply method has this type:

(AsyncReplyChannel<'Reply> -> 'Msg) -> Async<'Reply>

ignoring an optional timeout parameter.

The above Fetch case constructor fits the type of PostAndAsyncReply, since it has the type

AsyncReplyChannel<Option<IReadOnlyCollection<Song>>> -> SongMessage

This means that we can infer 'Reply to be Option<IReadOnlyCollection<Song>>. It also means that 'Msg must be SongMessage, and again we can infer that the agent parameter has the type MailboxProcessor<SongMessage>.

Composition #

With all components ready, we can now compose them as a blocking method. Notice that, in the following, the GetRecommendationsAsync method hasn't changed type or observable behaviour. The change from Task to Async (described above) required some trivial changes to FakeSongService, but apart from that, I had to change no test code to make this refactoring.

As a first attempt, we may compose the agents using the idiomatic left-to-right pipeline operator, like this:

type RecommendationsProvider (songService : SongService) =
    member _.GetRecommendationsAsync userName =
        let collect = collectRecommendations ()
        task {
            do! collect
                |> gatherOtherScrobbles songService
                |> gatherOtherListeners songService
                |> gatherOwnScrobbles userName songService
            return! poll collect }

First, the task expression starts all the agents, and then proceeds to poll the collect agent until it arrives at a result.

This passes all tests, but has at least two problems. One problem is that the composition seems backwards. It looks as though the process starts with collect, then proceeds to gatherOtherScrobbles, and so on. In reality, it's the other way around. You should really understand the composition as being defined 'bottom-up', or right-to-left, if we put it on a single line. We'll return to the other problem in a moment, but let's first see if we can do something about this one.

My first attempt to fix this problem was to try to use the reverse pipeline operator <|, but due to precedence rules, it didn't work without parentheses. And if we need parentheses anyway, there's no reason to use the reverse pipeline operator.

type RecommendationsProvider (songService : SongService) =
    member _.GetRecommendationsAsync userName =
        let collect = collectRecommendations ()
        task {
            do!
               gatherOwnScrobbles userName songService (
               gatherOtherListeners songService (
               gatherOtherScrobbles songService (
               collect)))
            return! poll collect }

This composition uses a slightly unorthodox code formatting style. Since collect is really nested inside of gatherOtherScrobbles, it should really have been indented to the right of it. Likewise, gatherOtherScrobbles is nested inside of gatherOtherListeners, and so on. A more idiomatic formatting of the code might be something like this:

type RecommendationsProvider (songService : SongService) =
    member _.GetRecommendationsAsync userName =
        let collect = collectRecommendations ()
        task {
            do! gatherOwnScrobbles userName songService (
                    gatherOtherListeners songService (
                        gatherOtherScrobbles songService collect))
            return! poll collect }

This, however, blurs the semantics of the composition in favour of the mechanics of it. I don't consider it an improvement.

All of this, however, turns out to be moot because of the other problem. The MailboxProcessor class implements IDisposable, and to be good citizens, we ought to dispose of the objects once we're done with them. This is possible, but we're now back to the backwards order of composition.

type RecommendationsProvider (songService : SongService) =
    member _.GetRecommendationsAsync userName = task {
        use collect = collectRecommendations ()
        use otherScrobbles = gatherOtherScrobbles songService collect
        use otherListeners = gatherOtherListeners songService otherScrobbles
        do! gatherOwnScrobbles userName songService otherListeners
 
        return! poll collect }

This may not be an entirely unsolvable problem, but this is where I'm no longer interested in pursuing this line of inquiry much further. Instead of those 'factory actions' that create and return agents, you could refactor each agent into a separate object that, when disposed of, also disposes of any inner agents it may contain. If so, you could again compose these objects as shown above, and only dispose of the outer object.

Evaluation #

These various attempts to make the agents compose nicely, in a way that also works as self-documenting code, reveals that F# agents aren't as composable as ReactiveX. To be fair, the MailboxProcessor class also predates Reactive Extensions, so we shouldn't blame it for not being as good as a more recent technology.

One major problem is that agents don't compose naturally, like IObservable<T> does. I briefly considered whether it'd be possible to make MailboxProcessor<'Msg> a monad, but armed with the knowledge of variance imparted by Thinking with Types, I quickly realized that the type is invariant. This is easily seen because one method, Post, is contravariant in 'Msg, whereas most other methods are covariant. I'm using deliberately vague language, since there's no reason to calculate the kind of variance for all methods when you've already found two incompatible members.

Another fly in the ointment is that the collectRecommendations action looks messy. As presented, it's not a pretty Impureim Sandwich. Most of the 'middle' message handling could be extracted to a pure function, were it not for the Fetch case. Calling replyChannel.Reply has a side effect, and while I know of refactorings that move side effects around, I'd need access to the replyChannel in order to impart that effect from somewhere else. This would still be possible if I returned an action to be invoked, but I don't see much point in that. In general, that request-reply API doesn't strike me as particularly functional.

Based on all that griping, you may be wondering whether this kind of architecture is worth the trouble. Keep in mind, though, that some of the issues I just outlined is the result of the particular MailboxProcessor API. It's not a given that if you use some other message-based framework, you'll run into the same issues.

You may also find the notion of posting messages to a chain of agents, only to poll one of them for the result, as carrying coals to Newcastle. Keep in mind, however, that the code presented here refactors a blocking method call that apparently takes about ten minutes to run to completion. It's possible that I read too much into the situation, but I'm guessing that the 'real' code base that was the inspiration for the example code, doesn't actually block for ten minutes in order to return a result. Rather, I still speculate, it's probably a background batch job that produces persisted views; e.g. as JSON files. If so, you'd really just want to trigger a new batch job and let it run to completion in the background. In such a scenario, I'd find an asynchronous, message-based architecture suitable for the job. In that case, you'd need no polling loop. Rather, you serve a persisted view whenever anyone asks for it, and once in a while, that persisted view has been updated by the background process.

Conclusion #

Compared to the previous article, which used Reactive Extensions to compose self-contained Recawr Sandwiches, using F# agents is a move towards a more standard kind of message-based architecture. Hopefully, it does a good enough job of illustrating how you can refactor an impure action into a composition of individual sandwiches, even if some of the details here are particular to F# agents.

It's not necessarily always the best solution to the underlying problem being addressed in this article series, but it seems appropriate if the problem of large data sets is combined with long running time. If you can convert the overall problem to a fire-and-forget architecture, a message-based system may be suitable.

If, on the other hand, you need to maintain the blocking nature of the operation, you may need to reach for the big, universal hammer.

Next: Song recommendations with free monads.

Observables as small Recawr Sandwiches.

This article is part of a series titled Alternative ways to design with functional programming. In the previous article in the series, you read some general reflections on a pipes-and-filters architecture. This article gives an example in C#.

The code shown here is from the rx branch of the example code Git repository. As the name implies, it uses ReactiveX, also known as Reactive Extensions for .NET.

To be honest, when refactoring an algorithm that's originally based on sequences of data, there's nothing particularly reactive going on here. You may, therefore, argue that it's a poor fit for this kind of architecture. Be that as it may, keep in mind that the example code in reality runs for about ten minutes, so moving towards an architecture that supports progress reporting or cancellation may not be entirely inappropriate.

The advantage of using Reactive Extensions for this particular example is that, compared to full message-bus-based frameworks, it offers a lightweight developer experience, which enables us to focus on the essentials of the architecture.

Handle own scrobbles #

We'll start with the part of the process that finds the user's own top scrobbles. Please consult with Oleksii Holub's original article, or my article on characterizing the implementation, if you need a refresher.

When using Reactive Extensions, should we model this part as IObservable<T> or IObserver<T>?

Once you recall that IObservable<T>, being a monad, is eminently composable, the choice is clear. The IObserver<T> interface, on the other hand, gives rise to a contravariant functor, but since that abstraction has weaker language support, we should go with the monad.

We can start by declaring the type and its initializer:

public sealed class HandleOwnScrobblesObservable : IObservable<Scrobble>
{
    private readonly string userName;
    private readonly SongService _songService;
 
    public HandleOwnScrobblesObservable(string userName, SongService songService)
    {
        this.userName = userName;
        _songService = songService;
    }
 
    // Implementation goes here...

Given a userName we want to produce a (finite) stream of scrobbles, so we declare that the class implements IObservable<Scrobble>. An instance of this class is also going to need the songService, so that its implementation can query the out-of-process system that holds the data.

What's that, you say? Why does _songService have a leading underscore, while the userName field does not? Because Oleksii Golub used that naming convention for that service, but I don't feel obliged to stay consistent with that.

Given that we already have working code, the implementation is relatively straightforward.

public IDisposable Subscribe(IObserver<Scrobble> observer)
{
    return Observable.Create<Scrobble>(Produce).Subscribe(observer);
}
 
private async Task Produce(IObserver<Scrobble> obs)
{
    // Impure
    var scrobbles = await _songService.GetTopScrobblesAsync(userName);
 
    // Pure
    var scrobblesSnapshot = scrobbles
        .OrderByDescending(s => s.ScrobbleCount)
        .Take(100);
 
    // Impure
    foreach (var scrobble in scrobblesSnapshot)
        obs.OnNext(scrobble);
    obs.OnCompleted();
}

If you are unused to Reactive Extensions, the hardest part may be figuring out how to implement Subscribe without getting bogged down with having to write too much of the implementation. Rx is, after all, a reusable library, so it should come with some building blocks for that, and it does.

It seems that the simplest way to implement Subscribe is to delegate to Observable.Create, which takes an expression as input. You can write the implementation inline as a lambda expression, but here I've used a private helper method to slightly decouple the implementation from the library requirements.

The first impure step is the same as we've already seen in the 'reference implementation', and the pure step should be familiar too. In the final impure step, the Produce method publishes the scrobbles to any subscribers that may be listening.

This is the step where you'll need to extrapolate if you want to implement this kind of architecture on another framework than Reactive Extensions. If you're using a distributed message-based framework, you may have a message bus on which you publish messages, instead of obs. So obs.OnNext may, instead, be bus.Publish, or something to that effect. You may also need to package each scrobble in an explicit message object, and add correlation identifier and such.

In many message-based frameworks (NServiceBus, for example), you're expected to implement some kind of message handler where messages arrive at a Handle method, typically on a stateless, long-lived object. This enables you to set up robust, distributed systems, but also comes with some overhead that requires you to coordinate or correlate messages.

In this code example, userName is just a class field, and once the object is done producing messages, it signals so with obs.OnCompleted(), after which the stream has ended.

The Rx implementation is simpler than some message-based systems I just outlined. That's the reason I chose it for this article. It doesn't mean that it's better, because that simplicity comes at the expense of missing capabilities. This system has no persistence, and I while I'm no expert in this field, I don't think it easily expands to a distributed system. And again, to perhaps belabour the obvious, I'm not insisting that any of those capabilities are always needed. I'm only trying to outline some of the trade-offs you should be aware of.

Handle other listeners #

HandleOwnScrobblesObservable objects publish Scrobble objects. What does the next 'filter' look like? It's another observable stream, implemented by a class called HandleOtherListenersObservable. It implements IObservable<User>, and its class declaration, constructor, and Subscribe implementation look a lot like what's already on display above. The main difference is the Produce method.

private async Task Produce(IObserver<User> obs)
{
    // Impure
    var otherListeners = await _songService
        .GetTopListenersAsync(scrobble.Song.Id);
 
    // Pure
    var otherListenersSnapshot = otherListeners
        .Where(u => u.TotalScrobbleCount >= 10_000)
        .OrderByDescending(u => u.TotalScrobbleCount)
        .Take(20);
 
    // Impure
    foreach (var otherListener in otherListenersSnapshot)
        obs.OnNext(otherListener);
    obs.OnCompleted();
}

Compared to the reference architecture, this implementation is hardly surprising. The most important point to make is that, as was the goal all along, this is another small Recawr Sandwich.

A third observable, HandleOtherScrobblesObservable, handles the third step of the algorithm, and looks much like HandleOtherListenersObservable. You can see it in the Git repository.

Composition #

The three observable streams constitute most of the building blocks required to implement the song recommendations algorithm. Notice the 'fan-out' nature of the observables. The first step starts with a single userName and produces up to 100 scrobbles. To handle each scrobble, a new instance of HandleOtherListenersObservable is required, and each of those produces up to twenty User notifications, and so on.

In the abstract, we may view the HandleOwnScrobblesObservable constructor as a function from string to IObservable<Scrobble>. Likewise, we may view the HandleOtherListenersObservable constructor as a function that takes a single Scrobble as input, and gives an IObservable<User> as return value. And finally, HandleOtherScrobblesObservable takes a single User as input to return IObservable<Song> as output.

Quick, what does that look like, and how do you compose them?

Indeed, those are Kleisli arrows, but in practice, we use monadic bind to compose them. In C# this usually means SelectMany.

public async Task<IReadOnlyList<Song>> GetRecommendationsAsync(string userName)
{
    // 1. Get user's own top scrobbles
    // 2. Get other users who listened to the same songs
    // 3. Get top scrobbles of those users
    // 4. Aggregate the songs into recommendations
 
    var songs = await
        new HandleOwnScrobblesObservable(userName, _songService)
        .SelectMany(s => new HandleOtherListenersObservable(s, _songService))
        .SelectMany(u => new HandleOtherScrobblesObservable(u, _songService))
        .ToList();
    return songs
        .OrderByDescending(s => s.Rating)
        .Take(200)
        .ToArray();
}

The fourth step of the algorithm, you may notice, isn't implemented as an observable, but rather as a standard LINQ pipeline. This is because sorting is required, and if there's a way to sort an observable, I'm not aware of it. After all, given that observable objects may represent infinite data streams, I readily accept that there's no OrderByDescending method on IObservable<T>. (But then, the System.Reactive library defines Min and Max operations, and exactly how those work when faced with infinite streams, I haven't investigated.)

While I could have created a helper function for that small OrderByDescending/Take/ToArray pipeline, I consider it under the Fairbairn threshold.

Query syntax #

You can also compose the algorithm using query syntax, which I personally find prettier.

IObservable<Song> obs =
    from scr in new HandleOwnScrobblesObservable(userName, _songService)
    from usr in new HandleOtherListenersObservable(scr, _songService)
    from sng in new HandleOtherScrobblesObservable(usr, _songService)
    select sng;
IList<Song> songs = await obs.ToList();
return songs
    .OrderByDescending(s => s.Rating)
    .Take(200)
    .ToArray();

In this code snippet I've used explicit variable type declarations (instead of using the var keyword) for the sole purpose of making it easier to see which types are involved.

Conclusion #

This article shows an implementation example of refactoring the song recommendations problem to a pipes-and-filters architecture. It uses Reactive Extensions for .NET, since this showcases the (de)composition in the simplest possible way. Hopefully, you can extrapolate from this to a more elaborate, distributed asynchronous message-based system, if you need something like that.

The next example makes a small move in that direction.

Next: Song recommendations with F# agents.

Composing small Recawr Sandwiches.

This article is part of a larger series that outlines various alternative ways to design with functional programming. That (first) article contains a table of contents, as well as outlines the overall programme and the running example. In short, the example is a song recommendation engine that works on large data sets.

Previous articles in this series have explored refactoring to a pure function and composing impure actions with combinators. In the next few articles, we'll look at how to use message-based architectures to decouple the algorithm into smaller Recawr Sandwiches. As an overall concept, we may term such an architecture pipes and filters. The book Enterprise Integration Patterns is a great resource for this kind of (de)composition. Don't be mislead by the title: In essence, it's neither about enterprise programming nor integration.

Workflows of small sandwiches #

As speculated in Song recommendations as an Impureim Sandwich, the data sets involved when finding song recommendations for a user may be so large that an Impureim Sandwich is impractical.

On the other hand, a message-based system essentially consists of many small message handlers that each may be implemented as Impureim Sandwiches. I've already briefly discussed this kind of decomposition in Pure interactions, where each message handler or 'actor' is a small process equivalent to a web request handler (Controller) or similar.

When it comes to the song recommendation problem, we may consider a small pipes-and-filters architecture that uses small 'filters' to start even more work, handled by other filters, and so on.

Depending on the exact implementation details, you may call this pipes and filters, reactive functional programming, the actor model, map/reduce, or something else. What I consider crucial in this context is that each 'filter' is a small Recawr Sandwich. It queries the out-of-process music data service, applies a pure function to that data, and finally sends more messages over some impure channel. In the following articles, you'll see code examples.

• Song recommendations with C# Reactive Extensions
• Song recommendations with F# agents

As I'm writing this, I don't plan to supply a Haskell example. The main reason is that I've no experience with writing asynchronous message-based systems with Haskell, and while a quick web search indicates that there are plenty of libraries for reactive functional programming, on the other hand, I can't find much when it comes to message-bus-based asynchronous messaging.

Perhaps it'd be more idiomatic to supply an Erlang example, but it's been too many years since I tried teaching myself Erlang, and I never became proficient with it.

Modelling #

It turns out that when you decompose the song recommendation problem into smaller 'filters', each of which is a Recawr Sandwich, you arrive at a decomposition that looks suspiciously close to what we saw in Song recommendations from combinators. And as Oleksii Holub wrote,

"However, instead of having one cohesive element to reason about, we ended up with multiple fragments, each having no meaning or value of their own. While unit testing of individual parts may have become easier, the benefit is very questionable, as it provides no confidence in the correctness of the algorithm as a whole."

This remains true here. Why even bother, then?

The purpose of this article series is to present alternatives, just like Scott Wlaschin's excellent article Thirteen ways of looking at a turtle. It may be that a given design alternative isn't the absolute best fit for the song recommendation problem, but it may, on the other hand, be a good fit for some other problem that you run into. If so, you should be able to extrapolate from the articles in this series.

Conclusion #

Given that we know that the real code that the song recommendation example is based off runs for about ten minutes, some kind of asynchronous process that may support progress indication or cancellation may be worth considering. This easily leads us in the direction of some kind of pipes-and-filters architecture.

You can implement such an architecture with in-memory message streams, as the next article does, or you can go with a full-fledged messaging system based on persistent message buses and distributed, restartable message handlers. The details vary, but it's essentially the same kind of architecture.

Next: Song recommendations with C# Reactive Extensions.