In Defense of “Beautiful Code”

In my May 2008 APP article “Beauty Is Our Business?” I argued that neither in mathematics nor in programming the concept of Beauty is a useful one. But the B-word is hard to suppress. A kind reader of APP directed my attention to “Beautiful Code: Leading Programmers Explain How They Think”, a collection edited by Andy Oram and Greg Wilson. This book already existed when I wrote my article, so I could have known about it. It’s good that I didn’t, because we now have the benefit of Jeff Atwood’s comments [seen Sept. 30, 2010]. His critique is that an idea can be beautiful, or an algorithm. But the code embodying them is not beautiful, Atwood maintains, and code stands in the way of the appreciation of the beauty of the underlying idea or algorithm. In this article I argue that handwaving is not enough, that such abstract thing as an idea or an algorithm needs embodiment to be appreciated, and that for an algorithm the natural embodiment is in the form of code.

For the gist of Atwood’s criticism I quote:

Instead, many chapters just reprint a few pages of code and conclude — see, it is beautiful! Many times I was unable to grasp the problem — what was it that required that so-called beauty to emerge? I couldn’t see the whole picture, but the authors presume I do. Any possible appreciation of beauty requires deep understanding.

I can believe that, about the deep understanding! So here we have a software guru, like Brian Kernighan, or Jon Bentley, pointing at a piece of gobbledygook, and saying: “This is beautiful!” They are like many other gurus, through the ages, pointing at this:

μῆνιν ἄειδε θεὰ Πηληϊάδεω Ἀχιλῆος
οὐλομένην, ἣ μυρί’ Ἀχαιοῖς ἄλγε’ ἔθηκε,
πολλὰς δ’ ἰφθίμους ψυχὰς Ἄϊδι προί̈αψεν
ἡρώων, αὐτοὺς δὲ ἑλώρια τεῦχε κύνεσσιν
οἰωνοῖσί τε πᾶσι, Διὸς δ’ ἐτελείετο βουλή,
ἐξ οὗ δὴ τὰ πρῶτα διαστήτην ἐρίσαντε
Ἀτρεί̈δης τε ἄναξ ἀνδρῶν καὶ δῖος Ἀχιλλεύς.

and saying “This is beautiful!”. I both cases I’m not likely ever to undertake the arduous journey to the required deep understanding. But in both cases I am willing to believe the gurus and to respect those who do make the effort.

Atwood likens code to the paint of the painting. If you can only see the paint of Van Gogh’s Irises, and not the painting, then you don’t experience beauty. Similarly, if you only see the code, and not what’s behind it, then you don’t see beauty. A difference is that most people are endowed with an innate capacity to appreciate “Irises”, but do not have this capacity for text. Text needs to be worked at, to a greater or lesser extent.

If Van Gogh would talk to us about the idea in “Irises” it’s unlikely we would experience beauty. Beauty needs to be embodied, and for paintings embodiment takes the form of paint on canvas. But the paint can get in the way if you look at it the wrong way. Similarly, if the authors collected in “Beautiful Code” would only talk about “the idea, the algorithm”, then it wouldn’t be enough. The code is needed, just as the paint is needed.

With “Irises” it’s so that the artist can only present it on a take-it-or-leave-it basis: you either see it or you don’t. When asked what the meaning of a painting was, Picasso is reputed to have said: “If I could tell you, Madam, I would be a writer. As it happens, I am a painter.” Code does not need to be presented on a take-it-or-leave-it basis. The author happens to be a writer (she had better be), so can work at facilitating appreciation of the code. In this article I will try to demonstrate the phenomenon of beauty in code. Taking Atwood’s criticisms to heart, I make the examples drastically smaller and I add plenty of context.

I’m going to experiment with the possibility of supplementing beautiful code with the required understanding with two related examples. The first is the task of reversing an array segment a[p..q]. To be concrete, the task is that of writing a function declared as

void rev(int a[], int p, int q);

assuming one has available

void swap(int a[], int i, int j) {
  int temp = a[i]; a[i] = a[j]; a[j] = temp;
}

To reverse an array segment, one swaps each element in the left half of the segment with its mirror image in the right half, for example like this:

void rev(int a[], int p, int q) {
  for(int i = (p+q)/2; i >= p; i--) swap(a, i, q-(i-p));
}

