A Renaissance Computer Scientist

My friend, Norm Hardy, passed on October 30th of 2018, of late-stage terminal cancer. His final days were spent exchanging notes with friends and loved ones. Here is the final note that I sent to him:

Norm:

One of the traits you and I lack in common is a perception of time. Both of us have lived mainly in our heads, insulated in some measure from awareness of time passing. It is hard to imagine that we have known each other for almost 30 years — we first met at Stanford in 1989.

The demands of my life since 2009 have made me a stranger to friends and students alike. I had no wish to draw others into the mire of an ugly divorce, an uglier custody battle, and years of recovery for Alex and myself any more than I could help, and there was little else in my life to talk about during that period. Then I was building a new family, a new marriage, and a new business with my wife Darcy, and there has been little time for anything else. Between these two things, I have allowed us to drift apart. It has been one of my greatest regrets of this period of my life.

There is one quality of yours that I have admired and found bewildering in equal measure. To you, ideas and learning are a grand puzzle and adventure. Whether the outcome is a clever new algorithm, or a visual result, or a new way of thinking about computer architecture doesn’t matter; you have loved the process of discovery for its own sake. Seeing your joy in that process, I have often wished that I might look at ideas in the same way, but my path and my focus are different.

What with Mark as a friend, it won’t surprise you that I’ve given careful thought to cryonics for myself. To Mark’s lasting annoyance, the answer for me has always been “no.” I am content in the life that I have, and I will be content when the time comes for it to end. For you, I cannot imagine any decision other than the one you are making. Mark describes your view as “It’s not much of a chance, but it’s a chance,”, and I’m sure that’s part of your thinking. But I’m equally sure that you cannot imagine passing up a chance to explore the “Undiscovered Country,” and see what new discoveries and adventures it may hold.

Go with my love, and explore it for me as well.

Yours,

Jonathan

He replied that I had explained much of his drive. Gracious in sharing credit, he thanked me for infecting the L4 community with our ideas [about capability-based systems], noting that they seem to have caught on. He passed two days later, surrounded by friends, including Mark Miller (one of my doctoral students), who has written his own take on Norm’s contributions (link to follow when it is published).

Norm has been interviewed by San Jose’s Computer History Museum. So has his wife, Ann. Both made substantial contributions to the field of computing. They had a joint hand in some of the earliest of IBM’s scientific computers, in the commercialization of time sharing, and in the creation of the first functional capability-based operating system. Nathan Gregory devotes significant space to their involvement in Tymshare in The Tym Before, providing incidentally a sense of how small a place that early digital “wild west” was and how rapidly it changed. Ann has been grossly short-changed by history.

Since Mark Miller is writing up Norm’s contributions to capability-based systems, I thought I might focus on a second contribution that is, to my mind, more fundamental: translating the idea of “Units of Operation” into software. Before I explain what it is, let me explain how he came to it.

Though his younger colleagues mainly know of Norm’s through his work on software, Norm was an early member of IBM’s Advanced Computing Systems group. That group is arguably responsible for the entire foundation of modern computing and compilation. If you have any interest in such things, it is worth some time to delve into the careers of John Cocke, father of both RISC (IBM 801) and CISC (ACS/360) processing; Gene Amdahl, co-inventor with John Cocke of superscalar processing, later founder of Amdahl computing; Robert Tomasulo, inventor of out-of-order instruction processing and what is now called “register renaming”; Fran Allen, co-originator with John Cocke of modern compiler architecture; Lynn Conway, an inventor of modern VLSI design tools; John Zasio, an inventor of automated design tools for printed circuit boards and VLSI; and Fred Buelow, founder of Cadence and another inventor of VLSI tools. At various points in my own career I have been privileged to work with about half of these people and I’ve met and spoken with the others; I can’t imagine what it might have been like to work with all of them simultaneously. A firehose indeed.

One of the key ideas of ACS — which I believe is due to Cocke, though Tomasulo refined it — is that processors should operate in well-defined steps known as “units of operation.” A unit of operation either executes to successful completion and has an effect on the [architected] state of the processor, or it fails and it has a different effect on the state of the processor, typically in the form of an exception. In both (or rather, all) cases, the effect is well-defined. There is no third possibility, and in particular there is no notion of a partial effect. The essential point is that a unit of operation moves the processor from one architecturally well-defined state to another architecturally well-defined state. By virtue of maintaining this discipline, the processor’s state at any externally measurable point can be accounted for as the outcome of a linear sequence of steps proceeding from a well-defined initial state (the “power on” state). Distinct units of operation do not (logically) proceed at the same time; at least in retrospect, it is possible to tell a sequential story about how the processor got from where it has been to where it is now. This sequential story is the key to being able to reason about whether the processor has operated correctly. Indeed, it is how one defines what correct operation means.

