ploeh blog

Das verflixte Hunde-Spiel

2024-10-03T17:41:00+00:00

A puzzle kata, and a possible solution.

When I was a boy I had a nine-piece puzzle that I'd been gifted by the Swizz branch of my family. It's called Das verflixte Hunde-Spiel, which means something like the confounded dog game in English. And while a puzzle with nine pieces doesn't sound like much, it is, in fact, incredibly difficult.

It's just a specific incarnation of a kind of game that you've almost certainly encountered, too.

There are nine tiles, each with two dog heads and two dog ends. A dog may be coloured in one of four different patterns. The object of the game is to lay out the nine tiles in a 3x3 square so that all dog halves line up.

Game details #

The game is from 1979. Two of the tiles are identical, and, according to the information on the back of the box, two possible solutions exist. Described from top clockwise, the tiles are the following:

Brown head, grey head, umber tail, spotted tail
Brown head, spotted head, brown tail, umber tail
Brown head, spotted head, grey tail, umber tail
Brown head, spotted head, grey tail, umber tail
Brown head, umber head, spotted tail, grey tail
Grey head, brown head, spotted tail, umber tail
Grey head, spotted head, brown tail, umber tail
Grey head, umber head, brown tail, spotted tail
Grey head, umber head, grey tail, spotted tail

I've taken the liberty of using a shorthand for the patterns. The grey dogs are actually also spotted, but since there's only one grey pattern, the grey label is unambiguous. The dogs I've named umber are actually rather burnt umber, but that's too verbose for my tastes, so I just named them umber. Finally, the label spotted indicates dogs that are actually burnt umber with brown blotches.

Notice that there are two tiles with a brown head, a spotted head, a grey tail, and an umber tail.

The object of the game is to lay down the tiles in a 3x3 square so that all dogs fit. For further reference, I've numbered each position from one to nine like this:

What makes the game hard? There are nine cards, so if you start with the upper left corner, you have nine choices. If you just randomly put down the tiles, you now have eight left for the top middle position, and so on. Standard combinatorics indicate that there are at least 9! = 362,880 permutations.

That's not the whole story, however, since you can rotate each tile in four different ways. You can rotate the first tile four ways, the second tile four ways, etc. for a total of 4⁹ = 262,144 ways. Multiply these two numbers together, and you get 4⁹9! = 95,126,814,720 combinations. No wonder this puzzle is hard if there's only two solutions.

When analysed this way, however, there are actually 16 solutions, but that still makes it incredibly unlikely to arrive at a solution by chance. I'll get back to why there are 16 solutions later. For now, you should have enough information to try your hand with this game, if you'd like.

I found that the game made for an interesting kata: Write a program that finds all possible solutions to the puzzle.

If you'd like to try your hand at this exercise, I suggest that you pause reading here.

In the rest of the article, I'll outline my first attempt. Spoiler alert: I'll also show one of the solutions.

Types #

When you program in Haskell, it's natural to start by defining some types.

data Half = Head | Tail deriving (Show, Eq)
 
data Pattern = Brown | Grey | Spotted | Umber deriving (Show, Eq)
 
data Tile = Tile {
  top :: (Pattern, Half),
  right :: (Pattern, Half),
  bottom :: (Pattern, Half),
  left :: (Pattern, Half) }
  deriving (Show, Eq)

Each tile describes what you find on its top, right side, bottom, and left side.

We're also going to need a function to evaluate whether two halves match:

matches :: (Pattern, Half) -> (Pattern, Half) -> Bool
matches (p1, h1) (p2, h2) = p1 == p2 && h1 /= h2

This function demands that the patterns match, but that the halves are opposites.

You can use the Tile type and its constituents to define the nine tiles of the game:

tiles :: [Tile]
tiles =
  [
    Tile (Brown, Head) (Grey, Head) (Umber, Tail) (Spotted, Tail),
    Tile (Brown, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail),
    Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail),
    Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail),
    Tile (Brown, Head) (Umber, Head) (Spotted, Tail) (Grey, Tail),
    Tile (Grey, Head) (Brown, Head) (Spotted, Tail) (Umber, Tail),
    Tile (Grey, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail),
    Tile (Grey, Head) (Umber, Head) (Brown, Tail) (Spotted, Tail),
    Tile (Grey, Head) (Umber, Head) (Grey, Tail) (Spotted, Tail)
  ]

Because I'm the neatnik that I am, I've sorted the tiles in lexicographic order, but the solution below doesn't rely on that.

Brute force doesn't work #

Before I started, I cast around the internet to see if there was an appropriate algorithm for the problem. While I found a few answers on Stack Overflow, none of them gave me indication that any sophisticated algorithm was available. (Even so, there may be, and I just didn't find it.)

It seems clear, however, that you can implement some kind of recursive search-tree algorithm that cuts a branch off as soon as it realizes that it doesn't work. I'll get back to that later, so let's leave that for now.

Since I'd planned on writing the code in Haskell, I decided to first try something that might look like brute force. Because Haskell is lazily evaluated, you can sometimes get away with techniques that look wasteful when you're used to strict/eager evaluation. In this case, it turned out to not work, but it's often quicker to just make the attempt than trying to analyze the problem.

As already outlined, I first attempted a purely brute-force solution, betting that Haskell's lazy evaluation would be enough to skip over the unnecessary calculations:

allRotationsOf9 = replicateM 9 [0..3]
 
allRotations :: [Tile] -> [[Tile]]
allRotations ts = fmap (\rs -> (\(r, t) -> rotations t !! r) <$> zip rs ts) allRotationsOf9
 
allConfigurations :: [[Tile]]
allConfigurations = permutations tiles >>= allRotations
 
solutions = filter isSolution allConfigurations

My idea with the allConfigurations value was that it's supposed to enumerate all 95 billion combinations. Whether it actually does that, I was never able to verify, because if I try to run that code, my poor laptop runs for a couple of hours before it eventually runs out of memory. In other words, the GHCi process crashes.

I haven't shown isSolution or rotations, because I consider the implementations irrelevant. This attempt doesn't work anyway.

Now that I look at it, it's quite clear why this isn't a good strategy. There's little to be gained from lazy evaluation when the final attempt just attempts to filter a list. Even with lazy evaluation, the code still has to run through all 95 billion combinations.

Things might have been different if I just had to find one solution. With a little luck, it might be that the first solution appears after, say, a hundred million iterations, and lazy evaluation would then had meant that the remaining combinations would never run. Not so here, but hindsight is 20-20.

Search tree #

Back to the search tree idea. It goes like this: Start from the top left position and pick a random tile and rotation. Now pick an arbitrary tile that fits and place it to the right of it, and so on. As far as I can tell, you can always place the first four cards, but from there, you can easily encounter a combination that allows no further tiles. Here's an example:

None of the remaining five tiles fit in the fifth position. This means that we don't have to do any permutations that involve these four tiles in that combination. While the algorithm has to search through all five remaining tiles and rotations to discover that none fit in position 5, once it knows that, it doesn't have to go through the remaining four positions. That's 4⁴4! = 6,144 combinations that it can skip every time it discovers an impossible beginning. That doesn't sound like that much, but if we assume that this happens more often than not, it's still an improvement by orders of magnitude.

We may think of this algorithm as constructing a search tree, but immediately pruning all branches that aren't viable, as close to the root as possible.

Matches #

Before we get to the algorithm proper we need a few simple helper functions. One kind of function is a predicate that determines if a particular tile can occupy a given position. Since we may place any tile in any rotation in the first position, we don't need to write a predicate for that, but if we wanted to generalize, const True would do.

Whether or not we can place a given tile in the second position depends exclusively on the tile in the first position:

tile2Matches :: Tile -> Tile -> Bool
tile2Matches t1 t2 = right t1 `matches` left t2

If the right dog part of the first tile matches the left part of the second tile, the return value is True; otherwise, it's False. Note that I'm using infix notation for matches. I could also have written the function as

tile2Matches :: Tile -> Tile -> Bool
tile2Matches t1 t2 = matches (right t1) (left t2)

but it doesn't read as well.

In any case, the corresponding matching functions for the third and forth tile look similar:

tile3Matches :: Tile -> Tile -> Bool
tile3Matches t2 t3 = right t2 `matches` left t3
 
tile4Matches :: Tile -> Tile -> Bool
tile4Matches t1 t4 = bottom t1 `matches` top t4

Notice that tile4Matches compares the fourth tile with the first tile rather than the third tile, because position 4 is directly beneath position 1, rather than to the right of position 3 (cf. the grid above). For that reason it also compares the bottom of tile 1 to the top of the fourth tile.

The matcher for the fifth tile is different:

tile5Matches :: Tile -> Tile -> Tile -> Bool
tile5Matches t2 t4 t5 = bottom t2 `matches` top t5 && right t4 `matches` left t5

This is the first predicate that depends on two, rather than one, previous tiles. In position 5 we need to examine both the tile in position 2 and the one in position 4.

The same is true for position 6:

tile6Matches :: Tile -> Tile -> Tile -> Bool
tile6Matches t3 t5 t6 = bottom t3 `matches` top t6 && right t5 `matches` left t6

but then the matcher for position 7 looks like the predicate for position 4:

tile7Matches :: Tile -> Tile -> Bool
tile7Matches t4 t7 = bottom t4 `matches` top t7

This is, of course, because the tile in position 7 only has to consider the tile in position 4. Finally, not surprising, the two remaining predicates look like something we've already seen:

tile8Matches :: Tile -> Tile -> Tile -> Bool
tile8Matches t5 t7 t8 = bottom t5 `matches` top t8 && right t7 `matches` left t8
 
tile9Matches :: Tile -> Tile -> Tile -> Bool
tile9Matches t6 t8 t9 = bottom t6 `matches` top t9 && right t8 `matches` left t9

You may suggest that it'd be possible to reduce the number of predicates. After all, there's effectively only three different predicates: One that only looks at the tile to the left, one that only looks at the tile above, and one that looks both to the left and above.

Indeed, I could have boiled it down to just three functions:

matchesHorizontally :: Tile -> Tile -> Bool
matchesHorizontally x y = right x `matches` left y
 
matchesVertically :: Tile -> Tile -> Bool
matchesVertically x y = bottom x `matches` top y
 
matchesBoth :: Tile -> Tile -> Tile -> Bool
matchesBoth x y z = matchesVertically x z && matchesHorizontally y z

but I now run the risk of calling the wrong predicate from my implementation of the algorithm. As you'll see, I'll call each predicate by name at each appropriate step, but if I had only these three functions, there's a risk that I might mistakenly use matchesHorizontally when I should have used matchesVertically, or vice versa. Reducing eight one-liners to three one-liners doesn't really seem to warrant the risk.

Rotations #

In addition to examining whether a given tile fits in a given position, we also need to be able to rotate any tile:

rotateClockwise :: Tile -> Tile
rotateClockwise (Tile t r b l) = Tile l t r b
 
rotateCounterClockwise :: Tile -> Tile
rotateCounterClockwise (Tile t r b l) = Tile r b l t
 
upend :: Tile -> Tile
upend (Tile t r b l) = Tile b l t r

What is really needed, it turns out, is to enumerate all four rotations of a tile:

rotations :: Tile -> [Tile]
rotations t = [t, rotateClockwise t, upend t, rotateCounterClockwise t]

Since this, like everything else here, is a pure function, I experimented with defining a 'memoized tile' type that embedded all four rotations upon creation, so that the algorithm doesn't need to call the rotations function millions of times, but I couldn't measure any discernable performance improvement from it. There's no reason to make things more complicated than they need to be, so I didn't keep that change. (Since I do, however, use Git tactically i did, of course, stash the experiment.)

Permutations #

While I couldn't make things work by enumerating all 95 billion combinations, enumerating all 362,880 permutations of non-rotated tiles is well within the realm of the possible:

allPermutations :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
allPermutations =
  (\[t1, t2, t3, t4, t5, t6, t7, t8, t9] -> (t1, t2, t3, t4, t5, t6, t7, t8, t9))
  <$> permutations tiles

Doing this in GHCi on my old laptop takes 300 milliseconds, which is good enough compared to what comes next.

This list value uses permutations to enumerate all the permutations. You may already have noticed that it converts the result into a nine-tuple. The reason for that is that this enables the algorithm to pattern-match into specific positions without having to resort to the index operator, which is both partial and requires iteration of the list to reach the indexed element. Granted, the list is only nine elements long, and often the algorithm will only need to index to the fourth or fifth element. On the other hand, it's going to do it a lot. Perhaps it's a premature optimization, but if it is, it's at least one that makes the code more, rather than less, readable.

Algorithm #

I found it easiest to begin at the 'bottom' of what is effectively a recursive algorithm, even though I didn't implement it that way. At the 'bottom', I imagine that I'm almost done: That I've found eight tiles that match, and now I only need to examine if I can rotate the final tile so that it matches:

solve9th ::  (a, b, c, d, e, Tile, g, Tile, Tile)
         -> [(a, b, c, d, e, Tile, g, Tile, Tile)]
solve9th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile9Matches t6 t8) $ rotations t9
  return (t1, t2, t3, t4, t5, t6, t7, t8, match)

Recalling that Haskell functions compose from right to left, the function starts by enumerating the four rotations of the ninth and final tile t9. It then filters those four rotations by the tile9Matches predicate.

The match value is a rotation of t9 that matches t6 and t8. Whenever solve9th finds such a match, it returns the entire nine-tuple, because the assumption is that the eight first tiles are already valid.

Notice that the function uses do notation in the list monad, so it's quite possible that the first filter expression produces no match. In that case, the second line of code never runs, and instead, the function returns the empty list.

How do we find a tuple where the first eight elements are valid? Well, if we have seven valid tiles, we may consider the eighth and subsequently call solve9th:

solve8th ::  (a, b, c, d, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, c, d, Tile, Tile, Tile, Tile, Tile)]
solve8th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile8Matches t5 t7) $ rotations t8
  solve9th (t1, t2, t3, t4, t5, t6, t7, match, t9)

This function looks a lot like solve9th, but it instead enumerates the four rotations of the eighth tile t8 and filters with the tile8Matches predicate. Due to the do notation, it'll only call solve9th if it finds a match.

Once more, this function assumes that the first seven tiles are already in a legal constellation. How do we find seven valid tiles? The same way we find eight: By assuming that we have six valid tiles, and then finding the seventh, and so on:

solve7th ::  (a, b, c, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, c, Tile, Tile, Tile, Tile, Tile, Tile)]
solve7th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile7Matches t4) $ rotations t7
  solve8th (t1, t2, t3, t4, t5, t6, match, t8, t9)
 
solve6th ::  (a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve6th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile6Matches t3 t5) $ rotations t6
  solve7th (t1, t2, t3, t4, t5, match, t7, t8, t9)
 
solve5th ::  (a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve5th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile5Matches t2 t4) $ rotations t5
  solve6th (t1, t2, t3, t4, match, t6, t7, t8, t9)
 
solve4th ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve4th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile4Matches t1) $ rotations t4
  solve5th (t1, t2, t3, match, t5, t6, t7, t8, t9)
 
solve3rd ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve3rd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile3Matches t2) $ rotations t3
  solve4th (t1, t2, match, t4, t5, t6, t7, t8, t9)
 
solve2nd ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve2nd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile2Matches t1) $ rotations t2
  solve3rd (t1, match, t3, t4, t5, t6, t7, t8, t9)

You'll observe that solve7th down to solve2nd are very similar. The only things that really vary are the predicates, and the positions of the tile being examined, as well as its neighbours. Clearly I can generalize this code, but I'm not sure it's worth it. I wrote a few of these in the order I've presented them here, because it helped me think the problem through, and to be honest, once I had two or three of them, GitHub Copilot picked up on the pattern and wrote the remaining functions for me.

Granted, typing isn't a programming bottleneck, so we should rather ask if this kind of duplication looks like a maintenance problem. Given that this is a one-time exercise, I'll just leave it be and move on.

Particularly, if you're struggling to understand how this implements the 'truncated search tree', keep in mind that e..g solve5th is likely to produce no valid match, in which case it'll never call solve6th. The same may happen in solve6th, etc.

The 'top' function is a bit different because it doesn't need to filter anything:

solve1st ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve1st (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- rotations t1
  solve2nd (match, t2, t3, t4, t5, t6, t7, t8, t9)

In the first position, any tile in any rotation is legal, so solve1st only enumerates all four rotations of t1 and calls solve2nd for each.

The final step is to compose allPermutations with solve1st:

solutions :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solutions = allPermutations >>= solve1st

Running this in GHCi on my 4½-year old laptop produces all 16 solutions in approximately 22 seconds.

Evaluation #

Is that good performance? Well, it turns out that it's possible to substantially improve on the situation. As I've mentioned a couple of times, so far I've been running the program from GHCi, the Haskell REPL. Most of the 22 seconds are spent interpreting or compiling the code.

If I compile the code with some optimizations turned on, the executable runs in approximately 300 ms. That seems quite decent, if I may say so.

I can think of a few tweaks to the code that might conceivably improve things even more, but when I test, there's no discernable difference. Thus, I'll keep the code as shown here.

Here's one of the solutions:

The information on the box claims that there's two solutions. Why does the code shown here produce 16 solutions?

There's a good explanation for that. Recall that two of the tiles are identical. In the above solution picture, it's tile 1 and 3, although they're rotated 90° in relation to each other. This implies that you could take tile 1, rotate it counter-clockwise and put it in position 3, while simultaneously taking tile 3, rotating it clockwise, and putting it in position 1. Visually, you can't tell the difference, so they don't count as two distinct solutions. The algorithm, however, doesn't make that distinction, so it enumerates what is effectively the same solution twice.

Not surprising, it turns out that all 16 solutions are doublets in that way. We can confirm that by evaluating length $ nub solutions, which returns 8.

Eight solutions are, however, still four times more than two. Can you figure out what's going on?

The algorithm also enumerates four rotations of each solution. Once we take this into account, there's only two visually distinct solutions left. One of them is shown above. I also have a picture of the other one, but I'm not going to totally spoil things for you.

Conclusion #

When I was eight, I might have had the time and the patience to actually lay the puzzle. Despite the incredibly bad odds, I vaguely remember finally solving it. There must be some more holistic processing going on in the brain, if even a kid can solve the puzzle, because it seems inconceivable that it should be done as described here.

Today, I don't care for that kind of puzzle in analog form, but I did, on the other hand, find it an interesting programming exercise.

The code could be smaller, but I like it as it is. While a bit on the verbose side, I think that it communicates well what's going on.

I was pleasantly surprised that I managed to get execution time down to 300 ms. I'd honestly not expected that when I started.

This blog is totally free, but if you like it, please consider supporting it.

FSZipper in C#

2024-09-23T06:13:00+00:00

Another functional model of a file system, with code examples in C#.

This article is part of a series about Zippers. In this one, I port the FSZipper data structure from the Learn You a Haskell for Great Good! article Zippers.

A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there. Additionally, I'll make heavy use of certain standard constructs to port Haskell code, most notably Church encoding to model sum types in languages that don't natively have them. Such as C#. In some cases, I'll implement the Church encoding using the data structure's catamorphism. Since the cyclomatic complexity of the resulting code is quite low, you may be able to follow what's going on even if you don't know what Church encoding or catamorphisms are, but if you want to understand the background and motivation for that style of programming, you can consult the cited resources.

The code shown in this article is available on GitHub.

File system item initialization and structure #

If you haven't already noticed, Haskell (and other statically typed functional programming languages like F#) makes heavy use of sum types, and the FSZipper example is no exception. It starts with a one-liner to define a file system item, which may be either a file or a folder. In C# we must instead use a class:

public sealed class FSItem

Contrary to the two previous examples, the FSItem class has no generic type parameter. This is because I'm following the Haskell example code as closely as possible, but as I've previously shown, you can model a file hierarchy with a general-purpose rose tree.

Staying consistent with the two previous articles, I'll use Church encoding to model a sum type, and as discussed in the previous article I use a private implementation for that.

private readonly IFSItem imp;
 
private FSItem(IFSItem imp)
{
    this.imp = imp;
}
 
public static FSItem CreateFile(string name, string data)
{
    return new(new File(name, data));
}
 
public static FSItem CreateFolder(string name, IReadOnlyCollection<FSItem> items)
{
    return new(new Folder(name, items));
}

Two static creation methods enable client developers to create a single FSItem object, or an entire tree, like the example from the Haskell code, here ported to C#:

private static readonly FSItem myDisk =
    FSItem.CreateFolder("root",
    [
        FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
        FSItem.CreateFile("pope_time.avi", "god bless"),
        FSItem.CreateFolder("pics",
        [
            FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
            FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
            FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
        ]),
        FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
        FSItem.CreateFolder("programs",
        [
            FSItem.CreateFile("fartwizard.exe", "10gotofart"),
            FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
            FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
            FSItem.CreateFolder("source code",
            [
                FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                FSItem.CreateFile("random.hs", "main = print 4")
            ])
        ])
    ]);

Since the imp class field is just a private implementation detail, a client developer needs a way to query an FSItem object about its contents.

File system item catamorphism #

Just like the previous article, I'll start with the catamorphism. This is essentially the rose tree catamorphism, just less generic, since FSItem doesn't have a generic type parameter.

public TResult Aggregate<TResult>(
    Func<string, string, TResult> whenFile,
    Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
{
    return imp.Aggregate(whenFile, whenFolder);
}

The Aggregate method delegates to its internal implementation class field, which is defined as the private nested interface IFSItem:

private interface IFSItem
{
    TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder);
}

As discussed in the previous article, the interface is hidden away because it's only a vehicle for polymorphism. It's not intended for client developers to be used (although that would be benign) or implemented (which could break encapsulation). There are only, and should ever only be, two implementations. The one that represents a file is the simplest:

private sealed record File(string Name, string Data) : IFSItem
{
    public TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
    {
        return whenFile(Name, Data);
    }
}

The File record's Aggregate method unconditionally calls the supplied whenFile function argument with the Name and Data that was originally supplied via its constructor.

The Folder implementation is a bit trickier, mostly due to its recursive nature, but also because I wanted it to have structural equality.

private sealed class Folder : IFSItem
{
    private readonly string name;
    private readonly IReadOnlyCollection<FSItem> items;
 
    public Folder(string Name, IReadOnlyCollection<FSItem> Items)
    {
        name = Name;
        items = Items;
    }
 
    public TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
    {
        return whenFolder(
            name,
            items.Select(i => i.Aggregate(whenFile, whenFolder)).ToList());
    }
 
    public override bool Equals(object? obj)
    {
        return obj is Folder folder &&
               name == folder.name &&
               items.SequenceEqual(folder.items);
    }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(name, items);
    }
}

It, too, unconditionally calls one of the two functions passed to its Aggregate method, but this time whenFolder. It does that, however, by first recursively calling Aggregate within a Select expression. It needs to do that because the whenFolder function expects the subtree to have been already converted to values of the TResult return type. This is a common pattern with catamorphisms, and takes a bit of time getting used to. You can see similar examples in the articles Tree catamorphism, Rose tree catamorphism, Full binary tree catamorphism, as well as the previous one in this series.

I also had to make Folder a class rather than a record, because I wanted the type to have structural equality, and you can't override Equals on records (and if the base class library has any collection type with structural equality, I'm not aware of it).

File system item Church encoding #

True to the structure of the previous article, the catamorphism doesn't look quite like a Church encoding, but it's possible to define the latter from the former.

public TResult Match<TResult>(
    Func<string, string, TResult> whenFile,
    Func<string, IReadOnlyCollection<FSItem>, TResult> whenFolder)
{
    return Aggregate(
        whenFile: (name, data) =>
            (item: CreateFile(name, data), result: whenFile(name, data)),
        whenFolder: (name, pairs) =>
        {
            var items = pairs.Select(i => i.item).ToList();
            return (CreateFolder(name, items), whenFolder(name, items));
        }).result;
}

The trick is the same as in the previous article: Build up an intermediate tuple that contains both the current item as well as the result being accumulated. Once the Aggregate method returns, the Match method returns only the result part of the resulting tuple.

I implemented the whenFolder expression as a code block, because both tuple elements needed the items collection. You can inline the Select expression, but that would cause it to run twice. That's probably a premature optimization, but it also made the code a bit shorter, and, one may hope, a bit more readable.

Fily system breadcrumb #

Finally, things seem to be becoming a little easier. The port of FSCrumb is straightforward.

public sealed class FSCrumb
{
    public FSCrumb(
        string name,
        IReadOnlyCollection<FSItem> left,
        IReadOnlyCollection<FSItem> right)
    {
        Name = name;
        Left = left;
        Right = right;
    }
 
    public string Name { get; }
    public IReadOnlyCollection<FSItem> Left { get; }
    public IReadOnlyCollection<FSItem> Right { get; }
 
    public override bool Equals(object? obj)
    {
        return obj is FSCrumb crumb &&
               Name == crumb.Name &&
               Left.SequenceEqual(crumb.Left) &&
               Right.SequenceEqual(crumb.Right);
    }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(Name, Left, Right);
    }
}

The only reason this isn't a record is, once again, that I want to override Equals so that the type can have structural equality. Visual Studio wants me to convert to a primary constructor. That would simplify the code a bit, but actually not that much.

(I'm still somewhat conservative in my choice of new C# language features. Not that I have anything against primary constructors which, after all, F# has had forever. The reason I'm holding back is for didactic reasons. Not every reader is on the latest language version, and some readers may be using another programming language entirely. On the other hand, primary constructors seem natural and intuitive, so I may start using them here on the blog as well. I don't think that they're going to be much of a barrier to understanding.)

Now that we have both the data type we want to zip, as well as the breadcrumb type we need, we can proceed to add the Zipper.

File system Zipper #

The FSZipper C# class fills the position of the eponymous Haskell type alias. Data structure and initialization is straightforward.

public sealed class FSZipper
{
    private FSZipper(FSItem fSItem, IReadOnlyCollection<FSCrumb> breadcrumbs)
    {
        FSItem = fSItem;
        Breadcrumbs = breadcrumbs;
    }
 
    public FSZipper(FSItem fSItem) : this(fSItem, [])
    {
    }
 
    public FSItem FSItem { get; }
    public IReadOnlyCollection<FSCrumb> Breadcrumbs { get; }
 
    // Methods follow here...

True to the style I've already established, I've made the master constructor private in order to highlight that the Breadcrumbs are the responsibility of the FSZipper class itself. It's not something client code need worry about.

Going down #

The Haskell Zippers article introduces fsUp before fsTo, but if we want to see some example code, we need to navigate to somewhere before we can navigate up. Thus, I'll instead start with the function that navigates to a child node.

public FSZipper? GoTo(string name)
{
    return FSItem.Match(
        (_, _) => null,
        (folderName, items) =>
        {
            FSItem? item = null;
            var ls = new List<FSItem>();
            var rs = new List<FSItem>();
            foreach (var i in items)
            {
                if (item is null && i.IsNamed(name))
                    item = i;
                else if (item is null)
                    ls.Add(i);
                else
                    rs.Add(i);
            }
 
            if (item is null)
                return null;
 
            return new FSZipper(
                item,
                Breadcrumbs.Prepend(new FSCrumb(folderName, ls, rs)).ToList());
        });
}

This is by far the most complicated navigation we've seen so far, and I've even taken the liberty of writing an imperative implementation. It's not that I don't know how I could implement it in a purely functional fashion, but I've chosen this implementation for a couple of reasons. The first of which is that, frankly, it was easier this way.

This stems from the second reason: That the .NET base class library, as far as I know, offers no functionality like Haskell's break function. I could have written such a function myself, but felt that it was too much of a digression, even for me. Maybe I'll do that another day. It might make for a nice little exercise.

The third reason is that C# doesn't afford pattern matching on sequences, in the shape of destructuring the head and the tail of a list. (Not that I know of, anyway, but that language changes rapidly at the moment, and it does have some pattern-matching features now.) This means that I have to check item for null anyway.

In any case, while the implementation is imperative, an external caller can't tell. The GoTo method is still referentially transparent. Which means that it fits in your head.

You may have noticed that the implementation calls IsNamed, which is also new.

public bool IsNamed(string name)
{
    return Match((n, _) => n == name, (n, _) => n == name);
}

This is an instance method I added to FSItem.

In summary, the GoTo method enables client code to navigate down in the file hierarchy, as this unit test demonstrates:

[Fact]
public void GoToSkullMan()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.GoTo("skull_man(scary).bmp");
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFile("skull_man(scary).bmp", "Yikes!"),
        actual.FSItem);
}

The example is elementary. First go to the pics folder, and from there to the skull_man(scary).bmp.

Going up #

Going back up the hierarchy isn't as complicated.

public FSZipper? GoUp()
{
    if (Breadcrumbs.Count == 0)
        return null;
 
    var head = Breadcrumbs.First();
    var tail = Breadcrumbs.Skip(1);
 
    return new FSZipper(
        FSItem.CreateFolder(head.Name, [.. head.Left, FSItem, .. head.Right]),
        tail.ToList());
}

If the Breadcrumbs collection is empty, we're already at the root, in which case we can't go further up. In that case, the GoUp method returns null, as does the GoTo method if it can't find an item with the desired name. This possibility is explicitly indicated by the FSZipper? return type; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

If Breadcrumbs is not empty, it means that there's a place to go up to. It also implies that the previous operation navigated down, and the only way that's possible is if the previous node was a folder. Thus, the GoUp method knows that it needs to reconstitute a folder, and from the head breadcrumb, it knows that folder's name, and what was originally to the Left and Right of the Zipper's FSItem property.

This unit test demonstrates how client code may use the GoUp method:

[Fact]
public void GoUpFromSkullMan()
{
    var sut = new FSZipper(myDisk);
    // This is the same as the GoToSkullMan test
    var newFocus = sut.GoTo("pics")?.GoTo("skull_man(scary).bmp");
 
    var actual = newFocus?.GoUp()?.GoTo("watermelon_smash.gif");
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
        actual.FSItem);
}

This test first repeats the navigation also performed by the other test, then uses GoUp to go one level up, which finally enables it to navigate to the watermelon_smash.gif file.

Renaming a file or folder #

A Zipper enables you to navigate a data structure, but you can also use it to modify the element in focus. One option is to rename a file or folder.

public FSZipper Rename(string newName)
{
    return new FSZipper(
        FSItem.Match(
            (_, dat) => FSItem.CreateFile(newName, dat),
            (_, items) => FSItem.CreateFolder(newName, items)),
        Breadcrumbs);
}

The Rename method 'pattern-matches' on the 'current' FSItem and in both cases creates a new file or folder with the new name. Since it doesn't need the old name for anything, it uses the wildcard pattern to ignore that value. This operation is always possible, so the return type is FSZipper, without a question mark, indicating that the method never returns null.

The following unit test replicates the Haskell article's example by renaming the pics folder to cspi.

[Fact]
public void RenamePics()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.Rename("cspi").GoUp();
 
    Assert.NotNull(actual);
    Assert.Empty(actual.Breadcrumbs);
    Assert.Equal(
        FSItem.CreateFolder("root",
        [
            FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
            FSItem.CreateFile("pope_time.avi", "god bless"),
            FSItem.CreateFolder("cspi",
            [
                FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
                FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
                FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
            ]),
            FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
            FSItem.CreateFolder("programs",
            [
                FSItem.CreateFile("fartwizard.exe", "10gotofart"),
                FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
                FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
                FSItem.CreateFolder("source code",
                [
                    FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                    FSItem.CreateFile("random.hs", "main = print 4")
                ])
            ])
        ]),
        actual.FSItem);
}

Since the test uses GoUp after Rename, the actual value contains the entire tree, while the Breadcrumbs collection is empty.

Adding a new file #

Finally, we can add a new file to a folder.

public FSZipper? Add(FSItem item)
{
    return FSItem.Match<FSZipper?>(
        whenFile: (_, _) => null,
        whenFolder: (name, items) => new FSZipper(
            FSItem.CreateFolder(name, items.Prepend(item).ToList()),
            Breadcrumbs));
}

This operation may fail, since we can't add a file to a file. This is, again, clearly indicated by the return type, which allows null.

This implementation adds the file to the start of the folder, but it would also be possible to add it at the end. I would consider that slightly more idiomatic in C#, but here I've followed the Haskell example code, which conses the new item to the beginning of the list. As is idiomatic in Haskell.

The following unit test reproduces the Haskell article's example.

[Fact]
public void AddPic()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.Add(FSItem.CreateFile("heh.jpg", "lol"))?.GoUp();
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFolder("root",
        [
            FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
            FSItem.CreateFile("pope_time.avi", "god bless"),
            FSItem.CreateFolder("pics",
            [
                FSItem.CreateFile("heh.jpg", "lol"),
                FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
                FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
                FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
            ]),
            FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
            FSItem.CreateFolder("programs",
            [
                FSItem.CreateFile("fartwizard.exe", "10gotofart"),
                FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
                FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
                FSItem.CreateFolder("source code",
                [
                    FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                    FSItem.CreateFile("random.hs", "main = print 4")
                ])
            ])
        ]),
        actual.FSItem);
    Assert.Empty(actual.Breadcrumbs);
}

This example also follows the edit with a GoUp call, with the effect that the Zipper is once more focused on the entire tree. The assertion verifies that the new heh.jpg file is the first file in the pics folder.

Conclusion #

The code for FSZipper is actually a bit simpler than for the binary tree. This, I think, is mostly attributable to the FSZipper having fewer constituent sum types. While sum types are trivial, and extraordinarily useful in languages that natively support them, they require a lot of boilerplate in a language like C#.

Do you need something like FSZipper in C#? Probably not. As I've already discussed, this article series mostly exists as a programming exercise.

This blog is totally free, but if you like it, please consider supporting it.

Functor products

2024-09-16T06:08:00+00:00

A tuple or class of functors is also a functor. An article for object-oriented developers.

This article is part of a series of articles about functor relationships. In this one you'll learn about a universal composition of functors. In short, if you have a product type of functors, that data structure itself gives rise to a functor.

Together with other articles in this series, this result can help you answer questions such as: Does this data structure form a functor?

Since functors tend to be quite common, and since they're useful enough that many programming languages have special support or syntax for them, the ability to recognize a potential functor can be useful. Given a type like Foo<T> (C# syntax) or Bar<T1, T2>, being able to recognize it as a functor can come in handy. One scenario is if you yourself have just defined such a data type. Recognizing that it's a functor strongly suggests that you should give it a Select method in C#, a map function in F#, and so on.

Not all generic types give rise to a (covariant) functor. Some are rather contravariant functors, and some are invariant.

If, on the other hand, you have a data type which is a product of two or more (covariant) functors with the same type parameter, then the data type itself gives rise to a functor. You'll see some examples in this article.

Abstract shape #

Before we look at some examples found in other code, it helps if we know what we're looking for. Most (if not all?) languages support product types. In canonical form, they're just tuples of values, but in an object-oriented language like C#, such types are typically classes.

Imagine that you have two functors F and G, and you're now considering a data structure that contains a value of both types.

public sealed class FAndG<T>
{
    public FAndG(F<T> f, G<T> g)
    {
        F = f;
        G = g;
    }
 
    public F<T> F { get; }
    public G<T> G { get; }
 
    // Methods go here...

The name of the type is FAndG<T> because it contains both an F<T> object and a G<T> object.

Notice that it's an essential requirement that the individual functors (here F and G) are parametrized by the same type parameter (here T). If your data structure contains F<T1> and G<T2>, the following 'theorem' doesn't apply.

The point of this article is that such an FAndG<T> data structure forms a functor. The Select implementation is quite unsurprising:

public FAndG<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new FAndG<TResult>(F.Select(selector), G.Select(selector));
}

