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.

10 Responses to “In Defense of “Beautiful Code””

  1. Ruben Berenguel Says:

    I agree with you in that code can be beautiful. But beauty is an end per se, and not the way to finish let’s say an assignment, or a work. I love beautiful code, but I am just an apprentice, maybe a craftsman but not a master. I can write to get something done (like my translucent triangle approximator, or my C code assignment cheat analyser), but they are just tools. They are not meant to be beautiful, they are meant to just work and do something. Just like a hammer or a nail. But even those samples can be improved to levels I can’t even see, and make them beautiful in themselves. It’s just that there are times when this is good, and times when you’d better spend that afternoon debugging something else ;)

    Cheers,

    Ruben

  2. Joshua Says:

    My personal opinion is that the cleanliness and clarity of the mind of the programmer is made apparent by the structure and flow of their code.

    Code that is cluttered, disorganized, has misnamed variables, etc. simply reveals the developer probably has not thought things through well.

    At this point (I’ve been doing development for 10+ years) I can tell from a simple glance at code whether an individual understands what is going on. If there is beauty – simplicity expressed through consistency – then not only will I be able to understand their code faster but I will enjoy working with it more as well.

    And code that is enjoyable to work with will be more efficient to work with.

    Ultimately beautiful code makes applications run better and makes the entire development team more efficient.

    I would liken it to music. If the managers in a company were forced to listen to awful music all day their entire productivity would probably plummet because of pure annoyance. The same thing happens to developers who constantly have to look at ugly code.

  3. geoff Says:

    I think you scratch the surface but ultimately miss the gap between appreciating a beautiful algorithm and beautiful code.

    Just as looking at a foreign text that is supposedly ‘beautiful’ is lost on you, one who isn’t fluent enough in the language the code is written in can’t appreciate the beauty of the code.

    Thus it isn’t really the code that is beautiful, per se; it is just the code is the mechanism which allows you, the one fluent in the given language, to experience/appreciate the beauty of an elegant algorithm.

  4. René Says:

    Code can be beautiful indeed. But I think appreciation of that beauty, very much comes through understanding of it.

    I don’t understand Art and therefor, is not susceptible to it’s beauty. I’ve never looked at a painting and felt the way I do, when I see an elegant and simple piece of code provide a solution for a complex problem. One of my favourite bits is this:

    /^1?$|^(11+?)\1+$/

    Which most programmers probably know. To non-coders, this is random characters and ones. To me, it’s beautiful.

  5. Mujtaba Hussain Says:

    I am not sure about how a code should look. I think if a piece of code serves its purpose well without flaws, then it is beautiful.

  6. Dave Says:

    So, like Jeff Atwood, I’m not a great fan of the book. I follow your argument regarding paint, and have heard many like that from others. But, I don’t believe it. For me, beauty is inextricably linked with the visual or auditory. If I cannot see it, or hear it, then it’s very difficult for me to say it’s beautiful.

    Of course, code can be beautiful. But, it’s the simple things, like syntax highlighting and layout, which when used effectively make it so. Call me cynic if you like, but I think ultimately the human mind is very limited in how it can perceive complex things, and this is an inherent barrier to the notion of beauty of software.

    Anyway, I made a few comments after reading the book a while back:

    http://whiley.org/2010/08/19/beautiful-code/

    Dave

  7. Kia Kroas Says:

    Not to plug myself here, but I don’t think code is beautiful. And I may just be playing to semantics here, but code is not beautiful. Code is Ugly, Algorithms are Beautiful. Algorithms make the code elegant, not beautiful.

    linky to my blog for a longer explanation: http://www.kiakroas.com/blog/45/

    Thanks!

  8. Sam Says:

    The “beautiful” version of “rev” is IMO this one:

    void rev(int a[], int p, int q) {
      while (p<q) swap(a, p++, q--);
    }
    
  9. mrkkrj Says:

    The “hammer on a nail” metapher is good: hammer isn’t beautiful, it’s OK. Maybe not everything must be beautiful? Maybe clean code would do?

    The idea may be beautiful, but it code representation should be just clean.

    Thanks for the post!
    Marek

  10. Poesía, Caligramas y la Belleza del Código | La Naturaleza Del Software Says:

    [...] a tomar prestado parte del argumento Maarten Van Emden, autor de A Programmer’s Place, uno de mis blogs favoritos, para defender la necesidad de la [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 36 other followers

%d bloggers like this: