two beautiful [code] things
Despite what pg might tell you, computer programs are not “art” in the traditional sense. Yet they are art in the expanded sense of “Quality” expounded on in Zen and the Art of Motorcycle Maintenance. Engineering problems do have beautiful, aesthetic solutions. The aesthetic evoked by code is not obvious in the way that a painting or sculpture may be. It is an arcane beauty, accessible to those inducted in the ways of the Bit, familiar with binary logic and the real constraints imposed by the problem at hand.
I’m not alone in thinking about code this way — from the small amount that I’ve read, Knuth’s Art of Computer Programming is a book full of clear thinking and elegant algorithms. Beautiful Code is a fascinating volume of famous programmers answering the highly subjective question, “what is the most beautiful piece of code that you’ve encountered?”
I’ll let better writers than I wax lyrical on the virtues of engineering aesthetics and clean code, and present, with little comment, two pearls that I’ve lately encountered.
Café Life
Prof. Knuth argues passionately for something he calls “literate programming” — code and documentation, interspersed, both crafted for greater human understanding of the program at hand. His ideas have been implemented to various degrees of success, from things like JavaDoc, Docbook, etc., up to very elaborate tools like Dexy, Sphinx, and more. (I previously wrote about Dexy+Factor, an experiment in publishing code+prose.)
However.
Sometimes there’s a project that gives me pause because of the elegant beauty it displays. As the home page for Café au Life says:
If you haven’t seen how the algorithm works, you owe it to yourself to read the annotated source code.
And you really do, it’s quite beautiful. http://recursiveuniver.se/docs/cafeaulife.html
Conway’s Game of Life is a pet interest of mine. I’ve made several implementations, the latest of which was in Lua for Codea on my iPad. Optimizing Life is an interesting problem, and many papers have been published on the subject. (ed. note “optimizing [my] life” is a completely different and also highly interesting problem!)
One of the fastest implementations is known as “Hashlife” and it optimizes the hard problem of updating a large board by hashing sections of the board along with the calculated “next state” of the hashed part. For example, a glider or period 2 oscillator both move in predictable ways. But beyond that, there are larger and larger structures whose behaviour can be known and calculated — for example, the period 15/30 “Gosper glider gun”. Hashlife analyses these structures at all different levels and develops an efficient in-memory structure for quickly finding the “next generation” for a given 2n swath of board.
And Café au Life is an clear & understandable implementation of Hashlife, so you should definitely be reading it now. :)
The Raft consensus algorithm
As we approach the limits of Moore’s Law the old problems of parallelism, concurrency, and distributed systems have surfaced again with new interest.
To me, one of the most interesting developments is the Raft algorithm for distributed systems. But rather than focus on some hard technical aspect, the Raft authors cared about making the algorithm easy to teach and understand.
Paxos is the established work here, used by Amazon, Google, and others to build scalable & highly-available systems. It is an excellent solution to a very difficult problem. But Paxos has one major flaw — it’s notoriously difficult to implement correctly. I can’t find the citation at the moment, but engineers at one of those major companies found subtle problems in their implementation that only showed up after days of burn-in testing, suggesting highly improbable & difficult to test edge cases.
The Raft paper, on the other hand, is quite accessible, nicely formatted, and easy to understand. There are several standard implementations of Raft that are easy to read and reason about. The only criticism I’ve seen leveled against Raft is that it’s a sole-master architecture (all nodes forward requests to the currently elected master).
Ease of understanding is a feature. It’s interesting to read a paper written with that assumption and see the consequences of their work — dozens of implementations of Raft, and a growing community. Even if you’re not in the habit of reading CS papers it’s worth at least flipping through Raft.
bonus reading
Distributed systems are hard. Distributed data stores are harder, and make promises they often can’t keep. Aphyr’s tales of testing with Jepsen, a custom Clojure tool for simulating cluster splits and rejoins, makes for an exciting crash course in distributed systems. If you find yourself with an evening to spare, wanting to level up your understanding of distributed systems, I highly recommend reading through the Aphyr posts.