Since we've assumed that both F and G already are functors, they must come with some projection function. In C# it's idiomatically called Select, while in F# it'd typically be called map:

// ('a -> 'b) -> FAndG<'a> -> FAndG<'b>
let map f fandg = { F = F.map f fandg.F; G = G.map f fandg.G }

assuming a record type like

type FAndG<'a> = { F : F<'a>; G : G<'a> }

In both the C# Select example and the F# map function, the composed functor passes the function argument (selector or f) to both F and G and uses it to map both constituents. It then composes a new product from these individual results.

I'll have more to say about how this generalizes to a product of more than two functors, but first, let's consider some examples.

List Zipper #

One of the simplest example I can think of is a List Zipper, which in Haskell is nothing but a type alias of a tuple of lists:

type ListZipper a = ([a],[a])

In the article A List Zipper in C# you saw how the ListZipper<T> class composes two IEnumerable<T> objects.

private readonly IEnumerable<T> values;
public IEnumerable<T> Breadcrumbs { get; }
 
private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs)
{
    this.values = values;
    Breadcrumbs = breadcrumbs;
}

Since we already know that sequences like IEnumerable<T> form functors, we now know that so must ListZipper<T>. And indeed, the Select implementation looks similar to the above 'shape outline'.

public ListZipper<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new ListZipper<TResult>(values.Select(selector), Breadcrumbs.Select(selector));
}

It passes the selector function to the Select method of both values and Breadcrumbs, and composes the results into a new ListZipper<TResult>.

While this example is straightforward, it may not be the most compelling, because ListZipper<T> composes two identical functors: IEnumerable<T>. The knowledge that functors compose is more general than that.

Non-empty collection #

Next after the above List Zipper, the simplest example I can think of is a non-empty list. On this blog I originally introduced it in the article Semigroups accumulate, but here I'll use the variant from NonEmpty catamorphism. It composes a single value of the type T with an IReadOnlyCollection<T>.

public NonEmptyCollection(T head, params T[] tail)
{
    if (head == null)
        throw new ArgumentNullException(nameof(head));
 
    this.Head = head;
    this.Tail = tail;
}
 
public T Head { get; }
 
public IReadOnlyCollection<T> Tail { get; }

The Tail, being an IReadOnlyCollection<T>, easily forms a functor, since it's a kind of list. But what about Head, which is a 'naked' T value? Does that form a functor? If so, which one?

Indeed, a 'naked' T value is isomorphic to the Identity functor. This situation is an example of how knowing about the Identity functor is useful, even if you never actually write code that uses it. Once you realize that T is equivalent with a functor, you've now established that NonEmptyCollection<T> composes two functors. Therefore, it must itself form a functor, and you realize that you can give it a Select method.

public NonEmptyCollection<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new NonEmptyCollection<TResult>(selector(Head), Tail.Select(selector).ToArray());
}

Notice that even though we understand that T is equivalent to the Identity functor, there's no reason to actually wrap Head in an Identity<T> container just to call Select on it and unwrap the result. Rather, the above Select implementation directly invokes selector with Head. It is, after all, a function that takes a T value as input and returns a TResult object as output.

Ranges #

It's hard to come up with an example that's both somewhat compelling and realistic, and at the same time prototypically pure. Stripped of all 'noise' functor products are just tuples, but that hardly makes for a compelling example. On the other hand, most other examples I can think of combine results about functors where they compose in more than one way. Not only as products, but also as sums of functors, as well as nested compositions. You'll be able to read about these in future articles, but for the next examples, you'll have to accept some claims about functors at face value.

In Range as a functor you saw how both Endpoint<T> and Range<T> are functors. The article shows functor implementations for each, in both C#, F#, and Haskell. For now we'll ignore the deeper underlying reason why Endpoint<T> forms a functor, and instead focus on Range<T>.

In Haskell I never defined an explicit Range type, but rather just treated ranges as tuples. As stated repeatedly already, tuples are the essential products, so if you accept that Endpoint gives rise to a functor, then a 'range tuple' does, too.

In F# Range is defined like this:

type Range<'a> = { LowerBound : Endpoint<'a>; UpperBound : Endpoint<'a> }

Such a record type is also easily identified as a product type. In a sense, we can think of a record type as a 'tuple with metadata', where the metadata contains names of elements.

In C# Range<T> is a class with two Endpoint<T> fields.

private readonly Endpoint<T> min;
private readonly Endpoint<T> max;
 
public Range(Endpoint<T> min, Endpoint<T> max)
{
    this.min = min;
    this.max = max;
}

In a sense, you can think of such an immutable class as equivalent to a record type, only requiring substantial ceremony. The point is that because a range is a product of two functors, it itself gives rise to a functor. You can see all the implementations in Range as a functor.

Binary tree Zipper #

In A Binary Tree Zipper in C# you saw that the BinaryTreeZipper<T> class has two class fields:

public BinaryTree<T> Tree { get; }
public IEnumerable<Crumb<T>> Breadcrumbs { get; }

Both have the same generic type parameter T, so the question is whether BinaryTreeZipper<T> may form a functor? We now know that the answer is affirmative if BinaryTree<T> and IEnumerable<Crumb<T>> are both functors.

For now, believe me when I claim that this is the case. This means that you can add a Select method to the class:

public BinaryTreeZipper<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new BinaryTreeZipper<TResult>(
        Tree.Select(selector),
        Breadcrumbs.Select(c => c.Select(selector)));
}

By now, this should hardly be surprising: Call Select on each constituent functor and create a proper return value from the results.

Higher arities #

All examples have involved products of only two functors, but the result generalizes to higher arities. To gain an understanding of why, consider that it's always possible to rewrite tuples of higher arities as nested pairs. As an example, a triple like (42, "foo", True) can be rewritten as (42, ("foo", True)) without loss of information. The latter representation is a pair (a two-tuple) where the first element is 42, but the second element is another pair. These two representations are isomorphic, meaning that we can go back and forth without losing data.

By induction you can generalize this result to any arity. The point is that the only data type you need to describe a product is a pair.

Haskell's base library defines a specialized container called Product for this very purpose: If you have two Functor instances, you can Pair them up, and they become a single Functor.

Let's start with a Pair of Maybe and a list:

ghci> Pair (Just "foo") ["bar", "baz", "qux"]
Pair (Just "foo") ["bar","baz","qux"]

This is a single 'object', if you will, that composes those two Functor instances. This means that you can map over it:

ghci> elem 'b' <$> Pair (Just "foo") ["bar", "baz", "qux"]
Pair (Just False) [True,True,False]

Here I've used the infix <$> operator as an alternative to fmap. By composing with elem 'b', I'm asking every value inside the container whether or not it contains the character b. The Maybe value doesn't, while the first two list elements do.

If you want to compose three, rather than two, Functor instances, you just nest the Pairs, just like you can nest tuples:

ghci> elem 'b' <$> Pair (Identity "quux") (Pair (Just "foo") ["bar", "baz", "qux"])
Pair (Identity False) (Pair (Just False) [True,True,False])

This example now introduces the Identity container as a third Functor instance. I could have used any other Functor instance instead of Identity, but some of them are more awkward to create or display. For example, the Reader or State functors have no Show instances in Haskell, meaning that GHCi doesn't know how to print them as values. Other Functor instances didn't work as well for the example, since they tend to be more awkward to create. As an example, any non-trivial Tree requires substantial editor space to express.

Conclusion #

A product of functors may itself be made a functor. The examples shown in this article are all constrained to two functors, but if you have a product of three, four, or more functors, that product still gives rise to a functor.

This is useful to know, particularly if you're working in a language with only partial support for functors. Mainstream languages aren't going to automatically turn such products into functors, in the way that Haskell's Product container almost does. Thus, knowing when you can safely give your generic types a Select method or map function may come in handy.

There are more rules like this one. The next article examines another.

Next: Functor sums.

This blog is totally free, but if you like it, please consider supporting it.

A Binary Tree Zipper in C#

2024-09-09T06:09:00+00:00

A port of another Haskell example, still just because.

This article is part of a series about Zippers. In this one, I port the Zipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.

The code shown in this article is available on GitHub.

Binary tree initialization and structure #

In the Haskell code, the binary Tree type is a recursive sum type, defined on a single line of code. C#, on the other hand, has no built-in language construct that supports sum types, so a more elaborate solution is required. At least two options are available to us. One is to model a sum type as a Visitor. Another is to use Church encoding. In this article, I'll do the latter.

I find the type name (Tree) used in the Zippers article a bit too vague, and since I consider explicit better than implicit, I'll use a more precise class name:

public sealed class BinaryTree<T>

Even so, there are different kinds of binary trees. In a previous article I've shown a catamorphism for a full binary tree. This variation is not as strict, since it allows a node to have zero, one, or two children. Or, strictly speaking, a node always has exactly two children, but both, or one of them, may be empty. BinaryTree<T> uses Church encoding to distinguish between the two, but we'll return to that in a moment.

First, we'll examine how the class allows initialization:

private readonly IBinaryTree root;
 
private BinaryTree(IBinaryTree root)
{
    this.root = root;
}
 
public BinaryTree() : this(Empty.Instance)
{
}
 
public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right)
    : this(new Node(value, left.root, right.root))
{
}

The class uses a private root object to implement behaviour, and constructor chaining for initialization. The master constructor is private, since the IBinaryTree interface is private. The parameterless constructor implicitly indicates an empty node, whereas the other public constructor indicates a node with a value and two children. Yes, I know that I just wrote that explicit is better than implicit, but it turns out that with the target-typed new operator feature in C#, constructing trees in code becomes easier with this design choice:

BinaryTree<int> sut = new(
    42,
    new(),
    new(2, new(), new()));

As the variable name suggests, I've taken this code example from a unit test.

Private interface #

The class delegates method calls to the root field, which is an instance of the private, nested IBinaryTree interface:

private interface IBinaryTree
{
    TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode);
}

Why is IBinaryTree a private interface? Why does that interface even exist?

To be frank, I could have chosen another implementation strategy. Since there's only two mutually exclusive alternatives (node or empty), I could also have indicated which is which with a Boolean flag. You can see an example of that implementation tactic in the Table class in the sample code that accompanies Code That Fits in Your Head.

Using a Boolean flag, however, only works when there are exactly two choices. If you have three or more, things because more complicated. You could try to use an enum, but in most languages, these tend to be nothing but glorified integers, and are typically not type-safe. If you define a three-way enum, there's no guarantee that a value of that type takes only one of these three values, and a good compiler will typically insist that you check for any other value as well. The C# compiler certainly does.

Church encoding offers a better alternative, but since it makes use of polymorphism, the most idiomatic choice in C# is either an interface or a base class. Since I favour interfaces over base classes, that's what I've chosen here, but for the purposes of this little digression, it makes no difference: The following argument applies to base classes as well.

An interface (or base class) suggests to users of an API that they can implement it in order to extend behaviour. That's an impression I don't wish to give client developers. The purpose of the interface is exclusively to enable double dispatch to work. There's only two implementations of the IBinaryTree interface, and under no circumstances should there be more.

The interface is an implementation detail, which is why both it, and its implementations, are private.

Binary tree catamorphism #

The IBinaryTree interface defines a catamorphism for the BinaryTree<T> class. Since we may often view a catamorphism as a sort of 'generalized fold', and since these kinds of operations in C# are typically called Aggregate, that's what I've called the method.

An aggregate function affords a way to traverse a data structure and collect information into a single value, here of type TResult. The return type may, however, be a complex type, including another BinaryTree<T>. You'll see examples of complex return values later in this article.

As already discussed, there are exactly two implementations of IBinaryTree. The one representing an empty node is the simplest:

private sealed class Empty : IBinaryTree
{
    public readonly static Empty Instance = new();
 
    private Empty()
    {
    }
 
    public TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode)
    {
        return whenEmpty();
    }
}

The Aggregate implementation unconditionally calls the supplied whenEmpty function, which returns some TResult value unknown to the Empty class.

Although not strictly necessary, I've made the class a Singleton. Since I like to take advantage of structural equality to write better tests, it was either that, or overriding Equals and GetHashCode.

The other implementation gets around that problem by being a record:

private sealed record Node(T Value, IBinaryTree Left, IBinaryTree Right) : IBinaryTree
{
    public TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode)
    {
        return whenNode(
            Value,
            Left.Aggregate(whenEmpty, whenNode),
            Right.Aggregate(whenEmpty, whenNode));
    }
}

It, too, unconditionally calls one of the two functions passed to its Aggregate method, but this time whenNode. It does that, however, by first recursively calling Aggregate on both Left and Right. It needs to do that because the whenNode function expects the subtrees to have been already converted to values of the TResult return type. This is a common pattern with catamorphisms, and takes a bit of time getting used to. You can see similar examples in the articles Tree catamorphism, Rose tree catamorphism, and Full binary tree catamorphism.

The BinaryTree<T> class defines a public Aggregate method that delegates to its root field:

public TResult Aggregate<TResult>(
    Func<TResult> whenEmpty,
    Func<T, TResult, TResult, TResult> whenNode)
{
    return root.Aggregate(whenEmpty, whenNode);
}

The astute reader may now remark that the Aggregate method doesn't look like a Church encoding.

Binary tree Church encoding #

A Church encoding will typically have a Match method that enables client code to match on all the alternative cases in the sum type, without those confusing already-converted TResult values. It turns out that you can implement the desired Match method with the Aggregate method.

One of the advantages of doing meaningless coding exercises like this one is that you can pursue various ideas that interest you. One idea that interests me is the potential universality of catamorphisms. I conjecture that a catamorphism is an algebraic data type's universal API, and that you can implement all other methods or functions with it. I admit that I haven't done much research in the form of perusing existing literature, but at least it seems to be the case conspicuously often.

As it is here.

public TResult Match<TResult>(
    Func<TResult> whenEmpty,
    Func<T, BinaryTree<T>, BinaryTree<T>, TResult> whenNode)
{
    return root
        .Aggregate(
            () => (tree: new BinaryTree<T>(), result: whenEmpty()),
            (x, l, r) => (
                new BinaryTree<T>(x, l.tree, r.tree),
                whenNode(x, l.tree, r.tree)))
        .result;
}

Now, I readily admit that it took me a couple of hours tossing and turning in my bed before this solution came to me. I don't find it intuitive at all, but it works.

The Aggregate method requires that the whenNode function's left and right values are of the same TResult type as the return type. How do we consolidate that requirement with the Match method's variation, where its whenNode function requires the left and right values to be BinaryTree<T> values, but the return type still TResult?

The way out of this conundrum, it turns out, is to combine both in a tuple. Thus, when Match calls Aggregate, the implied TResult type is not the TResult visible in the Match method declaration. Rather, it's inferred to be of the type (BinaryTree<T>, TResult). That is, a tuple where the first element is a BinaryTree<T> value, and the second element is a TResult value. The C# compiler's type inference engine then figures out that (BinaryTree<T>, TResult) must also be the return type of the Aggregate method call.

That's not what Match should return, but the second tuple element contains a value of the correct type, so it returns that. Since I've given the tuple elements names, the Match implementation accomplishes that by returning the result tuple field.

Breadcrumbs #

That's just the tree that we want to zip. So far, we can only move from root to branches, but not the other way. Before we can define a Zipper for the tree, we need a data structure to store breadcrumbs (the navigation log, if you will).

In Haskell it's just another one-liner, but in C# this requires another full-fledged class:

public sealed class Crumb<T>

It's another sum type, so once more, I make the constructor private and use a private class field for the implementation:

private readonly ICrumb imp;
 
private Crumb(ICrumb imp)
{
    this.imp = imp;
}
 
internal static Crumb<T> Left(T value, BinaryTree<T> right)
{
    return new(new LeftCrumb(value, right));
}
 
internal static Crumb<T> Right(T value, BinaryTree<T> left)
{
    return new(new RightCrumb(value, left));
}

To stay consistent throughout the code base, I also use Church encoding to distinguish between a Left and Right breadcrumb, and the technique is similar. First, define a private interface:

private interface ICrumb
{
    TResult Match<TResult>(
        Func<T, BinaryTree<T>, TResult> whenLeft,
        Func<T, BinaryTree<T>, TResult> whenRight);
}

Then, use private nested types to implement the interface.

private sealed record LeftCrumb(T Value, BinaryTree<T> Right) : ICrumb
{
    public TResult Match<TResult>(
        Func<T, BinaryTree<T>, TResult> whenLeft,
        Func<T, BinaryTree<T>, TResult> whenRight)
    {
        return whenLeft(Value, Right);
    }
}

The RightCrumb record is essentially just the 'mirror image' of the LeftCrumb record, and just as was the case with BinaryTree<T>, the Crumb<T> class exposes an externally accessible Match method that just delegates to the private class field:

public TResult Match<TResult>(
    Func<T, BinaryTree<T>, TResult> whenLeft,
    Func<T, BinaryTree<T>, TResult> whenRight)
{
    return imp.Match(whenLeft, whenRight);
}

Finally, all the building blocks are ready for the actual Zipper.

Zipper data structure and initialization #

In the Haskell code, the Zipper is another one-liner, and really just a type alias. In C#, once more, we're going to need a full class.

public sealed class BinaryTreeZipper<T>

The Haskell article simply calls this type alias Zipper, but I find that name too general, since there's more than one kind of Zipper. I think I understand that the article chooses that name for didactic reasons, but here I've chosen a more consistent disambiguation scheme, so I've named the class BinaryTreeZipper<T>.

The Haskell example is just a type alias for a tuple, and the C# class is similar, although with significantly more ceremony:

public BinaryTree<T> Tree { get; }
public IEnumerable<Crumb<T>> Breadcrumbs { get; }
 
private BinaryTreeZipper(
    BinaryTree<T> tree,
    IEnumerable<Crumb<T>> breadcrumbs)
{
    Tree = tree;
    Breadcrumbs = breadcrumbs;
}
 
public BinaryTreeZipper(BinaryTree<T> tree) : this(tree, [])
{
}

I've here chosen to add an extra bit of encapsulation by making the master constructor private. This prevents client code from creating an arbitrary object with breadcrumbs without having navigated through the tree. To be honest, I don't think it violates any contract even if we allow this, but it at least highlights that the Breadcrumbs role is to keep a log of what previously happened to the object.

Navigation #

We can now reproduce the navigation functions from the Haskell article.

public BinaryTreeZipper<T>? GoLeft()
{
    return Tree.Match<BinaryTreeZipper<T>?>(
        whenEmpty: () => null,
        whenNode: (x, l, r) => new BinaryTreeZipper<T>(
            l,
            Breadcrumbs.Prepend(Crumb.Left(x, r))));
}

Going left 'pattern-matches' on the Tree and, if not empty, constructs a new BinaryTreeZipper object with the left tree, and a Left breadcrumb that stores the 'current' node value and the right subtree. If the 'current' node is empty, on the other hand, the method returns null. This possibility is explicitly indicated by the BinaryTreeZipper<T>? return type; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

The GoRight method is similar to GoLeft.

We may also attempt to navigate up in the tree, undoing our last downward move:

public BinaryTreeZipper<T>? GoUp()
{
    if (!Breadcrumbs.Any())
        return null;
    var head = Breadcrumbs.First();
 
    var tail = Breadcrumbs.Skip(1);
    return head.Match(
        whenLeft: (x, r) => new BinaryTreeZipper<T>(
            new BinaryTree<T>(x, Tree, r),
            tail),
        whenRight: (x, l) => new BinaryTreeZipper<T>(
            new BinaryTree<T>(x, l, Tree),
            tail));
}

This is another operation that may fail. If we're already at the root of the tree, there are no Breadcrumbs, in which case the only option is to return a value indicating that the operation failed; here, null, but in other languages perhaps None or Nothing.

If, on the other hand, there's at least one breadcrumb, the GoUp method uses the most recent one (head) to construct a new BinaryTreeZipper<T> object that reconstitutes the opposite (sibling) subtree and the parent node. It does that by 'pattern-matching' on the head breadcrumb, which enables it to distinguish a left breadcrumb from a right breadcrumb.

Finally, we may keep trying to GoUp until we reach the root:

public BinaryTreeZipper<T> TopMost()
{
    return GoUp()?.TopMost() ?? this;
}

You'll see an example of that a little later.

Modifications #

Continuing the port of the Haskell code, we can Modify the current node with a function:

public BinaryTreeZipper<T> Modify(Func<T, T> f)
{
    return new BinaryTreeZipper<T>(
        Tree.Match(
            whenEmpty: () => new BinaryTree<T>(),
            whenNode: (x, l, r) => new BinaryTree<T>(f(x), l, r)),
        Breadcrumbs);
}

This operation always succeeds, since it chooses to ignore the change if the tree is empty. Thus, there's no question mark on the return type, indicating that the method never returns null.

Finally, we may replace a node with a new subtree:

public BinaryTreeZipper<T> Attach(BinaryTree<T> tree)
{
    return new BinaryTreeZipper<T>(tree, Breadcrumbs);
}

The following unit test demonstrates a combination of several of the methods shown above:

[Fact]
public void AttachAndGoTopMost()
{
    var sut = new BinaryTreeZipper<char>(freeTree);

    var farLeft = sut.GoLeft()?.GoLeft()?.GoLeft()?.GoLeft();
    var actual = farLeft?.Attach(new('Z', new(), new())).TopMost();
 
    Assert.NotNull(actual);
    Assert.Equal(
        new('P',
            new('O',
                new('L',
                    new('N',
                        new('Z', new(), new()),
                        new()),
                    new('T', new(), new())),
                new('Y',
                    new('S', new(), new()),
                    new('A', new(), new()))),
            new('L',
                new('W',
                    new('C', new(), new()),
                    new('R', new(), new())),
                new('A',
                    new('A', new(), new()),
                    new('C', new(), new())))),
        actual.Tree);
    Assert.Empty(actual.Breadcrumbs);
}

The test starts with freeTree (not shown) and first navigates to the leftmost empty node. Here it uses Attach to add a new 'singleton' subtree with the value 'Z'. Finally, it uses TopMost to return to the root node.

In the Assert phase, the test verifies that the actual object contains the expected values.

Conclusion #

The Tree Zipper shown here is a port of the example given in the Haskell Zippers article. As I've already discussed in the introduction article, this data structure doesn't make much sense in C#, where you can easily implement a navigable tree with two-way links. Even if this requires state mutation, you can package such a data structure in a proper object with good encapsulation, so that operations don't leave any dangling pointers or the like.

As far as I can tell, the code shown in this article isn't useful in production code, but I hope that, at least, you still learned something from it. I always learn a new thing or two from doing programming exercises and writing about them, and this was no exception.

In the next article, I continue with the final of the Haskell article's three examples.

Next: FSZipper in C#.

This blog is totally free, but if you like it, please consider supporting it.

Keeping cross-cutting concerns out of application code

2024-09-02T06:19:00+00:00

Don't inject third-party dependencies. Use Decorators.

I recently came across a Stack Overflow question that reminded me of a topic I've been meaning to write about for a long time: Cross-cutting concerns.

When it comes to the usual suspects, logging, fault tolerance, caching, the best solution is usually to apply the Decorator pattern.

I often see code that uses Dependency Injection (DI) to inject, say, a logging interface into application code. You can see an example of that in Repeatable execution, as well as a suggestion for a better design. Not surprisingly, the better design involves logging Decorators.

The Stack Overflow question isn't about logging, but rather about fault tolerance; Circuit Breaker, retry policies, timeouts, etc.

Injected concern #

The question does a good job of presenting a minimal, reproducible example. At the outset, the code looks like this:

public class MyApi
{
    private readonly ResiliencePipeline pipeline;
    private readonly IOrganizationService service;
 
    public MyApi(ResiliencePipelineProvider<string> provider, IOrganizationService service)
    {
        this.pipeline = provider.GetPipeline("retry-pipeline");
        this.service = service;
    }
 
    public List<string> GetSomething(QueryByAttribute query)
    {
        var result = this.pipeline.Execute(() => service.RetrieveMultiple(query));
        return result.Entities.Cast<string>().ToList();
    }
}

The Stack Overflow question asks how to test this implementation, but I'd rather take the example as an opportunity to discuss design alternatives. Not surprisingly, it turns out that with a more decoupled design, testing becomes easier, too.

Before we proceed, a few words about this example code. I assume that this isn't Andy Cooke's actual production code. Rather, I interpret it as a reduced example that highlights the actual question. This is important because you might ask: Why bother testing two lines of code?

Indeed, as presented, the GetSomething method is so simple that you may consider not testing it. Thus, I interpret the second line of code as a stand-in for more complicated production code. Hold on to that thought, because once I'm done, that's all that's going to be left, and you may then think that it's so simple that it really doesn't warrant all this hoo-ha.

Coupling #

As shown, the MyApi class is coupled to Polly, because ResiliencePipeline is defined by that library. To be clear, all I've heard is that Polly is a fine library. I've used it for a few projects myself, but I also admit that I haven't that much experience with it. I'd probably use it again the next time I need a Circuit Breaker or similar, so the following discussion isn't a denouncement of Polly. Rather, it applies to all third-party dependencies, or perhaps even dependencies that are part of your language's base library.

Coupling is a major cause of spaghetti code and code rot in general. To write sustainable code, you should be cognizant of coupling. The most decoupled code is code that you can easily delete.

This doesn't mean that you shouldn't use high-quality third-party libraries like Polly. Among myriads of software engineering heuristics, we know that we should be aware of the not-invented-here syndrome.

When it comes to classic cross-cutting concerns, the Decorator pattern is usually a better design than injecting the concern into application code. The above example clearly looks innocuous, but imagine injecting both a ResiliencePipeline, a logger, and perhaps a caching service, and your real application code eventually disappears in 'infrastructure code'.

It's not that we don't want to have these third-party dependencies, but rather that we want to move them somewhere else.

Resilient Decorator #

The concern in the above example is the desire to make the IOrganizationService dependency more resilient. The MyApi class only becomes more resilient as a transitive effect. The first refactoring step, then, is to introduce a resilient Decorator.

public sealed class ResilientOrganizationService(
    ResiliencePipeline pipeline,
    IOrganizationService inner) : IOrganizationService
{
    public QueryResult RetrieveMultiple(QueryByAttribute query)
    {
        return pipeline.Execute(() => inner.RetrieveMultiple(query));
    }
}

As Decorators must, this class composes another IOrganizationService while also implementing that interface itself. It does so by being an Adapter over the Polly API.

I've applied Nikola Malovic's 4th law of DI:

"Every constructor of a class being resolved should not have any implementation other then accepting a set of its own dependencies."

Inversion Of Control, Single Responsibility Principle and Nikola’s laws of dependency injection, Nikola Malovic, 2009

Instead of injecting a ResiliencePipelineProvider<string> only to call GetPipeline on it, it just receives a ResiliencePipeline and saves the object for use in the RetrieveMultiple method. It does that via a primary constructor, which is a recent C# language addition. It's just syntactic sugar for Constructor Injection, and as usual F# developers should feel right at home.

Simplifying MyApi #

Now that you have a resilient version of IOrganizationService you don't need to have any Polly code in MyApi. Remove it and simplify:

public class MyApi
{
    private readonly IOrganizationService service;
 
    public MyApi(IOrganizationService service)
    {
        this.service = service;
    }
 
    public List<string> GetSomething(QueryByAttribute query)
    {
        var result = service.RetrieveMultiple(query);
        return result.Entities.Cast<string>().ToList();
    }
}

As promised, there's almost nothing left of it now, but I'll remind you that I consider the second line of GetSomething as a stand-in for something more complicated that you might need to test. As it is now, though, testing it is trivial:

[Theory]
[InlineData("foo", "bar", "baz")]
[InlineData("qux", "quux", "corge")]
[InlineData("grault", "garply", "waldo")]
public void GetSomething(params string[] expected)
{
    var service = new Mock<IOrganizationService>();
    service
        .Setup(s => s.RetrieveMultiple(new QueryByAttribute()))
        .Returns(new QueryResult(expected));
    var sut = new MyApi(service.Object);
 
    var actual = sut.GetSomething(new QueryByAttribute());
 
    Assert.Equal(expected, actual);
}

The larger point, however, is that not only have you now managed to keep third-party dependencies out of your application code, you've also simplified it and made it easier to test.

Composition #

You can still create a resilient MyApi object in your Composition Root:

var service = new ResilientOrganizationService(pipeline, inner);
var myApi = new MyApi(service);

Decomposing the problem in this way, you decouple your application code from third-party dependencies. You can define ResilientOrganizationService in the application's Composition Root, which also keeps the Polly dependency there. Even so, you can implement MyApi as part of your application layer.

I usually illustrate Ports and Adapters, or, if you will, Clean Architecture as concentric circles, but in this diagram I've skewed the circles to make space for the boxes. In other words, the diagram is 'not to scale'. Ideally, the outermost layer is much smaller and thinner than any of the the other layers. I've also included an inner green layer which indicates the architecture's Domain Model, but since I assume that MyApi is part of some application layer, I've left the Domain Model empty.

Reasons to decouple #

Why is it important to decouple application code from Polly? First, keep in mind that in this discussion Polly is just a stand-in for any third-party dependency. It's up to you as a software architect to decide how you'll structure your code, but third-party dependencies are one of the first things I look for. A third-party component changes with time, and often independently of your base platform. You may have to deal with breaking changes or security patches at inopportune times. The organization that maintains the component may cease to operate. This happens to commercial entities and open-source contributors alike, although for different reasons.

Second, even a top-tier library like Polly will undergo changes. If your time horizon is five to ten years, you'll be surprised how much things change. You may protest that no-one designs software systems with such a long view, but I think that if you ask the business people involved with your software, they most certainly expect your system to last a long time.

I believe that I heard on a podcast that some Microsoft teams had taken a dependency on Polly. Assuming, for the sake of argument, that this is true, while we may not wish to depend on some random open-source component, depending on Polly is safe, right? In the long run, it isn't. Five years ago, you had the same situation with Json.NET, but then Microsoft hired James Newton-King and had him make a JSON API as part of the .NET base library. While Json.NET isn't dead by any means, now you have two competing JSON libraries, and Microsoft uses their own in the frameworks and libraries that they release.

Deciding to decouple your application code from a third-party component is ultimately a question of risk management. It's up to you to make the bet. Do you pay the up-front cost of decoupling, or do you postpone it, hoping it'll never be necessary?

I usually do the former, because the cost is low, and there are other benefits as well. As I've already touched on, unit testing becomes easier.

Configuration #

Since Polly only lives in the Composition Root, you'll also need to define the ResiliencePipeline there. You can write the code that creates that pieline wherever you like, but it might be natural to make it a creation function on the ResilientOrganizationService class:

public static ResiliencePipeline CreatePipeline()
{
    return new ResiliencePipelineBuilder()
        .AddRetry(new RetryStrategyOptions
        {
            MaxRetryAttempts = 4
        })
        .AddTimeout(TimeSpan.FromSeconds(1))
        .Build();
}

That's just an example, and perhaps not what you'd like to do. Perhaps you rather want some of these values to be defined in a configuration file. Thus, this isn't what you have to do, but rather what you could do.

If you use this option, however, you could take the return value of this method and inject it into the ResilientOrganizationService constructor.

Conclusion #

Cross-cutting concerns, like caching, logging, security, or, in this case, fault tolerance, are usually best addressed with the Decorator pattern. In this article, you saw an example of using the Decorator pattern to decouple the concern of fault tolerance from the consumer of the service that you need to handle in a fault-tolerant manner.

The specific example dealt with the Polly library, but the point isn't that Polly is a particularly nasty third-party component that you need to protect yourself against. Rather, it just so happened that I came across a Stack Overflow question that used Polly, and I though it was a a nice example.

As far as I can tell, Polly is actually one of the top .NET open-source packages, so this article is not a denouncement of Polly. It's just a sketch of how to move useful dependencies around in your code base to make sure that they impact your application code as little as possible.

This blog is totally free, but if you like it, please consider supporting it.

A List Zipper in C#

2024-08-26T13:19:00+00:00

A port of a Haskell example, just because.

This article is part of a series about Zippers. In this one, I port the ListZipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.

A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there.

The code shown in this article is available on GitHub.

Initialization and structure #

In the Haskell code, ListZipper is just a type alias, but C# doesn't have that, so instead, we'll have to introduce a class.

public sealed class ListZipper<T> : IEnumerable<T>

Since it implements IEnumerable<T>, it may be used like any other sequence, but it also comes with some special operations that enable client code to move forward and backward, as well as inserting and removing values.

The class has the following fields, properties, and constructors:

private readonly IEnumerable<T> values;
public IEnumerable<T> Breadcrumbs { get; }
 
private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs)
{
    this.values = values;
    Breadcrumbs = breadcrumbs;
}
 
public ListZipper(IEnumerable<T> values) : this(values, [])
{
}
 
public ListZipper(params T[] values) : this(values.AsEnumerable())
{
}

It uses constructor chaining to initialize a ListZipper object with proper encapsulation. Notice that the master constructor is private. This prevents client code from initializing an object with arbitrary Breadcrumbs. Rather, the Breadcrumbs (the log, if you will) is going to be the result of various operations performed by client code, and only the ListZipper class itself can use this constructor.

You may consider the constructor that takes a single IEnumerable<T> as the 'main' public constructor, and the other one as a convenience that enables a client developer to write code like new ListZipper<string>("foo", "bar", "baz").

The class' IEnumerable<T> implementation only enumerates the values:

public IEnumerator<T> GetEnumerator()
{
    return values.GetEnumerator();
}

In other words, when enumerating a ListZipper, you only get the 'forward' values. Client code may still examine the Breadcrumbs, since this is a public property, but it should have little need for that.

(I admit that making Breadcrumbs public is a concession to testability, since it enabled me to write assertions against this property. It's a form of structural inspection, which is a technique that I use much less than I did a decade ago. Still, in this case, while you may argue that it violates information hiding, it at least doesn't allow client code to put an object in an invalid state. Had the ListZipper class been a part of a reusable library, I would probably have hidden that data, too, but since this is exercise code, I found this an acceptable compromise. Notice, too, that in the original Haskell code, the breadcrumbs are available to client code.)

Regular readers of this blog may be aware that I usually favour IReadOnlyCollection<T> over IEnumerable<T>. Here, on the other hand, I've allowed values to be any IEnumerable<T>, which includes infinite sequences. I decided to do that because Haskell lists, too, may be infinite, and as far as I can tell, ListZipper actually does work with infinite sequences. I have, at least, written a few tests with infinite sequences, and they pass. (I may still have missed an edge case or two. I can't rule that out.)

Movement #

It's not much fun just being able to initialize an object. You also want to be able to do something with it, such as moving forward:

public ListZipper<T>? GoForward()
{
    var head = values.Take(1);
    if (!head.Any())
        return null;
 
    var tail = values.Skip(1);
    return new ListZipper<T>(tail, head.Concat(Breadcrumbs));
}

You can move forward through any IEnumerable, so why make things so complicated? The benefit of this GoForward method (function, really) is that it records where it came from, which means that moving backwards becomes an option:

public ListZipper<T>? GoBack()
{
    var head = Breadcrumbs.Take(1);
    if (!head.Any())
        return null;
 
    var tail = Breadcrumbs.Skip(1);
    return new ListZipper<T>(head.Concat(values), tail);
}

This test may serve as an example of client code that makes use of those two operations:

[Fact]
public void GoBack1()
{
    var sut = new ListZipper<int>(1, 2, 3, 4);
 
    var actual = sut.GoForward()?.GoForward()?.GoForward()?.GoBack();
 
    Assert.Equal([3, 4], actual);
    Assert.Equal([2, 1], actual?.Breadcrumbs);
}

