Part 2: Case study critiquing the design of Uncle Bob's Word Wrap "Kata"

A very good example of the power of incremental design is provided by Uncle Bob Martin, who is one of the few writers on software design that is worth reading. In an especially thought-provoking article (URL below), he argues for a fine grained and highly structured form of design based on induction-rules. He calls these induction rules "transformations" and, importantly, puts them in a priority list with the principle that the weakest generalisation should be preferentially selected. I would call this design by structured induction.

In this article he demonstrates the use of structure induction with a "word wrapping" algorithm. I am going to describe the problem and list the final solution, skipping the actual inductive steps (which are interesting but you can read in the article yourself), and then critique that final solution. In another letter I'll tackle the same problem using abstraction techniques and compare the advantages and disadvantages. 

The Word Wrap Problem and Emergent Design

(Unfortunately I can't find a simple statement that describes the problem, so I have created this summary that I think is fair enough.)

The "word wrap" problem boils down to taking some written text and "setting" it into lines by selectively removing whitespace and by inserting newlines. All the lines must be no longer than some parameter L. Longer lines are better than shorter lines. Unbroken words are better than broken words.

Here is the entire induced implementation. 

public class WordWrapper {
    
    private int length;
    
    public WordWrapper( int length ) {
        this.length = length;
    }
    
    public static String wrap( String s, int length ) {
        return new WordWrapper( length ).wrap( s );
    }
    
    public String wrap( String s ) {
        if ( length < 1 ) throw new InvalidArgument();
        if ( s == null ) return "";
        
        if ( s.length() <= length ) {
            return s;
        } else {
            int space = s.substring( 0, length + 1 ).lastIndexOf( " " );
            if ( space >= 0 ) {
                return breakBetween( s, space, space + 1 );
            } else { 
                return breakBetween( s, length, length );
            }
        }
    }
    
    private String breakBetween( String s, int start, int end ) {
        return s.substring( 0, start ) + "\n" + wrap( s.substring( end ), length );
    }
    
    public static class InvalidArgument extends RuntimeException {
    }
      
}

Opaque

Because the design is expressed entirely in the implementation, there is no separate design description. Looking at this implementation, it is difficult to summarise - there are many chained and nested conditionals plus the use of mutual recursion.  The lack of explanation beyond this fairly confusing implementation means that even the simplest questions can only be answered by close inspection.

  • How are runs of whitespace handled? e.g. with L = 12, what happens to "foo         bar          gort"?
  • Can this design generate two consecutive newlines? e.g. with L = 3, what happens to " 012  012"
  • Will the lines be terminated with a newline? Or separated by newlines? e.g. with L = 3, what happens to "foo " and "foo"?

If you give these questions a little serious consideration, it quickly becomes clear how opaque the design is. It is not merely a matter of "I think it works this way but I would have to check" but more "I will have to simulate the code (or write a test) and find out what happens."

It might be argued that this means there is no design, meaning no separate explanatory design that sets out the implementation plan. I would prefer to say that the design is embodied by the program and the program has the disadvantage of being a challenging document to understand. 

A further disadvantage is that the design principles are unstated. This means that when we encounter some unexpected behaviour we have no way of determining whether or not this is deliberate or accidental.

To illustrate this claim, I will now answer those three questions. The first question is what happens to runs of whitespace? The test I gave to probe it was 

    "foo         bar          gort" with L=12.

And the answer the code gives is
    "foo        \nbar         \ngort"

In other words, the whitespace is maximally preserved. So is this a deliberate design decision or accidental? You are probably tempted to refer back to the original problem statement but a careful reading of that statement will reveal it is completely silent on this issue (because I retro-fitted it to the design). 

Can this design generate two consecutive newlines? The word "generate" is intended to imply that these are inserted newlines rather than newlines already present in the text. 

The test I gave was 

    " 012  012" with L = 3

The output is in fact
    "\n012\n\n012"

Surely that isn't what the designer intended? But perhaps there is an underlying principle that the output shall never be fewer characters than the input? (Which is clearly a property of the code - if you look closely.) 

Mistake or purposeful? You cannot tell for sure, once this potential principle has been identified. Indeed the more you look at the code the more it does look like a latent design principle. What does the problem description say? Again it is completely silent (or frustratingly vague). 

My third question was whether the lines are separated or terminated by newlines? By this time you will have figured out that the answer is neither. The previous tests show newlines as separators but this one shows it as a terminator.

    "foo " with L=3 has output "foo\n"

Deliberate? Given the possible principle of never making the output shorter, definitely. And do you believe that? No, it's a nagging suspicion. 

So these three questions illustrate how opaque and uninformative the program-as-design-document is. On the positive side, it does have the distinct advantage of being executable and objective and is written in a formal notation. But the lack of a strategic view means that it is hard to explore the design alternatives or communicate to someone else.

Quality Issues

But is the emergent design a good one? When we ask this question we are usually alluding to various properties apart from the input-output (or 'functional') behaviour. We might be concerned with 

  • Execution speed (faster is better)
  • Memory usage (less is better)
  • Robustness (well-defined behaviour is better)
  • Maintainability (easier is better)
  • Disaster recovery - and so on.

These typically have to be assessed by comparing different design options. But in this letter I want to make a broader commentary. (In Part 4 of this email I will draft an alternative design.)

Interestingly (and significantly) these qualities are all outcomes that are vulnerable to a single weak point badly affecting the overall assessment - they are global and typically synergistic. And that's exactly the kind of property that we would expect incremental design to have trouble with. 

Just so we can write some formulae, let's suppose the input string has size N and the wrap parameter is L

So let's look at performance. Does the code have any performance problems? Yes, the result is typically formed by appending three strings together. Because Java optimises successive appends, this is 'only' quadratic in N. Even so, in practice this design would be infeasibly slow. It can be fixed relatively easily by changing the design but, as it stands, it is terrible and a very serious problem waiting to happen.

What about memory usage? It definitely consumes store at a quadratic rate, which is very bad as it will aggravate the bad performance and (worse) impact on the performance of the entire machine but its instantaneous footprint is only linear (because Java substrings share backing store).  

And robustness? What does this mean? That it has well defined behaviour in all possible situations e.g. with bad inputs, with multi-threading, with indefinite pauses, memory exhaustion, file closure and so on. 

The first peculiarity is that wrap does not complain when given null. It returns an empty string. Why treats null as a valid input? Experience shows that one of the commonest results of a programming mistake is an inadvertent null return; defensive programming means capturing bad nulls as early as possible. Failing to do so increases the risk of silent failure. Using this design decreases the robustness of an application.

The next oddity arises from the handling of whitespace. Java lives in the world of Unicode and the usual way to detect whether or not a character is a space is to use Character.isSpaceChar. So this is definitely going to fail on Unicode characters such as 

spaces_table.png

It is robust, more by luck than design as it were, when supplied by large Strings (length == Integer.MAX_VAL) or large lengths (Integer.MAX_VAL -1). 

However, Java Strings are UTF-16 encoded. The design uses a mixture of codepoint aware and codepoint unaware routines. The result is that for languages outside of the BMP [[http://en.wikipedia.org/wiki/Plane_(Unicode)]] this will create gobbledegook. So it is not robust when the text uses mathematical symbols, musical notation or ancient languages, for instance.

Analysing maintainability is non-trivial, so I have broken that out into a separate part (part 3).


Back to Part 1 - Up to Contents - Forward to Part 3