Repeat Yourself Differently

posted by Craig Gidney on March 12, 2013

Rules of thumb, by their very nature, tend to contradict each other. They oversimplify, and break down in corner cases. Software development’s many rules of thumb (Keep it simple, stupid, You ain’t gonna need it, Fake it till you make it, Naming is everything, You suck at estimating, …), are no exception. Should my code be self-documenting or literate? Should I be succinct or not “clever”?

A great example of a rule of thumb is “Don’t Repeat Yourself“. Take any real world code, and it can probably be improved by extracting repeated patterns to reduce redundancy. Take the idea too far, and you can create some truly difficult to understand programs. Take it way too far, and there might be no possible proof your code works (even though it does)!

“Testing is Good” is another good rule of thumb. Yet… a test must be redundant, violating “Don’t Repeat Yourself”. If you can learn some fact about the code from a test, then you can also learn it from the implementation. Tests contain repackaged information, not new information. It may be more difficult to learn facts about the code through the implementation rather than the tests, but it must be possible. A blind optimizer of the DRY principle would be in favor of removing the redundant tests.

The redundancy in tests is (obviously) pragmatically justified, but how? Are there other ways to achieve the benefits of tests? This week, I talk (read: ramble) about the benefits of repeating yourself differently.

Preamble: Repeating yourself is bad

Unintentionally repeating yourself is, generally, bad. The best predictor we have for the number of bugs in a program is the number of lines of code (UNLESS. YOU. INCENTIVIZE. THAT.). Repeating yourself increases the size of the code, and (based on the heuristic) thus tends to increase the number of bugs.

This is not just some theoretical idea without practical applications. Some time ago, a company asked us to review some code (written by another company) and give advice on how to proceed. The code was awful. Some of the worst I’ve ever seen. Amongst other flaws, the code blatantly and constantly repeated itself. (Note: fabricated details ahead, for anonymization.)

For example, the names of waypoints were hard-coded into the program. Many times. There was a hard-coded dictionary from waypoint names to waypoint locations, a hard-coded dictionary from waypoint names to secondary names of waypoints and even a hard-coded dictionary for the opposite direction from waypoint secondary names to the original waypoint names. A nice little trap for anyone who might have crazy ideas like “Lets improve the name of that waypoint.” or “Lets localize the waypoint names based on the user’s language.”.

On top of the repetition of data, there was a lot of repeated code (copy pasta). Every possible network request/response had its own static dictionary field for mapping request ids to callbacks, its own slightly-customized method to send a request and place a callback in the appropriate dictionary, and its own slightly-customized method to invoke the stored callback when a response was received. Naturally the dictionary entries were inconsistently cleared and callbacks could potentially overwrite each other because the ids weren’t necessarily unique. The copy pasta repeated these bugs (and minor variations) dozens and dozens of times.

Ultimately the authoring company was, technically, let go for repeating themselves so much. Clearly something to avoid.

Flawed humans

Ideally, you would never repeat yourself. Unfortunately, we humans are not perfect. Come to think of it, we’re barely adequate. We miss key presses, type one word when intending to type another, infer based on temporarily confused mathematical intuitions, and are generally terrible at consistently correctly performing tasks.

The best way to reduce errors in a process is removing the humans. Unfortunately, that’s not achievable when it comes to software development. It’s hard to translate human intentions into executable specifications (a.k.a. developing software) without a human to source intentions from.

Human error happens. This is an unavoidable fact. We’re going to make mistakes. However, that doesn’t mean we can’t later detect and correct those mistakes.

Do it again

The simplest technique for catching mistakes is… repetition. Implement the same thing twice (or more), and compare the two implementations. Differences are guaranteed to be bugs (mistakes), and bugs tend to be represented in the differences. We’re not unnecessarily repeating ourselves, we’re trying to reduce errors.

The problem with doing the same thing twice, even if different people are doing the two implementations, is that bugs can correlate. If I make a mistake because I’m confused about some mathematical fact (as opposed to just making a typo), I’m going to make the same mistake again and again and again. I might even un-repair correct code. There’s no guarantee another person won’t be confused in the same way, either. There are common false beliefs in mathematics.