Going forward takes the first element off values and adds it to the front of Breadcrumbs. Going backwards is nearly symmetrical: It takes the first element off the Breadcrumbs and adds it back to the front of the values. Used in this way, Breadcrumbs works as a stack.

Notice that both GoForward and GoBack admit the possibility of failure. If values is empty, you can't go forward. If Breadcrumbs is empty, you can't go back. In both cases, the functions return null, which are also indicated by the ListZipper<T>? return types; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

To be clear, the Zippers article does discuss handling failures using Maybe, but only applies it to its binary tree example. Thus, the error handling shown here is my own addition.

Modifications #

In addition to moving back and forth in the list, we can also modify it. The following operations are also not in the Zippers article, but are rather my own contributions. Adding a new element is easy:

public ListZipper<T> Insert(T value)
{
    return new ListZipper<T>(values.Prepend(value), Breadcrumbs);
}

Notice that this operation is always possible. Even if the list is empty, we can Insert a value. In that case, it just becomes the list's first and only element.

A simple test demonstrates usage:

[Fact]
public void InsertAtFocus()
{
    var sut = new ListZipper<string>("foo", "bar");
 
    var actual = sut.GoForward()?.Insert("ploeh").GoBack();
 
    Assert.NotNull(actual);
    Assert.Equal(["foo", "ploeh", "bar"], actual);
    Assert.Empty(actual.Breadcrumbs);
}

Likewise, we may attempt to remove an element from the list:

public ListZipper<T>? Remove()
{
    if (!values.Any())
        return null;
 
    return new ListZipper<T>(values.Skip(1), Breadcrumbs);
}

Contrary to Insert, the Remove operation will fail if values is empty. Notice that this doesn't necessarily imply that the list as such is empty, but only that the focus is at the end of the list (which, of course, never happens if values is infinite):

[Fact]
public void RemoveAtEnd()
{
    var sut = new ListZipper<string>("foo", "bar").GoForward()?.GoForward();
 
    var actual = sut?.Remove();
 
    Assert.Null(actual);
    Assert.NotNull(sut);
    Assert.Empty(sut);
    Assert.Equal(["bar", "foo"], sut.Breadcrumbs);
}

In this example, the focus is at the end of the list, so there's nothing to remove. The list, however, is not empty, but all the data currently reside in the Breadcrumbs.

Finally, we can combine insertion and removal to implement a replacement operation:

public ListZipper<T>? Replace(T newValue)
{
    return Remove()?.Insert(newValue);
}

As the name implies, this operation replaces the value currently in focus with a completely different value. Here's an example:

[Fact]
public void ReplaceAtFocus()
{
    var sut = new ListZipper<string>("foo", "bar", "baz");
 
    var actual = sut.GoForward()?.Replace("qux")?.GoBack();
 
    Assert.NotNull(actual);
    Assert.Equal(["foo", "qux", "baz"], actual);
    Assert.Empty(actual.Breadcrumbs);
}

Once more, this may fail if the current focus is empty, so Replace also returns a nullable value.

Conclusion #

For a C# developer, the ListZipper<T> class looks odd. Why would you ever want to use this data structure? Why not just use List<T>?

As I hope I've made clear in the introduction article, I can't, indeed, think of a good reason.

I've gone through this exercise to hone my skills, and to prepare myself for the more intimidating exercise it is to implement a binary tree Zipper.

Next: A Binary Tree Zipper in C#.

This blog is totally free, but if you like it, please consider supporting it.

Zippers

2024-08-19T14:13:00+00:00

Some functional programming examples ported to C#, just because.

Many algorithms rely on data structures that enable the implementation to move in more than one way. A simple example is a doubly-linked list, where an algorithm can move both forward and backward from a given element. Other examples are various tree-based algorithms, such as red-black trees where certain operations trigger reorganization of the tree. Yet other data structures, such as Fibonacci heaps, combine doubly-linked lists with trees that allow navigation in more than one direction.

In an imperative programming language, you can easily implement such data structures, as long as the language allows data mutation. Here's a simple example:

var node1 = new Node<string>("foo");
var node2 = new Node<string>("bar") { Previous = node1 };
node1.Next = node2;

It's possible to double-link node1 to node2 by first creating node1. At that point, node2 still doesn't exist, so you can't yet assign node1.Next, but once you've initialized node2, you can mutate the state of node1 by changing its Next property.

When data structures are immutable (as they must be in functional programming) this is no longer possible. How may you get around that limitation?

Alternatives #

Some languages get around this problem in various ways. Haskell, because of its lazy evaluation, enables a technique called tying the knot that, frankly, makes my head hurt.

Even though I write a decent amount of Haskell code, that's not something that I make use of. Usually, it turns out, you can solve most problems by thinking about them differently. By choosing another perspective, and another data structure, you can often arrive at a good, functional solution to your problem.

One family of general-purpose data structures are called Zippers. The general idea is that the data structure has a natural 'focus' (e.g. the head of a list), but it also keeps a record of 'breadcrumbs', that is, where the caller has previously been. This enables client code to 'go back' or 'go up', if the natural direction is to 'go forward' or 'go down'. It's a bit like Event Sourcing, in that every operation leaves a log entry that can later be used to reconstruct what happened. Repeatable Execution also comes to mind, although it's not quite the same.

For an introduction to Zippers, I recommend the excellent and highly readable article Zippers. In this article series, I'm going to assume that you're familiar with the contents of that article.

C# ports #

While I may add more articles to this series in the future, as I'm writing this, I have nothing more planned than writing about how it's possible to implement the article's three Zippers in C#.

Why would you want to do this?

To be honest, for production code, I can't think of a good reason. I did it for a few reasons, most of them didactic. Additionally, writing code for exercise helps you improve. If you know enough Haskell to understand what's going on in the Zippers article, you may consider porting some of it to your favourite language, as an exercise.

It may help you grokking functional programming.

That's really it, though. There's no reason to use Zippers in a language like C#, which idiomatically makes use of mutation. If you want a doubly-linked list, you can just write code as shown in the beginning of this article.

If you're interested in an F# perspective on Zippers, Tomas Petricek has a cool article: Processing trees with F# zipper computation.

Conclusion #

Zippers constitute a family of data structures that enables you to move in multiple directions. Left and right in a list. Up or down in a tree. For an imperative programmer, that's literally just another day at the office, but in disciplined functional programming, making cyclic graphs can be surprisingly tricky.

Even in functional programming, I rarely reach for a Zipper, since I can often find a library with a higher level of abstraction that does what I need it to do. Still, learning of new ways to solve problems never seems a waste to me.

In the next three articles, I'll go through the examples from the Zipper article and show how I ported them to C#. While that article starts with a binary tree, I'll instead begin with the doubly-linked list, since it's the simplest of the three.

Next: A List Zipper in C#.

This blog is totally free, but if you like it, please consider supporting it.

Using only a Domain Model to persist restaurant table configurations

2024-08-12T12:57:00+00:00

A data architecture example in C# and ASP.NET.

This is part of a small article series on data architectures. In this, the third instalment, you'll see an alternative way of modelling data in a server-based application. One that doesn't rely on statically typed classes to model data. As the introductory article explains, the example code shows how to create a new restaurant table configuration, or how to display an existing resource. The sample code base is an ASP.NET 8.0 REST API.

Keep in mind that while the sample code does store data in a relational database, the term table in this article mainly refers to physical tables, rather than database tables.

The idea is to use 'raw' serialization APIs to handle communication with external systems. For the presentation layer, the example even moves representation concerns to middleware, so that it's nicely abstracted away from the application layer.

An architecture diagram like this attempts to capture the design:

Here, the arrows indicate mappings, not dependencies.

Like in the DTO-based Ports and Adapters architecture, the goal is to being able to design Domain Models unconstrained by serialization concerns, but also being able to format external data unconstrained by Reflection-based serializers. Thus, while this architecture is centred on a Domain Model, there are no Data Transfer Objects (DTOs) to represent JSON, XML, or database rows.

HTTP interaction #

To establish the context of the application, here's how HTTP interactions may play out. The following is a copy of the identically named section in the article Using Ports and Adapters to persist restaurant table configurations, repeated here for your convenience.

A client can create a new table with a POST HTTP request:

POST /tables HTTP/1.1
content-type: application/json

{ "communalTable": { "capacity": 16 } }

Which might elicit a response like this:

HTTP/1.1 201 Created
Location: https://example.com/Tables/844581613e164813aa17243ff8b847af

Clients can later use the address indicated by the Location header to retrieve a representation of the resource:

GET /Tables/844581613e164813aa17243ff8b847af HTTP/1.1
accept: application/json

Which would result in this response:

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8

{"communalTable":{"capacity":16}}

By default, ASP.NET handles and returns JSON. Later in this article you'll see how well it deals with other data formats.

Boundary #

ASP.NET supports some variation of the model-view-controller (MVC) pattern, and Controllers handle HTTP requests. At the outset, the action method that handles the POST request looks like this:

[HttpPost]
public async Task<IActionResult> Post(Table table)
{
    var id = Guid.NewGuid();
    await repository.Create(id, table).ConfigureAwait(false);
 
    return new CreatedAtActionResult(
        nameof(Get),
        null,
        new { id = id.ToString("N") },
        null);
}

While this looks identical to the Post method for the Shared Data Model architecture, it's not, because it's not the same Table class. Not by a long shot. The Table class in use here is the one originally introduced in the article Serializing restaurant tables in C#, with a few inconsequential differences.

How does a Controller action method receive an input parameter directly in the form of a Domain Model, keeping in mind that this particular Domain Model is far from serialization-friendly? The short answer is middleware, which we'll get to in a moment. Before we look at that, however, let's also look at the Get method that supports HTTP GET requests:

[HttpGet("{id}")]
public async Task<IActionResult> Get(string id)
{
    if (!Guid.TryParseExact(id, "N", out var guid))
        return new BadRequestResult();
    Table? table = await repository.Read(guid).ConfigureAwait(false);
    if (table is null)
        return new NotFoundResult();
    return new OkObjectResult(table);
}

This, too, looks exactly like the Shared Data Model architecture, again with the crucial difference that the Table class is completely different. The Get method just takes the table object and wraps it in an OkObjectResult and returns it.

The Table class is, in reality, extraordinarily opaque, and not at all friendly to serialization, so how do the service turn it into JSON?

JSON middleware #

Most web frameworks come with extensibility points where you can add middleware. A common need is to be able to add custom serializers. In ASP.NET they're called formatters, and can be added at application startup:

builder.Services.AddControllers(opts =>
{
    opts.InputFormatters.Insert(0, new TableJsonInputFormatter());
    opts.OutputFormatters.Insert(0, new TableJsonOutputFormatter());
});

As the names imply, TableJsonInputFormatter deserializes JSON input, while TableJsonOutputFormatter serializes strongly typed objects to JSON.

We'll look at each in turn, starting with TableJsonInputFormatter, which is responsible for deserializing JSON documents into Table objects, as used by, for example, the Post method.

JSON input formatter #

You create an input formatter by implementing the IInputFormatter interface, although in this example code base, inheriting from TextInputFormatter is enough:

internal sealed class TableJsonInputFormatter : TextInputFormatter

You can use the constructor to define which media types and encodings the formatter will support:

public TableJsonInputFormatter()
{
    SupportedMediaTypes.Add(MediaTypeHeaderValue.Parse("application/json"));
 
    SupportedEncodings.Add(Encoding.UTF8);
    SupportedEncodings.Add(Encoding.Unicode);
}

You'll also need to tell the formatter, which .NET type it supports:

protected override bool CanReadType(Type type)
{
    return type == typeof(Table);
}

As far as I can tell, the ASP.NET framework will first determine which action method (that is, which Controller, and which method on that Controller) should handle a given HTTP request. For a POST request, as shown above, it'll determine that the appropriate action method is the Post method.

Since the Post method takes a Table object as input, the framework then goes through the registered formatters and asks them whether they can read from an HTTP request into that type. In this case, the TableJsonInputFormatter answers true only if the type is Table.

When CanReadType answers true, the framework then invokes a method to turn the HTTP request into an object:

public override async Task<InputFormatterResult> ReadRequestBodyAsync(
    InputFormatterContext context,
    Encoding encoding)
{
    using var rdr = new StreamReader(context.HttpContext.Request.Body, encoding);
    var json = await rdr.ReadToEndAsync().ConfigureAwait(false);
 
    var table = TableJson.Deserialize(json);
    if (table is { })
        return await InputFormatterResult.SuccessAsync(table).ConfigureAwait(false);
    else
        return await InputFormatterResult.FailureAsync().ConfigureAwait(false);
}

The ReadRequestBodyAsync method reads the HTTP request body into a string value called json, and then passes the value to TableJson.Deserialize. You can see the implementation of the Deserialize method in the article Serializing restaurant tables in C#. In short, it uses the default .NET JSON parser to probe a document object model. If it can turn the JSON document into a Table value, it does that. Otherwise, it returns null.

The above ReadRequestBodyAsync method then checks if the return value from TableJson.Deserialize is null. If it's not, it wraps the result in a value that indicates success. If it's null, it uses FailureAsync to indicate a deserialization failure.

With this input formatter in place as middleware, any action method that takes a Table parameter will automatically receive a deserialized JSON object, if possible.

JSON output formatter #

The TableJsonOutputFormatter class works much in the same way, but instead derives from the TextOutputFormatter base class:

internal sealed class TableJsonOutputFormatter : TextOutputFormatter

The constructor looks just like the TableJsonInputFormatter, and instead of a CanReadType method, it has a CanWriteType method that also looks identical.

The WriteResponseBodyAsync serializes a Table object to JSON:

public override Task WriteResponseBodyAsync(
    OutputFormatterWriteContext context,
    Encoding selectedEncoding)
{
    if (context.Object is Table table)
        return context.HttpContext.Response.WriteAsync(table.Serialize(), selectedEncoding);
 
    throw new InvalidOperationException("Expected a Table object.");
}

If context.Object is, in fact, a Table object, the method calls table.Serialize(), which you can also see in the article Serializing restaurant tables in C#. In short, it pattern-matches on the two possible kinds of tables and builds an appropriate abstract syntax tree or document object model that it then serializes to JSON.

Data access #

While the application stores data in SQL Server, it uses no object-relational mapper (ORM). Instead, it simply uses ADO.NET, as also outlined in the article Do ORMs reduce the need for mapping?

At first glance, the Create method looks simple:

public async Task Create(Guid id, Table table)
{
    using var conn = new SqlConnection(connectionString);
    using var cmd = table.Accept(new SqlInsertCommandVisitor(id));
    cmd.Connection = conn;
 
    await conn.OpenAsync().ConfigureAwait(false);
    await cmd.ExecuteNonQueryAsync().ConfigureAwait(false);
}

The main work, however, is done by the nested SqlInsertCommandVisitor class:

private sealed class SqlInsertCommandVisitor(Guid id) : ITableVisitor<SqlCommand>
{
    public SqlCommand VisitCommunal(NaturalNumber capacity)
    {
        const string createCommunalSql = @"
            INSERT INTO [dbo].[Tables] ([PublicId], [Capacity])
            VALUES (@PublicId, @Capacity)";
        var cmd = new SqlCommand(createCommunalSql);
        cmd.Parameters.AddWithValue("@PublicId", id);
        cmd.Parameters.AddWithValue("@Capacity", (int)capacity);
        return cmd;
    }
 
    public SqlCommand VisitSingle(NaturalNumber capacity, NaturalNumber minimalReservation)
    {
        const string createSingleSql = @"
            INSERT INTO [dbo].[Tables] ([PublicId], [Capacity], [MinimalReservation])
            VALUES (@PublicId, @Capacity, @MinimalReservation)";
        var cmd = new SqlCommand(createSingleSql);
        cmd.Parameters.AddWithValue("@PublicId", id);
        cmd.Parameters.AddWithValue("@Capacity", (int)capacity);
        cmd.Parameters.AddWithValue("@MinimalReservation", (int)minimalReservation);
        return cmd;
    }
}

It 'pattern-matches' on the two possible kinds of table and returns an appropriate SqlCommand that the Create method then executes. Notice that no 'Entity' class is needed. The code works straight on SqlCommand.

The same is true for the repository's Read method:

public async Task<Table?> Read(Guid id)
{
    const string readByIdSql = @"
        SELECT [Capacity], [MinimalReservation]
        FROM [dbo].[Tables]
        WHERE[PublicId] = @id";
 
    using var conn = new SqlConnection(connectionString);
    using var cmd = new SqlCommand(readByIdSql, conn);
    cmd.Parameters.AddWithValue("@id", id);
 
    await conn.OpenAsync().ConfigureAwait(false);
    using var rdr = await cmd.ExecuteReaderAsync().ConfigureAwait(false);
    if (!await rdr.ReadAsync().ConfigureAwait(false))
        return null;
 
    var capacity = (int)rdr["Capacity"];
    var mimimalReservation = rdr["MinimalReservation"] as int?;
    if (mimimalReservation is null)
        return Table.TryCreateCommunal(capacity);
    else
        return Table.TryCreateSingle(capacity, mimimalReservation.Value);
}

It works directly on SqlDataReader. Again, no extra 'Entity' class is required. If the data in the database makes sense, the Read method return a well-encapsulated Table object.

XML formats #

That covers the basics, but how well does this kind of architecture stand up to changing requirements?

One axis of variation is when a service needs to support multiple representations. In this example, I'll imagine that the service also needs to support not just one, but two, XML formats.

Granted, you may not run into that particular requirement that often, but it's typical of a kind of change that you're likely to run into. In REST APIs, for example, you should use content negotiation for versioning, and that's the same kind of problem.

To be fair, application code also changes for a variety of other reasons, including new features, changes to business logic, etc. I can't possibly cover all, though, and many of these are much better described than changes in wire formats.

As described in the introduction article, ideally the XML should support a format implied by these examples:

<communal-table>
  <capacity>12</capacity>
</communal-table>

<single-table>
  <capacity>4</capacity>
  <minimal-reservation>3</minimal-reservation>
</single-table>

Notice that while these two examples have different root elements, they're still considered to both represent a table. Although at the boundaries, static types are illusory we may still, loosely speaking, consider both of those XML documents as belonging to the same 'type'.

With both of the previous architectures described in this article series, I've had to give up on this schema. The present data architecture, finally, is able to handle this requirement.

HTTP interactions with element-biased XML #

The service should support the new XML format when presented with the the "application/xml" media type, either as a content-type header or accept header. An initial POST request may look like this:

POST /tables HTTP/1.1
content-type: application/xml

<communal-table><capacity>12</capacity></communal-table>

Which produces a reply like this:

HTTP/1.1 201 Created
Location: https://example.com/Tables/a77ac3fd221e4a5caaca3a0fc2b83ffc

And just like before, a client can later use the address in the Location header to request the resource. By using the accept header, it can indicate that it wishes to receive the reply formatted as XML:

GET /Tables/a77ac3fd221e4a5caaca3a0fc2b83ffc HTTP/1.1
accept: application/xml

Which produces this response with XML content in the body:

HTTP/1.1 200 OK
Content-Type: application/xml; charset=utf-8

<communal-table><capacity>12</capacity></communal-table>

How do you add support for this new format?

Element-biased XML formatters #

Not surprisingly, you can add support for the new format by adding new formatters.

opts.InputFormatters.Add(new ElementBiasedTableXmlInputFormatter());
opts.OutputFormatters.Add(new ElementBiasedTableXmlOutputFormatter());

Importantly, and in stark contrast to the DTO-based Ports and Adapters example, you don't have to change the existing code to add XML support. If you're concerned about design heuristics such as the Single Responsibility Principle, you may consider this a win. Apart from the two lines of code adding the formatters, all other code to support this new feature is in new classes.

Both of the new formatters support the "application/xml" media type.

Deserializing element-biased XML #

The constructor and CanReadType implementation of ElementBiasedTableXmlInputFormatter is nearly identical to code you've already seen here, so I'll skip the repetition. The ReadRequestBodyAsync implementation is also conceptually similar, but of course differs in the details.

public override async Task<InputFormatterResult> ReadRequestBodyAsync(
    InputFormatterContext context,
    Encoding encoding)
{
    var xml = await XElement
        .LoadAsync(context.HttpContext.Request.Body, LoadOptions.None, CancellationToken.None)
        .ConfigureAwait(false);
 
    var table = TableXml.TryParseElementBiased(xml);
    if (table is { })
        return await InputFormatterResult.SuccessAsync(table).ConfigureAwait(false);
    else
        return await InputFormatterResult.FailureAsync().ConfigureAwait(false);
}

As is also the case with the JSON input formatter, the ReadRequestBodyAsync method really only implements an Adapter over a more specialized parser function:

internal static Table? TryParseElementBiased(XElement xml)
{
    if (xml.Name == "communal-table")
    {
        var capacity = xml.Element("capacity")?.Value;
        if (capacity is { })
        {
            if (int.TryParse(capacity, out var c))
                return Table.TryCreateCommunal(c);
        }
    }
 
    if (xml.Name == "single-table")
    {
        var capacity = xml.Element("capacity")?.Value;
        var minimalReservation = xml.Element("minimal-reservation")?.Value;
        if (capacity is { } && minimalReservation is { })
        {
            if (int.TryParse(capacity, out var c) &&
                int.TryParse(minimalReservation, out var mr))
                return Table.TryCreateSingle(c, mr);
        }
    }
 
    return null;
}

In keeping with the common theme of the Domain Model Only data architecture, it deserialized by examining an Abstract Syntax Tree (AST) or document object model (DOM), specifically making use of the XElement API. This class is really part of the LINQ to XML API, but you'll probably agree that the above code example makes little use of LINQ.

Serializing element-biased XML #

Hardly surprising, turning a Table object into element-biased XML involves steps similar to converting it to JSON. The ElementBiasedTableXmlOutputFormatter class' WriteResponseBodyAsync method contains this implementation:

public override Task WriteResponseBodyAsync(
    OutputFormatterWriteContext context,
    Encoding selectedEncoding)
{
    if (context.Object is Table table)
        return context.HttpContext.Response.WriteAsync(
            table.GenerateElementBiasedXml(),
            selectedEncoding);
 
    throw new InvalidOperationException("Expected a Table object.");
}

Again, the heavy lifting is done by a specialized function:

internal static string GenerateElementBiasedXml(this Table table)
{
    return table.Accept(new ElementBiasedTableVisitor());
}
 
private sealed class ElementBiasedTableVisitor : ITableVisitor<string>
{
    public string VisitCommunal(NaturalNumber capacity)
    {
        var xml = new XElement(
            "communal-table",
            new XElement("capacity", (int)capacity));
        return xml.ToString(SaveOptions.DisableFormatting);
    }
 
    public string VisitSingle(
        NaturalNumber capacity,
        NaturalNumber minimalReservation)
    {
        var xml = new XElement(
            "single-table",
            new XElement("capacity", (int)capacity),
            new XElement("minimal-reservation", (int)minimalReservation));
        return xml.ToString(SaveOptions.DisableFormatting);
    }
}

True to form, GenerateElementBiasedXml assembles an appropriate AST for the kind of table in question, and finally converts it to a string value.

Attribute-biased XML #

I was curious how far I could take this kind of variation, so for the sake of exploration, I invented yet another XML format to support. Instead of making exclusive use of XML elements, this format uses XML attributes for primitive values.

<communal-table capacity="12" />
        
<single-table capacity="4" minimal-reservation="3" />

In order to distinguish this XML format from the other, I invented the vendor media type "application/vnd.ploeh.table+xml". The new formatters only handle this media type.

There's not much new to report. The new formatters work like the previous. In order to parse the new format, a new function does that, still based on XElement:

internal static Table? TryParseAttributeBiased(XElement xml)
{
    if (xml.Name == "communal-table")
    {
        var capacity = xml.Attribute("capacity")?.Value;
        if (capacity is { })
        {
            if (int.TryParse(capacity, out var c))
                return Table.TryCreateCommunal(c);
        }
    }
 
    if (xml.Name == "single-table")
    {
        var capacity = xml.Attribute("capacity")?.Value;
        var minimalReservation = xml.Attribute("minimal-reservation")?.Value;
        if (capacity is { } && minimalReservation is { })
        {
            if (int.TryParse(capacity, out var c) &&
                int.TryParse(minimalReservation, out var mr))
                return Table.TryCreateSingle(c, mr);
        }
    }
 
    return null;
}

Likewise, converting a Table object to this format looks like code you've already seen:

internal static string GenerateAttributeBiasedXml(this Table table)
{
    return table.Accept(new AttributedBiasedTableVisitor());
}
 
private sealed class AttributedBiasedTableVisitor : ITableVisitor<string>
{
    public string VisitCommunal(NaturalNumber capacity)
    {
        var xml = new XElement(
            "communal-table",
            new XAttribute("capacity", (int)capacity));
        return xml.ToString(SaveOptions.DisableFormatting);
    }
 
    public string VisitSingle(
        NaturalNumber capacity,
        NaturalNumber minimalReservation)
    {
        var xml = new XElement(
            "single-table",
            new XAttribute("capacity", (int)capacity),
            new XAttribute("minimal-reservation", (int)minimalReservation));
        return xml.ToString(SaveOptions.DisableFormatting);
    }
}

Consistent with adding the first XML support, I didn't have to touch any of the existing Controller or data access code.

Evaluation #

If you're concerned with separation of concerns, the Domain Model Only architecture gracefully handles variation in external formats without impacting application logic, Domain Model, or data access. You deal with each new format in a consistent and independent manner. The architecture offers the ultimate data representation flexibility, since everything you can write as a stream of bytes you can implement.

Since at the boundary, static types are illusory this architecture is congruent with reality. For a REST service, at least, reality is what goes on the wire. While static types can also be used to model what wire formats look like, there's always a risk that you can use your IDE's refactoring tools to change a DTO in such a way that the code still compiles, but you've now changed the wire format. This could easily break existing clients.

When wire compatibility is important, I test-drive enough self-hosted tests that directly use and verify the wire format to give me a good sense of stability. Without DTO classes, it becomes increasingly important to cover externally visible behaviour with a trustworthy test suite, but really, if compatibility is important, you should be doing that anyway.

It almost goes without saying that a requirement for this architecture is that your chosen web framework supports it. As you've seen here, ASP.NET does, but that's not a given in general. Most web frameworks worth their salt will come with mechanisms that enable you to add new wire formats, but the question is how opinionated such extensibility points are. Do they expect you to work with DTOs, or are they more flexible than that?

You may consider the pure Domain Model Only data architecture too specialized for everyday use. I may do that, too. As I wrote in the introduction article, I don't intent these walk-throughs to be prescriptive. Rather, they explore what's possible, so that you and I have a bigger set of alternatives to choose from.

Hybrid architectures #

In the code base that accompanies Code That Fits in Your Head, I use a hybrid data architecture that I've used for years. ADO.NET for data access, as shown here, but DTOs for external JSON serialization. As demonstrated in the article Using Ports and Adapters to persist restaurant table configurations, using DTOs for the presentation layer may cause trouble if you need to support multiple wire formats. On the other hand, if you don't expect that this is a concern, you may decide to run that risk. I often do that.

When presenting these three architectures to a larger audience, one audience member told me that his team used another hybrid architecture: DTOs for the presentation layer, and separate DTOs for data access, but no Domain Model. I can see how this makes sense in a mostly CRUD-heavy application where nonetheless you need to be able to vary user interfaces independently from the database schema.

Finally, I should point out that the Domain Model Only data architecture is, in reality, also a kind of Ports and Adapters architecture. It just uses more low-level Adapter implementations than you idiomatically see.

Conclusion #

The Domain Model Only data architecture emphasises modelling business logic as a strongly-typed, well-encapsulated Domain Model, while eschewing using statically-typed DTOs for communication with external processes. What I most like about this alternative is that it leaves little confusion as to where functionality goes.

When you have, say, TableDto, Table, and TableEntity classes, you need a sophisticated and mature team to trust all developers to add functionality in the right place. If there's only a single Table Domain Model, it may be more evident to developers that only business logic belongs there, and other concerns ought to be addressed in different ways.

Even so, you may consider all the low-level parsing code not to your liking, and instead decide to use DTOs. I may too, depending on context.

Comments

Jes Hansen #

In this version of the data archictecture, let's suppose that the controller that now accepts a Domain Object directly is part of a larger REST API. How would you handle discoverability of the API, as the usual OpenAPI (Swagger et.al.) tools probably takes offence at this type of request object?

2024-08-19 12:10 UTC

Mark Seemann #

Jes, thank you for writing. If by discoverability you mean 'documentation', I would handle that the same way I usually handle documentation requirements for REST APIs: by writing one or my documents that explain how the API works. If there are other possible uses of OpenAPI than that, and the GUI to perform ad-hoc experiments, I'm going to need to be taken to task, because then I'm not aware of them.

I've recently discussed my general misgivings about OpenAPI, and they apply here as well. I'm aware that other people feel differently about this, and that's okay too.

"the usual OpenAPI (Swagger et.al.) tools probably takes offence at this type of request object"

You may be right, but I haven't tried, so I don't know if this is the case.

2024-08-22 16:55 UTC

This blog is totally free, but if you like it, please consider supporting it.

Using a Shared Data Model to persist restaurant table configurations

2024-08-05T06:14:00+00:00

A data architecture example in C# and ASP.NET.

This is part of a small article series on data architectures. In this, the second instalment, you'll see a common attempt at addressing the mapping issue that I mentioned in the previous article. As the introductory article explains, the example code shows how to create a new restaurant table configuration, or how to display an existing resource. The sample code base is an ASP.NET 8.0 REST API.

Keep in mind that while the sample code does store data in a relational database, the term table in this article mainly refers to physical tables, rather than database tables.

The idea in this data architecture is to use a single, shared data model for each business object in the service. This is in contrast to the Ports and Adapters architecture, where you typically have a Data Transfer Object (DTO) for (JSON or XML) serialization, another class for the Domain Model, and a third to support an object-relational mapper.

An architecture diagram may attempt to illustrate the idea like this:

While ostensibly keeping alive the idea of application layers, data models are allowed to cross layers to be used both for database persistence, business logic, and in the presentation layer.

Data model #

Since the goal is to use a single class to model all application concerns, it means that we also need to use it for database persistence. The most commonly used ORM in .NET is Entity Framework, so I'll use that for the example. It's not something that I normally do, so it's possible that I could have done it better than what follows.

Still, assume that the database schema defines the Tables table like this:

CREATE TABLE [dbo].[Tables] (
    [Id]                 INT                NOT NULL IDENTITY PRIMARY KEY,
    [PublicId]           UNIQUEIDENTIFIER   NOT NULL UNIQUE,
    [Capacity]           INT                NOT NULL,
    [MinimalReservation] INT                NULL
)

I used a scaffolding tool to generate Entity Framework code from the database schema and then modified what it had created. This is the result:

public partial class Table
{
    [JsonIgnore]
    public int Id { get; set; }
 
    [JsonIgnore]
    public Guid PublicId { get; set; }
 
    public string Type => MinimalReservation.HasValue ? "single" : "communal";
 
    public int Capacity { get; set; }
 
    public int? MinimalReservation { get; set; }
}

Notice that I added [JsonIgnore] attributes to two of the properties, since I didn't want to serialize them to JSON. I also added the calculated property Type to include a discriminator in the JSON documents.

HTTP interaction #

A client can create a new table with a POST HTTP request:

POST /tables HTTP/1.1
content-type: application/json

{"type":"communal","capacity":12}

Notice that the JSON document doesn't follow the desired schema described in the introduction article. It can't, because the data architecture is bound to the shared Table class. Or at least, if it's possible to attain the desired format with a single class and only some strategically placed attributes, I'm not aware of it. As the article Using only a Domain Model to persist restaurant table configurations will show, it is possible to attain that goal with the appropriate middleware, but I consider doing that to be an example of the third architecture, so not something I will cover in this article.

The service will respond to the above request like this:

HTTP/1.1 201 Created
Location: https://example.com/Tables/777779466d2549d69f7e30b6c35bde3c

Clients can later use the address indicated by the Location header to retrieve a representation of the resource:

GET /Tables/777779466d2549d69f7e30b6c35bde3c HTTP/1.1
accept: application/json

Which elicits this response:

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8

{"type":"communal","capacity":12}

The JSON format still doesn't conform to the desired format because the Controller in question deals exclusively with the shared Table data model.

Boundary #

At the boundary of the application, Controllers handle HTTP requests with action methods (an ASP.NET term). The framework matches requests by a combination of naming conventions and attributes. The Post action method handles incoming POST requests.

[HttpPost]
public async Task<IActionResult> Post(Table table)
{
    var id = Guid.NewGuid();
    await repository.Create(id, table).ConfigureAwait(false);
 
    return new CreatedAtActionResult(
        nameof(Get),
        null,
        new { id = id.ToString("N") },
        null);
}

Notice that the input parameter isn't a separate DTO, but rather the shared Table object. Since it's shared, the Controller can pass it directly to the repository without any mapping.

The same simplicity is on display in the Get method:

[HttpGet("{id}")]
public async Task<IActionResult> Get(string id)
{
    if (!Guid.TryParseExact(id, "N", out var guid))
        return new BadRequestResult();
    Table? table = await repository.Read(guid).ConfigureAwait(false);
    if (table is null)
        return new NotFoundResult();
    return new OkObjectResult(table);
}

Once the Get method has parsed the id it goes straight to the repository, retrieves the table and returns it if it's there. No mapping is required by the Controller. What about the repository?

Data access #

The SqlTablesRepository class reads and writes data from SQL Server using Entity Framework. The Create method is as simple as this:

public async Task Create(Guid id, Table table)
{
    ArgumentNullException.ThrowIfNull(table);
 
    table.PublicId = id;
    await context.Tables.AddAsync(table).ConfigureAwait(false);
    await context.SaveChangesAsync().ConfigureAwait(false);
}

The Read method is even simpler - a one-liner:

public async Task<Table?> Read(Guid id)
{
    return await context.Tables
        .SingleOrDefaultAsync(t => t.PublicId == id).ConfigureAwait(false);
}

Again, no mapping. Just return the database Entity.

XML serialization #

Simple, so far, but how does this data architecture handle changing requirements?

One axis of variation is when a service needs to support multiple representations. In this example, I'll imagine that the service also needs to support XML.

As was also the case in the previous article, it quickly turns out that it's not possible to support any of the desired XML formats described in the introduction article. Instead, for the sake of exploring what is possible, I'll compromise and support XML documents like these examples:

<table>
  <type>communal</type>
  <capacity>12</capacity>
</table>

<table>
  <type>single</type>
  <capacity>4</capacity>
  <minimal-reservation>3</minimal-reservation>
</table>

This schema, it turns out, is the same as the element-biased format from the previous article. I could, instead, have chosen to support the attribute-biased format, but, because of the shared data model, not both.

Notice how using statically typed classes, attributes, and Reflection to guide serialization leads toward certain kinds of formats. You can't easily support any arbitrary JSON or XML schema, but are rather nudged into a more constrained subset of possible formats. There's nothing too bad about this. As usual, there are trade-offs involved. You concede flexibility, but gain convenience: Just slab some attributes on your DTO, and it works well enough for most purposes. I mostly point it out because this entire article series is about awareness of choice. There's always some cost to be paid.

That said, supporting that XML format is surprisingly easy:

[XmlRoot("table")]
public partial class Table
{
    [JsonIgnore, XmlIgnore]
    public int Id { get; set; }
 
    [JsonIgnore, XmlIgnore]
    public Guid PublicId { get; set; }
 