Even in this simple example the student author must have experienced a few annoyances. Is the halfway index OK for both odd and even segment lengths? Should I introduce another variable to save recomputation in the argument expression in the call to swap?

Compare this student’s effort with that of another:

void rev(int a[], int p, int q) {
  for(; p<q; p++,q--) swap(a, p, q);
}

This was my favourite until I saw the comment from Samuel Tardieu:

void rev(int a[], int p, int q) {
  while(p<q) swap(a, p++, q--);
}

Isn’t this more than just better code? Don’t you experience this “more” as, er, beauty? The function definitions embody the same idea and the same algorithm. According to Atwood one cannot be more beautiful than the other. But just look … code can make a difference.

As the other example I choose the task of cyclically shifting the contents of a one-dimensional array. I used this example in the first course I ever taught, which was for novice programmers. The problem has besides some obvious solutions an interesting one. How could I keep my students away from the obvious ones? Well, I showed them these in advance, so they would know what I did not want them to do.

I explained that the array can be copied shifted to a temporary other array and that the contents can be copied back, like this:

void cycShift(int a[], int n, int k) {
  int b[n];
  for(int j=0; j<n; j++)
    if (j-k < 0) b[j-k+n] = a[j];
    else b[j-k] = a[j];
  for(int j=0; j<n; j++) a[j] = b[j];
}

The novice needs to be made aware of the dire disadvantages of this simplistic solution: all that wasted space. OK, so how about no extra space, like here:

void cycShift(int a[], int n, int k) {
  while(k-- > 0) {
    int temp = a[0];
    for(int i=1; i<n; i++) a[i-1] = a[i];
    a[n-1] = temp;
  }
}

The novice needs to be made aware of the dire disadvantages of this simplistic solution: all that wasted time.

By denying the novice these easy ways out, I was hoping to light the spark of inspiration. I suggested using mathematics, showing that there is a kind of algebra of sequences. What the operations of such an algebra are depends on who you talk to. But all would agree that concatenation and reversal are worth including, if only because of the following property: (x.y)’ = y’.x’ where the dot is concatenation and the prime is reversal. And note how the order of x and y is reversed.

I left it at this, hoping that they would continue with something like the following. Let s be the sequence to be shifted by k places to the left. Define x and y such that s = x.y with the length of x equal to k. Let us denote by s|k the result of cyclical shift of s by k places to the left. Then we have s|k = y.x.

How do we get y.x? Let’s set s = x.y so that s’ = (x.y)’ = y’.x’. Then an algorithm for cyclical shift is obtained by

s|k = (x.y)|k = y.x = (y.x)'' = (x'.y')'

It is an algorithm because the latter expression consists of easily implementable operations. The algorithm is apparently: first reverse left and right segments separately, then reverse the entire sequence. In code:

void cycShift(int a[], int n, int k) {
  rev(a, 0, k-1); rev(a, k, n-1); rev(a, 0, n-1);
}

This steers the way between the Scylla of excessive memory use and the Charybdis of excessive processing. It needs a constant amount of memory beyond that for the array to be shifted, so it is well clear of Scylla. It needs n swaps, each of which require 4 array accesses (2 reads, 2 writes), so it is well clear of Charybdis. By showing my students two ways how not to do it, I hoped to give them a push on the way to finding this piece of beautiful code.

I wasn’t sure whether I could expect any of the students to get this, the bonus question. After all, one needs some experience and sophistication to relate algebraic manipulations with code. I was in for a surprise. Actually, a double surprise. One part of the surprise was that there was a student who submitted what he claimed was working code that needed only a constant amount of extra memory and an amount of processing that was independent of k. The other surprise was that he did it not in the way I believed to be the one right and elegant way. What did he do?

I found the code puzzling. By the time I figured out what he had been doing, I realized that he only used one half of the number of array accesses compared to mine. The idea that I found was that if one has merely one free location in the array, then one can have this free location jump all around the array to receive every element in turn at the new location required by the cyclic shift. Is this idea beautiful? Maybe it can only become so by being realized in every detail so that a machine can do it this way fully automatically. That is, to code it. But first I need to make the above hand-waving sketch of the idea more concrete by an example.

Here is an array with indexes 0..9 containing the first ten letters of the alphabet:

          0 1 2 3 4 5 6 7 8 9
         ---------------------
          a b c d e f g h i j