There is a benefit to doing the same thing twice. You’ll catch some dumb mistakes. However, you’ll also miss all the interesting mistakes, and take twice as long to do anything.

Repeating the same implementation has a large cost in repetition, and its benefit in error reduction is debatable. We want something better.

Do it again, but not the same

In order to avoid correlated bugs, you can approach problems from multiple directions. Instead of repeating your solution twice, try to create a totally different solution using a totally different approach.

For example, mistakes in imperative programs and mistakes in functional programs don’t always translate. You can’t mistakenly use <= when you’re using List.map instead of for (int i = 0; i < n; i++). You can’t accidentally modify a list while iterating it, if you can’t modify lists in the first place. You can’t blow the stack with an accidentally-not-tail-recursive call, if you’re using while loops instead of recursion.

Logic programming is even further removed from imperative programming, compared to functional programming. Both imperative programs and functional programs tend to explicitly construct results, but a logical program implicitly constrains what a result can be. In an imperative language, a choose-smaller-value function would be implemented like this: if (a < b) return a; else return b;. In a logic language, it would be implemented totally differently:

int min(int a, int b):
    ensure result <= a
    ensure result <= b
    ensure result == a or result == b

You have to be mistaken about what you want and how to get it, in order to translate an error between an imperative-style implementation and a logic-style implementation. That's a pretty high bar, though it's still possible to make mistakes. Even computer-checked theorems might accidentally prove the wrong thing (i.e. I think the most likely way the computer proof of (say) the four color theorem could be wrong, is that there was a mistake in the translation from the human understanding of the problem to the theorem proving language.).

Using a different paradigm for each implementation has great error reduction benefits. After all, even formal verification is an example of checking that an implementation matches a logical implementation / specification. Actually, comparing implementations across different paradigms is formal verification.

Unfortunately, doing a full re-implementation of a program into a logical style is a lot of work. Comparing the two implementations is also difficult, because they might use totally different abstractions or separate the problem domain differently (especially if you have separate programmers writing each implementation, which is reasonable since most wouldn't be good at both styles). It would be ideal to have something more flexible in terms of cost, and more approachable / concrete in terms of concepts.

Do it again, but not the same, and only a little bit

To make it easier to map functionality between our two hypothetical implementations, we can use consistent pieces (i.e. control the allowed types of differences). Instead of independently creating the architecture of the logic-style program, make sure it has the same components as the imperative program (perhaps straight down to having the same functions).

A nice bonus of using the same pieces is that you no longer have to implement the entire logical implementation before you can start comparing. You can do it piece by piece. If that sounds like a test to you... well, it's actually more like a fully-specified contract:

int Divide(int numerator, int denominator):
    require denominator != 0
    ensure result.remainder + result.quotient * denominator == numerator
    ensure sign(results.remainder) != -sign(denominator)
    ensure 0 <= abs(results.remainder) < abs(denominator)

Tests are one tiny step further, where we let the logical implementation be significantly 'looser' than the imperative implementation. This allows us to check concrete details, without having to mimic all the minutia of the other implementation:

assert Divide(5,3) == {quotient: 1, remainder: 2}
assert Divide(5,-3) == {quotient: 1, remainder: -2}
assert Divide(-5,3) == {quotient: -2, remainder: 1}

So, it turns out, tests are a natural way to repeat yourself differently. They're concrete, they're a totally different way of looking at the problem ("what" vs "how"), and they allow you to independently verify small bits of functionality. They're not quite as safe as a full logical specification to compare against, but a great trade-off.

Summary

To catch human errors, you must repeat yourself.

To catch tricky human errors, you must repeat yourself differently.

Tests, contracts, formal verification, and even running-it-and-changing-if-it-looks-wrong are all examples of repeating yourself differently.

This is incredibly obvious in hindsight.

---

Discuss on Hacker News, Reddit

---


Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive

More interesting posts (8 of 39 articles)

Or check out our Portfolio.