    [XmlElement("type"), NotMapped]
    public string? Type { get; set; }
 
    [XmlElement("capacity")]
    public int Capacity { get; set; }
 
    [XmlElement("minimal-reservation")]
    public int? MinimalReservation { get; set; }
 
    public bool ShouldSerializeMinimalReservation() =>
        MinimalReservation.HasValue;
 
    internal void InferType()
    {
        Type = MinimalReservation.HasValue ? "single" : "communal";
    }
}

Most of the changes are simple additions of the XmlRoot, XmlElement, and XmlIgnore attributes. In order to serialize the <type> element, however, I also had to convert the Type property to a read/write property, which had some ripple effects.

For one, I had to add the NotMapped attribute to tell Entity Framework that it shouldn't try to save the value of that property in the database. As you can see in the above SQL schema, the Tables table has no Type column.

This also meant that I had to change the Read method in SqlTablesRepository to call the new InferType method:

public async Task<Table?> Read(Guid id)
{
    var table = await context.Tables
        .SingleOrDefaultAsync(t => t.PublicId == id).ConfigureAwait(false);
    table?.InferType();
    return table;
}

I'm not happy with this kind of sequential coupling, but to be honest, this data architecture inherently has an appalling lack of encapsulation. Having to call InferType is just par for the course.

That said, despite a few stumbling blocks, adding XML support turned out to be surprisingly easy in this data architecture. Granted, I had to compromise on the schema, and could only support one XML schema, so we shouldn't really take this as an endorsement. To paraphrase Gerald Weinberg, if it doesn't have to work, it's easy to implement.

Evaluation #

There's no denying that the Shared Data Model architecture is simple. There's no mapping between different layers, and it's easy to get started. Like the DTO-based Ports and Adapters architecture, you'll find many documentation examples and getting-started guides that work like this. In a sense, you can say that it's what the ASP.NET framework, or, perhaps particularly the Entity Framework (EF), 'wants you to do'. To be fair, I find ASP.NET to be reasonably unopinionated, so what inveigling you may run into may be mostly attributable to EF.

While it may feel nice that it's easy to get started, instant gratification often comes at a cost. Consider the Table class shown here. Because of various constraints imposed by EF and the JSON and XML serializers, it has no encapsulation. One thing is that the sophisticated Visitor-encoded Table class introduced in the article Serializing restaurant tables in C# is completely out of the question, but you can't even add a required constructor like this one:

public Table(int capacity)
{
    Capacity = capacity;
}

Granted, it seems to work with both EF and the JSON serializer, which I suppose is a recent development, but it doesn't work with the XML serializer, which requires that

"A class must have a parameterless constructor to be serialized by XmlSerializer."

XML serialization, Microsoft documentation, 2023-04-05, retrieved 2024-07-27, their emphasis

Even if this, too, changes in the future, DTO-based designs are at odds with encapsulation. If you doubt the veracity of that statement, I challenge you to complete the Priority Collection kata with serializable DTOs.

Another problem with the Shared Data Model architecture is that it so easily decays to a Big Ball of Mud. Even though the above architecture diagram hollowly insists that layering is still possible, a Shared Data Model is an attractor of behaviour. You'll soon find that a class like Table has methods that serve presentation concerns, others that implement business logic, and others again that address persistence issues. It has become a God Class.

From these problems it doesn't follow that the architecture doesn't have merit. If you're developing a CRUD-heavy application with a user interface (UI) that's merely a glorified table view, this could be a good choice. You would be coupling the UI to the database, so that if you need to change how the UI works, you might also have to modify the database schema, or vice versa.

This is still not an indictment, but merely an observation of consequences. If you can live with them, then choose the Shared Data Model architecture. I can easily imagine application types where that would be the case.

Conclusion #

In the Shared Data Model architecture you use a single model (here, a class) to handle all application concerns: UI, business logic, data access. While this shows a blatant disregard for the notion of separation of concerns, no law states that you must, always, separate concerns.

Sometimes it's okay to mix concerns, and then the Shared Data Model architecture is dead simple. Just make sure that you know when it's okay.

While this architecture is the ultimate in simplicity, it's also quite constrained. The third and final data architecture I'll cover, on the other hand, offers the ultimate in flexibility, at the expense (not surprisingly) of some complexity.

Next: Using only a Domain Model to persist restaurant table configurations.

This blog is totally free, but if you like it, please consider supporting it.

Using Ports and Adapters to persist restaurant table configurations

2024-07-29T08:05:00+00:00

A data architecture example in C# and ASP.NET.

This is part of a small article series on data architectures. In the first instalment, you'll see the outline of a Ports and Adapters implementation. As the introductory article explains, the example code shows how to create a new restaurant table configuration, or how to display an existing resource. The sample code base is an ASP.NET 8.0 REST API.

Keep in mind that while the sample code does store data in a relational database, the term table in this article mainly refers to physical tables, rather than database tables.

While Ports and Adapters architecture diagrams are usually drawn as concentric circles, you can also draw (subsets of) it as more traditional layered diagrams:

Here, the arrows indicate mappings, not dependencies.

HTTP interaction #

A client can create a new table with a POST HTTP request:

POST /tables HTTP/1.1
content-type: application/json

{ "communalTable": { "capacity": 16 } }

Which might elicit a response like this:

HTTP/1.1 201 Created
Location: https://example.com/Tables/844581613e164813aa17243ff8b847af

Clients can later use the address indicated by the Location header to retrieve a representation of the resource:

GET /Tables/844581613e164813aa17243ff8b847af HTTP/1.1
accept: application/json

Which would result in this response:

HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8

{"communalTable":{"capacity":16}}

By default, ASP.NET handles and returns JSON. Later in this article you'll see how well it deals with other data formats.

Boundary #

ASP.NET supports some variation of the model-view-controller (MVC) pattern, and Controllers handle HTTP requests. At the outset, the action method that handles the POST request looks like this:

[HttpPost]
public async Task<IActionResult> Post(TableDto dto)
{
    ArgumentNullException.ThrowIfNull(dto);
 
    var id = Guid.NewGuid();
    await repository.Create(id, dto.ToTable()).ConfigureAwait(false);
 
    return new CreatedAtActionResult(nameof(Get), null, new { id = id.ToString("N") }, null);
}

As is idiomatic in ASP.NET, input and output are modelled by data transfer objects (DTOs), in this case called TableDto. I've already covered this little object model in the article Serializing restaurant tables in C#, so I'm not going to repeat it here.

The ToTable method, on the other hand, is a good example of how trying to cut corners lead to more complicated code:

internal Table ToTable()
{
    var candidate =
        Table.TryCreateSingle(SingleTable?.Capacity ?? -1, SingleTable?.MinimalReservation ?? -1);
    if (candidate is { })
        return candidate.Value;
 
    candidate = Table.TryCreateCommunal(CommunalTable?.Capacity ?? -1);
    if (candidate is { })
        return candidate.Value;
 
    throw new InvalidOperationException("Invalid TableDto.");
}

Compare it to the TryParse method in the Serializing restaurant tables in C# article. That one is simpler, and less error-prone.

I think that I wrote ToTable that way because I didn't want to deal with error handling in the Controller, and while I test-drove the code, I never wrote a test that supply malformed input. I should have, and so should you, but this is demo code, and I never got around to it.

Enough about that. The other action method handles GET requests:

[HttpGet("{id}")]
public async Task<IActionResult> Get(string id)
{
    if (!Guid.TryParseExact(id, "N", out var guid))
        return new BadRequestResult();
    var table = await repository.Read(guid).ConfigureAwait(false);
    if (table is null)
        return new NotFoundResult();
    return new OkObjectResult(TableDto.From(table.Value));
}

The static TableDto.From method is identical to the ToDto method from the Serializing restaurant tables in C# article, just with a different name.

To summarize so far: At the boundary of the application, Controller methods receive or return TableDto objects, which are mapped to and from the Domain Model named Table.

Domain Model #

The Domain Model Table is also identical to the code shown in Serializing restaurant tables in C#. In order to comply with the Dependency Inversion Principle (DIP), mapping to and from TableDto is defined on the latter. The DTO, being an implementation detail, may depend on the abstraction (the Domain Model), but not the other way around.

In the same spirit, conversions to and from the database are defined entirely within the repository implementation.

Data access layer #

Keeping the example consistent, the code base also models data access with C# classes. It uses Entity Framework to read from and write to SQL Server. The class that models a row in the database is also a kind of DTO, even though here it's idiomatically called an entity:

public partial class TableEntity
{
    public int Id { get; set; }
 
    public Guid PublicId { get; set; }
 
    public int Capacity { get; set; }
 
    public int? MinimalReservation { get; set; }
}

I had a command-line tool scaffold the code for me, and since I don't usually live in that world, I don't know why it's a partial class. It seems to be working, though.

The SqlTablesRepository class implements the mapping between Table and TableEntity. For instance, the Create method looks like this:

public async Task Create(Guid id, Table table)
{
    var entity = table.Accept(new TableToEntityConverter(id));
    await context.Tables.AddAsync(entity).ConfigureAwait(false);
    await context.SaveChangesAsync().ConfigureAwait(false);
}

That looks simple, but is only because all the work is done by the TableToEntityConverter, which is a nested class:

private sealed class TableToEntityConverter : ITableVisitor<TableEntity>
{
    private readonly Guid id;
 
    public TableToEntityConverter(Guid id)
    {
        this.id = id;
    }
 
    public TableEntity VisitCommunal(NaturalNumber capacity)
    {
        return new TableEntity
        {
            PublicId = id,
            Capacity = (int)capacity,
        };
    }
 
    public TableEntity VisitSingle(
        NaturalNumber capacity,
        NaturalNumber minimalReservation)
    {
        return new TableEntity
        {
            PublicId = id,
            Capacity = (int)capacity,
            MinimalReservation = (int)minimalReservation,
        };
    }
}

Mapping the other way is easier, so the SqlTablesRepository does it inline in the Read method:

public async Task<Table?> Read(Guid id)
{
    var entity = await context.Tables
        .SingleOrDefaultAsync(t => t.PublicId == id).ConfigureAwait(false);
    if (entity is null)
        return null;
 
    if (entity.MinimalReservation is null)
        return Table.TryCreateCommunal(entity.Capacity);
    else
        return Table.TryCreateSingle(
            entity.Capacity,
            entity.MinimalReservation.Value);
}

Similar to the case of the DTO, mapping between Table and TableEntity is the responsibility of the SqlTablesRepository class, since data persistence is an implementation detail. According to the DIP it shouldn't be part of the Domain Model, and it isn't.

XML formats #

That covers the basics, but how well does this kind of architecture stand up to changing requirements?

One axis of variation is when a service needs to support multiple representations. In this example, I'll imagine that the service also needs to support not just one, but two, XML formats.

As described in the introduction article, ideally the XML should support a format implied by these examples:

<communal-table>
  <capacity>12</capacity>
</communal-table>

<single-table>
  <capacity>4</capacity>
  <minimal-reservation>3</minimal-reservation>
</single-table>

To be honest, if there's a way to support this kind of schema by defining DTOs to be serialized and deserialized, I don't know what it looks like. That's not meant to imply that it's impossible. There's often an epistemological problem associated with proving things impossible, so I'll just leave it there.

To be clear, it's not that I don't know how to support that kind of schema at all. I do, as the article Using only a Domain Model to persist restaurant table configurations will show. I just don't know how to do it with DTO-based serialisation.

Element-biased XML #

Instead of the above XML schema, I will, instead explore how hard it is to support a variant schema, implied by these two examples:

<table>
  <type>communal</type>
  <capacity>12</capacity>
</table>

<table>
  <type>single</type>
  <capacity>4</capacity>
  <minimal-reservation>3</minimal-reservation>
</table>

This variation shares the same <table> root element and instead distinguishes between the two kinds of table with a <type> discriminator.

This kind of schema we can define with a DTO:

[XmlRoot("table")]
public class ElementBiasedTableXmlDto
{
    [XmlElement("type")]
    public string? Type { get; set; }
 
    [XmlElement("capacity")]
    public int Capacity { get; set; }
 
    [XmlElement("minimal-reservation")]
    public int? MinimalReservation { get; set; }
 
    public bool ShouldSerializeMinimalReservation() =>
        MinimalReservation.HasValue;
 
    // Mapping methods not shown here...
}

As you may have already noticed, however, this isn't the same type as TableJsonDto, so how are we going to implement the Controller methods that receive and send objects of this type?

Posting XML #

The service should still accept JSON as shown above, but now, additionally, it should also support HTTP requests like this one:

POST /tables HTTP/1.1
content-type: application/xml

<table><type>communal</type><capacity>12</capacity></table>

How do you implement this new feature?

My first thought was to add a Post overload to the Controller:

[HttpPost]
public async Task<IActionResult> Post(ElementBiasedTableXmlDto dto)
{
    ArgumentNullException.ThrowIfNull(dto);
 
    var id = Guid.NewGuid();
    await repository.Create(id, dto.ToTable()).ConfigureAwait(false);
 
    return new CreatedAtActionResult(
        nameof(Get),
        null,
        new { id = id.ToString("N") },
        null);
}

I just copied and pasted the original Post method and changed the type of the dto parameter. I also had to add a ToTable conversion to ElementBiasedTableXmlDto:

internal Table ToTable()
{
    if (Type == "single")
    {
        var t = Table.TryCreateSingle(Capacity, MinimalReservation ?? 0);
        if (t is { })
            return t.Value;
    }
 
    if (Type == "communal")
    {
        var t = Table.TryCreateCommunal(Capacity);
        if (t is { })
            return t.Value;
    }
 
    throw new InvalidOperationException("Invalid Table DTO.");
}

While all of that compiles, it doesn't work.

When you attempt to POST a request against the service, the ASP.NET framework now throws an AmbiguousMatchException indicating that "The request matched multiple endpoints". Which is understandable.

This lead me to the first round of Framework Whac-A-Mole. What I'd like to do is to select the appropriate action method based on content-type or accept headers. How does one do that?

After some web searching, I came across a Stack Overflow answer that seemed to indicate a way forward.

Selecting the right action method #

One way to address the issue is to implement a custom ActionMethodSelectorAttribute:

public sealed class SelectTableActionMethodAttribute : ActionMethodSelectorAttribute
{
    public override bool IsValidForRequest(RouteContext routeContext, ActionDescriptor action)
    {
        if (action is not ControllerActionDescriptor cad)
            return false;
 
        if (cad.Parameters.Count != 1)
            return false;
        var dtoType = cad.Parameters[0].ParameterType;
 
        // Demo code only. This doesn't take into account a possible charset
        // parameter. See RFC 9110, section 8.3
        // (https://www.rfc-editor.org/rfc/rfc9110#field.content-type) for more
        // information.
        if (routeContext?.HttpContext.Request.ContentType == "application/json")
            return dtoType == typeof(TableJsonDto);
        if (routeContext?.HttpContext.Request.ContentType == "application/xml")
            return dtoType == typeof(ElementBiasedTableXmlDto);
 
        return false;
    }
}

As the code comment suggests, this isn't as robust as it should be. A content-type header may also look like this:

Content-Type: application/json; charset=utf-8

The exact string equality check shown above would fail in such a scenario, suggesting that a more sophisticated implementation is warranted. I'll skip that for now, since this demo code already compromises on the overall XML schema. For an example of more robust content negotiation implementations, see Using only a Domain Model to persist restaurant table configurations.

Adorn both Post action methods with this custom attribute, and the service now handles both formats:

[HttpPost, SelectTableActionMethod]
public async Task<IActionResult> Post(TableJsonDto dto)
    // ...
 
[HttpPost, SelectTableActionMethod]
public async Task<IActionResult> Post(ElementBiasedTableXmlDto dto)
    // ...

While that handles POST requests, it doesn't implement content negotiation for GET requests.

Getting XML #

In order to GET an XML representation, clients can supply an accept header value:

GET /Tables/153f224c91fb4403988934118cc14024 HTTP/1.1
accept: application/xml

which will reply with

HTTP/1.1 200 OK
Content-Length: 59
Content-Type: application/xml; charset=utf-8

<table><type>communal</type><capacity>12</capacity></table>

How do we implement that?

Keep in mind that since this data-architecture variation uses two different DTOs to model JSON and XML, respectively, an action method can't just return an object of a single type and hope that the ASP.NET framework takes care of the rest. Again, I'm aware of middleware that'll deal nicely with this kind of problem, but not in this architecture; see Using only a Domain Model to persist restaurant table configurations for such a solution.

The best I could come up with, given the constraints I'd imposed on myself, then, was this:

[HttpGet("{id}")]
public async Task<IActionResult> Get(string id)
{
    if (!Guid.TryParseExact(id, "N", out var guid))
        return new BadRequestResult();
    var table = await repository.Read(guid).ConfigureAwait(false);
    if (table is null)
        return new NotFoundResult();
 
    // Demo code only. This doesn't take into account quality values.
    var accept =
        httpContextAccessor?.HttpContext?.Request.Headers.Accept.ToString();
    if (accept == "application/json")
        return new OkObjectResult(TableJsonDto.From(table.Value));
    if (accept == "application/xml")
        return new OkObjectResult(ElementBiasedTableXmlDto.From(table.Value));
 
    return new StatusCodeResult((int)HttpStatusCode.NotAcceptable);
}

As the comment suggests, this is once again code that barely passes the few tests that I have, but really isn't production-ready. An accept header may also look like this:

accept: application/xml; q=1.0,application/json; q=0.5

Given such an accept header, the service ought to return an XML representation with the application/xml content type, but instead, this Get method returns 406 Not Acceptable.

As I've already outlined, I'm not going to fix this problem, as this is only an exploration. It seems that we can already conclude that this style of architecture is ill-suited to deal with this kind of problem. If that's the conclusion, then why spend time fixing outstanding problems?

Attribute-biased XML #

Even so, just to punish myself, apparently, I also tried to add support for an alternative XML format that use attributes to record primitive values. Again, I couldn't make the schema described in the introductory article work, but I did manage to add support for XML documents like these:

<table type="communal" capacity="12" />

<table type="single" capacity="4" minimal-reservation="3" />

The code is similar to what I've already shown, so I'll only list the DTO:

[XmlRoot("table")]
public class AttributeBiasedTableXmlDto
{
    [XmlAttribute("type")]
    public string? Type { get; set; }
 
    [XmlAttribute("capacity")]
    public int Capacity { get; set; }
 
    [XmlAttribute("minimal-reservation")]
    public int MinimalReservation { get; set; }
 
    public bool ShouldSerializeMinimalReservation() => 0 < MinimalReservation;
 
    // Mapping methods not shown here...
}

This DTO looks a lot like the ElementBiasedTableXmlDto class, only it adorns properties with XmlAttribute rather than XmlElement.

Evaluation #

Even though I had to compromise on essential goals, I wasted an appalling amount of time and energy on yak shaving and Framework Whac-A-Mole. The DTO-based approach to modelling external resources really doesn't work when you need to do substantial content negotiation.

Even so, a DTO-based Ports and Adapters architecture may be useful when that's not a concern. If, instead of a REST API, you're developing a web site, you'll typically not need to vary representation independently of resource. In other words, a web page is likely to have at most one underlying model.

Compared to other large frameworks I've run into, ASP.NET is fairly unopinionated. Even so, the idiomatic way to use it is based on DTOs. DTOs to represent external data. DTOs to represent UI components. DTOs to represent database rows (although they're often called entities in that context). You'll find a ton of examples using this data architecture, so it's incredibly well-described. If you run into problems, odds are that someone has blazed a trail before you.

Even outside of .NET, this kind of architecture is well-known. While I've learned a thing or two from experience, I've picked up a lot of my knowledge about software architecture from people like Martin Fowler and Robert C. Martin.

When you also apply the Dependency Inversion Principle, you'll get good separations of concerns. This aspect of Ports and Adapters is most explicitly described in Clean Architecture. For example, a change to the UI generally doesn't affect the database. You may find that example ridiculous, because why should it, but consult the article Using a Shared Data Model to persist restaurant table configurations to see how this may happen.

The major drawbacks of the DTO-based data architecture is that much mapping is required. With three different DTOs (e.g. JSON DTO, Domain Model, and ORM Entity), you need four-way translation as indicated in the above figure. People often complain about all that mapping, and no: ORMs don't reduce the need for mapping.

Another problem is that this style of architecture is complicated. As I've argued elsewhere, Ports and Adapters often constitute an unstable equilibrium. While you can make it work, it requires a level of sophistication and maturity among team members that is not always present. And when it goes wrong, it may quickly deteriorate into a Big Ball of Mud.

Conclusion #

A DTO-based Ports and Adapters architecture is well-described and has good separation of concerns. In this article, however, we've seen that it doesn't deal successfully with realistic content negotiation. While that may seem like a shortcoming, it's a drawback that you may be able to live with. Particularly if you don't need to do content negotiation at all.

This way of organizing code around data is quite common. It's often the default data architecture, and I sometimes get the impression that a development team has 'chosen' to use it without considering alternatives.

It's not a bad architecture despite evidence to the contrary in this article. The scenario examined here may not be relevant. The main drawback of having all these objects playing different roles is all the mapping that's required.

The next data architecture attempts to address that concern.

Next: Using a Shared Data Model to persist restaurant table configurations.

This blog is totally free, but if you like it, please consider supporting it.

Three data architectures for the server

2024-07-25T18:30:00+00:00

A comparison, for educational purposes.

Use the right tool for the job. How often have you encountered that phrase when discussing software architecture?

There's nothing wrong with the sentiment per se, but it's almost devoid of meaning. It doesn't pass the 'not test'. Try to negate it and imagine if anyone would seriously hold that belief: Don't use the right tool for the job, said no-one ever.

Even so, the underlying idea is that there are better and worse ways to solve problems. In software architecture too. It follows that you should choose the better solution.

How to do that requires skill and experience. When planning a good software architecture, an important consideration is how it'll handle future requirements. This seems to indicate that an architect should be able to predict the future in order to pick the best architecture. Which is, in general, not possible. Predicting the future is not the topic of this article.

There is, however, a more practical issue related to the notion of using the right tool for the job. One that we can address.

Choice #

In order to choose the better solution, you need to be aware of alternatives. You can't choose if there's nothing to choose from. This seems obvious, but a flowchart may drive home the point in an even stronger fashion.

On the other hand, if you have options, you're now in a position to choose.

In order to make a decision, you must be able to identify alternatives. This is hardly earth-shattering, but perhaps a bit abstract. To make it concrete, in this article, I'll look at a particular example.

Default data architecture #

Many applications need some sort of persistent storage. Particularly when it comes to (relational) database-based systems, I've seen more than one organization defaulting to a single data architecture: A presentation layer with View Models, a business logic layer with Domain Models, and a data access layer with ORM objects. A few decades ago, you'd typically see that model illustrated with horizontal layers. This is no longer en vogue. Today, most organizations that I consult with will tell me that they've decided on Ports and Adapters. Even so, if you do it right, it's the same architecture.

Reusing a diagram from a recent article, we may draw it like this:

The architect or senior developer who made that decision is obviously aware of some of the lore in the industry. He or she can often name that data architecture as either Ports and Adapters, Hexagonal Architecture, Clean Architecture, or, more rarely, Onion Architecture.

I still get the impression that this way of arranging code was chosen by default, without much deliberation. I see it so often that it strikes me as a 'default architecture'. Are architects aware of alternatives? Can they compare the benefits and drawbacks of each alternative?

Three alternatives #

As an example, I'll explore three alternative data architectures, one of them being Ports and Adapters. My goal with this is only to raise awareness. Since I rarely (if ever) see my customers use anything other than Ports and Adapters, I think some readers may benefit from seeing some alternatives.

I'll show three ways to organize data with code, but that doesn't imply that these are the only three options. At the very least, some hybrid combinations are also possible. It's also possible that a fourth or fifth alternative exists, and I'm just not aware of it.

In three articles, you'll see each data architecture explored in more detail.

As the titles suggest, all three examples will attempt to address the same problem: How to persist restaurant table configuration for a restaurant. The scenario is the same as already outlined in the article Serialization with and without Reflection, and the example code base also attempts to follow the external data format of those articles.

Data formats #

In JSON, a table may be represented like this:

{
  "singleTable": {
    "capacity": 16,
    "minimalReservation": 10
  }
}

Or like this:

{ "communalTable": { "capacity": 10 } }

But I'll also explore what happens if you need to support multiple external formats, such as XML. Generally speaking, a given XML specification may lean towards favouring a verbose style based on elements, or a terser style based on attributes. An example of the former could be:

<communal-table>
  <capacity>12</capacity>
</communal-table>

<single-table>
  <capacity>4</capacity>
  <minimal-reservation>3</minimal-reservation>
</single-table>

while examples of the latter style include

<communal-table capacity="12" />

and

<single-table capacity="4" minimal-reservation="3" />

As it turns out, only one of the three data architectures is flexible enough to fully address such requirements.

Comparisons #

A REST API is the kind of application where data representation flexibility is most likely to be an issue. Thus, that only one of the three alternative architectures is able to exhibit enough expressive power in that dimension doesn't disqualify the other two. Each come with their own benefits and drawbacks.

	Ports and Adapters	Shared Data Model	Domain Model only
Advantages	Separation of concerns Well-described	Simple No mapping	Flexible Congruent with reality
Disadvantages	Much mapping Easy to get wrong	Inflexible God Class attractor	Requires non-opinionated framework Requires more testing

I'll discuss each alternative's benefits and drawbacks in their individual articles.

An important point of all this is that none of these articles are meant to be prescriptive. While I do have favourites, my biases are shaped by the kind of work I typically do. In other contexts, another alternative may prevail.

Example code #

As usual, example code is in C#. Of the three languages in which I'm most proficient (the other two being F# and Haskell), this is the most easily digestible for a larger audience.

All three alternatives are written with ASP.NET 8.0, and it's unavoidable that there will be some framework-specific details. In Code That Fits in Your Head, I made it an explicit point that while the examples in the book are in C#, the book (and the code in it) should be understandable by developers who normally use Java, C++, TypeScript, or similar C-based languages.

The book is, for that reason, light on .NET-specific details. Instead, I published an article that collects all the interesting .NET things I ran into while writing the book.

Not so here. The three articles cover enough ASP.NET particulars that readers who don't care about that framework are encouraged to skim-read.

I've developed the three examples as three branches of the same Git repository. The code is available upon request against a small support donation of 10 USD (or more). If you're one of my regular supporters, you have my gratitude and can get the code without further donation. Send me an email in both cases.

Conclusion #

There's more than one way to organize a code base to deal with data. Depending on context, one may be a better choice than another. Thus, it pays to be aware of alternatives.

In the remaining articles in this series, you'll see three examples of how to deal with persistent data from a database. In order to establish a baseline, the first covers the well-known Ports and Adapters architecture.

Next: Using Ports and Adapters to persist restaurant table configurations.

This blog is totally free, but if you like it, please consider supporting it.

The end of trust?

2024-07-15T19:07:00+00:00

Software development in a globalized, hostile world.

Imagine that you're perusing the thriller section in an airport book store and come across a book with the following back cover blurb:

Programmers are dying.

Holly-Ann Kerr works as a data scientist for an NGO that fights workplace discrimination. While scrubbing input, she discovers an unusual pattern in the data. Some employees seem to have an unusually high fatal accident rate. Programmers are dying in traffic accidents, falling on stairs, defect electrical wiring, smoking in bed. They work for a variety of companies. Some for Big Tech, others for specialized component vendors, some for IT-related NGOs, others again for utility companies. The deaths seem to have nothing in common, until H-A uncovers a disturbing pattern.

All victims had recently started in a new position. And all were of Iranian descent.

Is a racist killer on the loose? But if so, why is he only targeting new hires? And why only software developers?

When H-A shares her discovery with the wrong people, she soon discovers that she'll be the next victim.

Okay, I'm not a professional editor, so this could probably do with a bit of polish. Does it sound like an exiting piece of fiction, though?

I'm going to spoil the plot, since the book doesn't exist anyway.

An international plot #

