Sometime when I was an undergraduate, I came across a news article announcing that all the EWDs has been published online. After figuring out what EWD meant (EWD are Dijkstra’s initials; he used “EWD” followed by a number to index his essays), I started reading a few and got hooked. For having an ivory-tower sort of reputation (stemming from opinions on formal verification and how computer science should be taught), it was surprising how personable, humble and clear his writing is. Many of the essays are handwritten and even his handwriting style is delightful (someone even turned it into a font).
For fun, I recently decided to re-read some of the outstanding EWDs to see how they sounded to me now; for the last few years I’ve been hacking on the Mozilla JS engine (SpiderMonkey) so presumably my perspective on software development has changed. To my surprise, instead of finding the essays milder than remembered (as happens with movies that used to be terrifying (Critters) or incredibly awesome (Dino-Riders)), I found some new things relevant to what is happening now in SpiderMonkey. That’s what I’d like to share in this post.
One of, if not the most, famous EWD is “Notes on Structured Programming” (NOSP). This essay is the expansion of the famous “Go To Statement Considered Harmful” CACM article that started the “X considered harmful” and, more generally, “X considered Y” memes. Primarily, NOSP makes a well-reasoned argument for why it is better to use structured control flow constructs (like if/then/else and loops) than goto. Great, we all get that — so much so that goto is now often rejected a priori despite having legitimate (albeit uncommon) applications (cf. Knuth’s “Structured programming with go to statements“).
However, NOSP’s agenda is broader than just browbeating us into not using goto. Dijkstra frames the goto issue with some general notes on making programs simpler and in the process states two principles of program simplicity that I really like. He doesn’t announce them as principles — they’re just sentences buried in the middle of paragraphs — but they seem like principles to me… so I’ll call them principles. Often, judging the simplicity of a patch or piece of code feels highly subjective and more a matter of taste than anything. However, I was delighted to see how many simplifications (considering recent SpiderMonkey patches I’ve written or seen flying by) could be viewed as following from these two principles.
Let’s start with the first principle, taken from the following quote:
In vague terms we may state the desirability that the structure of the program text reflects the structure of the computation. Or, in other terms, ‘What can we do to shorten the conceptual gap between the static program text (spread out in “text space”) and the corresponding computations (evolving in time)?’
For the specific case of goto, Dijkstra proceeds to spell out in great detail how structured control flow admits an unequivocally shorter conceptual gap.
In SpiderMonkey, many recent simplifications have simply been removing old uses of goto (e.g., check out js_GC before a heroic set of patches by Jason Orendorff, as well as obj_eval and js_Invoke before several incremental rewritings). I should note that switching SpiderMonkey to C++ a few years ago has been invaluable in control flow refactoring since with C++ comes RAII which has been used in practically every big function cleanup since.
Because of the, to put it kindly, dependently typed nature of many central SpiderMonkey data structures, types must often be bolted on, like an exoskeleton, to an underlying representation that is being treated like a bag of bits. Here, C++’s unsafe casts, inlining, and templates are critical for avoiding performance penalties for using abstraction. The data structure that holds the JS call stack is one example. Another example is the recently-refactored set of types iteratively concocted by Gregor Wagner, Igor Bukanov, and Bill McCloskey to abstract GC data structures.
Another interesting non-standard application of types can be seen in the recent refactoring of strings. Here, the C++ class hierarchy captures the logical hierarchy of string invariants. Unlike an ordinary C++ class hierarchy, the string hierarchy contains no virtual functions and all instances of the hierarchy are necessarily the same size. JSObject is incrementally growing a similar hierarchy (which I hope continues!). In both cases, the C++ type system is being used (and sometimes abused) to provide the desired connection between static types and dynamic properties of strings/objects.
Finally, in the worst case, no language or type system will help you simplify the mapping from syntax to dynamic computation; you just need to suck it up and completely change tack. An admirable example of this last year was Andreas Gal’s transformation of jsiter. It is a beautiful thing when a patch, in total, removes 500 lines and SunSpider gets 4% faster.
The second principle contained in NOSP that I’d like to point out comes from the following quote:
Eventually, one of our aims is to make such well-structured programs that the intellectual effort (measured in some loose sense) needed to understand them is proportional to program length (measured in some equally loose sense). In particular, we have to guard against an exploding appeal to enumerative reasoning, […]
To give a bit of context, “enumerative reasoning” is defined in the essay to mean the mode of reasoning where you are forced to consider every possible case and make sure the desired property holds for each of them individually. Dijkstra contrasts this to the more desirable “abstractive” and “inductive” reasoning and explains how building up structured control flow allows their use instead of enumerative reasoning.
One example of this in SpiderMonkey is typified by pretty much any work that Jeff Walden does. In his patches (and, as the style spreads, others’ too), each step of the implementation is made to correspond closely to the individual steps of the corresponding ECMAScript sections, complete with comments labeling the steps. This reduces enumerative reasoning by allowing one to judge the spec-conformance of an individual statement instead of an entire function.
Another way enumerative reasoning is reduced is by simply having less code. This of course is Reusability, the Holy Grail of Software Engineering (apparently, a solved problem). One of the biggest examples of this I can think of is the security wrapper rewrite that was part of the mammoth compartmentalization effort. Allegedly, thousands of lines of mind-bending security-critical code were removed, replaced by a small set of composable policy templates. And if that wasn’t enough, harmony:proxies got to ride along at a bargain rate!
That last class of enumerative-reasoning-reducing changes that come to mind are those that cut down on the number of VM-wide concepts — be they states, requirements, corner cases, gotchas, possibilities, etc — that must be kept in mind to effectively work on the SpiderMonkey. Examples from recent memory include the removal of: JSScope, slow natives, watchpoint hacks, JSObjectMap, GC-from-malloc, concurrent JSRuntime access, local rooting scopes, newborn roots, display optimizations, multi-threaded objects and titles, multi-threaded strings, dormant stack frames, __count__, __parent__, non-identifier atoms, heap-doubles, null-is-an-object, the no-int-valued-doubles-in-values rule… and those are just things that appeared on my radar; a simple bugzilla search for “remove” shows a lot more.
Altogether, I think this demonstrates that these two simplification principles cover a lot of real-world patches. It’s neat to find them nestled in a 40 year old essay written when goto still ruled the land.
On a side note, I think continual simplification is vital to maintaining a healthy, long-lived codebase. Thus, I see the size of the — far from complete– set of simplifications listed above to be a very good sign for an already rather long-lived codebase.
I’ll conclude with the summary of a section in NOSP entitled “On Our Inability To Do Much”:
Summarizing: as a slow-witted human being I have a very small head and I had better learn to live with it and to respect my limitations and give them full credit, rather than to try to ignore them, for the latter vain effort will be punished by failure.