Mythbusting - Part 1

(Disclaimer: as always, the issue of reasoning about software quality is largely a matter of personal judgment)

Yes, I really like Adam and Jamie. This post is about myths that you won't see on their TV show.

Actually, this post is motivated by Ian Sutton's post titled: "Software erosion in pictures - Findbugs". That piece shows the package dependency graphs of several releases of Findbugs. The graphs were obtained by Structure101, a static analyzer that reads class files. The conclusion there is that Findbugs is eroding since the number of cycles (tangles) in the graph, as well as the size of these cycles, grows over time.

Ian's premise is that tangled packages are indicative of poor code quality.

I think this premise is based on myths that needs to be carefully examined. So this is what I'll do here.

Myth #1: Tangled packages cannot be tested separately

The counter argument is this: When the packages were not tangled were they tested separately? It is likely that the answer to this question is "No". The lack of compile-time dependency does not mean lack of run-time dependency. Maybe the two packages were already implicitly related (let's say through data passed as a String), and we just made this relation explicit (through a dedicated class).

Myth #2: Tangled packages cannot be deployed separately

This is not true in Java (and in many other modern languages) since we have dynamic loading. And again, due to hidden run-time dependencies, it may very well be the case that you will not be able to separately deploy packages even if they were *not* statically tangled.

Myth #3: Non tangled packages can be modified without affecting each other

Assume you pass an Iterator, implemented by class from package A to some code from package B. The packages are not statically related (they depend on Iterator but not on each other). Still, they must agree on certain things: Can this iterator's next() method return null? What is the semantics of remove()? If one side breaks the contract, the other side will bleed.

Myth #4: If I eliminated a package level tangle, I solved some dependency issues

Not necessarily. You might have just consolidated the participating packages. So the dependency is still there, this time at the class level.

Myth #5: A similar analysis is also valuable at the class level

This is usually not true. The *full* dependency graph of many well written classes is so cluttered that it is practically useless. Most visualization tools workaround this by (a) showing (by default) dependencies only from the same package; (b) ignoring library classes. When you choose the non-default view you see how intricate the network of classes is. This happens with almost every program you examine regardless of what you think of its quality. Additionally, class level analysis is also ignorant of run-time dependencies.

There a few more myths, but I think we can stop now. However, there is one more thing that I wanted to talk about: After reading Ian's post I did some field research: I took all the jar files that come along with Spring (including spring.jar itself) and fed them into Structure101, just like Ian. All in all: 23 jar files. Do you know how many of these *didn't* have tangled packages?



The answer is: 3.

Let me repeat that: 20 libraries had their packages tangled.


So, if you want your library to be used by Spring you should make the packages tangled. That's what the numbers are telling us. As long as you keep writing test cases, you have no reason to be afraid of tangles: the developers of JUnit, Dom4J, Log4J, Ant, Antlr (partial list) are happily living with tangles.

Email This BlogThis! Share to X Share to Facebook

Shorter is Better?

It is widely believed that compactness is a desirable quality of code. Sadly, I often see people claiming that compactness is an absolute metric, in the sense that shorter code is always superior to longer code.

Leaving aside the issue of how length should be measured (character count? line count? token count? executable size?), here are two different Javascript functions that fulfill the same task: translate an integer in the range 0..13 to roman numerals.

function toRoman1(n) {
  return n == 0 ? "" : 
    n % 5 == 4 ? "I" + toRoman1(n + 1) : n >= 5 ?
      (String.fromCharCode(
        84 + Math.floor(n / 5)*2)) + 
      toRoman1(n % 5) : "I" + toRoman1(n - 1)
}

function toRoman2(n) {
      
   if(n < 4 && n > 0)
      return "I" + toRoman2(n - 1);
            
   if(n == 4 || n == 9)
      return "I" + toRoman2(n + 1);
            
   if(n >= 10)
      return "X" + toRoman2(n - 10);
      
   if(n >= 5)
      return "V" + toRoman2(n - 5);  

   return "";
}

The former function, toRoman1(), is much shorter than the latter. Moreover, its cyclomatic complexity is lower (since it has fewer branches) suggesting that it is simpler to understand. Still, for most programmers, toRoman1() is more difficult to read, to write, and to debug.

My advice is to go easy with this "shorter is always better" claim. Just like many other things in programming, the right degree of compactness is also a matter of striking a balance. Or, as Allen Holub puts it: "Good and bad are not absolutes".

Update 1: Fixed the no-return-value issue spotted by Yardena.

Update 2: Added the cyclomatic complexity point.

Email This BlogThis! Share to X Share to Facebook

Is it a bug? Is it a feature?

In his latest post Jeff Atwood argues that there should be no distinction between a bug and a feature request. I couldn't agree more. Both bugs and feature requests are actually requests to change the behavior of the program.

I guess this distinction is based on the assumption that the implications of fixing a bug tend to be "local" (i.e.: affecting smaller parts of the program) where-as those of implementing a feature tend to be "global". Thus, implementing a feature is more likely to introduce new bugs, so it makes sense to postpone it until most current bugs are solved.

I disagree with this thesis.

First, I saw many bug fixes that resulted in new bugs being introduced, thereby contradicting the "locality" assumption.

Second, in a test-infected program (that is: a program with a strong test suite), the chances of unwanted side effects being introduced due to a feature implementation are practically zero: you write the code, you run the tests, and if the bar is green then everything is likely to be fine.

One final point: It seems that this distinction, along with several other (mis)conceptions came from the Waterfall approach: With development and debugging being two separate phases it is only natural to classify the items on the project's to-do list as being either a feature or a bug.

Email This BlogThis! Share to X Share to Facebook

On Syntax and Religion

Ola Bini published a piece showing how the introduction of a special variable, the "it" variable, into the Ioke language makes regular-expression matching less verbose. In short, the it-variable captures the result of the expression examined by the enclosing "if" or "unless" decision. Thus, you can write (pseudo-code):

if(/[a-z]*/.matches("ab")) {
 println(it.matchLength()); }

instead of

var x = /[a-z]*/.matches("ab");
if(x != null) { println(x.matchLength()); }

Personally, I tend to agree with Ola regarding the virtue of this mechanism.

The comments made by readers show how subjective - not to say: biased - the whole issue of "syntactic elegance" is. As of Tuesday evening (GMT), here is a short summary of the various opinions.

Marcelo prefers a Smalltalk-like style:

/[a-z]*/.ifMatches("ab", res,
 { println(res.matchLength()); },
 { println("no match"); })

Stefano wants the variable declaration to be explicit:

if(x = /[a-z]*/.matches("ab")) {
 println(x.matchLength()); }

Paul advocates the introduction of "=>" as a pattern matching operator:

/[a-z]*/ => x

Antares Trader argues for a closure with a parameter:

if(/[a-z]*/.matches("ab")) { |x|
 println(x.matchLength()); }

Johannes says that Option types neatly express the idiom in question.

I think that local optimizations of the syntax (in contrast to global aspects such as: typing discipline, programming paradigm, object model, standard library) are largely a waste of time. Will programmers not use the language because they cannot change the name of the "it" variable? Even fifty (local) improvements to the syntax, will not make a difference. The exact notation chosen for this construct will have nearly no impact on Ioke's future success.

Therefore, my rule of thumb is this: It is worth while to debate over a local syntactic issue only if you have knock-out argument. If you are only going to win by points, don't bother.

Email This BlogThis! Share to X Share to Facebook

Crup

Lately I've been using the acronym C.R.U.P as a shorthand for "Code that is RedUndant in the Program". In this post I will explore some of the negative implications of crup. In order to reduce verbosity I will use the word "crup" instead of the acronym C.R.U.P. (Too bad the word crup has no meaning. Really wish it did).

Program development can be thought of as a process where you repeatedly add new pieces of functionality. The implementation of each such piece may depend on existing functionality but may also require the introduction of new functionality, which in turn spawns additional functionality pieces. This model can be naturally represented as a tree where child nodes represent pieces of functionality that were introduced as part of the implementation of the parent. Note that a node can be method, a class, a collaboration of classes, a module, whatever.

Redundant functionality (that is: redundant nodes, crup) is a node that provides more services that its parent expects. In other words, you can replace the subtree rooted at this node with a smaller tree and the program as a whole will still deliver the behavior it was expected to deliver.

programmers often introduce crup into the code-base, thinking that a certain piece of functionality will be needed in the future, and that it is less effort to introduce it sooner than later. This resonates with the famous YAGNI debate: The pro-YAGNI people say that crup is really bad. The pro-crup people say that by predicting future behavior of a program you can ensure your program's structure is well optimized for the long run, and that no post-facto refactoring will be able to match that.

So, let's throw some numbers into the picture: each node has 5 children. 1 in 5 children is a crup node. The tree has 4 levels (that is: a root node, five children, 25 grandchildren, 125 grand-grand children). Total number of nodes is therefore: 1+5+25+125=156.

How much crup do we have in the program? Let's see. The root is obviously not redundant. However, one of its children (level-2) is redundant along with its whole subtree. That's 1+5+25 = 31.

The other four nodes at level-2 are not crup, but each of them is a proud parent of a level-3 crup node: 4*(1+5) = 24. We are left with sixteen non-crup level-3 nodes. These nodes have eighty children, of which one fifth is crup: 16.

So in this program the total crup factor is: (31 + 24 + 16) / 156 = 71 / 156 = 45%. In other words, almost half of the effort went into redundant functionality. That's a lot of extra work. The programmer must posses good future-prediction skills to make this extra work pay off.

The crup factor rises exponentially with the height of tree. If the tree had 5 levels, our crup factor would rise to 56%.

This little post is by no means a scientific study. There are a lot of other factors to consider if one wants to make a scientific claim regarding crup, which is kind of ironic since empirical study of real life software projects/software development is a thorny issue. Here is one factor that mitigates the negative effects of crup: if a prediction regarding a crup node, which is close to the root, turns out to be correct, then the vast majority of the cruppy nodes in the program will stop being crup.

On the other hand, other factors compound the crup effect. For instance, Maintenance and developments costs are probably super-linear with respect to program size (e.g.: program size doubles the but costs quadruple). Thus, Even a small amount of residual crup has a significant negative impact on the program's complexity.

As I said, I am not trying to make a scientific claim here. I just wanted to make the intuition behind YAGNI a bit more concrete. The aforementioned example, with its 45% crup factor, suggests that you could be much more productive if you just cut the crap.

Email This BlogThis! Share to X Share to Facebook

Structural Subtyping == Reduced Compile-Time Coupling

Although I've been wrapping my mind around structural subtyping in Java for quite some time now, there is one argument in favor of structural typing that didn't get the attention it deserves: it is much easier to develop code against an API that relies on structural types due to reduced compile-time dependencies.

As always I'll illustrate my point with an example. We'll start with the standard (non-structural) approach.

(Side note: In the very first lecture at the Programming-Languages class I took, my teacher, Prof. Ron Pinter, made the point that a programming language is an excellent device for formally expressing ideas: "Instead of battling a natural language hopelessly trying to get the precise meaning, just write the thing in a PL and your intention will be clear". I think this is a very good advice)

Suppose someone has finally written the huge algorithm that realizes the overwhelmingly complicated logic of the bridge-keeper from Monty Python and the Holly Grail. The algorithm is encapsulated within the Bridgekeeper class whose protocol relies on the Knight interface.

public interface Knight {
  public String answerMe(String question);
}

class Birdgekeeper {
  public boolean canCross(Knight k) { ... }
}

My friend Graham developed an AbstractKnight class which provides some services common to all knights:

public abstract class AbstractKnight 
    implements Knight {
  private final String name;

  protected AbstractKnight(String name_) {
    name = name_;
  } 

  protected abstract String nonNameQuestion(String q);

  public String answerMe(String question) {
    if("What is your name?".equals(question))
      return name;
    String answer = nonNameQuestion(question);    
    if(answer == null)
      answer = "I don't know that";
    return answer;
  }
}

If I want to develop a concrete subclass of AbstractKnight (Lancelot or Robin come to mind), Graham needs to send me two jars (or two source file packages):

1. Graham.jar - Providing the definition of the AbstractKnight class
2. Bridgekeeper.jar - Providing the definition of the Knight interface

Yes. Without Bridgekeeper.jar I will not be able to compile my Lancelot class, despite the fact that Lancelot is only indirectly coupled with Knight. When you compile a class the compiler requires all its ancestors to be present.

Graham is therefore forced to distribute Bridgekeeper.jar to allow other programmers to subclass his AbstractKnight class. This often leads to proliferation of download-able packages (with/without dependencies) which is a constant headache for open source developers. Of course, if you choose to download the full package (the one that does include the dependencies) you are then risking having several different version of the same library on your machine, which - again - leads to headaches.

With structural subtyping things are much simpler:

// library: Bridgekeeper.jar
public struct Knight {
  public String answerMe(String question);
}

...  // everything else remains the same


// library: Graham.jar
public abstract class AbstractKnight  { 
  // "implements Knight" removed
 
  ...  // everything else remains the same
  
}

With this approach, AbstractKnight has no compile-time dependency on Knight. Thus, you can compile your Lancelot class even if Bridgekeeper.jar is not present on your classpath:

public class Lancelot extends AbstractKnight  {

  public Lancelot() { 
    super("Sir Lancelot of Camelot"); 
  } 

  protected String nonNameQuestion(String q) {
    if("What is your quest?".equals(q))
      return "To seek the Holy Grail";
    if("What is your favorite color?".equals(q))
      return "Blue";
    return null;
  }
}

Update 1: OK. I couldn't resist the temptation. Here it is, in its full glory, scene 35:

Email This BlogThis! Share to X Share to Facebook

Bulletprooof - II

Following my previous post, here is another example for bulletproofing your API (again, I am not saying that you should, just wanted to provide a few concrete examples).

Simple (non bulletproof) version:

public class Resource {
  public enum Mode { READ, WRITE }
  public Resource(String fileName) { ... }
  public void open(Mode m, boolean autoFlush) { ... }
  public char read() { ... }
  public void write(char c) { ... }
}

Legal usage:

Resource res = ... ;
res.open(Resource.Mode.READ, false);
char c = res.read();

Illegal usage:

Resource res = ... ;
res.open(Resource.Mode.READ, false);
res.write('a'); // Runtime error: 
                // Resource was opened for READ

The bulletproofing technique remains the same: introduce new classes to make it possible for the compiler to distinguish between the different variants.

public class Readable {
  public char read() { ... }
}

public class Writable {
  public void write(char c) { ... }
}

public class Resource {
  public Resource(String fileName) { ... }
  public Readable openRead(boolean autoFlush) { ... }
  public Writable openWrite(boolean autoFlush) { ... }
}

Email This BlogThis! Share to X Share to Facebook

Bulletproof

This post waited a long-long time to be written. The motivation to finally do it came from a discussion I had with Andreas Brink at OOPSLA'08. We both felt that TDD made us more productive. In the pre-TDD era we were always trying to make our API bullet-proof, i.e.: that it will be really difficult to write code that will fail at run time. With TDD this is not such a big concern. You write simpler code (which is much faster than writing bulletproof code) and you rely on the tests suite to keep from you doing mistakes.

I don't want to get into the can-tests-really-prevent-bugs debate. My intention here is just to show what I mean by a bulletproof design. Here is a simple (non-bulletproof) Flight class:

public class Flight {
  private final int numSeats;
  private final Set<Traveler> travelers 
    = new HashSet<Traveler>();

  public Flight(int numSeats_) {
    numSeats = numSeats_;
  }

  public void book(Traveler t) {
    if(travelers.size() >= numSeats)
      throw new RuntimeException("Fully booked");
    travelers.add(t);
  }

  public void unbook(Traveler t) { 
    if(!travelers.contains(t))
      throw new IllegalArgumentException("t=" + t);
    travelers.remove(t);
  }
}

public class Traveler {
   ...
}

The predicament lies in the Flight.unbook() method. If we pass the wrong argument, this method will fail:

Filght f1 = ...;
Filght f2 = ...;
Traveler t = ...;
f1.book(t);
f2.unbook(t); // Illegal argument error!

And now, let's see the bulletproof approach. The trick is to use static type checking - sometimes in conjunction with encapsulation - to make it impossible to issue an incorrect unbook() request:

public class Flight {

  private final int numSeats;
  private final Set<Traveler> travelers 
    = new HashSet<Traveler>();

  public Flight(int numSeats_) {
    numSeats = numSeats_;
  }

  public Traveler book(Traveler t) {
    if(travelers.size() >= numSeats)
      throw new RuntimeException("Fully booked");
    travelers.add(t);
    return new Reservation(t);
  }

  public class Reservation {
    public final Traveler traveler;
    public Reservation(Traveler t) { 
      traveler = t;
    }

    public void unbook() {
      travelers.remove(traveler);
    }
  }
}

With this design unbook requests (now issued through a Reservation object) cannot fail:

Filght f1 = ...;
Filght f2 = ...;
Traveler t = ...;
Flight.Reservation r = f1.book(t);
r.unbook(); // Always safe!

Email This BlogThis! Share to X Share to Facebook

Three Kinds of Bugs

I tend to classify bugs into one of these three groups:

• Laziness
• Lack of Creativity
• Betrayal

The running example that I'll use here is a method that finds the largest value in a list of integers.

Laziness

  public static Integer maxA(List<integer> list) {
     int result = Integer.MAX_VALUE;
     for(int i = 0; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

Do you see the problem? result's initial value is completely wrong. Such bugs often happen when the programmer copies the code of a similar method but neglects to make all the neccssary adjustments.

Why is this group called "laziness"? That's because this method will not pass even the simplest test: assertEquals(new Integer(30), maxA(Arrays.asList(10, 20, 30))); In other words, if you weren't lazy you could have caught the bug with the very first test you threw at it. Actually, you don't even need a test case: just run it once on any piece of input and you'll find the bug. BTW, this "run it once" practice shows why read-eval-print shells are useful. Too bad they are common only in the arena of dynamically typed languages.

Lack of Creativity

  public static Integer maxB(List<integer> list) {
     int result = 0;
     for(int i = 0; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

maxB() is clearly better than maxA(). It will not fail at the very first attempt. In fact, as long as your input contains only positive integers this method will seem fine. You need a certain degree of creativity to devise an input that will manifest the bug, such as: assertEquals(new Integer(-4), maxB(Arrays.asList(-4)));

Betrayal

  public static Integer maxC(List<integer> list) {
     int result = list.get(0);
     for(int i = 1; i < result)
        if(result < list.get(i))
           result = list.get(i);
     return result;
  }

This version works quite well. It will pass both of the aforementioned tests. The bug here is much more subtle. With Betrayal bugs the root of the problem is a disagreement between two methods.

Such a disagreement may occur if the method that builds the list (which is then fed into maxC()) will also generate empty lists. This situation contradicts maxC()'s assumption that the list is non empty. In a sense, maxC() is betrayed by its own program.

It is very tempting to say something like: "Well, maxC() has a clear precondition. This precondition is not met, so the bug is in the caller". However tempting, this view is overly simplistic. Suppose the program method that the code that calls maxC(), looks like this:

public class Driver {
  public int n;

  public List<Integer> listBuilder() { 
    List<Integer> newList = new ArrayList<Integer>
    for(int i = 0; i < n; ++i)
      newList.add(i);
    return newList;
  }

  public Integer m() {
    return maxC(listBuilder());
  }
}

The contract of listBuilder() says that it should return a list with the integers 0..n-1 (inclusive). In particular, if n is zero the returned list should be empty. The contract of m() says that it should apply maxC() on the list created by listBuilder(). The contract of maxC() says that it should return the highest number from a non empty list.

So, every method is doing exactly what it is supposed to be doing, and yet the net effect is a runtime error. Despite the fact that maxC() is the one being betrayed we may decide that the correct way to fix the program is to change maxC() rather than listBuilder(). This is typically the case when we realize that our program needs to handle a wider range of inputs.


This type of bug cannot be detected by a testing maxC() in isolation. We need a higher level test, to expose the bug.

One final comment: Earlier I defined m()'s contract to be: "inbvoke maxC() on whetever listBuilder() returns" . I guess that some people may claim that this is not a valid contract for a method since it specifies implementation details rather than taking a black-box approach for specifying m()'s behavior. I am sorry to disappoint you guys, but such an approach will only work with simple programs. If your program is doing complicated computations you will not be able to express the contract (purely) in terms of input- vs. output- data. The input data will undergo such complicated transformations that you will have to use some form of abstraction, which is exactly what I did. Given that abstraction is the process of ignoring some details, there is an inherent lose of precision when one tries to formulate the contracts of elaborate computations.

Email This BlogThis! Share to X Share to Facebook

Reuse: A goal or a by-product?

I found this gem in the comp.object mailing list:

"Re-use is a happy side-effect of good designs. The primary goal is managing dependencies between modules, by making them more pluggable"

I like this statement because it captures an important insight that is too often overlooked due to us following common conceptions without questioning them. Reuse is not a goal. Reuse is a trait of source code that usually goes hand in hand with good programs. This does not mean that a high degree of reuse is a must for achieving high quality code.

If your program's complexity is well controlled then you're in a good position regardless of the amount of duplicated code therein. Conversely, having no duplications does not mean that you successfully tamed complexity. One reason for that is that highly-reused modules are also highly-coupled: even a tiny a modification in a (highly reused) module is likely to break a good fraction of its many clients. This is sheer mathematics: the more clients you have, the greater the chances that you break something.

Degradation of locality is also a risk: when you reuse (for instance by means of inheritance), the various pieces making up your class are actually defined outside the scope the class. This will make it difficult to understand what the class is doing because it's actual definition is scattered across several locations.

These ideas are not new. They were already expressed by Riachard Gabriel in his book "Patterns of Software".

Gabriel coined the term "compression" to describe reuse within a program. In the very first chapter, "Reuse vs. Compression", he says:

"Compression is a little dangerous because it requires the programmer to understand a fair amount about the context from which compressed code will take its meaning.

...The primary feature for easy maintenance is locality: Locality is that characteristic of source code that enables a programmer to understand that source by looking at only a small portion of it. Compressed code doesn’t have this property, unless you are using a very fancy programming environment."

Email This BlogThis! Share to X Share to Facebook