Monday, February 19, 2007

Writing Readable Code

Writing readable - and therefore maintainable and debuggable - code is one of the challenges of the professional programmer. There seems to be two schools of thought on how to do this. One is to insert inline, or even block, comments wherever code might be unclear or where it might be helpful to know what the developer was thinking. The other school says that the code is its own documentation.

While the second attitude seems obnoxious, the first attitude tends to not work in practice. Either comments aren't written ("I'll add them in when I'm done and know I won't change the code") or they restate the obvious (x = 4; // assign 4 to x ) and through their prevelance actually make the code harder to read. I'm not saying good comments can't be helpful, but it is hard to write good comments, and even good comments can become bad if the code changes and the comment doesn't change with it.

The solution is to strive to write code that is easily readable without comments. To demonstrate, I will show some code I randomly found online and I will show how it can be made more readable. Since that will make this post long enough, I will save my analysis on the tradeoffs of my approach for next week.

First, the "before" code:

void sort(int a[], int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo >= hi) {
return;
}
int mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo < hi && a[lo] < mid) {
lo++;
}
while (lo < hi && a[hi] >= mid) {
hi--;
}
if (lo < hi) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
sort(a, lo0, lo);
sort(a, lo == lo0 ? lo+1 : lo, hi0);
}

As you can see, it is a sorting algorithm. In particular, it is an implementation of QuickSort. Is it correct? If it wasn't an algorithm you were familiar with it, how long would it take you to figure out what it does. If you found a bug in it, how confident are you that you could fix it without introducing new bugs? These are the problems that come up when coding clever algorithms. Obviously these issues could be partially mitigated with some inline comments explaining the purpose of the various blocks of code. Rather than show that, I will show an alternative, which is to make the comments be the code.

Basically you take each section of the algorithm that you would comment and you make it a method which is named descriptively:

void quickSortRange(int a[], int low, int high) {
if ( ! indicesInRange(low, high) ) {
return;
}
int pivot = getPivot(a, low, high);
int splitPointIndex = adjustElementsAroundPivot(a, low, high, pivot);
sortSubRanges(a, low, high, splitPointIndex);
}

When you look at this, it is easy to see what is happening. As long as the sub-methods do their job correctly, you can be confident this works. If it's too complicated to describe what a method does with just a name, the description can go in the method header which is much less disruptive than cluttering up the code in line. Modern IDE's will even display this comment in a context sensitive way for the maintenance developer.

So now to define the sub methods:

boolean indicesInRange(int low, int high) {
return low < high;
}

int getPivot(int[] a, int low, int high) {
int middleIndex = (low + high) / 2;
return a[middleIndex];
}

int adjustElementsAroundPivot(int[] a, int low, int high, int pivot) {
while (indicesInRange(low, high) ) {
low = findFirstBadLow(a, low, high, pivot);
high = findFirstBadHigh(a, low, high, pivot);
swapBadElements(a, low, high);
}
return getSplitPoint(low, high);
}

void sortSubRanges(int[] a, int low, int high, int splitPointIndex) {
quickSortRange(a, low, splitPointIndex);
int newLow = (low == splitPointIndex) ? splitPointIndex+1 : splitPointIndex;
quickSortRange(a, splitPointIndex+1, high);
}

As you can see, sub-methods should be implemented with the same idea. i.e. Rather than complicated code, they should call out to their own sub-methods.

int findFirstBadLow(int[] a, int low, int high, int pivot) {
while (indicesInRange(low, high) && isLowOk(a, low, pivot)) {
low++;
}
return low;
}

int findFirstBadHigh(int[] a, int low, int high, int pivot) {
while (indicesInRange(low, high) && isHighOk(a, high, pivot)) {
high--;
}
return high;
}

void swapBadElements(int[] a, int low, int high) {
if (indicesInRange(low, high)) {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}

int getSplitPoint(int low, int high) {
return Math.min(low, high);
}

boolean isLowOk(int[] a, int low, int pivot) {
return a[low] < pivot;
}

boolean isHighOk(int[] a, int high, int pivot) {
return a[high] >= pivot;
}

When code is written this way, inline comments become much less necessary. If you change how the code works, just make sure you rename methods appropriately.

This has gone on long enough for one post, but I think this example provides plenty of fodder to think about. At least it does for me. Next week, I will analyze this example in further detail including the bug that is in both versions of the code.