Applied Mathematics: DRY up your code

It's only fair to share...Share on Google+0Share on Facebook0Tweet about this on TwitterShare on LinkedIn0Email this to someone

Recently, I had a few discussions about the usage of mathematics in programming. Unfortunately, a lot of computer science students believe that the mathematics they learned for their degree is not applicable to their every day work as software developers. Let me give you a glimpse into “applied” mathematics in every day programming with this post.

Maths first

For this post, we will look at the mathematical concept of a Monoid. The wikipedia page is already right on topic, as its first paragraph contains words such as “abstract algebra”, “algebraic structure” or “semigroup theory”. If you think those expressions justify that you don’t need to know or care about a monoid, then just read on – here and/or on wikipedia. Wikipedia already follows up on the importance of monoids in mathematics with “commonly used in computer science […] and in practical programming”.

So let’s quickly recap what a monoid is: A monoid consists of a set S and a binary operation op: S × SS such that two properties/laws hold:

  1. Identity: There exists an element e of S such that for any s of S it holds that op(e, s) = op(s, e) = s
  2. Associativity: For all a,b,c of S it holds that op(a, op(b, c)) = op(op(a, b), c)

So far, this sounds really mathy. For your own sake, if you consider yourself a programmer and have trouble with identity elements and associativity, do yourself and others a favor and learn some basic maths. It’ll help you immensely in the long run.

Turning it into code

Now that we know what a monoid is in mathematics, how do we apply it to programming? The first simple realization is that the set S corresponds to a type, like Integer, or rather its possible values. But since every set S can form a monoid with the corresponding operation and identity element, let’s not limit ourselves and use a generic type T instead:

public interface Monoid<T> {

    T op(final T arg1, final T arg2);

    T identity();
}

You could of course use a library like functionaljava or scalaz. You’ll notice that the most significant difference will be the names of these methods. The identity element is often referred to as zero, the operation as sum or append. But as we will see in this post, neither does identity imply zero-ness, nor does the operation have anything to do with summation or appending. Since names aren’t important and we can so easily define a Monoid ourselves, you can basically choose whichever name you want as long as it resembles the above concepts.

Since we have this nice interface, we will probably want an implementation class for it as well. Let’s take a simple and well-known monoid as an example: the set of integers with addition as binary operation and the integer 0 as its identity element. You can easily prove mathematically that this forms a monoid, but for now, we’ll just write it straight into code:

public class IntegerAdditionMonoid implements Monoid<Integer> {
    @Override
    public Integer op(Integer arg1, Integer arg2) {
        return arg1 + arg2;
    }

    @Override
    public Integer identity() {
        return 0;
    }
}

Excursion: Proving mathematical properties

The implementation code above is almost trivially simple, yet even for seamingly simple code it is not always clear whether the mathematical requirements of identity and associativity hold. In mathematics, we can prove that this is a monoid. We can implement it exactly like that and take the proof for granted. The nice thing is that this piece of code is extremely unlikely to change – ever. Why would you change it? It is based on a mathematical concept, which more or less has to be implemented in this way. Changing anything (meaningful, i.e. not names or comments, etc.) in this code messes up the semantics of this class and violates the implicit monoid contract, which means most code working with this monoid will likely fail. And what could you potentially gain from that code change? I haven’t the faintest idea.

Nevertheless, there are monoids, for which it is much harder to see whether they satisfy the monoid laws. Unless you want to mathematically prove that the monoid you are implementing satisfies the laws, your next best bet is to write unit tests. Since this is a post about mathematics, we’ll also add this excursion into the realm of JUnit theories. Instead of a traditional unit test, we will write a theory test, which is then executed with a different argument several times. The arguments are selected from the data points you defined yourself. It’s not as generic as property-based testing with value generators, but it’s available in JUnit, so already available in most Java projects. (Note that the Iterable DataPoints only work since 4.12 – use an Integer[] instead if you’re on an older version).

@RunWith(Theories.class)
public class IntegerAdditionMonoidTest {

    @DataPoints
    public static List<Integer> integers = Arrays.asList(
            0, 1, -1, 3, 5, 8, 134,
            Integer.MAX_VALUE, Integer.MIN_VALUE);

    private static final Monoid<Integer> M = new IntegerAdditionMonoid();

    @Theory
    public void leftIdentity(Integer arg) {
        assertThat(M.op(M.identity(), arg), equalTo(arg));
    }

    @Theory
    public void rightIdentity(Integer arg) {
        assertThat(M.op(arg, M.identity()), equalTo(arg));
    }

    @Theory
    public void associativity(Integer arg1, Integer arg2, Integer arg3) {
        assertThat(M.op(arg1, M.op(arg2, arg3)),
                equalTo(M.op(M.op(arg1, arg2), arg3)));
    }
}

As you can see, the theories we use in this test correspond directly to the monoidal laws. We just split up the identity law into a left and right identity, depending on whether the identity element is used as the first or second argument of the operation.  When we run this test, all the data points are used one after the other to execute each of these methods just like a normal JUnit test. For associativity, this means that each of the datapoints is used for each argument, so take care of the combinatorial explosion slowing down your tests. Of course, proper property-based testing libraries have several means to address this, but for a small sample of data points this theory approach may suffice for your needs.

