Sunday, November 15, 2009

On conciseness

I meant to write this thought for a while, but a recent blog post about implementing the Quicksort algorithm in Scala finally prompted me to write this. As a refresher, here is pseudocode from the Wikipedia entry on quicksort that illustrates a simple version of the algorithm.

function sort(array) // pseudocode from Wikipedia
    var list less, greater
    if length(array) ≤ 1 return array  
    select a pivot value pivot from array
    for each x in array
        if x < pivot then append x to less
        if x > pivot then append x to greater
    return concatenate(sort(less), pivot, sort(greater))

From the Groovy in Action book, here is a Groovy implementation. It works on a List of objects that implement the compareTo() method. The findAll method returns elements from the list that satisfy the given expression, with "it" representing the object in the list.

def sort(list) { 
    if (!list) return list
    def pivot = list[0]
    def less    = list.findAll {it < pivot}
    def same    = list.findAll {it == pivot}
    def greater = list.findAll {it > pivot}
    sort(less) + same + sort(greater)
}

What I find significant about this example is that the real-code, working implementation of an algorithm is every bit as concise and readable as the pseudocode used to explain the algorithm.

From the same book, here is a Java implementation:

    public static void qsort(Comparable[] c,int start,int end){
        if(end <= start) return;
        Comparable comp = c[start];
        int i = start,j = end + 1;
        for(;;){
            do i++; while(i<end && c[i].compareTo(comp)<0);
            do j--; while(j>start && c[j].compareTo(comp)>0);
            if(j <= i)   break;
            Comparable tmp = c[i];
            c[i] = c[j];
            c[j] = tmp;
        }
        c[start] = c[j];
        c[j] = comp;
        qsort(c,start,j-1);
        qsort(c,j+1,end);
    }

    public static void qsort(Comparable[] c){
        qsort(c,0,c.length-1);
    }


This contrast is not completely fair to Java, since this Java version does an in-place sort of the array. Nevertheless, I think it illustrates the look of typical Java code.

Clearly, the newer JVM languages like Groovy allow for concise code. But I suggest that the real value of such conciseness comes not from reduced typing, but from the improved readability of the resulting code. You will read a piece of source code far more often than you will write it. It helps enormously -- whether you are enhancing or debugging code -- if you can comprehend meaning of the code immediately. In this example, the Groovy code's meaning comes through as clearly as the pseudocode. By contrast, the Java code is cluttered with the tedious mechanics of achieving the desired result. Here, the Groovy code emphasizes the what -- the meaning -- while the Java code emphasizes the how -- the process.

Of course, if performance is the primary consideration then it makes sense to write less concise code. See, for example, the various implementations of Quicksort in java.util.Arrays. And I am glad that we have performance-tuned libraries. But most application code has little impact on overall application performance, and for such code I suggest that the readability and conciseness that comes from the expressiveness of languages like Groovy is a big win.

4 comments:

  1. I'm afraid I don't know Groovy -- how does the version shown deal with empty lists?

    Here's a somewhat cleaner java version:

    List<Comparable> sort(List<Comparable> list) {
    ArrayList<Comparable> sorted = new ArrayList<Comparable>();
    ArrayList<Comparable> less = new ArrayList<Comparable>();
    ArrayList<Comparable> same = new ArrayList<Comparable>();
    ArrayList<Comparable> greater = new ArrayList<Comparable>();

    if (list.size() > 0) {
    Comparable pivot = list.get(0);

    for (Comparable x: list) {
    if (x.compareTo(pivot) < 0) less.add(x);
    else if (x.compareTo(pivot) > 0) greater.add(x);
    else same.add(x);
    }

    sorted.addAll(sort(less));
    sorted.addAll(same);
    sorted.addAll(sort(greater));
    }
    return sorted;
    }

    ReplyDelete
  2. (That looked a lot cleaner when it was formatted. Is there a way to preserve formatting when posting comments?)

    ReplyDelete
  3. Thanks for catching the bug. In fact, I left out a line in the code (now fixed) that ends the recursion: "if (!list) return list". Without that line, the code in fact goes into infinite recursion. Oops. The fixed code will handle empty and null lists, as well as arrays.

    Unfortunately, Blogger is notorious for being source-code unfriendly. If you want to post a substantial code sample, maybe you can post a link to your own blog.

    ReplyDelete
  4. Okay, I created a blog here to show the sample in it's original formatting. Thanks for the suggestion!

    ReplyDelete