I first met Norm at Stanford in 1989, where he gave a talk on KeyKOS, a derivative of the GNOSIS operating system that he had originally created at Tymshare along with Bill Frantz, Charlie Landau, Allen Bomberger, and Jay Jonekait. In the course of that talk, he said (or perhaps he propounded) three key ideas:

1. Every kernel operation moves the system from one well-defined state to another
2. The kernel maintains no “hidden” state; the conceptual state of the system is entirely defined by the content of Pages and Nodes (which wasn’t quite true, as there were also “Meters” for scheduling).
3. Authorization and naming should never be separated — the ability to name an operation and the authority to perform that operation should be identical. This is the “capability” notion, which Mark Miller discusses elsewhere.

This led me to read his paper The KeyKOS Architecture (here, with others), so dense that it took seven readings and several conversations to fully internalize.

By this time in my career, I was thoroughly familiar with UNIX from my time at Bell Labs, and I had done a bunch of compiler work of my own. Through compilers, I had come to take for granted that machine instructions implement units of operation; I didn’t yet understand enough of the history to appreciate quite how revolutionary that idea had been when the ACS team created it. It had even found its way into the Intel processors, largely unrecognized and unappreciated, through John Wharton’s creation of the Intel 4004. Many later problems in what became the Pentium line were due to the “unrecognized” aspect of this inheritance, and were fixed by its re-adoption as virtual machine support was added to that product line.

Conspicuously, no analogous concept existed in UNIX or DOS, and the notion wasn’t really recognized in the software world outside of the software verification and the theory of computation communities — and even there without ever managing to be earn itself a name by which it might properly be talked about. In the world of computing practice, Tom Killian introduced the /proc file system into UNIX 8th Edition at Bell Labs, and halfway-introduced a notion of “sequence points” more or less of necessity; debugging a process is very hard if the state of a stopped process isn’t reasonably well-defined. Roger Faulkner and Ron Gomes worked together to hammer that idea fully home in UNIX System V Release 4 while we worked on a “green field” new debugger for AT&T’s version of UNIX. Roger and I later (independently, but in collusion) contrived to force the same notion into Sun Microsystem’s Solaris and Silicon Graphics’ IRIX operating systems.

Looking back, our notion of sequence point was pretty weak. It constituted a well-defined stopping point with respect to what we called “events of interest”, by which we mainly meant events of interest for the purpose of debugging. We didn’t really consider that the entire design of the UNIX system calls is built around a notion that undefined partial updates are OK as long as an error code is returned. We certainly didn’t have the benefit of exposure to the members of the ACS team at that point, and I don’t think that Dennis Ritchie or Ken Thompson had either. IBM and everyone else were opposing encampments with little communication across the two cultures.

To me, at least, the notion that the state of an operating system could be that well-defined was revolutionary. Enough so that I spent the subsequent year trying to convince my co-founders at HaL Computer Systems that we needed to adopt what Norm had built as our base operating system, and eventually leaving HaL when they declined. I spent much of the next year trying to license KeyKOS from by-then-imploded Key Logic, and the year after that building a clean-room version of KeyKOS under the name EROS, which eventually became the basis of my doctorate, and then Coyotos following my exposure to Jochen Liedtke, Hermann Hartig, Gernot Heiser, and their efforts on various versions of L4. My son Alex will be helping me get the many hours of cassette tapes of my conversations with Norm about the KeyKOS internals available online.

The idea of well-defined states and units of operation had come into software independently through software verification — albeit without a name — though I would only appreciate that well after my exposure to Norm and KeyKOS. What made Norm’s framing unusual was the assertion that this was the most sensible way to build software, and (never quite stated) the only way to get software right, and he took it for granted that this was an entirely practical approach to software construction rather than merely a theoretical or mathematical exercise. He was, of course, correct. Though we came to it from different paths, Jochen Liedtke and I independently used that concept to get to sub-microsecond interprocess communication implementations on processors that, in retrospect, were pretty damned slow. The thing that made this possible was that we knew what constituted a correct implementation, and therefore which optimizations were correct and which were not.

Many have called out Norm’s contributions to computer security — and through conceptual inheritance and Mark Miller to Javascript/ECMAscript security. I agree. But I think that this more fundamental notion of units of operation in software has tended to go unnoticed.

Those working in theory of computation have spent nearly 60 years on the semantics of computation, trying bring meaning to the theory of computation by developing a formal theory of how computation works. As a mathematician and physicist, Norm thoroughly appreciated this, particularly as it has been expressed in the lambda calculus and the pi calculus. Norm’s contribution was simpler and in some ways more important. He brought the notion of meaning to the practice of computation, and he taught that to several generations of students.

However things turn out, I’m pretty sure Norm will take delight in whatever undiscovered country he encounters.