What is critically important here is that none of the theories verifies the actual computed value of our operation. If we wanted to, we could add another Monoid<Integer> implementation, which realizes the monoid based on multiplication with 1 as the identity element. The very same theories would be applicable by simply exchanging the monoid M. Therefore, this unit test checks whether the monoidal laws hold, but it does not in any way express anything about your implementation details. If you want the monoid to be used for adding up Integer values, you could add further traditional tests, or add theories for which the assertions contain that required addition. For something as simple as addition, this may not be necessary, but we will see another monoid below, for which it would be more advisable.

Side note: I’d like to just provide an abstract test class, which encodes the monoid laws so that you can just subclass it for your custom monoid and only need to provide the monoid implementation and some data points. However, it seems that JUnit theories cannot be formulated with type parameters. If you know how to get around this, let me know in the comments please.

Non-standard Monoids

Once you learned about monoids, the next hard step is to identify them as a suitable algebraic structure in your every day work. Most developers have a really hard time with that, and it seems that experience is the most important aspect to this. A very well-known monoid is that of Strings with the empty string as identity element and the operation being the appending of two strings. (This monoid is also a nice example of why a monoid need not be commutative.) In this post, however, we will apply our knowledge to a slightly different, yet not unheard of, example: status enums and their aggregated value.

Suppose you have an enum in your project, which is used to represent the status of some domain object. For the sake of simplicity, let’s just distinguish Ok, Warning and Error. A typical requirement is that you need to be able to aggregate the statuses of individual domain objects into an overall status. Usually, when one object is in an error state, the overall state should reflect the error as well. Similarly for a warning, unless there also is an error present. So the only way to get an overall Ok status is if all individual statuses are Ok. I’m sure you can implement this enum and the added requirement just fine. But do you also realize that it forms this monoid?

public enum Status {
    OK, WARNING, ERROR;

    public static class StatusMonoid implements Monoid<Status> {

        @Override
        public Status op(Status arg1, Status arg2) {
            return Status.values()[Math.max(arg1.ordinal(), arg2.ordinal())];
        }

        @Override
        public Status identity() {
            return OK;
        }
    }
}

As you can see, the binary operation is no longer as simple as an addition, though it isn’t much more than a maximum calculation either. In the real world, there will be more enum values and a more refined way of combining them together to form their aggregate status, but this only makes the implementation of the operation method more complicated – it doesn’t change anything with regards to the mathematical monoid properties. (To be more precise: it shouldn’t change anything, as you’ll get into a lot of trouble in your aggregation if for example it isn’t associative. I’d strongly suggest to change the requirement in such a case to get more meaningful semantics.)

This example also shows the importance of not only testing the monoidal laws as we have seen above, but also include more concrete examples to verify the correct overall status gets computed. After all, implementing the StatusMonoid with a minimum operation and Error as identity element would satisfy these laws just as well, but may not be resembling what was required.

DRY up your code

Let me give you a small task: Write programs/methods for summing up all Integers in a List<Integer>, then for computing the product of these same Integers, and while you’re at it, implement the status aggregation mentioned above to compute the overall status of a list of statuses.

Before you read on, take a minute and try to solve this task. If you don’t feel like writing down code for such a simple problem, at least try to visualize what your code would look like.


 

We have an interface for a Monoid<T> now, along with implementations of different monoids, but what does all this have to do with Don’t Repeat Yourself (DRY, a clean code principle) ?

You may and should rely on the monoid classes presented above (and the one for integer multiplication which wasn’t shown here) to solve the task. And just like typical exam questions, if your core logic needs more than one line of code, you’re not doing it right. (If you even think about writing a loop, it may also be time for you to deep dive into functional programming first.)


 

It’s the same in programming, as in mathematics: once you identified a generic structure like a monoid, all operations that are based on it can be considered the same, as they only differ in the concrete monoid instance. All that remains is to recognize that the three subtasks mentioned above are essentially the same operation performed on different monoids.

public class MonoidExample {

    private static <T> T reduce(Collection<T> values, Monoid<T> m) {
        return values.stream().reduce(m.identity(), m::op);
    }

    public static void main(String ... args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
        System.out.println(reduce(numbers, new IntegerAdditionMonoid()));
        System.out.println(reduce(numbers, new IntegerMultiplicationMonoid()));

        List<Status> statuses = Arrays.asList(Status.OK, Status.WARNING, Status.OK);
        System.out.println(reduce(statuses, new Status.StatusMonoid()));
    }
}

The necessary implementation code is found in the highlighted line. The rest is just boilerplate to show you a few examples, which will print out 15, 120, and a WARNING.

You could have implemented all this in a much different way of course. And it certainly is up to you and your project to decide whether code like this is ok. The point of this exercise is merely to show you that a more traditional code (using loops and helper variables and what not) may not look like it has a close relation to mathematics, but once you rewrite to something like the above, the connection becomes undeniable.

Summary

I hope this post has shown you something interesting, or at the very least reminded you once more of what you already knew.

We have seen how a purely mathematical construct like the monoid can be applied in programming. Not only that it is possible to do so, but the resulting code has a sort of mathematical beauty to it due to that. We need very little boilerplate code (you can switch from Java to Haskell/Scala/scalaz to remove most of that) and get generic behaviors (like reduce) that can be reused in vastly different contexts. This sort of abstraction in turn is helpful to eliminate a lot of code duplication, for which it can be rather hard to actually realize the duplication (integer addition vs status aggregation).

It's only fair to share...Share on Google+0Share on Facebook0Tweet about this on TwitterShare on LinkedIn0Email this to someone

1 Comment

Comments are closed.