Kent Beck's money TDD example has some interesting properties.

This article is part of a series about monoids. In short, a monoid is an associative binary operation with a neutral element (also known as identity).

In the first half of Test-Driven Development By Example Kent Beck explores how to develop a simple and flexible Money API using test-driven development. Towards the end, he arrives at a design that warrants further investigation.

Kent Beck's API #

The following treatment of Kent Beck's code is based on Yawar Amin's C# reproduction of Kent Beck's original Java code, further forked and manipulated by me.

The goal of Kent Beck's exercise is to develop an object-oriented API able to handle money of multiple currencies, and for example be able to express operations such as 5 USD + 10 CHF. Towards the end of the example, he arrives at an interface that, translated to C#, looks like this:

public interface IExpression
{
    Money Reduce(Bank bank, string to);
    IExpression Plus(IExpression addend);
    IExpression Times(int multiplier);
}

The Reduce method reduces an IExpression object to a single currency (to), represented as a Money object. This is useful if you have an IExpression object that contains several currencies.

The Plus method adds another IExpression object to the current object, and returns a new IExpression. This could be money in a single currency, but could also represent money held in more than one currency.

The Times method multiplies an IExpression with a multiplier. You'll notice that, throughout this example code base, both multiplier and amounts are modelled as integers. I think that Kent Beck did this as a simplification, but a more realistic example should use decimal values.

The metaphor is that you can model money as one or more expressions. A simple expression would be 5 USD, but you could also have 5 USD + 10 CHF or 5 USD + 10 CHF + 10 USD. While you can reduce some expressions, such as 5 CHF + 7 CHF, you can't reduce an expression like 5 USD + 10 CHF unless you have an exchange rate. Instead of attempting to reduce monetary values, this particular design builds an expression tree until you decide to evaluate it. (Sounds familiar?)

Kent Beck implements IExpression twice:

  • Money models an amount in a single currency. It contains an Amount and a Currency read-only property. It's the quintessential Value Object.
  • Sum models the sum of two other IExpression objects. It contains two other IExpression objects, called Augend and Addend.
If you want to express 5 USD + 10 CHF, you can write:

IExpression sum = new Sum(Money.Dollar(5), Money.Franc(10));

where Money.Dollar and Money.Franc are two static factory methods that return Money values.

Associativity #

Did you notice that Plus is a binary operation? Could it be a monoid as well?

In order to be a monoid, it must obey the monoid laws, the first of which is that the operation must be associative. This means that for three IExpression objects, x, y, and z, x.Plus(y).Plus(z) must be equal to x.Plus(y.Plus(z)). How should you interpret equality here? The return value from Plus is another IExpression value, and interfaces don't have custom equality behaviour. Either, it's up to the individual implementations (Money and Sum) to override and implement equality, or you can use test-specific equality.

The xUnit.net assertion library supports test-specific equality via custom comparers (for more details, see my Advanced Unit Testing Pluralsight course). The original Money API does, however, already include a way to compare expressions!

The Reduce method can reduce any IExpression to a single Money object (that is, to a single currency), and since Money is a Value Object, it has structural equality. You can use this to compare the values of IExpression objects. All you need is an exchange rate.

In the book, Kent Beck uses a 2:1 exchange rate between CHF and USD. As I'm writing this, the exchange rate is 0.96 Swiss Franc to a Dollar, but since the example code consistently models money as integers, that rounds to a 1:1 exchange rate. This is, however, a degenerate case, so instead, I'm going to stick to the book's original 2:1 exchange rate.

You can now add an Adapter between Reduce and xUnit.net in the form of an IEqualityComparer<IExpression>:

public class ExpressionEqualityComparer : IEqualityComparer<IExpression>
{
    private readonly Bank bank;
 
    public ExpressionEqualityComparer()
    {
        bank = new Bank();
        bank.AddRate("CHF""USD", 2);
    }
 
    public bool Equals(IExpression x, IExpression y)
    {
        var xm = bank.Reduce(x, "USD");
        var ym = bank.Reduce(y, "USD");
        return object.Equals(xm, ym);
    }
 
    public int GetHashCode(IExpression obj)
    {
        return bank.Reduce(obj, "USD").GetHashCode();
    }
}