(Apologies to Iranian readers. I have nothing against Iranians, but find the regime despicable. In any case, nothing in the following hinges on the ICC. You can replace it with another adversarial intelligence agency that you don't like, including, but not limited to RGB, FSB, or a clandestine Chinese intelligence organization. You could probably even swap the roles and make CIA, MI5, or Mossad be the bad guys, if your loyalties lie elsewhere.)

In the story, it turns out that clandestine Iranian special operations are attempting to recruit moles in software organizations that constitute the supply chain of Western digital infrastructure.

Intelligence bureaus and software organizations that directly develop sensitive software tend to have good security measures. Planting a mole in such an organization is difficult. The entire supply chain of software dependencies, on the other hand, is much more vulnerable. If you can get an employee to install a backdoor in left-pad, chances are that you may attain remote execution capabilities on an ostensibly secure system.

In my hypothetical thriller, the Iranians kill those software developers that they fail to recruit. After all, one can't run a clandestine operation if people notify the police that they've been approached by a foreign power.

Long game #

Does that plot sound far-fetched?

I admit that I did turn to 11 some plot elements. This is, after all, supposed to be a thriller.

The story is, however, 'loosely based on real events'. Earlier this year, a Microsoft developer revealed a backdoor that someone had intentionally planted in xz Utils. That version of the software was close to being merged into Debian and Red Hat Linux distributions. It would have enabled an attacker to execute arbitrary code on an infected machine.

The attack was singularly sophisticated. It also looks as though it was initiated years ago by one or more persons who contributed real, useful work to an open-source project, apparently (in hindsight) with the sole intention of gaining the trust of the rest of the community.

This is such a long game that it reeks of an adversarial state actor. The linked article speculates on which foreign power may be behind the attack. No, not the Iranians, after all.

If you think about it, it's an entirely rational gambit for a foreign intelligence agency to make. It's not that the NSA hasn't already tried something comparable. If anything, the xz hack mostly seems far-fetched because it's so unnecessarily sophisticated.

Usually, the most effective hacking techniques utilize human trust or gullibility. Why spend enormous effort developing sophisticated buffer overrun exploits if you can get a (perhaps unwitting) insider to run arbitrary code for you?

It'd be much cheaper, and much more reliable, to recruit moles on the inside of software companies, and get them to add the backdoors you need. It doesn't necessary have to be new hires, but perhaps (I'm speculating) it's easier to recruit people before they've developed any loyalty to their new team mates.

The soft underbelly #

Which software organizations are the most promising targets? If it were me, I'd particularly try to go after various component vendors. One category may be companies that produce RAD tools such as grid GUIs, but also service providers that offer free SDKs to, say, send email, generate invoices, send SMS, charge credit cards, etc.

I'm not implying that any such company has ill intent, but since such software run on many machines, it's a juicy target if you can sneak a backdoor into one.

Why not open-source software (OSS)? Many OSS libraries run on even more machines, so wouldn't that be an even more attractive target for an adversary? Yes, but on the other hand, most popular open-source code is also scrutinized by many independent agents, so it's harder to sneak in a backdoor. As the attempted xz hack demonstrates, even a year-long sophisticated attack is at risk of being discovered.

Doesn't commercial or closed-source code receive the same level of scrutiny?

In my experience, not always. Of course, some development organizations use proper shared-code-ownership techniques like code reviews or pair programming, but others rely on siloed solo development. Programmers just check in code that no-one else ever looks at.

In such an organization, imagine how easy it'd be for a mole to add a backdoor to a widely-distributed library. He or she wouldn't even have to resort to sophisticated ways to obscure the backdoor, because no colleague would be likely to look at the code. Particularly not if you bury it in seven levels of nested for loops and call the class MonitorManager or similar. As long as the reusable library ships as compiled code, it's unlikely that customers will discover the backdoor before its too late.

Trust #

Last year I published an article on trust in software development. The point of that piece wasn't that you should suspect your colleagues of ill intent, but rather that you can trust neither yourself nor your co-workers for the simple reason that people make mistakes.

Since then, I've been doing some work in the digital security space, and I've been forced to think about concerns like supply-chain attacks. The implications are, unfortunately, that you can't automatically trust that your colleague has benign intentions.

This, obviously, will vary with context. If you're only writing a small web site for your HR department to use, it's hard to imagine how an adversarial state actor could take advantage of a backdoor in your code. If so, it's unlikely that anyone will go to the trouble of planting a mole in your organization.

On the other hand, if you're writing any kind of reusable library or framework, you just might be an interesting target. If so, you can no longer entirely trust your team mates.

As a Dane, that bothers me deeply. Denmark, along with the other Nordic countries, exhibit the highest levels of inter-societal trust in the world. I was raised to trust strangers, and so far, it's worked well enough for me. A business transaction in Denmark is often just a short email exchange. It's a great benefit to the business environment, and the economy in general, that we don't have to waste a lot of resources filling out formulas, contracts, agreements, etc. Trust is grease that makes society run smoother.

Even so, Scandinavians aren't naive. We don't believe that we can trust everyone. To a large degree, we rely on a lot of subtle social cues to assess a given situation. Some people shouldn't be trusted, and we're able to identify those situations, too.

What remains is that insisting that you can trust your colleague, just because he or she is your colleague, would be descending into teleology. I'm not a proponent of wishful thinking if good arguments suggest the contrary.

Shared code ownership #

Perhaps you shouldn't trust your colleagues. How does that impact software development?

The good news is that this is yet another argument to practice the beneficial practices of shared code ownership. Crucially, what this should entail is not just that everyone is allowed to edit any line of code, but rather that all team members take responsibility for the entire code base. No-one should be allowed to write code in splendid isolation.

There are several ways to address this concern. I often phrase it as follows: There should be at least two pair of eyes on every line of code before a merge to master.

As I describe in Code That Fits in Your Head, you can achieve that goal with pair programming, ensemble programming, or code reviews (including agile pull request reviews). That's a broad enough palette that it should be possible for every developer in every organization to find a modus vivendi that fits any personality and context.

Just looking at each others' code could significantly raise the bar for a would-be mole to add a backdoor to the code base. As an added benefit, it might also raise the general code quality.

What this does suggest to me, however, is that a too simplistic notion of running on trunk may be dangerous. Letting everyone commit to master and trusting that everyone means well no longer strikes me as a good idea (again, given the context, and all that).

Or, if you do, you should consider having some sort of systematic posterior ~~post mortem~~ review process. I've read of organizations that do that, but specific sources escape me at the moment. With Git, however, it's absolutely within the realms of the possible to make a diff of all change since the last ex-post review, and then go through those changes.

Conclusion #

The world is changed. I feel it in the OWASP top 10. I sense it in the shifting geopolitical climate. I smell it on the code I review.

Much that once was, is lost. The dream of a global computer network with boundless trust is no more. There are countries whose interests no longer align with ours. Who pay full-time salaries to people whose job it is to wage 'cyber warfare' against us. We can't rule out that parts of such campaigns include planting moles in our midsts. Moles whose task it is to weaken the foundations of our digital infrastructure.

In that light, should you always trust your colleagues?

Despite the depressing thought that I probably shouldn't, I'm likely to bounce back to my usual Danish most-people-are-to-be-trusted attitude tomorrow. On the other hand, I'll still insist that more than one person is involved with every line of code. Not only because every other person may be a foreign agent, but mostly, still, because humans are fallible, and two brains think better than one.

Comments

Tyson Williams #

Or, if you do, you should consider having some sort of systematic post mortem review process. I've read of organizations that do that, but specific sources escape me at the moment.

My company has a Google Docs template for postmortem analysis that we use when something goes especially wrong. The primary focus is stating what went wrong according to the "five whys technique". Our template links to this post by Eric Ries. There is alsothis Wikipedia article on the subject. The section heading are "What happened" (one sentence), "Impact on Customers" (duration and severity), "What went wrong (5 Whys)", "What went right (optional)", "Corrective Actions" (and all of the content so far should be short enough to fit on one page), "Timeline" (a bulleted list asking for "Event beginning", "Time to Detect (monitoring)", "Time to Notify (alerting)", "Time to Respond (devops)", "Time to Troubleshoot (devops)", "Time to Mitigate (devops)", "Event end"), "Logs (optional)".

2024-07-21 15:37 UTC

Mark Seemann #

Tyson, thank you for writing. I now realize that 'post mortem' was a poor choice of words on my part, since it implies that something went wrong. I should have written 'posterior' instead. I'll update the article.

I've been digging around a bit to see if I can find the article that originally made me aware of that option. I'm fairly sure that it wasn't Optimizing the Software development process for continuous integration and flow of work, but that article, on the other hand, seems to be the source that other articles cite. It's fairly long, and also discusses other concepts; the relevant section here is the one called Non-blocking reviews.

An shorter overview of this kind of process can be found in Non-Blocking, Continuous Code Reviews - a case study.

2024-07-26 08:04 UTC

Jiehong #

In change management/risk control, your There should be at least two pair of eyes on every line of code is called four eye principle, and is a standard practice in my industry (IT services provider for the travel industry).

It goes further, and requires 2 more pair of eyes for any changes from the code review, to the load of a specific software in production.

I has a nice side-effect during code reviews: it's an automatic way to dessiminate knowledge in the team, so the bus factor is never 1.

I think that real people can mostly be trusted. But, software is not always run by people. Even when it is, a single non-trust-worthy person's action is amplified by software being run by mindless computers. It's like one rotten apple is enough to poison the full bag.

In the end, and a bit counter-intuitively, trusting people less now is leading to being able to trust more soon: people are forced to say "you can trust me, and here are the proofs". (Eg: the recently announced Apple's Private Cloud Compute).

2024-07-29 14:29 UTC

Mark Seemann #

Jiehong, thank you for writing. Indeed, in Code That Fits in Your Head I discuss how shared code ownership reduces the bus factor.

From this article and previous discussions I've had, I can see that the term trust is highly charged. People really don't like the notion that trust may be misplaced, or that mistrust, even, might be appropriate. I can't tell if it's a cultural bias of which I'm not aware. While English isn't my native language, I believe that I'm sufficiently acquainted with anglo-saxon culture to know of its most obvious quirks. Still, I'm sometimes surprised.

I admit that I, too, first consider whether I'm dealing with a deliberate adversary if I'm asked whether I trust someone, but soon after, there's a secondary interpretation that originates from normal human fallibility. I've already written about that: No, I don't trust my colleagues to be infallible, as I don't trust myself to be so.

Fortunately, it seems to me that the remedies that may address such concerns are the same, regardless of the underlying reasons.

2024-08-06 05:57 UTC

This blog is totally free, but if you like it, please consider supporting it.

Should interfaces be asynchronous?

2024-07-08T13:52:00+00:00

Async and await are notorious for being contagious. Must all interfaces be Task-based, just in case?

I recently came across this question on Mastodon:

"To async or not to async?

"How would you define a library interface for a service that probably will be implemented with an in memory procedure - let's say returning a mapped value to a key you registered programmatically - and a user of your API might want to implement a decorator that needs a 'long running task' - for example you want to log a msg into your db or load additional mapping from a file?

"Would you define the interface to return a Task<string> or just a string?"

Fandermill

While seemingly a simple question, it's both fundamental and turns out to have deeper implications than you may at first realize.

Interpretation #

Before I proceed, I'll make my interpretation of the question more concrete. This is just how I interpret the question, so doesn't necessarily reflect the original poster's views.

The post itself doesn't explicitly mention a particular language, and since several languages now have async and await features, the question may be of more general interest that a question constrained to a single language. On the other hand, in order to have something concrete to discuss, it'll be useful with some real code examples. From perusing the discussion surrounding the original post, I get the impression that the language in question may be C#. That suits me well, since it's one of the languages with which I'm most familiar, and is also a language where programmers of other C-based languages should still be able to follow along.

My interpretation of the implementation, then, is this:

public sealed class NameMap
{
    private readonly Dictionary<Guid, string> knownIds = new()
    {
        { new Guid("4778CA3D-FB1B-4665-AAC1-6649CEFA4F05"), "Bob" },
        { new Guid("8D3B9093-7D43-4DD2-B317-DCEE4C72D845"), "Alice" }
    };
 
    public string GetName(Guid guid)
    {
        return knownIds.TryGetValue(guid, out var name) ? name : "Trudy";
    }
}

Nothing fancy, but, as Fandermill writes in a follow-up post:

"Used examples that first came into mind, but it could be anything really."

Fandermill

The point, as I understand it, is that the intended implementation doesn't require asynchrony. A Decorator, on the other hand, may.

Should we, then, declare an interface like the following?

public interface INameMap
{
    Task<string> GetName(Guid guid);
}

If we do, the NameMap class can't automatically implement that interface because the return types of the two GetName methods don't match. What are the options?

Conform #

While the following may not be the 'best' answer, let's get the obvious solution out of the way first. Let the implementation conform to the interface:

public sealed class NameMap : INameMap
{
    private readonly Dictionary<Guid, string> knownIds = new()
    {
        { new Guid("4778CA3D-FB1B-4665-AAC1-6649CEFA4F05"), "Bob" },
        { new Guid("8D3B9093-7D43-4DD2-B317-DCEE4C72D845"), "Alice" }
    };
 
    public Task<string> GetName(Guid guid)
    {
        return Task.FromResult(
            knownIds.TryGetValue(guid, out var name) ? name : "Trudy");
    }
}

This variation of the NameMap class conforms to the interface by making the GetName method look asynchronous.

We may even keep the synchronous implementation around as a public method if some client code might need it:

public sealed class NameMap : INameMap
{
    private readonly Dictionary<Guid, string> knownIds = new()
    {
        { new Guid("4778CA3D-FB1B-4665-AAC1-6649CEFA4F05"), "Bob" },
        { new Guid("8D3B9093-7D43-4DD2-B317-DCEE4C72D845"), "Alice" }
    };
 
    public Task<string> GetName(Guid guid)
    {
        return Task.FromResult(GetNameSync(guid));
    }
 
    public string GetNameSync(Guid guid)
    {
        return knownIds.TryGetValue(guid, out var name) ? name : "Trudy";
    }
}

Since C# doesn't support return-type-based overloading, we need to distinguish these two methods by giving them different names. In C# it might be more idiomatic to name the asynchronous method GetNameAsync and the synchronous method just GetName, but for reasons that would be too much of a digression now, I've never much liked that naming convention. In any case, I'm not going to go in this direction for much longer, so it hardly matters how we name these two methods.

Kinds of interfaces #

Another digression is, however, quite important. Before we can look at some more code, I'm afraid that we have to perform a bit of practical ontology, as it were. It starts with the question: Why do we even need interfaces?

I should also make clear, as a digression within a digression, that by 'interface' in this context, I'm really interested in any kind of mechanism that enables you to achieve polymorphism. In languages like C# or Java, we may in fact avail ourselves of the interface keyword, as in the above INameMap example, but we may equally well use a base class or perhaps just what C# calls a delegate. In other languages, we may use function or action types, or even function pointers.

Regardless of specific language constructs, there are, as far as I can tell, two kinds of interfaces:

Interfaces that enable variability or extensibility in behaviour.
Interfaces that mostly or exclusively exist to support automated testing.

While there may be some overlap between these two kinds, in my experience, the intersection between the two tends to be surprisingly small. Interfaces tend to mostly belong to one of those two categories.

Strategies and higher-order functions #

In design-patterns parlance, examples of the first kind are Builder, State, Chain of Responsibility, Template Method, and perhaps most starkly represented by the Strategy pattern. A Strategy is an encapsulated piece of behaviour that you pass around as a single 'thing' (an object).

And granted, you could also use a Strategy to access a database or make a web-service call, but that's not how the pattern was originally described. We'll return to that use case in the next section.

Rather, the first kind of interface exists to enable extensibility or variability in algorithms. Typical examples (from Design Patterns) include page layout, user interface component rendering, building a maze, finding the most appropriate help topic for a given application context, and so on. If we wish to relate this kind of interface to the SOLID principles, it mostly exists to support the Open-closed principle.

A good heuristics for identifying such interfaces is to consider the Reused Abstractions Principle (Jason Gorman, 2010, I'd link to it, but the page has fallen off the internet. Use your favourite web archive to read it.). If your code base contains multiple production-ready implementations of the same interface, you're reusing the interface, most likely to vary the behaviour of a general-purpose data structure.

And before the functional-programming (FP) crowd becomes too smug: FP uses this kind of interface all the time. In the FP jargon, however, we rather talk about higher-order functions and the interfaces we use to modify behaviour are typically modelled as functions and passed as lambda expressions. So when you write Cata((_, xs) => xs.Sum(), _ => 1) (as one does), you might as well just have passed a Visitor implementation to an Accept method.

This hints at a more quantifiable distinction: If the interface models something that's intended to be a pure function, it'd typically be part of a higher-order API in FP, while we in object-oriented design (once again) lack the terminology to distinguish these interfaces from the other kind.

These days, in C# I mostly use these kinds of interfaces for the Visitor pattern.

Seams #

The other kind of interface exists to afford automated testing. In Working Effectively with Legacy Code, Michael Feathers calls such interfaces Seams. Modern object-oriented code bases often use Dependency Injection (DI) to control which Strategies are in use in a given context. The production system may use an object that communicates with a relational database, while an automated test environment might replace that with a Test Double.

Yes, I wrote Strategies. As I suggested above, a Strategy is really a replaceable object in its purest form. When you use DI you may call all those interfaces IUserRepository, ICommandHandler, IEmailGateway, and so on, but they're really all Strategies.

Contrary to the first kind of interface, you typically only find a single production implementation of each of these interfaces. If you find more that one, the rest are usually Decorators (one that logs, one that caches, one that works as a Circuit Breaker, etc.). All other implementations will be defined in the test code as dynamic mocks or Fakes.

Code bases that rely heavily on DI in order to support testing rub many people the wrong way. In 2014 David Heinemeier Hansson published a serious criticism of such test-induced damage. For the record, I agree with the criticism, but not with the conclusion. While I still practice test-driven development, I only define interfaces for true architectural dependencies. So, yes, my code bases may have an IReservationsRepository or IEmailGateway, but no ICommandHandler or IUserManager.

The bottom line, though, is that some interfaces exist to support testing. If there's a better way to make inherently non-deterministic systems behave deterministically in a test context, I've yet to discover it.

(As an aside, it's worth looking into tests that adopt non-deterministic behaviour as a driving principle, or at least an unavoidable state of affairs. Property-based testing is one such approach, but I also found the article When I'm done, I don't clean up by Arialdo Martini interesting. You may also want to refer to my article Waiting to happen for a discussion of how to make tests independent of system time.)

Where to define interfaces #

The reason the above distinction is important is that it fundamentally determines where interfaces should be defined. In short, the first kind of interface is part of an object model's API, and should be defined together with that API. The second kind, on the other hand, is part of a particular application's architecture, and should be defined by the client code that talks to the interface.

As an example of the first kind, consider this recent example, where the IPriorityEditor<T> interface is part of the PriorityCollection<T> API. You must ship the interface together with the class, because the Edit method takes an interface implementation as an argument. It's how client code interacts with the API.

Another example is this Table class that comes with an ITableVisitor<T> interface. In both cases, we'd expect interface implementations to be deterministic. These interfaces don't exist to support automated testing, but rather to afford a flexible programming model.

For the sake of argument, imagine that you package such APIs in reusable libraries that you publish via a package manager. In that case, it's obvious that the interface is as much part of the package as the class.

Contrast this with the other kind of interface, as described in the article Decomposing CTFiYH's sample code base or showcased in the article An example of state-based testing in C#. In the latter example, the interfaces IUserReader and IUserRepository are not part of any pre-packaged library. Rather, they are defined by the application code to support application-specific needs.

This may be even more evident if you contemplate the diagram in Decomposing CTFiYH's sample code base. Interfaces like IPostOffice and IReservationsRepository only exist to support the application. Following the Dependency Inversion Principle

"clients [...] own the abstract interfaces"

Robert C. Martin, APPP, chapter 11

In these code bases, only the Controllers (or rather the tests that exercise them) need these interfaces, so the Controllers get to define them.

Should it be asynchronous, then? #

Okay, so should INameMap.GetName return string or Task<string>, then?

Hopefully, at this point, it should be clear that the answer depends on what kind of interface it is.

If it's the first kind, the return type should support the requirements of the API. If the object model doesn't need the return type to be asynchronous, it shouldn't be.

If it's the second kind of interface, the application code decides what it needs, and defines the interface accordingly.

In neither case, however, is it the concrete class' responsibility to second-guess what client code might need.

But client code may need the method to be asynchronous. What's the harm of returning Task<string>, just in case?

The problem, as you may well be aware, is that the asynchronous programming model is contagious. Once you've made an API asynchronous, you can't easily make it synchronous, whereas if you have a synchronous API, you can easily make it asynchronous. This follows from Postel's law, in this case: Be conservative with what you send.

Library API #

Imagine, for the sake of argument, that the NameMap class is defined in a reusable library, wrapped in a package and imported into your code base via a package manager (NuGet, Maven, pip, NPM, Hackage, RubyGems, etc.).

Clearly it shouldn't implement any interface in order to 'support unit testing', since such interfaces should be defined by application code.

It could implement one or more 'extensibility' interfaces, if such interfaces are part of the wider API offered by the library. In the case of the NameMap class, we don't really know if that's the case. To complete this part of the argument, then, I'd just leave it as shown in the first code example, shown above. It doesn't need to implement any interface, and GetName can just return string.

Domain Model #

What if, instead of an external library, the NameMap class is part of an application's Domain Model?

In that case, you could define application-level interfaces as part of the Domain Model. In fact, most people do. Even so, I'd recommend that you don't, at least if you're aiming for a Functional Core, Imperative Shell architecture, a functional architecture, or even a Ports and Adapters or, if you will, Clean Architecture. The interfaces that exist only to support testing are application concerns, so keep them out of the Domain Model and instead define them in the Application Model.

You don't have to follow my advice. If you want to define interfaces in the Domain Model, I can't stop you. But what if, as I recommend, you define application-specific interfaces in the Application Model? If you do that, your NameMap Domain Model can't implement your INameMap interface, because the dependencies point the other way, and most languages will not allow circular dependencies.

In that case, what do you do if, as the original toot suggested, you need to Decorate the GetName method with some asynchronous behaviour?

You can always introduce an Adapter:

public sealed class NameMapAdapter : INameMap
{
    private readonly NameMap imp;
 
    public NameMapAdapter(NameMap imp)
    {
        this.imp = imp;
    }
 
    public Task<string> GetName(Guid guid)
    {
        return Task.FromResult(imp.GetName(guid));
    }
}

Now any NameMap object can look like an INameMap. This is exactly the kind of problem that the Adapter pattern addresses.

But, you say, that's too much trouble! I don't want to have to maintain two classes that are almost identical.

I understand the concern, and it may even be appropriate. Maybe you're right. As usual, I don't really intend this article to be prescriptive. Rather, I'm offering ideas for your consideration, and you can choose to adopt them or ignore them as it best fits your context.

When it comes to whether or not an Adapter is an unwarranted extra complication, I'll return to that topic later in this article.

Application Model #

The final architectural option is when the concrete NameMap class is part of the Application Model, where you'd also define the application-specific INameMap interface. In that case, we must assume that the NameMap class implements some application-specific concern. If you want it to implement an interface so that you can wrap it in a Decorator, then do that. This means that the GetName method must conform to the interface, and if that means that it must be asynchronous, then so be it.

As Kent Beck wrote in a Facebook article that used to be accessible without a Facebook account (but isn't any longer):

"Things that change at the same rate belong together. Things that change at different rates belong apart."

Naming From the Outside In, Kent Beck, Facebook, 2012

If the concrete NameMap class and the INameMap interface are both part of the application model, it's not unreasonable to guess that they may change together. (Do be mindful of Shotgun Surgery, though. If you expect the interface and the concrete class to frequently change, then perhaps another design might be more appropriate.)

Easier Adapters #

Before concluding this article, let's revisit the topic of introducing an Adapter for the sole purpose of 'architectural purity'. Should you really go to such lengths only to 'do it right'? You decide, but

You can only be pragmatic if you know how to be dogmatic.

What to test and not to test, me

I'm presenting a dogmatic solution for your consideration, so that you know what it might look like. Would I follow my own 'dogmatic' advice? Yes, I usually do, but then, I wouldn't log the return value of a pure function, so I wouldn't introduce an interface for that purpose, at least. To be fair to Fandermill, he or she also wrote: "or load additional mapping from a file", which could be an appropriate motivation for introducing an interface. I'd probably go with an Adapter in that case.

Whether or not an Adapter is an unwarranted complication depends, however, on language specifics. In high-ceremony languages like C#, Java, or C++, adding an Adapter involves at least one new file, and dozens of lines of code.

Consider, on the other hand, a low-ceremony language like Haskell. The corresponding getName function might close over a statically defined map and have the type getName :: UUID -> String.

How do you adapt such a pure function to an API that returns IO (which is roughly comparable to task-based programming)? Trivially:

getNameM :: Monad m => UUID -> m String
getNameM = return . getName

For didactic purposes I have here shown the 'Adapter' as an explicit function, but in idiomatic Haskell I'd consider this below the Fairbairn threshold; I'd usually just inline the composition return . getName if I needed to adapt the getName function to the Kleisli category.

You can do the same in F#, where the composition would be getName >> Task.FromResult. F# compositions usually go in the (for Westerners) intuitive left-to-right directions, whereas Haskell compositions follow the mathematical right-to-left convention.

The point, however, is that there's nothing conceptually complicated about an Adapter. Unfortunately, however, some languages require substantial ceremony to implement them.

Conclusion #

Should an API return a Task-based (asynchronous) value 'just in case'? In general: No.

You can't predict all possible use cases, so don't make an API more complicated than it has to be. If you need to implement an application-specific interface, use the Adapter design pattern.

A possible exception to this rule is if the entire API (the concrete implementation and the interface) only exists to support a specific application. If the interface and its concrete implementation are both part of the Application Model, you may as well skip the Adapter step and consider the concrete implementation as its own Adapter.

This blog is totally free, but if you like it, please consider supporting it.

An immutable priority collection

2024-07-01T17:28:00+00:00

With examples in C# and F#.

This article is part of a series about encapsulation and immutability. After two attempts at an object-oriented, mutable implementation, I now turn toward immutability. As already suggested in the introductory article, immutability makes it easier to maintain invariants.

In the introductory article, I described the example problem in more details, but in short, the exercise is to develop a class that holds a collection of prioritized items, with the invariant that the priorities must always sum to 100. It should be impossible to leave the object in a state where that's not true. It's quite an illuminating exercise, so if you have the time, you should try it for yourself before reading on.

Initialization #

Once again, I begin by figuring out how to initialize the object, and how to model it. Since it's a kind of collection, and since I now plan to keep it immutable, it seems natural to implement IReadOnlyCollection<T>.

In this, the third attempt, I'll reintroduce Prioritized<T>, with one important difference. It's now an immutable record:

public sealed record Prioritized<T>(T Item, byte Priority);

If you're not on a version of C# that supports records (which is also trivially true if you're not using C# at all), you can always define an immutable class by hand. It just requires more boilerplate code.

Prioritized<T> is going to be the T in the IReadOnlyCollection<T> implementation:

public sealed class PriorityCollection<T> : IReadOnlyCollection<Prioritized<T>>

Since an invariant should always hold, it should also hold at initialization, so the PriorityCollection<T> constructor must check that all is as it should be:

private readonly Prioritized<T>[] priorities;
 
public PriorityCollection(params Prioritized<T>[] priorities)
{
    if (priorities.Sum(p => p.Priority) != 100)
        throw new ArgumentException(
            "The sum of all priorities must be 100.",
            nameof(priorities));
    this.priorities = priorities;
}

The rest of the class is just the IReadOnlyCollection<T> implementation, which just delegates to the priorities field.

That's it, really. That's the API. We're done.

Projection #

But, you may ask, how does one edit such a collection?

(Comic originally by John Muellerleile.)

Humour aside, you don't edit an immutable object, but rather make a new object from a previous one. Most modern languages now come with built-in collection-projection APIs; in .NET, it's called LINQ. Here's an example. You begin with a collection with two items:

var pc = new PriorityCollection<string>(
    new Prioritized<string>("foo", 60),
    new Prioritized<string>("bar", 40));

You'd now like to add a third item with priority 20:

var newPriority = new Prioritized<string>("baz", 20);

How should you make room for this new item? One option is to evenly reduce each of the existing priorities:

var reduction = newPriority.Priority / pc.Count;
IEnumerable<Prioritized<string>> reduced = pc
    .Select(p => p with { Priority = (byte)(p.Priority - reduction) });

Notice that while the sum of priorities in reduced no longer sum to 100, it's okay, because reduced isn't a PriorityCollection object. It's just an IEnumerable<Prioritized<string>>.

You can now Append the newPriority to the reduced sequence and repackage that in a PriorityCollection:

var adjusted = new PriorityCollection<string>(reduced.Append(newPriority).ToArray());

Like the original pc object, the adjusted object is valid upon construction, and since its immutable, it'll remain valid.

Edit #

If you think this process of unwrapping and rewrapping seems cumbersome, we can make it a bit more palatable by defining a wrapping Edit function, similar to the one in the previous article:

public PriorityCollection<T> Edit(
    Func<IReadOnlyCollection<Prioritized<T>>, IEnumerable<Prioritized<T>>> edit)
{
    return new PriorityCollection<T>(edit(this).ToArray());
}

You can now write code equivalent to the above example like this:

var adjusted = pc.Edit(col =>
{
    var reduced = col.Select(p => p with { Priority = (byte)(p.Priority - reduction) });
    return reduced.Append(newPriority);
});

I'm not sure it's much of an improvement, though.

Using the right tool for the job #

While C# over the years has gained some functional-programming features, it's originally an object-oriented language, and working with immutable values may still seem a bit cumbersome. If so, consider using a language natively designed for this style of programming. On .NET, F# is the obvious choice.

First, you define the required types:

type Prioritized<'a> = { Item: 'a; Priority: byte }
 
type PriorityList = private PriorityList of Prioritized<string> list

Notice that PriorityList has a private constructor, so that client code can't just create any value. The type should protect its invariants, since encapsulation is also relevant in functional programming. Since client code can't directly create PriorityList objects, you instead supply a function for that purpose:

module PriorityList =
    let tryCreate priorities =
        if priorities |> List.sumBy (_.Priority) = 100uy
        then Some (PriorityList priorities)
        else None

That's really it, although you also need a way to work with the data. We supply two alternatives that correspond to the above C#:

let edit f (PriorityList priorities) = f priorities |> tryCreate
 
let toList (PriorityList priorities) = priorities

These functions are also defined on the PriorityList module.

Here's the same adjustment example as shown above in C#:

let pl  =
    [ { Item = "foo"; Priority = 60uy }; { Item = "bar"; Priority = 40uy } ]
    |> PriorityList.tryCreate
let newPriority = { Item = "baz"; Priority = 20uy }
let adjusted =
    pl
    |> Option.bind (PriorityList.edit (fun l ->
        l
        |> List.map (fun p ->
            { p with Priority = p.Priority - (newPriority.Priority / byte l.Length) })
        |> List.append [ newPriority ]))

The entire F# definition is 15 lines of code, including namespace declaration and blank lines.

Conclusion #

With an immutable data structure, you only need to check the invariants upon creation. Invariants therefore become preconditions. Once a value is created in a valid state, it stays valid because it never changes state.

If you're having trouble maintaining invariants in an object-oriented design, try making the object immutable. It's likely to make it easier to attain good encapsulation.

Comments

Jiehong #

First, it's a nice series of articles.

I see that nowadays C# has a generic projection, which is a sort of wither in Java parlance. I should be usable instead of having to define the `Edit` one.

A way to make it more palatable would be to have a `tryAddAndRedistrube(Prioritized element) : PriorityCollection | None` method to `PriorityCollection` that would try to reduce priorities of elements, before adding the new one and returning a new `PriorityCollection` using that same `with` projection. This would allow the caller to have a slightly simpler method to call, at the expense of having to store the new collection and assuming this is the intended way the caller wants to insert the element.

But, it's usually not possible to anticipate all the ways the clients wants to add elements to something, so I think I prefer the open-ended way this API lets clients choose.

2024-07-29 13:53 UTC

Mark Seemann #

Thank you for writing. Whether or not a wither works in this case depends on language implementation details. For example, the F# example code doesn't allow copy-and-update expressions because the record constructor is private. This is as it should be, since otherwise, client code would be able to circumvent the encapsulation.

I haven't tried to refactor the C# class to a record, and I don't recall whether C# with expressions respect custom constructors. That's a good exercise for any reader to try out; unfortunately, I don't have time for that at the moment.

As to your other point, it's definitely conceivable that a library developer could add more convenient methods to the PriorityCollection<T> class, including one that uses a simple formula to redistribute existing priorities to make way for the new one. As far as I can tell, though, you'd be able to implement such more convenient APIs as extension methods that are implemented using the basic affordances already on display here. If so, we may consider the constructor and the IReadOnlyCollection<Prioritized<T>> interface as the fundamental API. Everything else, including the Edit method, could build off that.

2024-07-30 06:46 UTC

This blog is totally free, but if you like it, please consider supporting it.

A mutable priority collection

2024-06-24T17:59:00+00:00

An encapsulated, albeit overly complicated, implementation.

This is the second in a series of articles about encapsulation and immutability. In the next article, you'll see how immutability makes encapsulation easier, but in order to appreciate that, you should see the alternative. This article, then, shows a working, albeit overly complicated, implementation that does maintain its invariants.

Initialization #

As the previous article demonstrated, inheriting directly from a base class seems like a dead end. Once you see the direction that I go in this article, you may argue that it'd be possible to also make that design work with an inherited collection. It may be, but I'm not convinced that it would improve anything. Thus, for this iteration, I decided to eschew inheritance.

On the other hand, we need an API to query the object about its state, and I found that it made sense to implement the IReadOnlyDictionary interface.

As before, invariants are statements that are always true about an object, and that includes a newly initialized object. Thus, the PriorityCollection<T> class should require enough information to safely initialize.

public sealed class PriorityCollection<T> : IReadOnlyDictionary<T, byte> where T : notnull
{
    private readonly Dictionary<T, byte> dict;
 
    public PriorityCollection(T initial)
    {
        dict = new Dictionary<T, byte> { { initial, 100 } };
    }
 
    // IReadOnlyDictionary implemented by delegating to dict field...
}

Several design decisions are different from the previous article. This design has no Prioritized<T> class. Instead it treats the item (of type T) as a dictionary key, and the priority as the value. The most important motivation for this design decision was that this enables me to avoid the 'leaf node mutation' problem that I demonstrated in the previous article. Notice how, while the general design in this iteration will be object-oriented and mutable, I already take advantage of a bit of immutability to make the design simpler and safer.

Another difference is that you can't initialize a PriorityCollection<T> object with a list. Instead, you only need to tell the constructor what the initial item is. The constructor will then infer that, since this is the only item so far, its priority must be 100. It can't be anything else, because that would violate the invariant. Thus, no assertion is required in the constructor.

Mutation API #

So far, the code only implements the IReadOnlyDictionary API, so we need to add some methods that will enable us to add new items and so on. As a start, we can add methods to add, remove, or update items:

public void Add(T key, byte value)
{
    AssertInvariants(dict.Append(KeyValuePair.Create(key, value)));
    dict.Add(key, value);
}
 
public void Remove(T key)
{
    AssertInvariants(dict.Where(kvp => !kvp.Key.Equals(key)));
    dict.Remove(key);
}
 
public byte this[T key]
{
    get { return dict[key]; }
    set
    {
        var l = dict.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
        l[key] = value;
        AssertInvariants(l);
 
        dict[key] = value;
    }
}

I'm not going to show the AssertInvariants helper method yet, since it's going to change anyway.

At this point, the implementation suffers from the same problem as the example in the previous article. While you can add new items, you can only add an item with priority 0. You can only remove items if they have priority 0. And you can only 'update' an item if you set the priority to the same value as it already had.

We need to be able to add new items, change their priorities, and so on. How do we get around the above problem, without breaking the invariant?

Edit mode #

One way out of this conundrum is introduce a kind of 'edit mode'. The idea is to temporarily turn off the maintenance of the invariant for long enough to allow edits.

Af first glance, such an idea seems to go against the very definition of an invariant. After all, an invariant is a statement about the object that is always true. If you allow a client developer to turn off that guarantee, then, clearly, the guarantee is gone. Guarantees only work if you can trust them, and you can't trust them if they can be cancelled.

That idea in itself doesn't work, but if we can somehow encapsulate such an 'edit action' in an isolated scope that either succeeds or fails in its entirety, we may be getting somewhere. It's an idea similar to Unit of Work, although here we're not involving an actual database. Still, an 'edit action' is a kind of in-memory transaction.

For didactic reasons, I'll move toward that design in a series of step, where the intermediate steps fail to maintain the invariant. We'll get there eventually. The first step is to introduce 'edit mode'.

private bool isEditing;

While I could have made that flag public, I found it more natural to wrap access to it in two methods:

public void BeginEdit()
{
    isEditing = true;
}
 
public void EndEdit()
{
    isEditing = false;
}

This still doesn't accomplishes anything in itself, but the final change in this step is to change the assertion so that it respects the flag:

private void AssertInvariants(IEnumerable<KeyValuePair<T, byte>> candidate)
{
    if (!isEditing && candidate.Sum(kvp => kvp.Value) != 100)
        throw new InvalidOperationException(
            "The sum of all values must be 100.");
}

Finally, you can add or change priorities, as this little F# example shows:

sut.BeginEdit ()
sut["foo"] <- 50uy
sut["bar"] <- 50uy
sut.EndEdit ()

Even if you nominally 'don't read F#', this little example is almost like C# without semicolons. The <- arrow is F#'s mutation or assignment operator, which in C# would be =, and the uy suffix is the F# way of stating that the literal is a byte.

The above example is well-behaved because the final state of the object is valid. The priorities sum to 100. Even so, no code in PriorityCollection<T> actually checks that, so we could trivially leave the object in an invalid state.

Assert invariant at end of edit #

The first step toward remedying that problem is to add a check to the EndEdit method:

public void EndEdit()
{
    isEditing = false;
    AssertInvariants(dict);
}

The class is still not effectively protecting its invariants, because a client developer could forget to call EndEdit, or client code might pass around a collection in edit mode. Other code, receiving such an object as an argument, may not know whether or not it's in edit mode, so again, doesn't know if it can trust it.

We'll return to that problem shortly, but first, there's another, perhaps more pressing issue that we should attend to.

Edit dictionary #

The current implementation directly edits the collection, and even if a client developer remembers to call EndEdit, other code, higher up in the call stack could circumvent the check and leave the object in an invalid state. Not that I expect client developers to be deliberately malicious, but the notion that someone might wrap a method call in a try-catch block seems realistic.

The following F# unit test demonstrates the issue:

[<Fact>]
let ``Attempt to circumvent`` () =
    let sut = PriorityCollection<string> "foo"
 
    try
        sut.BeginEdit ()
        sut["foo"] <- 50uy
        sut["bar"] <- 48uy
        sut.EndEdit ()
    with _ -> ()
 
    100uy =! sut["foo"]
    test <@ sut.ContainsKey "bar" |> not @>

Again, let me walk you through it in case you're unfamiliar with F#.

The try-with block works just like C# try-catch blocks. Inside of that try-with block, the test enters edit mode, changes the values in such a way that the sum of them is 98, and then calls EndEdit. While EndEdit throws an exception, those four lines of code are wrapped in a try-with block that suppresses all exceptions.

The test attempts to verify that, since the edit failed, the "foo" value should be 100, and there should be no "bar" value. This turns out not to be the case. The test fails. The edits persist, even though EndEdit throws an exception, because there's no roll-back.

You could probably resolve that defect in various ways, but I chose to address it by introducing two, instead of one, backing dictionaries. One holds the data that always maintains the invariant, and the other is a temporary dictionary for editing.

private Dictionary<T, byte> current;
private readonly Dictionary<T, byte> encapsulated;
private readonly Dictionary<T, byte> editable;
private bool isEditing;
 
public PriorityCollection(T initial)
{
    encapsulated = new Dictionary<T, byte> { { initial, 100 } };
    editable = [];
    current = encapsulated;
}

There are two dictionaries: encapsulated holds the always-valid list of priorities, while editable is the dictionary that client code will be editing when in edit mode. Finally, current is either of these: editable when the object is in edit mode, and encapsulated when it's not. Most of the existing code shown so far now uses current, which before was called dict. The important changes are in BeginEdit and EndEdit.

public void BeginEdit()
{
    isEditing = true;
 
    editable.Clear();
    foreach (var kvp in current)
        editable.Add(kvp.Key, kvp.Value);
    current = editable;
}

Besides setting the isEditing flag, BeginEdit now copies all data from current to editable, and then sets current to editable. Keep in mind that encapsulated still holds the original, valid values.

Now that I'm writing this, I'm not even sure if this method is re-entrant, in the following sense: What happens if client code calls BeginEdit, makes some changes, and then calls BeginEdit again? It's questions like these that I don't feel intelligent enough to feel safe that I always answer correctly. That's why I like functional programming better. I don't have to think so hard.

Anyway, this will soon become irrelevant, since BeginEdit and EndEdit will eventually become private methods.

The EndEdit method performs the inverse manoeuvre:

public void EndEdit()
{
    isEditing = false;
    try
    {
        AssertInvariants(current);
 
        encapsulated.Clear();
        foreach (var kvp in current)
            encapsulated.Add(kvp.Key, kvp.Value);
        current = encapsulated;
    }
    catch
    {
        current = encapsulated;
        throw;
    }
}

It first checks the invariant, and only copies the edited values to the encapsulated dictionary if the invariant still holds. Otherwise, it restores the original encapsulated values and rethrows the exception.

This helps to make the nature of editing 'transactional' in nature, but it doesn't address the issue that the collection is in an invalid state during editing, or that a client developer may forget to call EndEdit.

Edit action #

As the next step towards addressing that problem, we may now introduce a 'wrapper method' for that little object protocol:

public void Edit(Action<PriorityCollection<T>> editAction)
{
    BeginEdit();
    editAction(this);
    EndEdit();
}

As you can see, it just wraps that little call sequence so that you don't have to remember to call BeginEdit and EndEdit. My F# test code comes with this example:

sut.Edit (fun col ->
    col["bar"] <- 55uy
    col["baz"] <- 45uy
    col.Remove "foo"
)

The fun col -> part is just F# syntax for a lambda expression. In C#, you'd write it as col =>.

We're close to a solution. What remains is to make BeginEdit and EndEdit private. This means that client code can only edit a PriorityCollection<T> object through the Edit method.

Replace action with interface #

You may complain that this solution isn't properly object-oriented, since it makes use of Action<T> and requires that client code uses lambda expressions.

We can easily fix that.

Instead of the action, you can introduce a Command interface with the same signature:

public interface IPriorityEditor<T> where T : notnull
{
    void EditPriorities(PriorityCollection<T> priorities);
}

Next, change the Edit method:

public void Edit(IPriorityEditor<T> editor)
{
    BeginEdit();
    editor.EditPriorities(this);
    EndEdit();
}

Now you have a nice, object-oriented design, with no lambda expressions in sight.

Full code dump #

The final code is complex enough that it's easy to lose track of what it looks like, as I walk through my process. To make it easer, here's the full code for the collection class:

public sealed class PriorityCollection<T> : IReadOnlyDictionary<T, byte>
    where T : notnull
{
    private Dictionary<T, byte> current;
    private readonly Dictionary<T, byte> encapsulated;
    private readonly Dictionary<T, byte> editable;
    private bool isEditing;
 
    public PriorityCollection(T initial)
    {
        encapsulated = new Dictionary<T, byte> { { initial, 100 } };
        editable = [];
        current = encapsulated;
    }
 
    public void Add(T key, byte value)
    {
        AssertInvariants(current.Append(KeyValuePair.Create(key, value)));
        current.Add(key, value);
    }
 
    public void Remove(T key)
    {
        AssertInvariants(current.Where(kvp => !kvp.Key.Equals(key)));
        current.Remove(key);
    }
 
    public byte this[T key]
    {
        get { return current[key]; }
        set
        {
            var l = current.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
            l[key] = value;
            AssertInvariants(l);
 
            current[key] = value;
        }
    }
 
    public void Edit(IPriorityEditor<T> editor)
    {
        BeginEdit();
        editor.EditPriorities(this);
        EndEdit();
    }
 
    private void BeginEdit()
    {
        isEditing = true;
 
        editable.Clear();
        foreach (var kvp in current)
            editable.Add(kvp.Key, kvp.Value);
        current = editable;
    }
 
    private void EndEdit()
    {
        isEditing = false;
        try
        {
            AssertInvariants(current);
 
            encapsulated.Clear();
            foreach (var kvp in current)
                encapsulated.Add(kvp.Key, kvp.Value);
            current = encapsulated;
        }
        catch
        {
            current = encapsulated;
            throw;
        }
    }
 
    private void AssertInvariants(IEnumerable<KeyValuePair<T, byte>> candidate)
    {
        if (!isEditing && candidate.Sum(kvp => kvp.Value) != 100)
            throw new InvalidOperationException(
                "The sum of all values must be 100.");
    }
 
    public IEnumerable<T> Keys
    {
        get { return current.Keys; }
    }
 
    public IEnumerable<byte> Values
    {
        get { return current.Values; }
    }
 
    public int Count
    {
        get { return current.Count; }
    }
 
    public bool ContainsKey(T key)
    {
        return current.ContainsKey(key);
    }
 
    public IEnumerator<KeyValuePair<T, byte>> GetEnumerator()
    {
        return current.GetEnumerator();
    }
 
    public bool TryGetValue(T key, [MaybeNullWhen(false)] out byte value)
    {
        return current.TryGetValue(key, out value);
    }
 
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

The IPriorityEditor<T> interface remains as shown above.

Conclusion #

Given how simple the problem is, this solution is surprisingly complicated, and I'm fairly sure that it's not even thread-safe.

At least it does, as far as I can tell, protect the invariant that the sum of priorities must always be exactly 100. Even so, it's just complicated enough that I wouldn't be surprised if a bug is lurking somewhere. It'd be nice if a simpler design existed.

Next: An immutable priority collection.

Comments

Joker_vD #

Where does the notion come that a data structure invariant has to be true at all times? I am fairly certain that it's only required to be true at "quiescent" points of executions. That is, just as the loop invariant is only required to hold before and after each loop step but not inside the loop step, so is the data structure invariant is only required to hold before and after each invocation of its public methods.

This definition actually has an interesting quirk which is absent in the loop invariant: a data structure's method can't, generally speaking, call other public methods of the very same data structure because the invariant might not hold at this particular point of execution! I've been personally bitten by this a couple of times, and I've seen others tripping over this subtle point as well. You yourself notice it when you muse about the re-entrancy of the BeginEdit method.

Now, this particular problem is quite similar to the problem with inner iteration, and can be solved the same way, with the outer editor, as you've done, although I would have probably provided each editor with its own, separate editable dictionary because right now, the editors cannot nest/compose... but that'd complicate implementation even further.

2024-07-03 22:19 UTC

Mark Seemann #

Thank you for writing. As so many other areas of knowledge, the wider field of software development suffers from the problem of overlapping or overloaded terminology. The word invariant is just one of them. In this context, invariant doesn't refer to loop invariants, or any other kind of invariants used in algorithmic analysis.

As outlined in the introduction article, when discussing encapsulation, I follow Object-Oriented Software Construction (OOSC). In that seminal work, Bertrand Meyer proposes the notion of design-by-contract, and specifically decomposes a contract into three parts: preconditions, invariants, and postconditions.

Having actually read the book, I'm well aware that it uses Eiffel as an exemplar of the concept. This has led many readers to conflate design-by-contract with Eiffel, and (in yet another logical derailment) conclude that it doesn't apply to, say, Java or C# programming.

It turns out, however, to transfer easily to other languages, and it's a concept with much practical potential.

A major problem with object-oriented design is that most ideas about good design are too 'fluffy' to be of immediate use to most developers. Take the Single Responsibility Principle (SRP) as an example. It's seductively easy to grasp the overall idea, but turns out to be hard to apply. Being able to identify reasons to change requires more programming experience than most people have. Or rather, the SRP is mostly useful to programmers who already have that experience. Being too 'fluffy', it's not a good learning tool.

I've spent quite some time with development organizations and individual programmers eager to learn, but struggling to find useful, concrete design rules. The decomposition of encapsulation into preconditions, invariants, and postconditions works well as a concrete, almost quantifiable heuristic.

Does it encompass everything that encapsulation means? Probably not, but it's by far the most effective heuristic that I've found so far.

Since I'm currently travelling, I don't have my copy of OOSC with me, but as far as I remember, the notion that an invariant should be true at all times originates there.

In any case, if an invariant doesn't always hold, then of what value is it? The whole idea behind encapsulation (as I read Meyer) is that client developers should be able to use 'objects' without having intimate knowledge of their implementation details. The use of contracts proposes to achieve that ideal by decoupling affordances from implementation details by condensing the legal protocol between object and client code into a contract. This means that a client developer, when making programming decisions, should be able to trust that certain guarantees stipulated by a contract always hold. If a client developer can't trust those guarantees, they aren't really guarantees.

"the data structure invariant is only required to hold before and after each invocation of its public methods"

I can see how a literal reading of OOSC may leave one with that impression. One must keep in mind, however, that the book was written in the eighties, at a time when multithreading wasn't much of a concern. (Incidentally, this is an omission that also mars a much later book on API design, the first edition of the .NET Framework Design Guidelines.)

In modern code, concurrent execution is a real possibility, so is at least worth keeping in mind. I'm still most familiar with the .NET ecosystem, and in it, there are plenty of classes that are documented as not being thread-safe. You could say that such a statement is part of the contract, in which case what you wrote is true: The invariant is only required to hold before and after each method invocation.

If, on the other hand, you want to make the code thread-safe, you must be more rigorous than that. Then an invariant must truly always hold.

This is, of course, a design decision one may take. Just don't bother with thread-safety if it's not important.

Still, the overall thrust of this article series is that immutability makes encapsulation much simpler. This is also true when it comes to concurrency. Immutable data structures are automatically thread-safe.

2024-07-06 8:07 UTC

This blog is totally free, but if you like it, please consider supporting it.

A failed attempt at priority collection with inheritance

2024-06-17T08:04:00+00:00

An instructive dead end.

This article is part of a short series on encapsulation and immutability. As the introductory article claims, object mutation makes it difficult to maintain invariants. In order to demonstrate the problem, I deliberately set out to do it wrong, and report on the result.

In subsequent articles in this series I will then show one way you can maintain the invariants in the face of mutation, as well as how much easier everything becomes if you choose an immutable design.

For now, however, I'll pretend to be naive and see how far I can get with that.

In the first article, I described the example problem in more details, but in short, the exercise is to develop a class that holds a collection of prioritized items, with the invariant that the priorities must always sum to 100. It should be impossible to leave the object in a state where that's not true. It's quite an illuminating exercise, so if you have the time, you should try it for yourself before reading on.

Initialization #

In object-oriented design it's common to inherit from a base class. Since I'll try to implement a collection of prioritized items, it seems natural to inherit from Collection<T>:

public sealed class PriorityCollection<T> : Collection<Prioritized<T>>

Of course, I also had to define Prioritized<T>:

public sealed class Prioritized<T>
{
    public Prioritized(T item, byte priority)
    {
        Item = item;
        Priority = priority;
    }
 
    public T Item { get; set; }
    public byte Priority { get; set; }
}

Since Prioritized<T> is generic, it can be used to prioritize any kind of object. In the tests I wrote, however, I exclusively used strings.

A priority is a number between 0 and 100, so I chose to represent that with a byte. Not that this strongly protects invariants, because values can still exceed 100, but on the other hand, there's no reason to use a 32-bit integer to model a number between 0 and 100.

Now that I write this text, I realize that I could have added a Guard Clause to the Prioritized<T> constructor to enforce that precondition, but as you can tell, I didn't think of doing that. This omission, however, doesn't change the conclusion, because the problems that we'll run into stems from another source.

In any case, just inheriting from Collection<Prioritized<T>> isn't enough to guarantee the invariant that the sum of priorities must be 100. An invariant must always hold, even for a newly initialized object. Thus, we need something like this ensure that this is the case:

public sealed class PriorityCollection<T> : Collection<Prioritized<T>>
{
    public PriorityCollection(params Prioritized<T>[] priorities)
        : base(priorities)
    {
        AssertSumIsOneHundred();
    }
 
    private void AssertSumIsOneHundred()
    {
        if (this.Sum(p => p.Priority) != 100)
            throw new InvalidOperationException(
                "The sum of all priorities must be 100.");
    }
}

So far, there's no real need to have a separate AssertSumIsOneHundred helper method; I could have kept that check in the constructor, and that would have been simpler. I did, however, anticipate that I'd need the helper method in other parts of the code base. As it turned out, I did, but not without having to change it.

Protecting overrides #

The Collection<T> base class offers normal collection methods like Add, Insert, Remove and so on. The default implementation allows client code to make arbitrary changes to the collection, including clearing it. The PriorityCollection<T> class can't allow that, because such edits could easily violate the invariants.

Collection<T> is explicitly designed to be a base class, so it offers various virtual methods that inheritors can override to change the behaviour. In this case, this is necessary.

As it turned out, I quickly realized that I had to change my assertion helper method to check the invariant in various cases:

private static void AssertSumIsOneHundred(IEnumerable<Prioritized<T>> priorities)
{
    if (priorities.Sum(p => p.Priority) != 100)
        throw new InvalidOperationException(
            "The sum of all priorities must be 100.");
}

By taking the sequence of priorities as an input argument, this enables me to simulate what would happen if I make a change to the actual collection, for example when adding an item to the collection:

protected override void InsertItem(int index, Prioritized<T> item)
{
    AssertSumIsOneHundred(this.Append(item));
    base.InsertItem(index, item);
}

By using Append, the InsertItem method creates a sequence of values that simulates what the collection would look like if we add the candidate item. The Append function returns a new collection, so this operation doesn't change the actual PriorityCollection<T>. This only happens if we get past the assertion and call InsertItem.

Likewise, I can protect the invariant in the other overrides:

protected override void RemoveItem(int index)
{
    var l = this.ToList();
    l.RemoveAt(index);
    AssertSumIsOneHundred(l);
    base.RemoveItem(index);
}
 
protected override void SetItem(int index, Prioritized<T> item)
{
    var l = this.ToList();
    l[index] = item;
    AssertSumIsOneHundred(l);
    base.SetItem(index, item);
}

I can even use it in the implementation of ClearItems, although that may seem a tad redundant:

protected override void ClearItems()
{
    AssertSumIsOneHundred([]);
}

I could also just have thrown an exception directly from this method, since it's never okay to clear the collection. This would violate the invariant, because the sum of an empty collection of priorities is zero.

As far as I recall, the entire API of Collection<T> is (transitively) based on those four virtual methods, so now that I've protected the invariant in all four, the PriorityCollection<T> class maintains the invariant, right?

Not yet. See if you can spot the problem.

There are, in fact, at least two remaining problems. One that we can recover from, and one that is insurmountable with this design. I'll get back to the serious problem later, but see if you can spot it already.

Leaf mutation #

In the introductory article I wrote:

"If the mutation happens on a leaf node in an object graph, the leaf may have to notify its parent, so that the parent can recheck the invariants."

I realize that this may sound abstract, but the current code presents a simple example. What happens if you change the Priority of an item after you've initialized the collection?

Consider the following example. For various reasons, I wrote the examples (that is, the unit tests) for this exercise in F#, but even if you're not an F# developer, you can probably understand what's going on. First, we create a Prioritized<string> object and use it to initialize a PriorityCollection<string> object named sut:

let item = Prioritized<string> ("foo", 40uy)
let sut = PriorityCollection<string> (item, Prioritized<string> ("bar", 60uy))

The item has a priority of 40 (the uy suffix is the F# way of stating that the literal is a byte), and the other unnamed value has a priority of 60, so all is good so far; the sum is 100.

Since, however, item is a mutable object, we can now change its Priority:

item.Priority <- 50uy

This changes item.Priority to 50, but since none of the four virtual base class methods of Collection<T> are involved, the sut never notices, the assertion never runs, and the object is now in an invalid state.

That's what I meant when I discussed mutations in leaf nodes. You can think of a collection as a rather flat and boring tree. The collection object itself is the root, and each of the items are leaves, and no further nesting is allowed.

When you edit a leaf, the root isn't automatically aware of such an event. You explicitly have to wire the object graph up so that this happens.

Event propagation #

One possible way to address this issue is to take advantage of .NET's event system. If you're reading along, but you normally write in another language, you can also use the Observer pattern, or even ReactiveX.

We need to have Prioritized<T> raise events, and one option is to let it implement INotifyPropertyChanging:

public sealed class Prioritized<T> : INotifyPropertyChanging

A Prioritized<T> object can now raise its PropertyChanging event before accepting an edit:

public byte Priority
{
    get => priority;
    set
    {
        if (PropertyChanging is { })
            PropertyChanging(
                this,
                new PriorityChangingEventArgs(value));
        priority = value;
    }
}

where PriorityChangingEventArgs is a little helper class that carries the proposed value around:

public class PriorityChangingEventArgs(byte proposal)
    : PropertyChangingEventArgs(nameof(Priority))
{
    public byte Proposal { get; } = proposal;
}

A PriorityCollection<T> object can now subscribe to that event on each of the values it keeps track of, so that it can protect the invariant against leaf node mutations.

private void Priority_PropertyChanging(object? sender, PropertyChangingEventArgs e)
{
    if (sender is Prioritized<T> p &&
        e is Prioritized<T>.PriorityChangingEventArgs pcea)
    {
        var l = this.ToList();
        l[l.IndexOf(p)] = new Prioritized<T>(p.Item, pcea.Proposal);
        AssertSumIsOneHundred(l);
    }
}

Such a solution comes with its own built-in complexity, because the PriorityCollection<T> class must be careful to subscribe to the PropertyChanging event in various different places. A new Prioritized<T> object may be added to the collection during initialization, or via the InsertItem or SetItem methods. Furthermore, the collection should make sure to unsubscribe from the event if an item is removed from the collection.

To be honest, I didn't bother to implement these extra checks, because the point is moot anyway.

Fatal flaw #

The design shown here comes with a fatal flaw. Can you tell what it is?

Since the invariant is that the priorities must always sum to exactly 100, it's impossible to add, remove, or change any items after initialization.

Or, rather, you can add new Prioritized<T> objects as long as their Priority is 0. Any other value breaks the invariant.

Likewise, the only item you can remove is one with a Priority of 0. Again, if you remove an item with any other Priority, you'd be violating the invariant.

A similar situation arises with editing an existing item. While you can change the Priority of an item, you can only 'change' it to the same value. So you can change 0 to 0, 42 to 42, or 100 to 100, but that's it.

But, I can hear you say, I'll only change 60 to 40 because I intend to add a new item with a 20 priority! In the end, the sum will be 100!

Yes, but this design doesn't know that, and you have no way of telling it.

While we may be able to rectify the situation, I consider this design so compromised that I think it better to start afresh with this realization. Thus, I'll abandon this version of PriorityCollection<T> in favour of a fresh start in the next article.

Conclusion #

While I've titled this article "A failed attempt", the actual purpose was to demonstrate how 'aggregate' requirements make it difficult to maintain class invariants.

I've seen many code bases with poor encapsulation. As far as I can tell, a major reason for that is that the usual 'small-scale' object-oriented design techniques like Guard Clauses fall short when an invariant involves the interplay of multiple objects. And in real business logic, that's the rule rather than the exception.

Not all is lost, however. In the next article, I'll develop an alternative object-oriented solution to the priority collection problem.

Next: A mutable priority collection.

Comments

Daniel Frost #

2 things.

I had a difficult time getting this to work with as a mutable type and the only two things I could come with (i spent some hours on it, it was in fact hard!) was

1. To throw an exception when the items in the collection didn't sum up to the budget. That violates the variant because you can add and remove items all you want.
2. Another try, which I didn't finish, is to add some kind of result-object that could tell about the validity of the collection and not expose the collection items before the result is valid. I haven't tried this and it doesn't resemble a collection but it could perhaps be a way to go.
I am also leaning towards a wrapper around the item type, making it immutable, so the items cannot change afterwards. Cheating ?
I tried with the events approach but it is as you put yourself not a very friendly type you end up with.

2024-06-18 11:54 UTC

Mark Seemann #

Daniel, thank you for writing. You'll be interested in the next articles in the series, then.

2024-06-18 13:55 UTC

This blog is totally free, but if you like it, please consider supporting it.

Simpler encapsulation with immutability

2024-06-12T15:33:00+00:00

A worked example.

I've noticed that many software organizations struggle with encapsulation with 'bigger' problems. It may be understandable and easily applicable to define a NaturalNumber type or ensure that a minimum value is less than a maximum value, and so on. How do you, however, guarantee invariants once the scope of the problem becomes bigger and more complex?

In this series of articles, I'll attempt to illustrate how and why this worthy design goal seems elusive, and what you can do to achieve it.

Contracts #

As usual, when I discuss encapsulation, I first need to establish what I mean by the term. It is, after all, one of the most misunderstood concepts in software development. As regular readers will know, I follow the lead of Object-Oriented Software Construction. In that perspective, encapsulation is the appropriate modelling and application of preconditions, invariants, and postconditions.

Particularly when it comes to invariants, things seem to fall apart as the problem being modelled grows in complexity. Teams eventually give up guaranteeing any invariants, leaving client developers with no recourse but defensive coding, which again leads to code duplication, bugs, and maintenance problems.

If you need a reminder, an invariant is an assertion about an object that is always true. The more invariants an object has, the better guarantees it gives, and the more you can trust it. The more you can trust it, the less defensive coding you have to write. You don't have to check if return values are null, strings empty, numbers negative, collections empty, or so on.

All together, I usually denote the collection of invariants, pre-, and postconditions as a type's contract.

For a simple example like modelling a natural number, or a range, or a user name, most people are able to produce sensible and coherent designs. Once, however, the problem becomes more complex, and the invariants involve multiple interacting values, maintaining the contract becomes harder.

Immutability to the rescue #

I'm not going to bury the lede any longer. It strikes me that mutation is a major source of complexity. It's not that hard to check a set of conditions when you create a value (or object or record). What makes it hard to maintain invariants is when objects are allowed to change. This implies that for every possible change to the object, it needs to examine its current state in order to decide whether or not it should allow the operation.

If the mutation happens on a leaf node in an object graph, the leaf may have to notify its parent, so that the parent can recheck the invariants. If the graph has cycles it becomes more complicated still, and if you want to make the problem truly formidable, try making the object thread-safe.

Making the object immutable makes most of these problems go away. You don't have to worry about thread-safety, because immutable values are automatically thread-safe; there's no state for any thread to change.

Even better, though, is that an immutable object's contract is smaller and simpler. It still has preconditions, because there are rules that govern what has to be true before you can create such an object. Furthermore, there may also be rules that stipulate what must be true before you can call a method on it.

Likewise, postconditions are still relevant. If you call a method on the object, it may give you guarantees about what it returns.

There are, however, no independent invariants.

Or rather, the invariants for an immutable object entirely coincide with its preconditions. If it was valid at creation, it remains valid.

Priority collection #

As promised, I'll work through a problem to demonstrate what I mean. I'll first showcase how mutation makes the problem hard, and then how trivial it becomes with an immutable design.

The problem is this: Design and implement a class (or just a data structure if you don't want to do Object-Oriented programming) that models a priority list (not a Priority Queue) as you sometimes run into in surveys. You know, one of these survey questions that asks you to distribute 100 points on various different options:

Option F: 30%
Option A: 25%
Option C: 25%
Option E: 20%
Option B: 0%
Option D: 0%

If you have the time, I suggest that you treat this problem as a kata. Try to do the exercise before reading the next articles in this series. You can assume the following, which is what I did.

The budget is 100. (You could make it configurable, but the problem is gnarly enough even with a hard-coded value.)
You don't need to include items with priority value 0, but you should allow it.
The sum of priorities must be exactly 100. This is the invariant.

The difficult part is that last invariant. Let me stress this requirement: At any time, the object should be in a consistent state; i.e. at any time should the sum of priorities be exactly 100. Not 101 or 99, but 100. Good luck with that.

The object should also be valid at initialization.

Of course, having read this far, you understand that all you have to do is to make the object immutable, but just for the sake of argument, try designing a mutable object with this invariant. Once you've tried your hand with that, read on.

Attempts #

There's educational value going through even failed attempts. When I thought of this example, I fairly quickly outlined in my head one approach that was unlikely to ever work, one that could work, and the nice immutable solution that trivially works.

I'll cover each in turn:

It's surprising how hard even a simple exercise like this one turns out to be, if you try to do it the object-oriented way.

In reality, business rules are much more involved than what's on display here. For only a taste of how bad it might get, read Hillel Wayne's suggestions regarding a similar kind of problem.

Conclusion #

If you've lived all your programming life with mutation as an ever-present possibility, you may not realize how much easier immutability makes everything. This includes invariants.

When you have immutable data, object graphs tend to be simpler. You can't easily define cyclic graphs (although Haskell, due to its laziness, surprisingly does enable this), and invariants essentially coincide with preconditions.

In the following articles, I'll show how mutability makes even simple invariants difficult to implement, and how immutability easily addresses the issue.

Next: A failed attempt at priority collection with inheritance.

Comments

Marken Foo #

I've been enjoying going through your articles in the past couple months, and I really like the very pedagogic treatment of functional programming and adjacent topics.

The kata here is an interesting one, but I don't think I'd link it with the concept of immutability/mutability. My immediate thought was a naïve struct that can represent illegal values and whose validity is managed through functions containing some tricky logic, but that didn't seem promising whether it was done immutably or not.

Instead, the phrase "distribute 100 points" triggered an association with the stars and bars method for similar problems. The idea is that we have N=100 points in a row, and inserting dividers to break it into (numOptions) groups. Concretely, our data structure is (dividers: int array), which is a sorted array of length (numOptions + 1) where the first element is 0 and the last element is N=100. The priorities are then exactly the differences between adjacent elements of the array. The example in the kata (A=25, B=0, C=25, D=0, E=20, F=30) is then represented by the array [| 0; 25; 25; 50; 50; 70; 100|].

This solution seems to respect the invariant, has a configurable budget, can work with other numerical types, and works well whether immutable or not (if mutable, just ensure the array remains sorted, has min 0, and max N). The invariant is encoded in the representation of the data, which seems to me to be the more relevant point than mutability.

And a somewhat disjoint thought, the kata reminded me of a WinForms TableLayoutPanel (or MS Word table) whose column widths all must fit within the container's width...

2024-06-13 13:55 UTC

Mark Seemann #

Thank you for writing. The danger of writing these article series is always that as soon as I've published the first one, someone comes by and puts a big hole through my premise. Well, I write this blog for a couple of independent reasons, and one of them is to learn.

And you just taught me something. Thank you. That is, at least, an elegant implementation.

How would you design the API encapsulating that implementation?

Clearly, arrays already have APIs, so you could obviously define an array-like API that performs the appropriate boundary checks. That, however, doesn't seem to model the given problem. Rather, it reveals the implementation, and forces a client developer to think in terms of the data structure, rather the problem (s)he has to solve.

Ideally, again channelling Bertrand Meyer, an object should present as an Abstract Data Structure (ADT) that doesn't require client developers to understand the implementation details. I'm curious what such an API would look like.

You've already surprised me once, and please do so once again. I'm always happy to learn something new, and that little stars-and-bars concept I've now added to my tool belt.

All that said, this article makes a more general claim, although its possible that the example it showcases is a tad too simple and naive to be a truly revealing one. The claim is that this kind of 'aggregate constraint' often causes so much trouble in the face of arbitrary state mutation that most programmers give up on encapsulation.

What happens if we instead expand the requirements a bit? Let's say that we will require the user to spend at least 90% of the budget, but no more than 100%. Also, there must be at least three prioritized items, and no individual item can receive more than a third of the budget.

2024-06-14 14:22 UTC

Marken Foo #

Thank you for the response. Here's my thoughts - it's a bit of a wall of text, I might be wrong in any of the following, and the conclusion may be disappointing. When you ask how I'd design the API, I'd say it depends on how the priority list is going to be used. The implementation trick with stars and bars might just be a one-off trick that happens to work here, but it doesn't (shouldn't) affect the contract with the outside world.

If we're considering survey questions or budgets, the interest is in the priority values. So I think the problem then is about a list of priorities with an aggregate constraint. So I would define... an array-like API that performs the appropriate boundary checks (wow), but for the item priorities. My approach would be to go for "private data, public functions", and rely on a legal starting state and preserving the legality through the public API. In pseudocode:

                type PriorityList = { budget: int; dividers: int list }
                create :: numItems: int -> budget: int -> PriorityList
        
                // Returns priorities.
                getAll :: plist: PriorityList -> int list
                get :: itemIdx: int -> plist: PriorityList -> int
        
                // *Sets the priority for an item (taking the priority from other items, starting from the back).
                set :: itemIdx: int -> priority: int -> plist: PriorityList -> PriorityList
        
                // *Adds a new item to (the end of) the PriorityList (with priority zero).
                addItem :: plist: PriorityList -> PriorityList
        
                // *Removes an item from the PriorityList (and assigns its priority to the last item). 
                removeItem :: itemIdx: int -> plist PriorityList -> PriorityList
        
                // Utility functions: see text
                _toPriorities :: dividers: int list -> int list
                _toDividers :: priorities: int list -> int list

Crucially: since set, addItem, and removeItem must maintain the invariants, they must have "side effects" of altering other priorities. I think this is unavoidable here because we have aggregate/global constraints, rather than just elementwise/local constraints. (Is this why resizing rows and columns in WinForms tableLayoutPanels and MS Word tables is so tedious?) This will manifest in the API - the client needs to know what "side effects" there are (suggested behaviour in parentheses in the pseudocode comments above). See my crude attempt at implementation.

You may already see where this is going. If I accept that boundary checks are needed, then my secondary goal in encapsulation is to express the constraints as clearly as possible, and hopefully not spread the checking logic all over the code.

Whence the utility functions: it turned out to be useful to convert from a list of dividers to priorities, and vice versa. This is because the elementwise operations/invariants like the individual priority values are easier to express in terms of raw priorities, while the aggregate ones like the total budget are easier in terms of "dividers" (the cumulative priorities). There is a runtime cost to the conversion, but the code becomes clearer. This smells similar to feature envy...

So why not just have the underlying implementation hold a list of priorities in the first place?! Almost everything in the implementation needs translation back to that anyway. D'oh! I refactored myself back to the naïve approach. The original representation seemed elegant, but I couldn't find a way to manipulate it that clients would find intuitive and useful in the given problem.

But... if I approach the design from the angle "what advantages does the cumulative priority model offer?", I might come up with the following candidate API functions, which could be implemented cleanly in the "divider" space:

                // (same type, create, get, getAll, addItem as above)
                // Removes the item and merges its priority with the item before it.
                merge :: ItemIdx: int -> PriorityList
                // Sets the priority of an item to zero and gives it to the item after it.
                collapse :: itemIdx: int -> PriorityList
                // Swaps the priority of an item and the one after it (e.g. to "bubble" a priority value forwards or backwards, although this is easier in the "priority" space)
                swap :: itemIdx: int -> PriorityList
                // Sets (alternative: adds to) the priority of an item, taking the priority from the items after it in sequence ("consuming" them in the forward direction)
                consume :: itemIdx: int -> priority: int -> PriorityList
                // Splits the item into 2 smaller items each with half the priority (could be generalised to n items)
                split :: ItemIdx: int -> PriorityList
                // etc.

And this seems like a more fitting API for that table column width example I keep bringing up. What's interesting to me is that despite the data structures of the budget/survey question and the table column widths being isomorphic, we can come up with rather different APIs depending on which view we consider. I think this is my main takeaway from this exploration, actually.

As for the additional requirements, individually each constraint is easy to handle, but their composition is tricky. If it's easy to transform an illegal PriorityList to make it respect the invariants, we can just apply the transformation after every create/set/add/remove. Something like:

                type PriorityList =
                    { budget: int
                      dividers: int list
                      budgetCondition: int -> bool
                      maxPriority: int
                      minChoices: int }
                
                let _enforceBudget (predicate: int -> bool) (defaultBudget: int) (dividers: int list) : int list =
                    if (List.last dividers |> predicate) then
                        dividers
                    else
                        List.take (dividers.Length - 1) dividers @ [ defaultBudget ]
        
                let _enforceMaxPriority (maxPriority: int) (dividers: int list) : int list =
                    _toPriorities dividers |> List.map (fun p -> min p maxPriority) |> _toDividers

The problem is those transforms may not preserve each others' invariant. Life would be easy if we could write a single transform to preserve everything (I haven't found one - notice that the two above are operating on different int lists so it's tricky). Otherwise, we could write validations instead of transformations, then let create/set/add/remove fail by returning Option.None (explicitly fail) or the original list (silently fail). This comes at the cost of making the API less friendly.

Ultimately with this approach I can't see a way to make all illegal states unrepresentable without sprinkling ad-hoc checks everywhere in the code. The advantages of the "cumulative priorities" representation I can think of are (a) it makes the total budget invariant obvious, and (b) it maps nicely to a UI where you click and drag segments around. Since you might have gone down a different path in the series, I'm curious to see how that shapes up.

2024-06-15 14:48 UTC

Aliaksei Saladukhin #

Hello and thank you for your blog. It is really informative and provides great food for thought.

What if it will be impossible to compile and run program which would lead to illegal (list) state?

I've tried to implement priority collection in Rust, and what I've ended up with is a heterogenous priority list with compile-time priority validation. Idea behind this implementation is simple: you declare recursive generic struct, which holds current element and tail (another list or unit type).

				struct PriorityList<const B: usize, const P: usize, H, T> {
					head: H,
					tail: T,
				}

If, for example, we need list of two Strings with budget 100, and 30/70 priority split, it will have the following type: PriorityList<100, 30, String, PriorityList<100, 70, String, ()>> Note that information about list budget and current element priority is contained in generic arguments B and P respectively. These are compile-time "variables", and will be replaced be their values in compiled program.

Since each element of such list is a list itself, and budget is the same for each element, all elements except the first are invalid priority lists. So, in order to make it possible to create lists other than containing one element, or only one element with >0 priority, validity check should be targeted and deferred. In order to target invariant validation on the first element of the list, I've included validation into list methods (except set_priority method). Every time list method is called, compiler does recursive computation of priority sum, and compares it with list budget, giving compile-time error if there is mismatch. Consider the following example, which will compile and run:

				let list = ListBuilder::new::<10, 10>("Hello");
				let list = list.set_priority::<5>();

Seems like invariants have been violated and sum of priorities is less than the budget. But if we try to manipulate this list in any other way except to add element or change priority, program won't compile

				// Won't compile
				let _ = list.pop();

				// Won't compile
				let list = list.push::<4>("Hi");

				// Will do
				let list = list.push::<5>("Hello there");

This implementation may not be as practical as it could be due to verbose compilation error messages, but is a good showcase and exercise I've also uploaded full source code at GitLab: https://gitlab.com/studiedlist/priority-collection

2024-06-18 08:47 UTC

Mark Seemann #

Marken, thank you for writing. It's always interesting to learn new techniques, and, as I previously mentioned, the array-based implementation certainly seems to make illegal states unrepresentable. And then, as we'll see in the last (yet unpublished) article in this little series, if we also make the data structure immutable, we'll have a truly simple and easy-to-understand API to work with.

I've tried experimenting with the F# script you linked, but I must admit that I'm having trouble understanding how to use it. You did write that it was a crude attempt, so I'm not complaining, but on the other hand, it doesn't work well as an example of good encapsulation. The following may seem as though I'm moving the goalpost, so apologies for that in advance.

Usually, when I consult development organizations about software architecture, the failure to maintain invariants is so fundamental that I usually have to start with that problem. That's the reason that this article series is so narrow-mindedly focused on contract, and seemingly not much else. We must not, though, lose sight of what ultimately motivates us to consider encapsulation beneficial. This is what I've tried to outline in Code That Fits in Your Head: That the human brain is ill-suited to keep all implementation details in mind at the same time. One way we may attempt to address this problem is to hide implementation details behind an API which, additionally, comes with some guarantees. Thus (and this is where you may, reasonably, accuse me of moving the goal post), not only should an object fulfil its contract, it should also be possible to interact with its API without understanding implementation details.

The API you propose seem to have problems, some of which may be rectifiable:

At a fundamental level, it's not really clear to me how to use the various functions in the script file.
The API doesn't keep track of what is being prioritized. This could probably be fixed.
It's not clear whether it's possible to transition from one arbitrary valid distribution to another arbitrary valid distribution.

I'll briefly expand on each.

As an example of the API being less that clear to me, I can't say that I understand what's going on here:

> create 1 100 |> set 1 50 |> addItem |> set 1 30;;
val it: PriorityList = { budget = 100
                         dividers = [0; 50; 100] }

As for what's being prioritized, you could probably mend that shortcoming by letting the array be an array of tuples.

The last part I'm not sure of, but you write:

"Crucially: since set, addItem, and removeItem must maintain the invariants, they must have "side effects" of altering other priorities."

As the most recent article in this series demonstrates, this isn't an overall limitation imposed by the invariant, but rather by your chosen API design. Specifically, assuming that you initially have a 23, 31, 46 distribution, how do you transition to a 19, 29, 43, 7, 2 distribution?

2024-06-27 6:42 UTC

Mark Seemann #

Aliaksei, thank you for writing. I've never programmed in Rust, so I didn't know it had that capability. At first I though it was dependent typing, but after reading up on it, it seems as though it's not quite that.

An exercise like the one in this article series is useful because it can help shed light on options and their various combinations of benefits and drawbacks. Thus, there are no entirely right or wrong solutions to such an exercise.

Since I don't know Rust, I can't easily distinguish what might be possible drawbacks here. I usually regard making illegal states unrepresentable as a benefit, but we must always be careful not to go too far in that direction. One thing is to reject invalid states, but can we still represent all valid states? What if priority distributions are run-time values?

2024-06-28 7:21 UTC

This blog is totally free, but if you like it, please consider supporting it.

You'll regret using natural keys

2024-06-03T19:46:00+00:00

Beating another dead horse.

Although I live in Copenhagen and mostly walk or ride my bicycle in order to get around town, I do own an old car for getting around the rest of the country. In Denmark, cars go through mandatory official inspection every other year, and I've been through a few of these in my life. A few years ago, the mechanic doing the inspection informed me that my car's chassis number was incorrect.

This did make me a bit nervous, because I'd bought the car used, and I was suddenly concerned that things weren't really as I thought. Had I unwittingly bought a stolen car?

But the mechanic just walked over to his computer in order to correct the error. That's when a different kind of unease hit me. When you've programmed for some decades, you learn to foresee various typical failure modes. Since a chassis number is an obvious candidate for a natural key, I already predicted that changing the number would prove to be either impossible, or have all sorts of cascading effects, ultimately terminating in official records no longer recognizing that the car is mine.

As it turned out, though, whoever made that piece of software knew what they were doing, because the mechanic just changed the chassis number, and that was that. This is now five or six years ago, and I still own the same car, and I've never had any problems with the official ownership records.

Uniqueness #

The reason I related this story is that I'm currently following an undergraduate course in databases and information systems. Since this course is aimed at students with no real-world experience, it wisely moves forward in a pedagogical progression. In order to teach database keys, it starts with natural keys. From a didactic perspective, this makes sense, but the result, so far, is that the young people I work with now propose database designs with natural keys.

I'm not blaming anyone. You have to learn to crawl before you can walk.

Still, this situation made me reflect on the following question: Are natural keys ever a good idea?

Let's consider an example. For a little project we're doing, we've created a database of the World's 50 best restaurants. My fellow students suggest a table design like this:

CREATE TABLE Restaurants (
    year TEXT NOT NULL,
    rank TEXT NOT NULL,
    restaurantName TEXT NOT NULL,
    cityName TEXT NOT NULL
);

Granted, at this point, this table definition defines no key at all. I'm not complaining about that. After all, a month ago, the students probably hadn't seen a database table.

From following the course curriculum, it'd be natural, however, to define a key for the Restaurants table as the combination of restaurantName, cityName, and year. The assumption is that name and city uniquely identifies a restaurant.

In this particular example, this assumption may actually turn out to hold. So far. After all, the data set isn't that big, and it's important for restaurants in that league to have recognizable names. If I had to guess, I'd say that there's probably only one Nobelhart & Schmutzig in the world.

Still, a good software architect should challenge the underlying assumptions. Is name and city a natural key? It's easy to imagine that it's not. What if we expand the key to include the country as well? Okay, but what if we had a restaurant named China Wok in Springfield, USA? Hardly unique. Add the state, you say? Probably still not unique.

Identity #

Ensuring uniqueness is only the first of many problems with natural keys. You may quickly reach the conclusion that for a restaurant database, a synthetic key is probably the best choice.

But what about 'natural' natural keys, so to speak? An example may be a car's chassis number. This is already an opaque number, and it probably originates from a database somewhere. Or how about a personal identification number? In Denmark we have the CPR number, and I understand that the US Social Security Number is vaguely analogous.

If you're designing a database that already includes such a personal identification number, you might be tempted to use it as a natural key. After all, it's already a key somewhere else, so it's guaranteed to be unique, right?

Yes, the number may uniquely identify a person, but the converse may not be true. A person may have more than one identification number. At least when time is a factor.

As an example, for technical-historical reasons, the Danish CPR number carries information (which keys shouldn't do), such as a person's date of birth and sex. Since 2014 a new law enables transsexual citizens to get a new CPR number that reflects their perceived gender. The consequence is that the same person may have more than one CPR number. Perhaps not more than one at the same time, but definitely two during a lifetime.

Even if existing keys are guaranteed to be unique, you can't assume that the uniqueness gives rise to a bijection. If you use an external unique key, you may lose track of the entities that you're trying to keep track of.

This is true not only for people, but cars, bicycles (which also have chassis numbers), network cards, etc.

Clerical errors #

Finally, even if you've found a natural key that is guaranteed to be unique and track the actual entity that you want to keep track of, there's a final argument against using an externally defined key in your system: Data-entry errors.

Take the story about my car's chassis number. The mechanic who spotted the discrepancy clearly interpreted it as a clerical error.

After a few decades of programming, I've learned that sooner or later, there will be errors in your data. Either it's a clerical error, or the end-user mistyped, or there was a data conversion error when importing from an external system. Or even data conversion errors within the same system, as it goes through upgrades and migrations.

Your system should be designed to allow corrections to data. This includes corrections of external keys, such as chassis numbers, government IDs, etc. This means that you can't use such keys as database keys in your own system.

Heuristic #

Many were the times, earlier in my career, when I decided to use a 'natural key' as a key in my own database. As far as I recall, I've regretted it every single time.

These days I follow a hard heuristic: Always use synthetic keys for database tables.

Conclusion #

Is it ever a good idea to use natural keys in a database design? My experience tells me that it's not. Ultimately, regardless of how certain you can be that the natural key is stable and correctly tracks the entity that it's supposed to keep track of, data errors will occur. This includes errors in those natural keys.

You should be able to correct such errors without losing track of the involved entities. You'll regret using natural keys. Use synthetic keys.

Comments

James Snape #

There are lots of different types of keys. I agree that using natural keys as physical primary keys is a bad idea but you really should be modelling your data logically with natural keys. Thinking about uniqueness and identity is a part of your data design. Natural keys often end up as constraints, indexes and query plans. When natural keys are not unique enough then you need to consider additional attributes in your design to ensure access to a specific record.

Considering natural keys during design can help elicit additional requirements and business rules. "Does a social security number uniquely identify a person? If not why?" In the UK they recycle them so the natural key is a combination of national insurance number and birth year. You have to ask questions.

2024-06-04 15:43 UTC

Thomas Castiglione #

2024-06-05 9:33 UTC

Nicholas Peterson #

I largely agree with James Snape, but wanted to throw in a few other thoughts on top. Surrogates don't defend you from duplicate data, in fact they facilitate it, because the routine generating the surrogate key isn't influenced by any of the other data in the record. The concept of being unable to correct a natural key is also odd, why can't you? Start a transaction, insert a new record with the correct key, update the related records to point to the new record, then delete the old record, done. Want some crucial information about a related record but only have the surrogate to it? I guess you have to join it every time in order to get the columns the user actually wants to see. A foreign key that uses a natural key often often prevents the join entirely, because it tells the user what they wanted to know.

I find the problem with natural keys usually comes from another source entirely. Developers write code and don't tend to prefer using SQL. They typically interact with databases through ORM libraries. ORMs are complicated and rely on conventions to uniformly deal with data. It's not uncommon for ORMs to dictate the structure of tables to some degree, or what datatypes to prefer. It's usually easier in an ORM to have a single datatype for keys (BIGINT?) and use it uniformly across all the tables.

2024-06-05 12:42 UTC

Mark Seemann #

James, Nicholas, thank you for writing. I realize that there are some unstated assumptions and implied concerns that I should have made more explicit. I certainly have no problem with adding constraints and other rules to model data. For the Danish CPR number, for example, while I wouldn't make it a primary key (for the reasons outlined in the article), I'd definitely put a UNIQUE constraint on it.

Another unspoken context that I had in mind is that systems often exist in a wider context where ACID guarantees fall apart. I suppose it's true that if you look at a database in isolation, you may be able to update a foreign key with the help of some cascading changes rippling through the database, but if you've ever shared the old key outside of the database, you now have orphaned data.

A simple example could be sending out an email with a link that embeds the old key. If you change the key after sending out the email, but before the user clicks, the link no longer works.

That's just a simple and easy-to-explain example. The more integration (particularly system-to-system integration) you have, the worse this kind of problem becomes. I briefly discussed the CPR number example with my doctor wife, and she immediately confirmed that this is a real problem in the Danish health sector, where many independent software systems need to exchange patient data.

You can probably work around such problems in various ways, but if you had avoided using natural keys, you wouldn't have had to change the key in the first place.

2024-06-06 6:56 UTC

Greg Hall #

I think it is best to have two separate generated keys for each row:

A key used only for relationships between tables. I like to call this relid, and make it serialised, so it is just an increasing number. This key is the primary key and should never be exposed outside the database.
A key used only outside the database as a unique reference to which row to update. I like to call this id, and make it a uuid, since it is well accepted to uniquely identify rows by a uuid, and to expose them to the outside world - many public APIs do this. Theoretically, the same uuid should never be generated twice, so this key doesn't necessarily have to be declared as unique.

The relid can be used in simple foreign keys, and in bridging/join tables - tables that contain primary keys of multiple tables. Generally speaking, the relid is far more readable than a uuid - it is easier to hold in your head a simple integer, which usually is not that large, than a 36 character sequence that looks similar to other 36 character sequences. UUIDs generally look like a jumble.

A relid can be 32-bits for tables you're confident will never need more than 2.1 billion rows, which really is 99.99% of all tables ever created by 99.99% of applications. If this turns out to be wrong, it is possible to upgrade the relids to 64-bit for a given table. It's a bit of a pain, especially if there are lots of references to it, but it can be done.

The relid doesn't always have to be a serialised value, and you don't always have to call the column relid. Since the primary key is never exposed publicly, it doesn't matter if different column types or names are used for different use cases. For example, code tables might use one of the codes as the primary key.

I don't think it makes sense to be religious on key usage; just like everything else, there are valid reasons for periodically varying how they work. I'm sure somebody has a valid case where a single key is better than two. I just think it generally makes sense to have a pair of internal and external keys for most cases.

2024-06-07 3:31 UTC

James Snape #

The thing with databases keys is you really need to be precise on what you mean by a key. Any combination of attributes is a candidate key. There are also logical and physical representations of keys. For example, a SQL Server primary key is a physical record locator but logically a unique key constraint. Yes, these behave poorly when you use natural keys as the primary key for all the reasons you mention. They are a complete implementation detail. Users should never see these attributes though and you shouldn't share the values outside of your implementation. Sharing integer surrogate keys in urls is a classic issue allowing enumeration attacks on your data if not secured properly.

Foreign keys are another logical and physical dual use concept. In SQL Server a physical foreign key constrain must reference the primary key from a parent table but logically that doesn't need to happen for relational theory to work.

Alternate keys are combinations of attributes that identify a record (or many records); these are often the natural keys you use in your user interface and where clauses etc. Alternate keys are also how systems communicate. Take your CPR number example, you cannot exchange patient data unless both systems agree on a common key. This can't be an internally generated surrogate value.

Natural keys also serve another purpose in parent-child relationships. By sharing natural key attributes with a parent you can ensure a child is not accidentally moved to a new parent plus you can query a child table without needing to join to the parent table.

There isn't a one-size-fits all when it comes to databases and keys. Joe Celko has written extensively on the subject so maybe its better to read the following than my small commentary:

2024-06-07 09:57 UTC

Mark Seemann #

Greg, thank you for writing. I agree with everything you wrote, and I've been using that kind of design for... wow, at least a decade, it looks! for a slightly different reason. This kind of design seems, even if motivated by a different concern, congruent with what you describe.

Like you also imply, only a sith speaks in absolutes. The irony of the article is that I originally intended it to be more open-ended, in the sense that I was curious if there were genuinely good reasons to use natural keys. As I wrote, the article turned out more unconditional than I originally had in mind.

I am, in reality, quite ready to consider arguments to the contrary. But really, I was curious: Is it ever a good idea to use natural keys as primary keys? It sounds like a rhetorical question, but I don't mind if someone furnishes a counter-example.

As Nicholas Peterson intimated, it's probably not a real problem if those keys never 'leave' the database. What I failed to make explicit in this article is that the problems I've consistently run into occur when a system has shared keys with external systems or users.

2024-06-14 11:26 UTC

Mark Seemann #

James, thank you for writing. I think we're discussing issues at different levels of abstraction. This just underscores how difficult technical writing is. I should have made my context and assumptions more explicit. The error is mine.

Everything you write sounds correct to me. I am aware of both relational calculus and relational algebra, so I'm familiar with the claims you make, and I don't dispute them.

My focus is rather on systems architecture. Even an 'internal' system may actually be composed from multiple independent systems, and my concern is that using natural keys to exchange data between such systems ultimately turns out to make things more difficult than they could have been. The only statement of yours with which I think I disagree is that you can't exchange data between systems unless you use natural keys. You definitely can, although you need to appoint one of the systems to be a 'master key issuer'.

In practice, like Greg Hall, I'd prefer using GUIDs for that purpose, rather than sequential numbers. That also addresses the concern about enumeration attacks. (Somewhat tangentially, I also recommend signing URLs with a private key in order to prevent reverse-engineering, or 'URL-hacking'.)

2024-06-14 11:55 UTC

James Snape #

I think we are basically agreeing here because I would never use natural keys nor externally visible synthetic keys for physical primary keys. (I think this statement is even more restrictive than the article's main premise). Well, with a rule exception for configurable enum type tables because the overhead of joining to resolve a single column value is inefficient. I would however always use a natural key for a logical primary key.

The only reason why I'm slightly pedantic about this is due the the number of clients why have used surrogate keys in a logical model and then gone on to create databases where the concept of entity identity doesn't exist. This creates many of the issues Nicholas Peterson mentioned above: duplicates, historical change tracking, etc. Frankly, it doesn't help that lots of code examples for ORMs just start with an entity that has an ID attribute.

One final comment on sharing data based on a golden master synthetic key. The moment you do I would argue that you have now committed to maintaining that key through all types of data mergers and acquisitions. It must never collide, and always point to exactly the same record and only that record. Since users can use it to refer to an entity and it makes up part of your external API, it now meets the definition of a natural key. Whether you agree or not on my stretching the definition a little, you still should not use this attribute as the physical primary key (record locator) because we should not expose implementation details in our APIs. The first Celko article I linked to explains some of the difficulties for externally visible synthetic keys.

2024-06-14 13:45 UTC

Julius H #

I'd like to comment with an example where using a synthetic key came back to bite me. My system had posts and users with synthetic IDs. Now I wanted to track an unread state across them. Naively, I designed just another entity:

           
public int ID { get; set; }
public int PostID { get; set; }
public int UserID { get; set; }

And it worked flawlessly for years. One day, however, a user complained that he always got an exception "Sequence contains more than one element". Of course I used SingleOrDefault() in application code because I expected 0 or 1 record per user and post. The quick solution was deleting the spurious table row. As a permanant solution I removed the ID field (and column) so the unread state had its natural key as primary key (both columns). So if it happens again in the future, the app will error on insertin rather than querying.

Since my application is in control of the IDs and it's just a very simple join table I think it was the best solution. If the future requirements hold different kinds of unread state, I can always add the key again.

2024-07-22 14:40 UTC

Mark Seemann #

Julius, thank you for writing. I see what you mean, and would also tend to model this as just a table with two foreign keys. From the perspective of entity-relationship modelling, such a table isn't even an entity, but rather a relationship. For that reason, it doesn't need its own key; not because the combination is 'natural', but rather because it's not really an independent 'thing'.

2024-07-29 14:39 UTC

This blog is totally free, but if you like it, please consider supporting it.

Continuous delivery without a CI server

2024-05-27T13:34:00+00:00

An illustrative example.

More than a decade ago, I worked on a small project. It was a small single-page application (SPA) with a REST API backend, deployed to Azure. As far as I recall, the REST API used blob storage, so all in all it wasn't a complex system.

We were two developers, and although we wanted to do continuous delivery (CD), we didn't have much development infrastructure. This was a little startup, and back then, there weren't a lot of free build services available. We were using GitHub, but it was before it had any free services to compile your code and run tests.

Given those constraints, we figured out a simple way to do CD, even though we didn't have a continuous integration (CI) server.

I'll tell you how we did this.

Shining an extraordinary light on the mundane #

The reason I'm relating this little story isn't to convince you that you, too, should do it that way. Rather, it's a didactic device. By doing something extreme, we can sometimes learn about the ordinary.

You can only be pragmatic if you know how to be dogmatic.

What to test and not to test, me

From what I hear and read, it seems that there's a lot of organizations that believe that they're doing CI (or perhaps even CD) because they have a CI server. What the following tale will hopefully highlight is that, while build servers are useful, they aren't a requirement for CI or CD.

Distributed CD #

Dramatis personae: My colleague and me. Scene: One small SPA project with a REST API and blob storage, to be deployed to Azure. Code base in GitHub. Two laptops. Remote work.

One of us (let's say me) would start on implementing a feature, or fixing a bug. I'd use test-driven development (TDD) to get feedback on API ideas, as well as to accumulate a suite of regression tests. After a few hours of effective work, I'd send a pull request to my colleague.

Since we were only two people on the team, the responsibility was clear. It was the other person's job to review the pull request. It was also clear that the longer the reviewer dawdled, the less efficient the process would be. For that reason, we'd typically have agile pull requests with a good turnaround time.

While we were taking advantage of GitHub as a central coordination hub for pull requests, Git itself is famously distributed. Thus, we wondered whether it'd be possible to make the CD process distributed as well.

Yes, apart from GitHub, what we did was already distributed.

A little more automation #

Since we were both doing TDD, we already had automated tests. Due to the simple setup of the system, we'd already automated more than 80% of our process. It wasn't much of a stretch to automate whatever else needed automation. Such as deployment.

We agreed on a few simple rules:

Every part of our process should be automated.
Reviewing a pull request included running all tests.

When people review pull requests, they often just go to GitHub and look around before issuing an LGTM.

But, you do realize that this is Git, right? You can pull down the proposed changes and run them.

What if you're already in the middle of something, working on the same code base? Stash your changes and pull down the code.

The consequence of this process was that every time a pull request was accepted, we already knew that it passed all automated tests on two physical machines. We actually didn't need a server to run the tests a third time.

After a merge, the final part of the development process mandated that the original author should deploy to production. We had Bash script that did that.

Simplicity #

This process came with some built-in advantages. First of all, it was simple. There wasn't a lot of moving parts, so there weren't many steps that could break.

Have you ever had the pleasure of troubleshooting a build? The code works on your machine, but not on the build server.

It sometimes turns out that there's a configuration mismatch with the compiler or test tools. Thus, the problem with the build server doesn't mean that you prevented a dangerous defect from being deployed to production. No, the code just didn't compile on the build server, but would actually have run fine on the production system.

It's much easier troubleshooting issues on your own machine than on some remote server.

I've also seen build servers that were set up to run tests, but along the way, something had failed and the tests didn't run. And no-one was looking at logs or warning emails from the build system because that system would already be sending hundreds of warnings a day.

By agreeing to manually(!) run the automated tests as part of the review process, we were sure that they were exercised.

Finally, by keeping the process simple, we could focus on what mattered: Delivering value to our customer. We didn't have to waste time learning how a proprietary build system worked.

Does it scale? #

I know what you're going to say: This may have worked because the overall requirements were so simple. This will never work in a 'real' development organization, with a 'real' code base.

I understand. I never claimed that it would.

The point of this story is to highlight what CI and CD is. It's a way of working where you continuously integrate your code with everyone else's code, and where you continuously deploy changes to production.

In reality, having a dedicated build system for that can be useful. These days, such systems tend to be services that integrate with GitHub or other sites, rather than an actual server that you have to care for. Even so, having such a system doesn't mean that your organization makes use of CI or CD.

(Oh, and for the mathematically inclined: In this context continuous doesn't mean actually continuous. It just means arbitrarily often.)

Conclusion #

CI and CD are processes that describe how we work with code, and how we work together.

Continuous integration means that you often integrate your code with everyone else's code. How often? More than once a day.

Continuous deployment means that you often deploy code changes to production. How often? Every time new code is integrated.

A build system can be convenient to help along such processes, but it's strictly speaking not required.

This blog is totally free, but if you like it, please consider supporting it.

Fundamentals

2024-05-20T07:04:00+00:00

How to stay current with technology progress.

A long time ago, I landed my dream job. My new employer was a consulting company, and my role was to be the resident Azure expert. Cloud computing was still in its infancy, and there was a good chance that I might be able to establish myself as a leading regional authority on the topic.

As part of the role, I was supposed to write articles and give presentations showing how to solve various problems with Azure. I dug in with fervour, writing sample code bases and even an MSDN Magazine article. To my surprise, after half a year I realized that I was bored.

At that time I'd already spent more than a decade learning new technology, and I knew that I was good at it. For instance, I worked five years for Microsoft Consulting Services, and a dirty little secret of that kind of role is that, although you're sold as an expert in some new technology, you're often only a few weeks ahead of your customer. For example, I was once engaged as a Windows Workflow Foundation expert at a time when it was still in beta. No-one had years of experience with that technology, but I was still expected to know much more about it than my customer.

I had lots of engagements like that, and they usually went well. I've always been good at cramming, and as a consultant you're also unencumbered by all the daily responsibilities and politics that often occupy the time and energy of regular employees. The point being that while I'm decent at learning new stuff, the role of being a consultant also facilitates that sort of activity.

After more then a decade of learning new frameworks, new software libraries, new programming languages, new tools, new online services, it turned out that I was ready for something else. After spending a few months learning Azure, I realized that I'd lost interest in that kind of learning. When investigating a new Azure SDK, I'd quickly come to the conclusion that, oh, this is just another object-oriented library. There are these objects, and you call this method to do that, etc. That's not to say that learning a specific technology is a trivial undertaking. The worse the design, the more difficult it is to learn.

Still, after years of learning new technologies, I'd started recognizing certain patterns. Perhaps, I thought, well-designed technologies are based on some fundamental ideas that may be worth learning instead.

Staying current #

A common lament among software developers is that the pace of technology is so overwhelming that they can't keep up. This is true. You can't keep up.

There will always be something that you don't know. In fact, most things you don't know. This isn't a condition isolated only to technology. The sum total of all human knowledge is so vast that you can't know it all. What you will learn, even after a lifetime of diligent study, will be a nanoscopic fraction of all human knowledge - even of everything related to software development. You can't stay current. Get used to it.

A more appropriate question is: How do I keep my skill set relevant?

Assuming that you wish to stay employable in some capacity, it's natural to be concerned with how your mad Flash skillz will land you the next gig.

Trying to keep abreast of all new technologies in your field is likely to lead to burnout. Rather, put yourself in a position so that you can quickly learn necessary skills, just in time.

Study fundamentals, rather than specifics #

Those many years ago, I realized that it'd be a better investment of my time to study fundamentals. Often, once you have some foundational knowledge, you can apply it in many circumstances. Your general knowledge will enable you to get quickly up to speed with specific technologies.

Success isn't guaranteed, but knowing fundamentals increases your chances.

This may still seem too abstract. Which fundamentals should you learn?

In the remainder of this article, I'll give you some examples. The following collection of general programmer knowledge spans software engineering, computer science, broad ideas, but also specific tools. I only intend this set of examples to serve as inspiration. The list isn't complete, nor does it constitute a minimum of what you should learn.

If you have other interests, you may put together your own research programme. What follows here are just some examples of fundamentals that I've found useful during my career.

A criterion, however, for constituting foundational knowledge is that you should be able to apply that knowledge in a wide variety of contexts. The fundamental should not be tied to a particular programming language, platform, or operating system.

Design patterns #

Perhaps the first foundational notion that I personally encountered was that of design patterns. As the Gang of Four (GoF) wrote in the book, a design pattern is an abstract description of a solution that has been observed 'in the wild', more than once, independently evolved.

Please pay attention to the causality. A design pattern isn't prescriptive, but descriptive. It's an observation that a particular code organisation tends to solve a particular problem.

There are lots of misconceptions related to design patterns. One of them is that the 'library of patterns' is finite, and more or less constrained to the patterns included in the original book.

There are, however, many more patterns. To illustrate how much wider this area is, here's a list of some patterns books in my personal library:

In addition to these, there are many more books in my library that are patterns-adjacent, including one of my own. The point is that software design patterns is a vast topic, and it pays to know at least the most important ones.

A design pattern fits the criterion that you can apply the knowledge independently of technology. The original GoF book has examples in C++ and Smalltalk, but I've found that they apply well to C#. Other people employ them in their Java code.

Knowing design patterns not only helps you design solutions. That knowledge also enables you to recognize patterns in existing libraries and frameworks. It's this fundamental knowledge that makes it easier to learn new technologies.

Often (although not always) successful software libraries and frameworks tend to follow known patterns, so if you're aware of these patterns, it becomes easier to learn such technologies. Again, be aware of the causality involved. I'm not claiming that successful libraries are explicitly designed according to published design patterns. Rather, some libraries become successful because they offer good solutions to certain problems. It's not surprising if such a good solution falls into a pattern that other people have already observed and recorded. It's like parallel evolution.

This was my experience when I started to learn the details of Azure. Many of those SDKs and APIs manifested various design patterns, and once I'd recognized a pattern it became much easier to learn the rest.

The idea of design patterns, particularly object-oriented design patterns, have its detractors, too. Let's visit that as the next set of fundamental ideas.

Functional programming abstractions #

As I'm writing this, yet another Twitter thread pokes fun at object-oriented design (OOD) patterns as being nothing but a published collection of workarounds for the shortcomings of object orientation. The people who most zealously pursue that agenda tends to be functional programmers.

Well, I certainly like functional programming (FP) better than OOD too, but rather than poking fun at OOD, I'm more interested in how design patterns relate to universal abstractions. I also believe that FP has shortcomings of its own, but I'll have more to say about that in a future article.

Should you learn about monoids, functors, monads, catamorphisms, and so on?

Yes you should, because these ideas also fit the criterion that the knowledge is technology-independent. I've used my knowledge of these topics in Haskell (hardly surprising) and F#, but also in C# and Python. The various LINQ methods are really just well-known APIs associated with, you guessed it, functors, monads, monoids, and catamorphisms.

Once you've learned these fundamental ideas, it becomes easier to learn new technologies. This has happened to me multiple times, for example in contexts as diverse as property-based testing and asynchronous message-passing architectures. Once I realize that an API gives rise to a monad, say, I know that certain functions must be available. I also know how I should best compose larger code blocks from smaller ones.

Must you know all of these concepts before learning, say, F#? No, not at all. Rather, a language like F# is a great vehicle for learning such fundamentals. There's a first time for learning anything, and you need to start somewhere. Rather, the point is that once you know these concepts, it becomes easier to learn the next thing.

If, for example, you already know what a monad is when learning F#, picking up the idea behind computation expressions is easy once you realize that it's just a compiler-specific way to enable syntactic sugaring of monadic expressions. You can learn how computation expressions work without that knowledge, too; it's just harder.

This is a recurring theme with many of these examples. You can learn a particular technology without knowing the fundamentals, but you'll have to put in more time to do that.

On to the next example.

SQL #

Which object-relational mapper (ORM) should you learn? Hibernate? Entity Framework?

How about learning SQL? I learned SQL in 1999, I believe, and it's served me well ever since. I consider raw SQL to be more productive than using an ORM. Once more, SQL is largely technology-independent. While each database typically has its own SQL dialect, the fundamentals are the same. I'm most well-versed in the SQL Server dialect, but I've also used my SQL knowledge to interact with Oracle and PostgreSQL. Once you know one SQL dialect, you can quickly solve data problems in one of the other dialects.

It doesn't matter much whether you're interacting with a database from .NET, Haskell, Python, Ruby, or another language. SQL is not only universal, the core of the language is stable. What I learned in 1999 is still useful today. Can you say the same about your current ORM?

Most programmers prefer learning the newest, most cutting-edge technology, but that's a risky gamble. Once upon a time Silverlight was a cutting-edge technology, and more than one of my contemporaries went all-in on it.

On the contrary, most programmers find old stuff boring. It turns out, though, that it may be worthwhile learning some old technologies like SQL. Be aware of the Lindy effect. If it's been around for a long time, it's likely to still be around for a long time. This is true for the next example as well.

HTTP #

The HTTP protocol has been around since 1991. It's an effectively text-based protocol, and you can easily engage with a web server on a near-protocol level. This is true for other older protocols as well.

In my first IT job in the late 1990s, one of my tasks was to set up and maintain Exchange Servers. It was also my responsibility to make sure that email could flow not only within the organization, but that we could exchange email with the rest of the internet. In order to test my mail servers, I would often just telnet into them on port 25 and type in the correct, text-based instructions to send a test email.

Granted, it's not that easy to telnet into a modern web server on port 80, but a ubiquitous tool like curl accomplishes the same goal. I recently wrote how knowing curl is better than knowing Postman. While this wasn't meant as an attack on Postman specifically, neither was it meant as a facile claim that curl is the only tool useful for ad-hoc interaction with HTTP-based APIs. Sometimes you only realize an underlying truth when you write about a thing and then other people find fault with your argument. The underlying truth, I think, is that it pays to understand HTTP and being able to engage with an HTTP-based web service at that level of abstraction.

Preferably in an automatable way.

Shells and scripting #

The reason I favour curl over other tools to interact with HTTP is that I already spend quite a bit of time at the command line. I typically have a little handful of terminal windows open on my laptop. If I need to test an HTTP server, curl is already available.

Many years ago, an employer introduced me to Git. Back then, there were no good graphical tools to interact with Git, so I had to learn to use it from the command line. I'm eternally grateful that it turned out that way. I still use Git from the command line.

When you install Git, by default you also install Git Bash. Since I was already using that shell to interact with Git, it began to dawn on me that it's a full-fledged shell, and that I could do all sorts of other things with it. It also struck me that learning Bash would be a better investment of my time than learning PowerShell. At the time, there was no indication that PowerShell would ever be relevant outside of Windows, while Bash was already available on most systems. Even today, knowing Bash strikes me as more useful than knowing PowerShell.

It's not that I do much Bash-scripting, but I could. Since I'm a programmer, if I need to automate something, I naturally reach for something more robust than shell scripting. Still, it gives me confidence to know that, since I already know Bash, Git, curl, etc., I could automate some tasks if I needed to.

Many a reader will probably complain that the Git CLI has horrible developer experience, but I will, again, postulate that it's not that bad. It helps if you understand some fundamentals.

Algorithms and data structures #

Git really isn't that difficult to understand once you realize that a Git repository is just a directed acyclic graph (DAG), and that branches are just labels that point to nodes in the graph. There are basic data structures that it's just useful to know. DAGs, trees, graphs in general, adjacency lists or adjacency matrices.

Knowing that such data structures exist is, however, not that useful if you don't know what you can do with them. If you have a graph, you can find a minimum spanning tree or a shortest-path tree, which sometimes turn out to be useful. Adjacency lists or matrices give you ways to represent graphs in code, which is why they are useful.

Contrary to certain infamous interview practices, you don't need to know these algorithms by heart. It's usually enough to know that they exist. I can't remember Dijkstra's algorithm off the top of my head, but if I encounter a problem where I need to find the shortest path, I can look it up.

Or, if presented with the problem of constructing current state from an Event Store, you may realize that it's just a left fold over a linked list. (This isn't my own realization; I first heard it from Greg Young in 2011.)

Now we're back at one of the first examples, that of FP knowledge. A list fold is its catamorphism. Again, these things are much easier to learn if you already know some fundamentals.

What to learn #

These examples may seems overwhelming. Do you really need to know all of that before things become easier?

No, that's not the point. I didn't start out knowing all these things, and some of them, I'm still not very good at. The point is rather that if you're wondering how to invest your limited time so that you can remain up to date, consider pursuing general-purpose knowledge rather than learning a specific technology.

Of course, if your employer asks you to use a particular library or programming language, you need to study that, if you're not already good at it. If, on the other hand, you decide to better yourself, you can choose what to learn next.

Ultimately, if your're learning for your own sake, the most important criterion may be: Choose something that interests you. If no-one forces you to study, it's too easy to give up if you lose interest.

If, however, you have the choice between learning Noun.js or design patterns, may I suggest the latter?

For life #

When are you done, you ask?

Never. There's more stuff than you can learn in a lifetime. I've met a lot of programmers who finally give up on the grind to keep up, and instead become managers.

As if there's nothing to learn when you're a manager. I'm fortunate that, before I went solo, I mainly had good managers. I'm under no illusion that they automatically became good managers. All I've heard said about management is that there's a lot to learn in that field, too. Really, it'd be surprising if that wasn't the case.

I can understand, however, how just keep learning the next library, the next framework, the next tool becomes tiring. As I've already outlined, I hit that wall more than a decade ago.

On the other hand, there are so many wonderful fundamentals that you can learn. You can do self-study, or you can enrol in a more formal programme if you have the opportunity. I'm currently following a course on compiler design. It's not that I expect to pivot to writing compilers for the rest of my career, but rather,

"It is considered a topic that you should know in order to be "well-cultured" in computer science.

"A good craftsman should know his tools, and compilers are important tools for programmers and computer scientists.

"The techniques used for constructing a compiler are useful for other purposes as well.

"There is a good chance that a programmer or computer scientist will need to write a compiler or interpreter for a domain-specific language."

Introduction to Compiler Design (from the introduction), Torben Ægidius Mogensen

That's good enough for me, and so far, I'm enjoying the course (although it's also hard work).

You may not find this particular topic interesting, but then hopefully you can find something else that you fancy. 3D rendering? Machine learning? Distributed systems architecture?

Conclusion #

Technology moves at a pace with which it's impossible to keep up. It's not just you who's falling behind. Everyone is. Even the best-paid GAMMA programmer knows next to nothing of all there is to know in the field. They may have superior skills in certain areas, but there will be so much other stuff that they don't know.

You may think of me as a thought leader if you will. If nothing else, I tend to be a prolific writer. Perhaps you even think I'm a good programmer. I should hope so. Who fancies themselves bad at something?

You should, however, have seen me struggle with C programming during a course on computer systems programming. There's a thing I'm happy if I never have to revisit.

You can't know it all. You can't keep up. But you can focus on learning the fundamentals. That tends to make it easier to learn specific technologies that build on those foundations.

This blog is totally free, but if you like it, please consider supporting it.

Gratification

2024-05-13T06:27:00+00:00

Some thoughts on developer experience.

Years ago, I was introduced to a concept called developer ergonomics. Despite the name, it's not about good chairs, standing desks, or multiple monitors. Rather, the concept was related to how easy it'd be for a developer to achieve a certain outcome. How easy is it to set up a new code base in a particular language? How much work is required to save a row in a database? How hard is it to read rows from a database and display the data on a web page? And so on.

These days, we tend to discuss developer experience rather than ergonomics, and that's probably a good thing. This term more immediately conveys what it's about.

I've recently had some discussions about developer experience (DevEx, DX) with one of my customers, and this has lead me to reflect more explicitly on this topic than previously. Most of what I'm going to write here are opinions and beliefs that go back a long time, but apparently, it's only recently that these notions have congealed in my mind under the category name developer experience.

This article may look like your usual old-man-yells-at-cloud article, but I hope that I can avoid that. It's not the case that I yearn for some lost past where 'we' wrote Plankalkül in Edlin. That, in fact, sounds like a horrible developer experience.

The point, rather, is that most attractive things come with consequences. For anyone who have been reading this blog even once in a while, this should come as no surprise.

Instant gratification #

Fat foods, cakes, and wine can be wonderful, but can be detrimental to your health if you overindulge. It can, however, be hard to resist a piece of chocolate, and even if we think that we shouldn't, we often fail to restrain ourselves. The temptation of instant gratification is simply too great.

There are other examples like this. The most obvious are the use of narcotics, lack of exercise, smoking, and dropping out of school. It may feel good in the moment, but can have long-term consequences.

Small children are notoriously bad at delaying gratification, and we often associate the ability to delay gratification with maturity. We all, however, fall in from time to time. Food and wine are my weak spots, while I don't do drugs, and I didn't drop out of school.

It strikes me that we often talk about ideas related to developer experience in a way where we treat developers as children. To be fair, many developers also act like children. I don't know how many times I've heard something like, "I don't want to write tests/go through a code review/refactor! I just want to ship working code now!"

Fine, so do I.

Even if wine is bad for me, it makes life worth living. As the saying goes, even if you don't smoke, don't drink, exercise rigorously, eat healthily, don't do drugs, and don't engage in dangerous activities, you're not guaranteed to live until ninety, but you're guaranteed that it's going to feel that long.

Likewise, I'm aware that doing everything right can sometimes take so long that by the time we've deployed the software, it's too late. The point isn't to always or never do certain things, but rather to be aware of the consequences of our choices.

Developer experience #

I've no problem with aiming to make the experience of writing software as good as possible. Some developer-experience thought leaders talk about the importance of documentation, predictability, and timeliness. Neither do I mind that a development environment looks good, completes my words, or helps me refactor.

To return to the analogy of human vices, not everything that feels good is ultimately bad for you. While I do like wine and chocolate, I also love sushi, white asparagus, turbot, chanterelles, lumpfish roe caviar, true morels, Norway lobster, and various other foods that tend to be categorized as healthy.

A good IDE with refactoring support, statement completion, type information, test runner, etc. is certainly preferable to writing all code in Notepad.

That said, there's a certain kind of developer tooling and language features that strikes me as more akin to candy. These are typically tools and technologies that tend to demo well. Recent examples include OpenAPI, GitHub Copilot, C# top-level statements, code generation, and Postman. Not all of these are unequivocally bad, but they strike me as mostly aiming at immature developers.

The point of this article isn't to single out these particular products, standards, or language features, but on the other hand, in order to make a point, I do have to at least outline why I find them problematic. They're just examples, and I hope that by explaining what is on my mind, you can see the pattern and apply it elsewhere.

OpenAPI #

A standard like OpenAPI, for example, looks attractive because it automates or standardizes much work related to developing and maintaining REST APIs. Frameworks and tools that leverage that standard automatically creates machine-readable schema and contract, which can be used to generate client code. Furthermore, an OpenAPI-aware framework can also autogenerate an entire web-based graphical user interface, which developers can use for ad-hoc testing.

I've worked with clients who also published these OpenAPI user interfaces to their customers, so that it was easy to get started with the APIs. Easy onboarding.

Instant gratification.

What's the problem with this? There are clearly enough apparent benefits that I usually have a hard time talking my clients out of pursuing this strategy. What are the disadvantages? Essentially, OpenAPI locks you into level 2 APIs. No hypermedia controls, no smooth conneg-based versioning, no HATEOAS. In fact, most of what makes REST flexible is lost. What remains is an ad-hoc, informally-specified, bug-ridden, slow implementation of half of SOAP.

I've previously described my misgivings about Copilot, and while I actually still use it, I don't want to repeat all of that here. Let's move on to another example.

Top-level statements #

Among many other language features, C# 9 got top-level-statements. This means that you don't need to write a Main method in a static class. Rather, you can have a single C# code file where you can immediately start executing code.

It's not that I consider this language feature particularly harmful, but it also solves what seems to me a non-problem. It demos well, though. If I understand the motivation right, the feature exists because 'modern' developers are used to languages like Python where you can, indeed, just create a .py file and start adding code statements.

In an attempt to make C# more attractive to such an audience, it, too, got that kind of developer experience enabled.

You may argue that this is a bid to remove some of the ceremony from the language, but I'm not convinced that this moves that needle much. The level of ceremony that a language like C# has is much deeper than that. That's not to target C# in particular. Java is similar, and don't even get me started on C or C++! Did anyone say header files?

Do 'modern' developers choose Python over C# because they can't be arsed to write a Main method? If that's the only reason, it strikes me as incredibly immature. I want instant gratification, and writing a Main method is just too much trouble!

If developers do, indeed, choose Python or JavaScript over C# and Java, I hope and believe that it's for other reasons.

This particular C# feature doesn't bother me, but I find it symptomatic of a kind of 'innovation' where language designers target instant gratification.

Postman #

Let's consider one more example. You may think that I'm now attacking a company that, for all I know, makes a decent product. I don't really care about that, though. What I do care about is the developer mentality that makes a particular tool so ubiquitous.

I've met web service developers who would be unable to interact with the HTTP APIs that they are themselves developing if they didn't have Postman. Likewise, there are innumerable questions on Stack Overflow where people ask questions about HTTP APIs and post screen shots of Postman sessions.

It's okay if you don't know how to interact with an HTTP API. After all, there's a first time for everything, and there was a time when I didn't know how to do this either. Apparently, however, it's easier to install an application with a graphical user interface than it is to use curl.

Do yourself a favour and learn curl instead of using Postman. Curl is a command-line tool, which means that you can use it for both ad-hoc experimentation and automation. It takes five to ten minutes to learn the basics. It's also free.

It still seems to me that many people are of a mind that it's easier to use Postman than to learn curl. Ultimately, I'd wager that for any task you do with some regularity, it's more productive to learn the text-based tool than the point-and-click tool. In a situation like this, I'd suggest that delayed gratification beats instant gratification.

CV-driven development #

It is, perhaps, easy to get the wrong impression from the above examples. I'm not pointing fingers at just any 'cool' new technology. There are techniques, languages, frameworks, and so on, which people pick up because they're exciting for other reasons. Often, such technologies solve real problems in their niches, but are then applied for the sole reason that people want to get on the bandwagon. Examples include Kubernetes, mocks, DI Containers, reflection, AOP, and microservices. All of these have legitimate applications, but we also hear about many examples where people use them just to use them.

That's a different problem from the one I'm discussing in this article. Usually, learning about such advanced techniques requires delaying gratification. There's nothing wrong with learning new skills, but part of that process is also gaining the understanding of when to apply the skill, and when not to. That's a different discussion.

Innovation is fine #

The point of this article isn't that every innovation is bad. Contrary to Charles Petzold, I don't really believe that Visual Studio rots the mind, although I once did publish an article that navigated the same waters.

Despite my misgivings, I haven't uninstalled GitHub Copilot, and I do enjoy many of the features in both Visual Studio (VS) and Visual Studio Code (VS Code). I also welcome and use many new language features in various languages.

I can certainly appreciate how an IDE makes many things easier. Every time I have to begin a new Haskell code base, I long for the hand-holding offered by Visual Studio when creating a new C# project.

And although I don't use the debugger much, the built-in debuggers in VS and VS Code sure beat GDB. It even works in Python!

There's even tooling that I wish for, but apparently never will get.

Simple made easy #

In Simple Made Easy Rich Hickey follows his usual look-up-a-word-in-the-dictionary-and-build-a-talk-around-the-definition style to contrast simple with easy. I find his distinction useful. A tool or technique that's close at hand is easy. This certainly includes many of the above instant-gratification examples.

An easy technique is not, however, necessarily simple. It may or may not be. Rich Hickey defines simple as the opposite of complex. Something that is complex is assembled from parts, whereas a simple thing is, ideally, single and undivisible. In practice, truly simple ideas and tools may not be available, and instead we may have to settle with things that are less complex than their alternatives.

Once you start looking for things that make simple things easy, you see them in many places. A big category that I personally favour contains all the language features and tools that make functional programming (FP) easier. FP tends to be simpler than object-oriented or procedural programming, because it explicitly distinguishes between and separates predictable code from unpredictable code. This does, however, in itself tend to make some programming tasks harder. How do you generate a random number? Look up the system time? Write a record to a database?

Several FP languages have special features that make even those difficult tasks easy. F# has computation expressions and Haskell has do notation.

Let's say you want to call a function that consumes a random number generator. In Haskell (as in .NET) random number generators are actually deterministic, as long as you give them the same seed. Generating a random seed, on the other hand, is non-deterministic, so has to happen in IO.

Without do notation, you could write the action like this:

rndSelect :: Integral i => [a] -> i -> IO [a]
rndSelect xs count = (\rnd -> rndGenSelect rnd xs count) <$> newStdGen

(The type annotation is optional.) While terse, this is hardly readable, and the developer experience also leaves something to be desired. Fortunately, however, you can rewrite this action with do notation, like this:

rndSelect :: Integral i => [a] -> i -> IO [a]
rndSelect xs count = do
  rnd <- newStdGen
  return $ rndGenSelect rnd xs count

Now we can clearly see that the action first creates the rnd random number generator and then passes it to rndGenSelect. That's what happened before, but it was buried in a lambda expression and Haskell's right-to-left causality. Most people would find the first version (without do notation) less readable, and more difficult to write.

Related to developer ergonomics, though, do notation makes the simple code (i.e. code that separates predictable code from unpredictable code) easy (that is; at hand).

F# computation expressions offer the same kind of syntactic sugar, making it easy to write simple code.

Delay gratification #

While it's possible to set up a development context in such a way that it nudges you to work in a way that's ultimately good for you, temptation is everywhere.

Not only may new language features, IDE functionality, or frameworks entice you to do something that may be disadvantageous in the long run. There may also be actions you don't take because it just feels better to move on.

Do you take the time to write good commit messages? Not just a single-line heading, but a proper message that explains your context and reasoning?

Most people I've observed working with source control 'just want to move on', and can't be bothered to write a useful commit message.

I hear about the same mindset when it comes to code reviews, particularly pull request reviews. Everyone 'just wants to write code', and no-one want to review other people's code. Yet, in a shared code base, you have to live with the code that other people write. Why not review it so that you have a chance to decide what that shared code base should look like?

Delay your own gratification a bit, and reap the awards later.

Conclusion #

The only goal I have with this article is to make you think about the consequences of new and innovative tools and frameworks. Particularly if they are immediately compelling, they may be empty calories. Consider if there may be disadvantages to adopting a new way of doing things.

Some tools and technologies give you instant gratification, but may be unhealthy in the long run. This is, like most other things, context-dependent. In the long run your company may no longer be around. Sometimes, it pays to deliberately do something that you know is bad, in order to reach a goal before your competition. That was the original technical debt metaphor.

Often, however, it pays to delay gratification. Learn curl instead of Postman. Learn to design proper REST APIs instead of relying on OpenAI. If you need to write ad-hoc scripts, use a language suitable for that.

Comments

Thomas Levesque #

Regarding Postman vs. curl, I have to disagree. Sure, curl is pretty easy to use. But while it's good for one-off tests, it sucks when you need to maintain a collection of requests that you can re-execute whevenever you want. In a testing session, you either need to re-type whole command, or reuse a previous command from the shell's history. Or have a file with all your commands and copy-paste to the shell. Either way, it's not a good experience.

That being said, I'm not very fond of Postman either. It's too heavyweight for what it does, IMHO, and the import/export mechanism is terrible for sharing collections with the team. These days, I tend to use VSCode extensions like httpYac or REST Client, or the equivalent that is now built into Visual Studio and Rider. It's much easier to work with than Postman (it's just text), while still being interactive. And since it's just a text file, you can just add it to the Git to share it with the team.

2024-05-14 02:38 UTC

Jiehong #

@Thomas Levesque: I agree with you, yet VSCode or Rider's extensions lock you into an editor quite quickly.

But you can have the best of both worlds: a cli tool first, with editor extensions. Just like Hurl.

Note that you can run a curl command from a file with curl --config [curl_request.file], it makes chaining requests (like with login and secrets) rather cumbersome very quickly.

2024-05-16 13:57 UTC

Mark Seemann #

Thank you, both, for writing. In the end, it's up to every team to settle on technical solutions that work for them, in that context. Likewise, it's up to each developer to identify methodology and tools that work for her or him, as long as it doesn't impact the rest of the team.

The reason I suggest curl over other alternatives is that not only is it free, it also tends to be ubiquitous. Most systems come with curl baked in - perhaps not a consumer installation of Windows, but if you have developer tools installed, it's highly likely that you have curl on your machine. It's a fundamental skill that may serve you well if you know it.

In addition to that, since curl is a CLI you can always script it if you need a kind of semi-automation. What prevents you from maintaining a collection of script files? They could even take command-line arguments, if you'd like.

That said, personally, if I realize that I need to maintain a collection of requests that I can re-execute whenever I want, I'd prefer writing a 'real' program. On the other hand, I find a tool like curl useful for ad-hoc testing.

2024-05-21 5:36 UTC

Johannes Egger #

... maintain a collection of requests that you can re-execute whevenever you want.

@Thomas Levesque: that sounds like a proper collection of automatically executable tests would be a better fit. But yeah, it's just easier to write those simple commands than to set up a test project - instant gratification 😉

2024-05-28 17:02 UTC

This blog is totally free, but if you like it, please consider supporting it.

Conservative codomain conjecture

2024-05-06T06:35:00+00:00

An API design heuristic.

For a while now, I've been wondering whether, in the language of Postel's law, one should favour being liberal in what one accepts over being conservative in what one sends. Yes, according to the design principle, a protocol or API should do both, but sometimes, you can't do that. Instead, you'll have to choose. I've recently reached the tentative conclusion that it may be a good idea favouring being conservative in what one sends.

Good API design explicitly considers contracts. What are the preconditions for invoking an operation? What are the postconditions? Are there any invariants? These questions are relevant far beyond object-oriented design. They are equally important in Functional Programming, as well as in service-oriented design.

If you have a type system at your disposal, you can often model pre- and postconditions as types. In practice, however, it frequently turns out that there's more than one way of doing that. You can model an additional precondition with an input type, but you can also model potential errors as a return type. Which option is best?

That's what this article is about, and my conjecture is that constraining the input type may be preferable, thus being conservative about what is returned.

An average example #

That's all quite abstract, so for the rest of this article, I'll discuss this kind of problem in the context of an example. We'll revisit the good old example of calculating an average value. This example, however, is only a placeholder for any kind of API design problem. This article is only superficially about designing an API for calculating an average. More generally, this is about API design. I like the average example because it's easy to follow, and it does exhibit some characteristics that you can hopefully extrapolate from.

In short, what is the contract of the following method?

public static TimeSpan Average(this IEnumerable<TimeSpan> timeSpans)
{
    var sum = TimeSpan.Zero;
    var count = 0;
    foreach (var ts in timeSpans)
    {
        sum += ts;
        count++;
    }
    return sum / count;
}

What are the preconditions? What are the postconditions? Are there any invariants?

Before I answer these questions, I'll offer equivalent code in two other languages. Here it is in F#:

let average (timeSpans : TimeSpan seq) =
    timeSpans
    |> Seq.averageBy (_.Ticks >> double)
    |> int64
    |> TimeSpan.FromTicks

And in Haskell:

average :: (Fractional a, Foldable t) => t a -> a
average xs = sum xs / fromIntegral (length xs)

These three examples have somewhat different implementations, but the same externally observable behaviour. What is the contract?

It seems straightforward: If you input a sequence of values, you get the average of all of those values. Are there any preconditions? Yes, the sequence can't be empty. Given an empty sequence, all three implementations throw an exception. (The Haskell version is a little more nuanced than that, but given an empty list of NominalDiffTime, it does throw an exception.)

Any other preconditions? At least one more: The sequence must be finite. All three functions allow infinite streams as input, but if given one, they will fail to return an average.

Are there any postconditions? I can only think of a statement that relates to the preconditions: If the preconditions are fulfilled, the functions will return the correct average value (within the precision allowed by floating-point calculations).

All of this, however, is just warming up. We've been over this ground before.

Modelling contracts #

Keep in mind that this average function is just an example. Think of it as a stand-in for a procedure that's much more complicated. Think of the most complicated operation in your code base.

Not only do real code bases have many complicated operations. Each comes with its own contract, different from the other operations, and if the team isn't explicitly thinking in terms of contracts, these contracts may change over time, as the team adds new features and fixes bugs.

It's difficult work to keep track of all those contracts. As I argue in Code That Fits in Your Head, it helps if you can automate away some of that work. One way is having good test coverage. Another is to leverage a static type system, if you're fortunate enough to work in a language that has one. As I've also already covered, you can't replace all rules with types, but it doesn't mean that using the type system is ineffectual. Quite the contrary. Every part of a contract that you can offload to the type system frees up your brain to think about something else - something more important, hopefully.

Sometimes there's no good way to to model a precondition with a type, or perhaps it's just too awkward. At other times, there's really only a single way to address a concern. When it comes to the precondition that you can't pass an infinite sequence to the average function, change the type so that it takes some finite collection instead. That's not what this article is about, though.

Assuming that you've already dealt with the infinite-sequence issue, how do you address the other precondition?

Error-handling #

A typical object-oriented move is to introduce a Guard Clause:

public static TimeSpan Average(this IReadOnlyCollection<TimeSpan> timeSpans)
{
    if (!timeSpans.Any())
        throw new ArgumentOutOfRangeException(
            nameof(timeSpans),
            "Can't calculate the average of an empty collection.");
 
    var sum = TimeSpan.Zero;
    foreach (var ts in timeSpans)
        sum += ts;
    return sum / timeSpans.Count;
}

You could do the same in F#:

let average (timeSpans : TimeSpan seq) =
    if Seq.isEmpty timeSpans then
        raise (
            ArgumentOutOfRangeException(
                nameof timeSpans,
                "Can't calculate the average of an empty collection."))
 
    timeSpans
    |> Seq.averageBy (_.Ticks >> double)
    |> int64
    |> TimeSpan.FromTicks

You could also replicate such behaviour in Haskell, but it'd be highly unidiomatic. Instead, I'd rather discuss one idiomatic solution in Haskell, and then back-port it.

While you can throw exceptions in Haskell, you typically handle predictable errors with a sum type. Here's a version of the Haskell function equivalent to the above C# code:

average :: (Foldable t, Fractional a) => t a -> Either String a
average xs =
  if null xs
    then Left "Can't calculate the average of an empty collection."
    else Right $ sum xs / fromIntegral (length xs)

For the readers that don't know the Haskell base library by heart, null is a predicate that checks whether or not a collection is empty. It has nothing to do with null pointers.

This variation returns an Either value. In practice you shouldn't just return a String as the error value, but rather a strongly-typed value that other code can deal with in a robust manner.

On the other hand, in this particular example, there's really only one error condition that the function is able to detect, so you often see a variation where instead of a single error message, such a function just doesn't return anything:

average :: (Foldable t, Fractional a) => t a -> Maybe a
average xs = if null xs then Nothing else Just $ sum xs / fromIntegral (length xs)

This iteration of the function returns a Maybe value, indicating that a return value may or may not be present.

Liberal domain #

We can back-port this design to F#, where I'd also consider it idiomatic:

let average (timeSpans : IReadOnlyCollection<TimeSpan>) =
    if timeSpans.Count = 0 then None else
        timeSpans
        |> Seq.averageBy (_.Ticks >> double)
        |> int64
        |> TimeSpan.FromTicks
        |> Some

This version returns a TimeSpan option rather than just a TimeSpan. While this may seem to put the burden of error-handling on the caller, nothing has really changed. The fundamental situation is the same. Now the function is just being more explicit (more honest, you could say) about the pre- and postconditions. The type system also now insists that you deal with the possibility of error, rather than just hoping that the problem doesn't occur.

In C# you can expand the codomain by returning a nullable TimeSpan value, but such an option may not always be available at the language level. Keep in mind that the Average method is just an example standing in for something that may be more complicated. If the original return type is a reference type rather than a value type, only recent versions of C# allows statically-checked nullable reference types. What if you're working in an older version of C#, or another language that doesn't have that feature?

In that case, you may need to introduce an explicit Maybe class and return that:

public static Maybe<TimeSpan> Average(this IReadOnlyCollection<TimeSpan> timeSpans)
{
    if (timeSpans.Count == 0)
        return new Maybe<TimeSpan>();
 
    var sum = TimeSpan.Zero;
    foreach (var ts in timeSpans)
        sum += ts;
    return new Maybe<TimeSpan>(sum / timeSpans.Count);
}

Two things are going on here; one is obvious while the other is more subtle. Clearly, all of these alternatives change the static type of the function in order to make the pre- and postconditions more explicit. So far, they've all been loosening the codomain (the return type). This suggests a connection with Postel's law: be conservative in what you send, be liberal in what you accept. These variations are all liberal in what they accept, but it seems that the API design pays the price by also having to widen the set of possible return values. In other words, such designs aren't conservative in what they send.

Do we have other options?

Conservative codomain #

Is it possible to instead design the API in such a way that it's conservative in what it returns? Ideally, we'd like it to guarantee that it returns a number. This is possible by making the preconditions even more explicit. I've also covered that alternative already, so I'm just going to repeat the C# code here without further comments:

public static TimeSpan Average(this NotEmptyCollection<TimeSpan> timeSpans)
{
    var sum = timeSpans.Head;
    foreach (var ts in timeSpans.Tail)
        sum += ts;
    return sum / timeSpans.Count;
}

This variation promotes another precondition to a type. The precondition that the input collection mustn't be empty can be explicitly modelled with a type. This enables us to be conservative about the codomain. The method now guarantees that it will return a value.

This idea is also easily ported to F#:

type NonEmpty<'a> = { Head : 'a; Tail : IReadOnlyCollection<'a> }
 
let average (timeSpans : NonEmpty<TimeSpan>) =
    [ timeSpans.Head ] @ List.ofSeq timeSpans.Tail
    |> List.averageBy (_.Ticks >> double)
    |> int64
    |> TimeSpan.FromTicks

The average function now takes a NonEmpty collection as input, and always returns a proper TimeSpan value.

Haskell already comes with a built-in NonEmpty collection type, and while it oddly doesn't come with an average function, it's easy enough to write:

import qualified Data.List.NonEmpty as NE

average :: Fractional a => NE.NonEmpty a -> a
average xs = sum xs / fromIntegral (NE.length xs)

You can find a recent example of using a variation of that function here.

Choosing between the two alternatives #

While Postel's law recommends having liberal domains and conservative codomains, in the case of the average API, we can't have both. If we design the API with a liberal input type, the output type has to be liberal as well. If we design with a restrictive input type, the output can be guaranteed. In my experience, you'll often find yourself in such a conundrum. The average API examined in this article is just an example, while the problem occurs often.

Given such a choice, what should you choose? Is it even possible to give general guidance on this sort of problem?

For decades, I considered such a choice a toss-up. After all, these solutions seem to be equivalent. Perhaps even isomorphic?

When I recently began to explore this isomorphism more closely, it dawned on me that there's a small asymmetry in the isomorphism that favours the conservative codomain option.

Isomorphism #

An isomorphism is a two-way translation between two representations. You can go back and forth between the two alternatives without loss of information.

Is this possible with the two alternatives outlined above? For example, if you have the conservative version, can create the liberal alternative? Yes, you can:

average' :: Fractional a => [a] -> Maybe a
average' = fmap average . NE.nonEmpty

Not surprisingly, this is trivial in Haskell. If you have the conservative version, you can just map it over a more liberal input.

In F# it looks like this:

module NonEmpty =
    let tryOfSeq xs =
        if Seq.isEmpty xs then None
        else Some { Head = Seq.head xs; Tail = Seq.tail xs |> List.ofSeq }
 
let average' (timeSpans : IReadOnlyCollection<TimeSpan>) =
    NonEmpty.tryOfSeq timeSpans |> Option.map average

In C# we can create a liberal overload that calls the conservative method:

public static TimeSpan? Average(this IReadOnlyCollection<TimeSpan> timeSpans)
{
    if (timeSpans.Count == 0)
        return null;
 
    var arr = timeSpans.ToArray();
    return new NotEmptyCollection<TimeSpan>(arr[0], arr[1..]).Average();
}

Here I just used a Guard Clause and explicit construction of the NotEmptyCollection. I could also have added a NotEmptyCollection.TryCreate method, like in the F# and Haskell examples, but I chose the above slightly more imperative style in order to demonstrate that my point isn't tightly coupled to the concept of functors, mapping, and other Functional Programming trappings.

These examples highlight how you can trivially make a conservative API look like a liberal API. Is it possible to go the other way? Can you make a liberal API look like a conservative API?

Yes and no.

Consider the liberal Haskell version of average, shown above; that's the one that returns Maybe a. Can you make a conservative function based on that?

average' :: Fractional a => NE.NonEmpty a -> a
average' xs = fromJust $ average xs

Yes, this is possible, but only by resorting to the partial function fromJust. I'll explain why that is a problem once we've covered examples in the two other languages, such as F#:

let average' (timeSpans : NonEmpty<TimeSpan>) =
    [ timeSpans.Head ] @ List.ofSeq timeSpans.Tail |> average |> Option.get

In this variation, average is the liberal version shown above; the one that returns a TimeSpan option. In order to make a conservative version, the average' function can call the liberal average function, but has to resort to the partial function Option.get.

The same issue repeats a third time in C#:

public static TimeSpan Average(this NotEmptyCollection<TimeSpan> timeSpans)
{
    return timeSpans.ToList().Average().Value;
}

This time, the partial function is the unsafe Value property, which throws an InvalidOperationException if there's no value.

This even violates Microsoft's own design guidelines:

"AVOID throwing exceptions from property getters."

Krzystof Cwalina and Brad Abrams

I've cited Cwalina and Abrams as the authors, since this rule can be found in my 2006 edition of Framework Design Guidelines. This isn't a new insight.

While the two alternatives are 'isomorphic enough' that we can translate both ways, the translations are asymmetric in the sense that one is safe, while the other has to resort to an inherently unsafe operation to make it work.

Encapsulation #

I've called the operations fromJust, Option.get, and Value partial, and only just now used the word unsafe. You may protest that neither of the three examples are unsafe in practice, since we know that the input is never empty. Thus, we know that the liberal function will always return a value, and therefore it's safe to call a partial function, even though these operations are unsafe in the general case.

While that's true, consider how the burden shifts. When you want to promote a conservative variant to a liberal variant, you can rely on all the operations being total. On the other hand, if you want to make a liberal variant look conservative, the onus is on you. None of the three type systems on display here can perform that analysis for you.

This may not be so bad when the example is as simple as taking the average of a collection of numbers, but does it scale? What if the operation you're invoking is much more complicated? Can you still be sure that you safely invoke a partial function on the return value?

As Code That Fits in Your Head argues, procedures quickly become so complicated that they no longer fit in your head. If you don't have well-described and patrolled contracts, you don't know what the postconditions are. You can't trust the return values from method calls, or even the state of the objects you passed as arguments. This tend to lead to defensive coding, where you write code that checks the state of everything all too often.

The remedy is, as always, good old encapsulation. In this case, check the preconditions at the beginning, and capture the result of that check in an object or type that is guaranteed to be always valid. This goes beyond making illegal states unrepresentable because it also works with predicative types. Once you're past the Guard Clauses, you don't have to check the preconditions again.

This kind of thinking illustrates why you need a multidimensional view on API design. As useful as Postel's law sometimes is, it doesn't address all problems. In fact, it turned out to be unhelpful in this context, while another perspective proves more fruitful. Encapsulation is the art and craft of designing APIs in such a way that they suggest or even compels correct interactions. The more I think of this, the more it strikes me that a ranking is implied: Preconditions are more important than postconditions, because if the preconditions are unfulfilled, you can't trust the postconditions, either.

Mapping #

What's going on here? One perspective is to view types as sets. In the average example, the function maps from one set to another:

Which sets are they? We can think of the average function as a mapping from the set of non-empty collections of numbers to the set of real numbers. In programming, we can't represent real numbers, so instead, the left set is going to be the set of all the non-empty collections the computer or the language can represent and hold in (virtual) memory, and the right-hand set is the set of all the possible numbers of whichever type you'd like (32-bit signed integers, 64-bit floating-point numbers, 8-bit unsigned integers, etc.).

In reality, the left-hand set is much larger than the set to the right.

Drawing all those arrows quickly becomes awkward , so instead, we may draw each mapping as a pipe. Such a pipe also corresponds to a function. Here's an intermediate step in such a representation:

One common element is, however, missing from the left set. Which one?

Pipes #

The above mapping corresponds to the conservative variation of the function. It's a total function that maps all values in the domain to a value in the codomain. It accomplishes this trick by explicitly constraining the domain to only those elements on which it's defined. Due to the preconditions, that excludes the empty collection, which is therefore absent from the left set.

What if we also want to allow the empty collection to be a valid input?

Unless we find ourselves in some special context where it makes sense to define a 'default average value', we can't map an empty collection to any meaningful number. Rather, we'll have to map it to some special value, such as Nothing, None, or null:

This extra pipe is free, because it's supplied by the Maybe functor's mapping (Select, map, fmap).

What happens if we need to go the other way? If the function is the liberal variant that also maps the empty collection to a special element that indicates a missing value?

In this case, it's much harder to disentangle the mappings. If you imagine that a liquid flows through the pipes, we can try to be careful and avoid 'filling up' the pipe.

The liquid represents the data that we do want to transmit through the pipe. As this illustration suggests, we now have to be careful that nothing goes wrong. In order to catch just the right outputs on the right side, you need to know how high the liquid may go, and attach a an 'flat-top' pipe to it:

As this illustration tries to get across, this kind of composition is awkward and error-prone. What's worse is that you need to know how high the liquid is going to get on the right side. This depends on what actually goes on inside the pipe, and what kind of input goes into the left-hand side.

This is a metaphor. The longer the pipe is, the more difficult it gets to keep track of that knowledge. The stubby little pipe in these illustrations may correspond to the average function, which is an operation that easily fits in our heads. It's not too hard to keep track of the preconditions, and how they map to postconditions.

Thus, turning such a small liberal function into a conservative function is possible, but already awkward. If the operation is complicated, you can no longer keep track of all the details of how the inputs relate to the outputs.

Additive extensibility #

This really shouldn't surprise us. Most programming languages come with all sorts of facilities that enable extensibility: The ability to add more functionality, more behaviour, more capabilities, to existing building blocks. Conversely, few languages come with removability facilities. You can't, commonly, declare that an object is an instance of a class, except one method, or that a function is just like another function, except that it doesn't accept a particular subset of input.

This explains why we can safely make a conservative function liberal, but why it's difficult to make a liberal function conservative. This is because making a conservative function liberal adds functionality, while making a liberal function conservative attempts to remove functionality.

Conjecture #

All this leads me to the following conjecture: When faced with a choice between two versions of an API, where one has a liberal domain, and the other a conservative codomain, choose the design with the conservative codomain.

If you need the liberal version, you can create it from the conservative operation. The converse need not be true.

Conclusion #

Postel's law encourages us to be liberal with what we accept, but conservative with what we return. This is a good design heuristic, but sometimes you're faced with mutually exclusive alternatives. If you're liberal with what you accept, you'll also need to be too loose with what you return, because there are input values that you can't handle. On the other hand, sometimes the only way to be conservative with the output is to also be restrictive when it comes to input.

Given two such alternatives, which one should you choose?

This article conjectures that you should choose the conservative alternative. This isn't a political statement, but simply a result of the conservative design being the smaller building block. From a small building block, you can compose something bigger, whereas from a bigger unit, you can't easily extract something smaller that's still robust and useful.

This blog is totally free, but if you like it, please consider supporting it.

Service compatibility is determined based on policy

2024-04-29T11:12:00+00:00

A reading of the fourth Don Box tenet, with some commentary.

This article is part of a series titled The four tenets of SOA revisited. In each of these articles, I'll pull one of Don Box's four tenets of service-oriented architecture (SOA) out of the original MSDN Magazine article and add some of my own commentary. If you're curious why I do that, I cover that in the introductory article.

In this article, I'll go over the fourth tenet, quoting from the MSDN Magazine article unless otherwise indicated.

Service compatibility is determined based on policy #

The fourth tenet is the forgotten one. I could rarely remember exactly what it included, but it does give me an opportunity to bring up a few points about compatibility. The articles said:

Object-oriented designs often confuse structural compatibility with semantic compatibility. Service-orientation deals with these two axes separately. Structural compatibility is based on contract and schema and can be validated (if not enforced) by machine-based techniques (such as packet-sniffing, validating firewalls). Semantic compatibility is based on explicit statements of capabilities and requirements in the form of policy.

Every service advertises its capabilities and requirements in the form of a machine-readable policy expression. Policy expressions indicate which conditions and guarantees (called assertions) must hold true to enable the normal operation of the service. Policy assertions are identified by a stable and globally unique name whose meaning is consistent in time and space no matter which service the assertion is applied to. Policy assertions may also have parameters that qualify the exact interpretation of the assertion. Individual policy assertions are opaque to the system at large, which enables implementations to apply simple propositional logic to determine service compatibility.

As you can tell, this description is the shortest of the four. This is also the point where I begin to suspect that my reading of the third tenet may deviate from what Don Box originally had in mind.

This tenet is also the most baffling to me. As I understand it, the motivation behind the four tenets was to describe assumptions about the kind of systems that people would develop with Windows Communication Foundation (WCF), or SOAP in general.

While I worked with WCF for a decade, the above description doesn't ring a bell. Reading it now, the description of policy sounds more like a system such as clojure.spec, although that's not something I know much about either. I don't recall WCF ever having a machine-readable policy subsystem, and if it had, I never encountered it.

It does seem, however, as though what I interpret as contract, Don Box called policy.

Despite my confusion, the word compatibility is worth discussing, regardless of whether that was what Don Box meant. A well-designed service is one where you've explicitly considered forwards and backwards compatibility.

Versioning #

Planning for forwards and backwards compatibility does not imply that you're expected to be able to predict the future. It's fine if you have so much experience developing and maintaining online systems that you may have enough foresight to plan for certain likely changes that you may have to make in the future, but that's not what I have in mind.

Rather, what you should do is to have a system that enables you to detect breaking changes before you deploy them. Furthermore you should have a strategy for how to deal with the perceived necessity to introduce breaking changes.

The most effective strategy that I know of is to employ explicit versioning, particularly message versioning. You can version an entire service as one indivisible block, but I often find it more useful to version at the message level. If you're designing a REST API, for example, you can take advantage of Content Negotiation.

If you like, you can use Semantic Versioning as a versioning scheme, but for services, the thing that mostly matters is the major version. Thus, you may simply label your messages with the version numbers 1, 2, etc.

If you already have a published service without explicit message version information, then you can still retrofit versioning afterwards. Imagine that your existing data looks like this:

{
  "singleTable": {
    "capacity": 16,
    "minimalReservation": 10
  }
}

This JSON document has no explicit version information, but you can interpret that as implying that the document has the 'default' version, which is always 1:

{
  "singleTable": {
    "version": 1,
    "capacity": 16,
    "minimalReservation": 10
  }
}

If you later realize that you need to make a breaking change, you can do that by increasing the (major) version:

{
  "singleTable": {
    "version": 2,
    "id": 12,
    "capacity": 16,
    "minimalReservation": 10
  }
}

Recipients can now look for the version property to learn how to interpret the rest of the message, and failing to find it, infer that this is version 1.

As Don Box wrote, in a service-oriented system, you can't just update all systems in a single coordinated release. Therefore, you must never break compatibility. Versioning enables you to move forward in a way that does break with the past, but without breaking existing clients.

Ultimately, you may attempt to retire old service versions, but be ready to keep them around for a long time.

For more of my thoughts about backwards compatibility, see Backwards compatibility as a profunctor.

Conclusion #

The fourth tenet is the most nebulous, and I wonder if it was ever implemented. If it was, I'm not aware of it. Even so, compatibility is an important component of service design, so I took the opportunity to write about that. In most cases, it pays to think explicitly about message versioning.

I have the impression that Don Box had something in mind more akin to what I call contract. Whether you call it one thing or another, it stands to reason that you often need to attach extra rules to simple types. The schema may define an input value as a number, but the service does require that this particular number is a natural number. Or that a string is really a proper encoding of a date. Perhaps you call that policy. I call it contract. In any case, clearly communicating such expectations is important for systems to be compatible.

This blog is totally free, but if you like it, please consider supporting it.