Dreaming in Code

January

22, 2007

by John Shedletsky


Archive

Software is hard. – Knuth

Dreaming in Code

At least once a week I like to go to the Stanford bookstore and drink coffee while I read through books or magazines that I almost never intend to buy. You may think that this makes me a terrible person; however, I think it’s a great deal for the bookstore. They’ve been selling me $3 bean water regularly for the past five and a half years. I used to hit them up ever day or so for breakfast, which I would have never done were I not able to read all sorts of interesting things while enjoying my meal.

This Saturday, I picked up the new Wired and this book that caught my eye, Dreaming in Code. I used to dream in code, but as a grad student I found that more often than not, when there was coding to be done, I was doing that instead of dreaming. But that is neither here nor there. The book talks about the problem of writing software. Fifty years after the invention of the digital computer, the modern world is dependent on software. Yet writing software remains a black art. Unlike other types of projects, the length of time it takes to complete a software project is non-deterministic. Anyone who has tried to write even a simple program will have noticed this property of software. Maybe you bang out the code, compile, and run it and it works the first time. Bam, you’re done. Maybe you write all the code out, compile, and wham! Blue Screen of Death. You’re hosed. There’s a bug in your code somewhere. It will randomly take you between 1 and 5000 minutes to find and fix it. Ready, set, go!

This issue is compounded by the increasing complexity of contemporary computer programs. Large programming projects are necessarily huge creations of crystallized logic, manifest as lines of code. It stands to reason that the more lines of code you have in your project, the more places there are for bugs to hide. Traditionally the length of a computer program has been measured in KLOCs (a very cool sounding unit that is pronounced “KAY-locks”). 1 KLOC = 1000 lines of code. To give you an idea of what programmers today have to deal with, when I was interviewing up at the Empire, someone told me that the Halo source code is about 1.6 million lines of code. Printed, that would be about 40,000 pages. That’s more or less the size of the entire Encyclopedia Britannica. It’s probably fair to say that there is not one person alive who knows or understands every line of the Halo codebase.

I’m not sure that anyone on the Roblox Team knows how many lines of code we have that get compiled into our game. With all the 3rd party libraries we use, it could well be over a million. We cope with the complexity in several ways. First, except for Erik, who is a coding demigod, probably no one at Roblox knows how everything works. We each have a specific domain that we are knowledgeable about, and everything outside that is black magic. Second, to the extent that is possible, we use modular design to simplify individual components of the project. This is standard practice for programmers, and way too abstract of a notion to be interesting to non-programmers, so I will gloss over it. Third, we make aggressive use of asserts – a special programming construct that enforces a “sanity check” on certain assumptions made at different points in the code. This has helped us to find bugs that would have otherwise been impossible to track down. Fixing a bug is often very easy. The hard part is locating the root cause of a bug. Our assertions get us closer to the root cause than we would get if we just waited for the whole thing to crash.

Dreaming in Code points out the essential problem with developing software, but does not point the way towards any solutions. In fact, it is my personal feeling that writing good software is probably beyond the abilities of mere human intellect. It may even be beyond the ken of putative super intelligent machines of the future. There are many specific problems relating to program verification (for example: detecting buffer overruns) that are NP-complete, which means they are beyond the abilities of any classical computer to solve. If a computer cannot verify that a supplied program is correct, it would be very surprising if it could supply a correct program that accomplishes a given task. So next time Roblox crashes on you, or throws an error, take pity on us. Like you, we have only meat in our heads to think with.

– Telamon