We are asked to shift it by three locations to the left. Index 0 is the initial free space. It is “free” because its content is saved away outside the array:

          0 1 2 3 4 5 6 7 8 9
         ---------------------
   a        b c d e f g h i j

In the shifted situation this location has to have the d in it. So we move it there, thereby freeing the location where the d was before. We continue in this way until all nine remaining elements are in their new locations:

          0 1 2 3 4 5 6 7 8 9
         ---------------------
   a        b c d e f g h i j
   a      d b c   e f g h i j
   a      d b c g e f   h i j
   a      d b c g e f j h i
   a      d b   g e f j h i c
   a      d b f g e   j h i c
   a      d b f g e i j h   c
   a      d   f g e i j h b c
   a      d e f g   i j h b c
   a      d e f g h i j   b c
          d e f g h i j a b c

In the penultimate line all nine remaining elements have been moved to their shifted positions. The location of the hole in the penultimate line has to be the place for the element that was initially shunted away. So that’s where it went in the last line.

This example is simple because the distance to be shifted, 3, and the length of the array, 10, are mutually prime. As a result, everything is moved in a single cycle. In general, gcd(n,k) cycles are needed for shifting by k in an array of length n. Here is the example with shifting by 2:

          0 1 2 3 4 5 6 7 8 9
         ---------------------
   a        b c d e f g h i j
   a      c b   d e f g h i j
   a      c b e d   f g h i j
   a      c b e d g f   h i j
   a      c b e d g f i h   j
          c b e d g f i h a j    end of first cycle
   b      c   e d g f i h a j
   b      c d e   g f i h a j
   b      c d e f g   i h a j
   b      c d e f g h i   a j
   b      c d e f g h i j a
          c d e f g h i j a b    end of second cycle

Time for coding.

Executing a single cycle is a self-contained task:

void cycle(int a[], int n, int k, int start) {
// executes single cycle starting from "start"
    int i = start;
    int j = (i+k)%n;
    int saved = a[i];
    // save element at first location of cycle
    while (j != start) {
      a[i] = a[j]; // shift element
      i = j; j = (j+k)%n; // shift indexes
    }
    a[i] = saved;
}

To complete the cyclic shift, gcd(n,k) cycles are needed; hence the function:

void cycShift(int a[], int n, int k) {
// shift a[0..n-1] to the left by k places, cyclically
  assert((0 < k) && (k  0));
  int start = 0; // index where cycle begins
  for (int i = gcd(n,k); i > 0; i--)
    cycle(a, n, k, start ++);
}

Is this Beautiful Code? In this case again I agree with Atwood that the beauty is not an attribute that applies to code. “Beauty is in the eye of the beholder”. A more precise formulation of this piece of wisdom is that beauty is a binary relation. One that may or may not exist between the beholder and the object beheld. Beauty as a unary predicate is erroneously derived from this binary relation. The patter that preceded the code in this article is intended to establish that relation.

This brings me back, way back, to when I first used this exercise. C did not exist; the language was Algol 60. The student who got this solution was Dik Winter. His code ended with the comment:

Like as the waves make towards the pebbled shore,
So do our minutes hasten to their end,
Each changing place with that which goes before
In sequent toil all forwards do contend.

From sonnet LX by William Shakespeare

Dik was a famously uncommunicative person. I take it that in this way he wanted to tell me that he had experienced beauty.

Let this article be dedicated to the memory of this remarkable man, who died on December 28, 2009.

PS Paul McJones was so kind as to provide some scholarly background to this article:

Your reverse and cycShift examples are nice. I believe that the earliest published version of the algorithm that Dik Winter discovered was Fletcher and Silver in 1966 (Algorithm 284: Interchange of two blocks of data. CACM 9(5): 326). Actually, Dik’s is slightly better: his cycle uses n+1 assignments, whereas theirs uses n swaps. Note Dik’s algorithm requires general indexing, whereas the algorithm based on rev requires only ++ and — on indices. There is another efficient variation that requires only ++ (e.g., it will work on a singly-linked list); it was first published by Gries and Mills in 1981 (Swapping Sections. Tech Report 81-452, Department of Computer Science, Cornell University). Perhaps unsurprisingly, GCD comes up again with it. Our chapter 10 (“Rearrangements”) covers these things.

PPS The “Chapter 10” in the PS is in “Elements of Programming” by Alexander Stepanov and Paul McJones; Addison-Wesley, 2009.