You'll notice that this custom equality comparer uses a Bank object with a 2:1 exchange rate. Bank is another object from the Test-Driven Development example. It doesn't implement any interface itself, but it does appear as an argument in the Reduce method.

In order to make your test code more readable, you can add a static helper class:

public static class Compare
{
    public static ExpressionEqualityComparer UsingBank =
        new ExpressionEqualityComparer();
}

This enables you to write an assertion for associativity like this:

Assert.Equal(
    x.Plus(y).Plus(z),
    x.Plus(y.Plus(z)),
    Compare.UsingBank);

In my fork of Yawar Amin's code base, I added this assertion to an FsCheck-based automated test, and it holds for all the Sum and Money objects that FsCheck generates.

In its present incarnation, IExpression.Plus is associative, but it's worth noting that this isn't guaranteed to last. An interface like IExpression is an extensibility point, so someone could easily add a third implementation that would violate associativity. We can tentatively conclude that Plus is currently associative, but that the situation is delicate.

Identity #

If you accept that IExpression.Plus is associative, it's a monoid candidate. If an identity element exists, then it's a monoid.

Kent Beck never adds an identity element in his book, but you can add one yourself:

public static class Plus
{
    public readonly static IExpression Identity = new PlusIdentity();
 
    private class PlusIdentity : IExpression
    {
        public IExpression Plus(IExpression addend)
        {
            return addend;
        }
 
        public Money Reduce(Bank bank, string to)
        {
            return new Money(0, to);
        }
 
        public IExpression Times(int multiplier)
        {
            return this;
        }
    }
}

There's only a single identity element, so it makes sense to make it a Singleton. The private PlusIdentity class is a new IExpression implementation that deliberately doesn't do anything.

In Plus, it simply returns the input expression. This is the same behaviour as zero has for integer addition. When adding numbers together, zero is the identity element, and the same is the case here. This is more explicitly visible in the Reduce method, where the identity expression simply reduces to zero in the requested currency. Finally, if you multiply the identity element, you still get the identity element. Here, interestingly, PlusIdentity behaves similar to the identity element for multiplication (1).

You can now write the following assertions for any IExpression x:

Assert.Equal(x, x.Plus(Plus.Identity), Compare.UsingBank);
Assert.Equal(x, Plus.Identity.Plus(x), Compare.UsingBank);

Running this as a property-based test, it holds for all x generated by FsCheck. The same caution that applies to associativity also applies here: IExpression is an extensibility point, so you can't be sure that Plus.Identity will be the identity element for all IExpression implementations someone could create, but for the three implementations that now exist, the monoid laws hold.

IExpression.Plus is a monoid.

Multiplication #

In basic arithmetic, the multiplication operator is called times. When you write 3 * 5, it literally means that you have 3 five times (or do you have 5 three times?). In other words:

3 * 5 = 3 + 3 + 3 + 3 + 3

Does a similar relationship exist for IExpression?

Perhaps, we can take a hint from Haskell, where monoids and semigroups are explicit parts of the core library. You're going to learn about semigroups later, but for now, it's interesting to observe that the Semigroup typeclass defines a function called stimes, which has the type Integral b => b -> a -> a. Basically, what this means that for any integer type (16-bit integer, 32-bit integer, etc.) stimes takes an integer and a value a and 'multiplies' the value. Here, a is a type for which a binary operation exists.

In C# syntax, stimes would look like this as an instance method on a Foo class:

public Foo Times(int multiplier)

I named the method Times instead of STimes, since I strongly suspect that the s in Haskell's stimes stands for Semigroup.

Notice how this is the same type of signature as IExpression.Times.

If it's possible to define a universal implementation of such a function in Haskell, could you do the same in C#? In Money, you can implement Times based on Plus:

public IExpression Times(int multiplier)
{
    return Enumerable
        .Repeat((IExpression)this, multiplier)
        .Aggregate((x, y) => x.Plus(y));
}

The static Repeat LINQ method returns this as many times as requested by multiplier. The return value is an IEnumerable<IExpression>, but according to the IExpression interface, Times must return a single IExpression value. You can use the Aggregate LINQ method to repeatedly combine two IExpression values (x and y) to one, using the Plus method.

This implementation is hardly as efficient as the previous, individual implementation, but the point here isn't about efficiency, but about a common, reusable abstraction. The exact same implementation can be used to implement Sum.Times:

public IExpression Times(int multiplier)
{
    return Enumerable
        .Repeat((IExpression)this, multiplier)
        .Aggregate((x, y) => x.Plus(y));
}

This is literally the same code as for Money.Times. You can also copy and paste this code to PlusIdentity.Times, but I'm not going to repeat it here, because it's the same code as above.

This means that you can remove the Times method from IExpression:

public interface IExpression
{
    Money Reduce(Bank bank, string to);
    IExpression Plus(IExpression addend);
}

Instead, you can implement it as an extension method:

public static class Expression
{
    public static IExpression Times(this IExpression exp, int multiplier)
    {
        return Enumerable
            .Repeat(exp, multiplier)
            .Aggregate((x, y) => x.Plus(y));
    }
}

This works because any IExpression object has a Plus method.

As I've already admitted, this is likely to be less efficient than specialised implementations of Times. In Haskell, this is addressed by making stimes part of the typeclass, so that implementers can implement a more efficient algorithm than the default implementation. In C#, the same effect could be achieved by refactoring IExpression to an abstract base class, with Times as a public virtual (overridable) method.

Haskell sanity check #

Since Haskell has a more formal definition of a monoid, you may want to try to port Kent Beck's API to Haskell, as a proof of concept. In its final modification, my C# fork has three implementations of IExpression:

  • Money
  • Sum
  • PlusIdentity
While interfaces are extensible, we were rightfully uneasy about this, so in Haskell, it seems safer to model these three subtypes as a sum type:

data Expression = Money { amount :: Int, currency :: String }
                | Sum { augend :: Expression, addend :: Expression }
                | MoneyIdentity
                deriving (Show)

You can formally make this a Monoid:

instance Monoid Expression where
  mempty = MoneyIdentity
  mappend MoneyIdentity y = y
  mappend x MoneyIdentity = x
  mappend x y             = Sum x y

The C# Plus method is here implemented by the mappend function. The only remaining member of IExpression is Reduce, which you can implement like this:

import Data.Map.Strict (Map(!))

reduce :: Ord a => Map (String, a) Int -> a -> Expression -> Int
reduce bank to (Money amt cur) = amt `div` rate
  where rate = bank ! (cur, to)
reduce bank to (Sum x y) = reduce bank to x + reduce bank to y
reduce _ _ MoneyIdentity = 0

Haskell's typeclass mechanism takes care of the rest, so that, for example, you can reproduce one of Kent Beck's original tests like this:

λ> let bank = fromList [(("CHF","USD"),2), (("USD", "USD"),1)]
λ> let sum = stimesMonoid 2 $ MoneyPort.Sum (Money 5 "USD") (Money 10 "CHF")
λ> reduce bank "USD" sum
20

Just like stimes works for any Semigroup, stimesMonoid is defined for any Monoid, and therefore you can also use it with Expression.

With the historical 2:1 exchange rate, 5 Dollars + 10 Swiss Franc, times 2, is equivalent to 20 Dollars.

Summary #

In chapter 17 of his book, Kent Beck describes that he'd been TDD'ing a Money API many times before trying out the expression-based API he ultimately used in the book. In other words, he had much experience, both with this particular problem, and with programming in general. Clearly this is a highly skilled programmer at work.

I find it interesting that he seems to intuitively arrive at a design involving a monoid and an interpreter. If he did this on purpose, he doesn't say so in the book, so I rather speculate that he arrived at the design simply because he recognised its superiority. This is the reason that I find it interesting to identify this, an existing example, as a monoid, because it indicates that there's something supremely comprehensible about monoid-based APIs. It's conceptually 'just like addition'.

In this article, we returned to a decade-old code example in order to identify it as a monoid. In the next article, I'm going to revisit an example code base of mine from 2015.

Next: Convex hull monoid.


Comments

You'll notice that, throughout this example code base, both multiplier and amounts are modelled as integers. I think that Kent Beck did this as a simplification, but a more realistic example should use decimal values.

Actually, in a lot of financial systems money is stored in cents, and therefore as integers, because it avoids rounding errors.

Great articles btw! :)

2017-10-20 7:09 UTC

