Old Dijkstra Essays Considered

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.

But there is a lot more to this “shortening the syntax/computation gap” than control flow level refactoring.  It seems to me that trying to encode more invariants and program structure in static types falls under this category since static typing entails statements of the form “for all executions, variables of this type must have some property”.  One recent banner example is Chris Leary’s recent refactoring of JSAtomList et al into something far more typeful.  As demonstrated in his patch, C++ types often ends up simulating discriminated unions found in higher-level language (or, more generally, ADTs).  Another example of this is the type representing a JavaScript value.

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.

new mozilla::indonesia::Kumi()

Over the weekend I constructed a 3D Kumi from this 2D pattern which my two year old has been so kind as to demonstrate in a picture:

3D Kumi

If you were wondering, Kumi is a creation of the Mozilla Indonesia community.  You can’t quite see it from the photo, but Kumi is wearing the traditional dress of Balinese Kecak Dancer.  The Mozilla Indonesia community has also created a number of other variations on Kumi that feature different cultural regions.  Another fun fact that you may have already seen is that Firefox market share in Indonesia is incredibly high, somewhere around 80%!  Clearly, this is a pretty hip group :-)

A little over a month ago, I had the chance to visit Indonesia along with my wife and some of my Mountain View based coworkers (Christian Legnitto, Dave Mandelin and the Bieber-esque David Anderson) for the local Firefox 4 release parties.  It was an amazing experience and the country was really hospitable.  In particular, we had two incredible hosts.  One was Viking Karwur, a freelance web-developer in Jakarta, who I think is something like a general or commander in the Mozilla Indonesia community.  He worked with a bunch of different local groups in Indonesia to plan some really successful release parties; if you look under the “Largest Firefox Communities” header on the Firefox 4 Release Party site on meetup.com 7 of the cities are in Indonesia!  The other gracious host was Yofie Setiawan, another freelance web-developer in Jakarta.  Yofie was kind enough to take Jenn and I around the city including a market so Jenn could find some Batik cloth to take back home.

One great thing about the trip was getting to hear what aspects of Firefox mattered to the Indonesian community.  Pretty much the number one thing I heard was Firefox memory usage, so I’m glad that Nicholas Nethercote and others have started this new MemShrink push (you can see a stream of updates on Nick’s blog).  I also think this Electrolysis effort should help since closing a process should hopefully sweep away any leaked garbage associated with a page when it closes.  Also, on a practical level, I wonder how much of a free perception boost Chrome gets since its total resource usage is spread between many processes that may not all be visible to the user when they open Task Manager / Activity Monitor.

I also heard a lot of requests for Firefox Mobile on BlackBerry… nothing much positive I can say there… but also Firefox Mobile on iPhone.  Now, Apple Terms and Conditions seem to clearly lock us out of putting Firefox Mobile in the app store so I think its great how we’ve taken the positive/constructive route by creating Firefox Home.  But, and I’m totally shooting in the dark here, wouldn’t it be cool if we put real development effort behind a Firefox Mobile that ran on jail-broken iPhones?  Is that an illegal activity?  Would that cause our legit Firefox Home app to get booted?  If nothing else, it seems like it would be useful for Mozilla to rattle the gates here to point out how Apple is locking out a browser that IMHO offers a superior mobile browsing experience (its the only reason I have and continue to use my Motorola Atrix).

While I am shooting uniformed questions out into the InterWebz, another question came up while in Indonesia: this Kumi artwork that I linked to at the top of my post is a really neat fusion of Mozilla and local Indonesia culture.  Is there any good extension points in the Indonesian Firefox where Kumi could be featured?  The first thought that came to mind is in the “About Firefox” window, perhaps in the whitespace to the bottom-left of the giant official Firefox logo.  I know there is value in having a uniform experience across Firefoxen, but perhaps there is a sensible balance, or perhaps such extension points already exist.

Oh, we also got to feed monkeys!

Tab-completion works with scp

Today I was using ‘scp’ and I reflexively tried to tab-complete the remote path.  Right about the time I thought “oh yeah, tab-completion doesn’t work with scp, duh”, tab-completion worked.  Incredible.