Hrvoje, thank you for writing. Yes, it's a good point that you could model the values as cents and rappen, but I think I recall that Kent Beck's text distinctly discusses dollars and francs. I am, however, currently travelling, without access to the book, so I can't check.

The scenario, as simplistic as it may be, involves currency exchange, and exchange rates tend to involve much smaller fractions. As an example, right now, one currency exchange web site reports that 1 CHF is 1.01950 USD. Clearly, representing the U.S. currency with cents would incur a loss of precision, because that would imply an exchange rate of 102 cents to 100 rappen. I'm sure arbitrage opportunities would be legion if you ever wrote code like that.

If I remember number theory correctly, you can always scale any rational number to an integer. I.e. in this case, you could scale 1.01950 to 101,950. There's little reason to do that, because you have the decimal struct for that purpose:

"The Decimal value type is appropriate for financial calculations that require large numbers of significant integral and fractional digits and no round-off errors."
All of this, however, is just idle speculation on my point. I admit that I've never had to implement complex financial calculations, so there may be some edge cases of which I'm not aware. For all the run-of-the-mill eCommerce and payment solutions I've implemented over the years, decimal has always been more than adequate.

2017-10-20 8:14 UTC

Although exchange rates are typically represented as decimal fractions, it does not follow that amounts of money should be, even if the amounts were determined by calculations involving that exchange rate.

The oversimplified representation of foreign exchange (FX) in Kent Beck's money examples has always struck me as a particularly weak aspect (and not simply because they are integers; that's the least of the problems). You could argue that the very poor modelling of FX is tolerable because that aspect of the problem domain is not the focus in his example. But I think it's problematic because it can lead you to the wrong conclusion about the design of the central parts of the model. Your conclusion that it might be a good idea not to represent a money amount as an integer is an example - I believe it's the wrong conclusion, and that you've been led to it by the completely wrong-headed way his example represents FX.

The nature of foreign exchange is that it is a transaction with a third party. Some entity (perhaps a bank, or the FX trading desk within an company that may or may not be a financial institution (large multinational firms sometimes have their own FX desks) or maybe a friend who has some of the kind of currency you need in her purse) agrees to give you a specific amount of one currency if you give them a specific amount of some other currency, and there is usually an accompanying agreement on the timescale in which the actual monies are to be transferred. (There will sometimes be more than two currencies involved, either because you're doing something complex, or just because you agree to pay a commission fee in some currency that is different from either the 'to' or 'from' currency.) The amounts of actual money that changes hands will invariably be some integer multiple of the smallest available denomination of the currencies in question.

There may well be a published exchange rate. It might even form part of some contract, although such an advertised rate is very often not binding because markets can move fast, and the exchange rate posted when you started negotiation could change at any moment, and might not be available by the time you attempt to reach an agreement. In cases where a published exchange rate has some reliable meaning, it will necessarily come with a time limit (and unless this time limit is pretty short, the time window itself may come at a price - if someone has agreed to sell you currency for a specific price within some time window, what you have there is in effect either a future or an option, depending on whether you are allowed to decide not to complete the transaction).

One very common case where a 'current' exchange rate does in fact apply is when using a credit or debit card abroad. In this case, somewhere in the terms and conditions that you agreed to at some point in the past, it will say that the bank gets to apply the current rate for some definition of current. (The bank will generally have freedom to define what it means by 'current', which is one of the reasons you tend not to get a very good deal on such transactions.) And there will be rules (often generally accepted conventions, instead of being explicitly set out in the contract) about how the rate is applied. It will necessarily involve some amount of rounding. When you bought something on your credit card in a foreign currency, it will have been for a precise amount in that currency - merchants don't get to charge you Pi dollars for something. And when the bank debits your account, they will also do so by a precise amount - if you've ever used a card in this way you'll know that you didn't end up with some fractional number of cents or pennies or whatever in your account afterwards. So the exchange rate you got in practice will very rarely be exactly the advertised one (unless it's such a large transaction that the amounts involved have more decimal places than the 'current' exchange rate, or, by sheer coincidence, the numbers worked out in such a way that you happened to get the exact exchange rate advertised.).

So although you will often see published exchange rates with multiple decimal places, the actual exchange rate depends entirely on the agreement you strike with whoever it is that is going to give you money in the currency you want in exchange for money in the currency you have. The actual exchanges that result from such agreements do not involve fractional amounts.

Where does this leave Kent's example? Fundamentally, 'reducing' a multi-currency expression to a single-currency result will need to create at least one FX transaction (possibly several). So you'll need some sort of mechanism for agreeing the terms of those transactions with the other party or parties. And realistically you'd want to do something to minimize transaction costs (e.g., if you perform multiple USD to GBP conversions, you'll want to handle that with a single FX transaction), so you'll need some sort of logic for managing that too. It's certainly not going to be as simple as looking up the bank's rate.

2018-04-13 9:51 UTC

Ian, thank you for writing. Much of what you write about foreign exchange matches the little I know. What interested me about Kent Beck's example was that his intuition about good programming lead him to a monoidal design.

It seems to me that your criticism mostly targets how the exchange itself is implemented, i.e. the Reduce method, or rather, its bank argument. In its current form, the Bank implementation is indisputably naive.

Would a more sophisticated Bank implementation address some of the problems? What if, instead of calling it Bank, we called it Exchange?

Already in its current form, the Bank implementation is nothing but a dictionary of exchange rates, defined by a from and a to currency. It follow that the USD/CHF entry isn't the same as the CHF/USD entry. They don't have to be each others' inverses. Doesn't this, already, enable arbitrage?

Another change that we could add to a hypothetical more sophisticated Exchange class would be to subtract a fee from the returned value. Would that address one of the other concerns?

Furthermore, we could add a time limit to each dictionary of exchange rates.

It's not my intent to claim that such a model would be sufficient to implement an international bank's foreign exchange business, but that's not the scenario that Kent Beck had in mind. The introduction to Test-Driven Development By Example explicitly explains that the scenario is a bond portfolio management system. Doesn't the overall API he outlines sufficiently address that?

2018-04-14 9:51 UTC

Hi Mark, thanks for the code examples here. I do have a few clarifying questions:

  1. When you mention the identity element, you write, "Finally, if you multiply the identity element, you still get the identity element. Here, interestingly, PlusIdentity behaves similar to the identity element for multiplication (1)". But with multiplication, when you multiply the identity element with another factor, you get the other factor, not the identity element. Am I misreading you here?
  2. Your C# example has Money Reduce(Bank bank, string to);, but your Haskell example has reduce :: Ord a => Map (String, a) Int -> a -> Expression -> Int. The return types here are different, right? C# returns a Money object. Haskell seems to return an Int from the code signature and sample output. Was this intentional?

I know I'm often focused on little details, I just want to make sure it's not a sign of me misunderstanding the main concept. The rest of the article is very clear :)

2022-02-07 5:35 UTC

Mark, thank you for writing. You're right about the first quote - it does look a little odd. The first sentence, however, looks good enough to me. The Times method does, indeed, return this - itself. The second sentence, on the other hand, looks wrong. I'm not sure what I had in mind when I wrote that four years ago, but now that you ask, it does look incorrect. It still behaves like zero. I think I'm going to strike out that sentence. Thank you for pointing that out.

You're also right about the Haskell example. For better parity, I should have wrapped the result of reduce in a new Expression value. This is trivially possible like this:

reduce' :: Map (StringStringInt -> String -> Expression -> Expression
reduce' bank to exp = Money (reduce bank to exp) to

This new 'overload' calls the above reduce function and wraps the resulting Int in a new Expression value.

2022-02-08 9:01 UTC

After the article was written, a proposal to make Semigroup as a superclass of Monoid came out and eventually made it into GHC 8+. The changes so that the Haskell part of the article compiles (with GHC 8+) are:

{-# LANGUAGE CPP #-}
import           Data.Semigroup (stimesMonoid)
#if !MIN_VERSION_base(4,11,0)
import qualified Data.Semigroup as Semigroup
#endif

instance Monoid Expression where
#if !MIN_VERSION_base(4,11,0)
  mappend =
    (Semigroup.<>)
#endif
  mempty =
    MoneyIdentity

instance Semigroup Expression where
  MoneyIdentity <> y =
    y
  x <> MoneyIdentity =
    x
  x <> y =
    Sum x y
        

2022-08-12 5:35 UTC


Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 16 October 2017 07:28:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 16 October 2017 07:28:00 UTC