Unix and Beyond: An Interview with Ken Thompson

Daniel Cooke
Texas Tech University

Joseph Urban
Arizona State University

Scott Hamilton
Computer

Computer

May 1999

Computer recently visited Ken Thompson at Lucent's Bell Labs to learn about Thompson's early work on Unix and his more recent work in distributed computing.

Ken Thompson needs no introduction: the co-creator of the Unix operating system as well as the Plan 9 and Inferno distributed operating systems; creator, along with Joseph Condon, of Belle, a world champion chess computer; 1998 US National Medal of Technology winner, along with Dennis Ritchie, for their role in developing the Unix system and C.

On the occasion of the presentation of the Computer Society's and Hitachi's inaugural Tsutomu Kanai Award for distributed computing, Computer visited recipient Ken Thompson at Lucent's Bell Labs. We were interested in learning about Thompson's early work on Unix and his more recent work in distributed computing. We were especially interested in learning about the creative process within Bell Labs and his sense of where computer science was heading.

CREATIVITY AND SOFTWARE DEVELOPMENT

Computer. Your nominators and endorsers for the Kanai Award consistently characterized your work as simple yet powerful. How do you discover such powerful abstractions?

Thompson. It is the way I think. I am a very bottom-up thinker. If you give me the right kind of Tinker Toys, I can imagine the building. I can sit there and see primitives and recognize their power to build structures a half mile high, if only I had just one more to make it functionally complete. I can see those kinds of things.

The converse is true, too, I think. I can't from the building imagine the Tinker Toys. When I see a top-down description of a system or language that has infinite libraries described by layers and layers, all I just see is a morass. I can't get a feel for it. I can't understand how the pieces fit; I can't understand something presented to me that's very complex. Maybe I do what I do because if I built anything more complicated, I couldn't understand it. I really must break it down into little pieces.

Computer. In your group you probably have both the bottom-up thinker and the top-down thinker. How do you interact with both?

Thompson. I think there's room for both, but it makes for some interesting conversations, where two people think they are talking to each other but they're not. They just miss, like two ships in the night, except that they are using words, and the words mean different things to both sides. I don't know how to answer that really. It takes both; it takes all kinds.

Occasionally—maybe once every five years—I will read a paper and I'll say, "Boy, this person just doesn't think like normal people. This person thinks at an orthogonal angle." When I see people like that, my impulse is to try to meet them, read their work, hire them. It's always good to take an orthogonal view of something. It develops ideas.

I think that computer science in its middle age has become incestuous: people are trained by people who think one way. As a result, these so-called orthogonal thinkers are becoming rarer and rarer. Of course, many of their ideas have become mainstream–like message passing, which I thought was something interesting when I first saw it. But occasionally you still see some very strange stuff.

SOFTWARE DEVELPOMENT PARADIGMS

Computer. What makes Plan 9 and the Inferno network operating system very striking is the consistent and aggressive use of a small number of abstractions. It seems clear that there's a coherent vision and team assembled here working on these projects. Could you give us further insight into how the process works?

Thompson. The aggressive use of a small number of abstractions is, I think, the direct result of a very small number of people who interact closely during the implementation. It's not a committee where everyone is trying to introduce their favorite thing. Essentially, if you have a technical argument or question, you have to sway two or three other people who are very savvy. They know what is going on, and you can't put anything over on them.

As for the process, it's hard to describe. It's chaotic, but somehow something comes out of it. There is a structure that comes out of it. I am a member of the Computing Sciences Research Center, which consists of a bunch of individuals—no teams, no leaders. It's the old Bell Labs model of research; these people just interact every day.

At different times you have nothing to do. You've stopped working for some reason—you finished a project or got tired of it—and you sit around and look for something to do. You latch on to somebody else, almost like water molecules interacting.

You get together and say, "I have an idea for a language," and somebody gets interested. Somebody else asks how we put networking in it. Well, so-and-so has a model for networking, and somebody else comes in. So you have these teams that rarely get above five or six, and usually hover around two or three. They each bring in whatever they did previously.

So that's the way it works. There are no projects per se in the Computing Sciences Research Center. There are projects near it of various sorts that will draw on our research as a resource. But they have to deal with our style. If people get stuck, they come to us but usually don't want to deal with the management style—which means none—that comes along with it.

Computer. You mentioned technical arguments and how you build your case. How are technical arguments resolved?

Thompson. When you know something is systemically wrong despite all the parts being correct, you say there has to be something better. You argue back and forth. You may sway or not sway, but mostly what you do is come up with an alternative. Try it. Many of the arguments end up that way.

You say, "I am right, the hell with you." And, of course the person who has been "to helled with" wants to prove his point, and so he goes off and does it. That's ultimately the way you prove a point. So that is the way most of the arguments are done—simply by trying them.

I don't think there are many people up in research who have strong ideas about things that they haven't really had experience with. They won't argue about the theory of something that's never been done. Instead, they'll say, "Let's try this." Also, there's not that much ego up there either, so if it's a failure you come back and say, "Do you have another idea? That one didn't work." I have certainly generated as many bad ideas as I have good ones.

Computer. What advice do you have for developers who are out there now to improve their designs so that they could be viewed as producing simple yet powerful systems?

Thompson. That is very hard; that is a very difficult question. There are very few people in my position who can really do a design and implement it. Most people are a smaller peg in a big organization where the design is done, or they do the design but can't implement it, or they don't understand the entire system. They are just part of a design team. There are very few people I could give advice to.

It's hard to give advice in a product kind of world when what I do, I guess, is some form of computer Darwinism: Try it, and if it doesn't work throw it out and do it again. You just can't do that in a product-development environment.

Plus I am not sure there are real principles involved as opposed to serendipity: You happened to require this as a function before someone else saw the need for it. The way you happen upon what you think about is just very lucky. My advice to you is just be lucky. Go out there and buy low and sell high, and everything will be fine.

UNIX

Computer. In an earlier interview you were asked what you might do differently if you had to do Unix over again, and you said that you would add an "e" to the creat system call. Seriously, in hindsight, can you give us an assessment of the problems you overcame, the elegant solutions, and the things you would have done differently.

Thompson. I think the major good idea in Unix was its clean and simple interface: open, close, read, and write. This enabled the implementation of the shell as well as Unix's portability. In earlier systems, I/O had different entry points, but with Unix you could abstract them away: You open a file, and if the file happens to be a tape, you could write to it. Pipes allowed tools and filters that could accommodate classical monster programs like sort.

Probably the glaring error in Unix was that it underevaluated the concept of remoteness. The open-close-read-write interface should have been encapsulated together as something for remoteness; something that brought a group of interfaces together as a single thing—a remote file system as opposed to a local file system.

Unix lacked that concept; there was just one group of open-close-read-write interfaces. It was a glaring omission and was the reason that some of the awful things came into Unix like ptrace and some of the system calls. Every time I looked at later versions of Unix there were 15 new system calls, which tells you something's wrong. I just didn't see it at the time. This was fixed in a fairly nice way in Plan 9.

Computer. Going back a little bit further, what were the good and not so good aspects of Multics that were the major drivers in the Unix design rationale?

Thompson. The one thing I stole was the hierarchical file system because it was a really good idea—the difference being that Multics was a virtual memory system and these "files" weren't files but naming conventions for segments. After you walk one of these hierarchical name spaces, which were tacked onto the side and weren't really part of the system, you touch it and it would be part of your address space and then you use machine instructions to store the data in that segment. I just plain lifted this.

By the same token, Multics was a virtual memory system with page faults, and it didn't differentiate between data and programs. You'd jump to a segment as it was faulted in, whether it was faulted in as data or instructions. There were no files to read or write—nothing you could remote—which I thought was a bad idea. This huge virtual memory space was the unifying concept behind Multics—and it had to be tried in an era when everyone was looking for the grand unification theory of programming—but I thought it was a big mistake.

I wanted to separate data from programs, because data and instructions are very different. When you're reading a file, you're almost always certain that the data will be read sequentially, and you're not surprised when you fault a and read a + 1. Moreover, it's much harder to excise instructions from caches than to excise data. So I added the exec system call that says "invoke this thing as a program," whereas in Multics you would fault in an instruction and jump to it.

DEVELOPMENT HISTORY

Computer. What about the development history of Unix?

Thompson. The early versions were essentially me experimenting with some Multics concepts on a PDP-7 after that project disbanded, which is about as small a team as you can imagine. I then picked up a couple of users, Doug McIlroy and Dennis Ritchie, who were interested in languages. Their criticism, which was very expert and very harsh, led to a couple of rewrites in PDP-7 assembly.

At one point, I took BCPL from Martin Richards at MIT and converted it into what I thought was a fairly straight translation, but it turned out to be a different language so I called it B, and then Dennis took it and added types and called it C.

We bought a PDP–11—one of the very first—and I rewrote Unix in PDP-11 assembly and got it running. That was exported to several internal Bell telephone applications, to gather trouble reports and monitor various things like rerouted cables. Those applications, independent of what we were doing, started a political pressure to get support for the operating system; they demanded service. So Bell Labs started the Unix Support Group, whose purpose was to serve as the interface to us, to take our modifications and interface them with the applications in the field, which demanded a more stable environment. They didn't like surprises. This grew over time into the commercial version from AT&T and the more autonomous version from USL.

Independently, we went on and tried to rewrite Unix in this higher-level language that was evolving simultaneously. It's hard to say who was pushing whom—whether Unix was pushing C or C was pushing Unix. These rewrites failed twice in the space of six months, I believe, because of problems with the language. There would be a major change in the language and we'd rewrite Unix.

The third rewrite—I took the OS proper, the kernel, and Dennis took the block I/O, the disk—was successful; it turned into version 5 in the labs and version 6 that got out to universities. Then there was a version 7 that I rewrote for Johnson and Ritchie to port to an Interdata 832; I rewrote the OS with almost all its language intact but reapportioned the portable and nonportable parts so that the next port would be better.

Around version 6, ARPA [Advanced Research Projects Agency] adopted it as a standard language for the Arpanet community. Berkeley was contracted to fix the Arpanet interface—which started at the University of Illinois and was extended by Berkeley's getHostbyName interface—and to add virtual memory to Bell Labs' port to the VAX.

There's a nice history of Unix written by Dennis that's available on his home page [ed.—"The Evolution of the Unix Time-Sharing System," [ http://cm.bell-labs.com/cm/cs/who/dmr/hist.html ]].

Computer: What accounted for the success of Unix ultimately?

Thompson: I mostly view it as serendipitous. It was a massive change in the way people used computers, from mainframes to minis; we crossed a monetary threshold where computers became cheaper. People used them in smaller groups, and it was the beginning of the demise of the monster comp center, where the bureaucracy hidden behind the guise of a multimillion dollar machine would dictate the way computing ran. People rejected the idea of accepting the OS from the manufacturer and these machines would never talk to anything but the manufacturer's machine.

I view the fact that we were caught up in that—where we were glommed onto as the only solution to maintaining open computing—as the main driving force for the revolution in the way computers were used at the time.

There were other smaller things. Unix was a very small, understandable OS, so people could change it at their will. It would run itself—you could type "go" and in a few minutes it would recompile itself. You had total control over the whole system. So it was very beneficial to a lot of people, especially at universities, because it was very hard to teach computing from an IBM end-user point of view. Unix was small, and you could go through it line by line and understand exactly how it worked. That was the origin of the so-called Unix culture.

Computer: In a sense, Linux is following in this tradition. Any thoughts on this phenomenon?

Thompson: I view Linux as something that's not Microsoft—a backlash against Microsoft, no more and no less. I don't think it will be very successful in the long run. I've looked at the source and there are pieces that are good and pieces that are not. A whole bunch of random people have contributed to this source, and the quality varies drastically.

My experience and some of my friends' experience is that Linux is quite unreliable. Microsoft is really unreliable but Linux is worse. In a non-PC environment, it just won't hold up. If you're using it on a single box, that's one thing. But if you want to use Linux in firewalls, gateways, embedded systems, and so on, it has a long way to go.

DISTRIBUTED COMPUTING: NETWORK OPERATING SYSTEMS AND LANGUAGES

Computer: How does your work on Plan 9 and Inferno derive from your earlier work on Unix? What are some of the new ideas arising out of this work that could and should apply to distributed operating systems in general?

Thompson: Saying these ideas haven't been applied before is tough because, if you look closely, everything is reinvented, nothing's new. There are good ideas and bad ideas in Unix. You can't escape your history. What you think today is not much different from what you thought yesterday. And, by induction, it is not that different from what you thought twenty years ago.

In Plan 9 and Inferno, the key ideas are the protocol for communicating between components and the simplification and extension of particular concepts. In Plan 9, the key abstraction is the file system—anything you can read and write and select by names in a hierarchy—and the protocol exports that abstraction to remote channels to enable distribution. Inferno works similarly, but it has a layer of language interaction above it through the Limbo language interface—which is like Java, but cleaner I think.

LIMBO

Computer: How would you characterize Limbo as a language?

Thompson: First, I have to say that the language itself is almost exclusively the work of Sean Dorward, and in my talking about it I don't want to imply I had much to do with it.

I think it's a good language. In a pragmatic sense, it's a simplification of the larger languages like C++ and Java. The inheritance rules are much simpler, it's easier to use, and the restrictions there for simplicity don't seem to impair its functionality.

In C++ and Java I experience a certain amount of angst when you ask how to do this and they say, "Well, you do it like this or you could do it like that." There are obviously too many features if you can do something that many ways—and they are more or less equivalent. I think there are smaller concepts that fit better in Inferno.

Computer: We know that Plan 9 was done in C. It would almost seem that the group needed Limbo to develop Inferno. Do we need new types of languages to build distributed systems?

Thompson: The language, I think, doesn't matter per se. The language's actual size and features are almost separate issues from the distribution of the language. It shouldn't be too large or too small; it should be some nice language that you can live with. The idea, though, is that it is dynamically loadable so that you can replace little modules. And through some other mechanisms like encryption you can validate those modules, and when they are loaded you have some confidence that it's the module you wanted and that someone hasn't spoofed you.

There are certain features you must have—some form of object–orientation, for example. You could replace Limbo with Java—I wouldn't want to—and not change Inferno's basic principles other than the way it meets system requirements. Sean decided the whole system had to have a garbage-collected language at a much higher level in that it's not separate interacting processes maintaining their own addresses, with some being garbage-collected and some not.

The language and the system are all garbage-collected together. Whatever protection mechanisms you have for the language apply all the way down through the system. For example, if you open a file, you don't have to close it. If you stop using it, just return from the function and it will be garbage-collected and the file will be closed. So the system and the language are part of the same ball of wax.

In addition, the language implementation—and again I don't want to take any credit—doesn't have big mark–and–sweep type garbage collection. It has reference counting: If you open something and then return, it's gone by reference count. Thus, you don't have high and low watermarks because 99 percent of the garbage goes away as soon as it is dereferenced. If you store a null in a pointer, it chases the pointer and all that stuff goes.

If you make cycles, there is a background distributed mark-and-sweep algorithm that just colors the next step a little bit at a time. It doesn't have to be very aggressive because there is not much garbage around in most applications: People really don't leave dangling loop structures that require this kind of algorithm. So you can devote just one percent of your time in the background looking for garbage without these monster mark-and-sweep things.

So, again, it's pragmatic. It's not the theoretical top-of-the-line garbage collection paper. It's just a way of doing it that seems to be very, very effective.

CURRENT WORK

Computer: What are you working on now?

Thompson: A few of us in research were tapped by a newly formed development organization within Lucent to work on a product called the PathStar Access Server. It's essentially a central office switch and router for IP phone and data services. It's strictly IP-based. You pick up the phone, dial it, and make conference calls.

I think packet switching will replace circuit switching in the phone system and will invert the hierarchy. Whereas data is currently carried in the leftover space of a circuit-switched network, eventually the backbone will be a packet-switched network with the phone implemented under it. You don't have to go out on a limb to say this—probably 90 percent of the people believe that now. But this project is "put up or shut up." We are actually inverting the phone system to run across a pretty classical packet-switched router.

In this kind of application what you need to pay attention to is maintenance and configuration, which is where Inferno comes in. All of the configuration code is Inferno and Limbo. You have to pay attention to quality of service so that you can raise the loading above minimal and still get real-time voice, in this particular case.

There were some fun parts: The actual call processing, which is typically done by a huge finite state machine, was fun to do. We did it by making a finite-state-machine-generation language. The object of the language is a finite state machine, but the source is not. The actual phone conversation or feature is a group interacting finite state machines, almost like processes. And, of course, they have to be distributed because you make calls to other phones.

Computer: So this language generates the finite state machines. Did you create the language to allow for experimentation to come up with different finite state machines?

Thompson: Well, at first we thought it was simple: You just write a finite state machine for this phone system. And at first it was simple. You just say, "Well if you're here do this, and if you're there do that, and just manually lay out these finite state machines." And that works just beautifully for the very first implementation, which is just picking up a phone, dialing a number, calling another phone, picking that phone up, conversing, and hanging up. You can just picture those states laying out.

But when you get to some of the simple features—three–way calls, for example—what happens when caller ID or call waiting comes in on a three-way call? The classical phone just says busy because it can't handle more than three phones.

So you build a model, which was initially a finite state machine model, and then you slowly add the features you need until the model breaks. It breaks pretty quickly, so you build a second one until it breaks, and so on. You just do it by exhaustion. So that's how the FSM-generation language came about; it wasn't "let's sit down and do everything at once." I think that's probably the way computer languages were built.

Interestingly, this work was extended further by Gerard Holzmann, someone in our area who has been into state verification—running exhaustive studies finding error states in the finite state system. He was just delighted with this little FSM-generation language because now he could build his models, and he inverted it. He took it the way it is, which is to build finite state machines, but he also took it to build drivers. So he has my model, which runs the phones on the inside, but then he needed telephones to drive his model. So he can now build another finite state machine to model the telephone and do not only the synthesis but the analysis.

JUKEBOX MUSIC COLLECTION

Computer: You're also collecting music?

Thompson: It's kind of a personal/research hobby/project. Let me explain it from an external point of view. Basically, I'm just collecting music. I'm getting lists from various sources—top 10s, top 50s—and I try to collect the music.

Right now, my list has around 35,000 songs, of which I've collected around 20,000. I compress the songs with a Bell Labs-invented algorithm called PAC [Perceptual Audio Coding] and store them on a jukebox storage system. I started this before MP3 was heard of on the network. PAC is vastly superior to MP3.

My collection is not generally available because of the legal aspects. I went to legal and told them I was collecting a lot of music, but I don't think they realized what I meant by "a lot." Anyway, they said that in the case of research there's something similar to fair use and that they'd back me, but wouldn't go to jail for me. So I can't release it generally. But it's pretty impressive. It's split-screen like a Web browser; you can walk down lists, years, or weeks.

Computer: It's a personal hobby.

Thompson: It's hard to differentiate since, if you haven't noticed, almost everything I've done is personal interest. Almost everything I've done has been supported and I'm allowed to do it, but it's always been on the edge of what's acceptable for computer science at the time. Even Unix was right on the edge of what was acceptable at Bell Labs at the time. That's almost been my history.

COMPUTER SCIENCE AND THE FUTURE

Computer: You've been there through Multics, Unix, Inferno, and so on. Any thoughts about where computer science is going or should be going?

Thompson: Well, I had to give advice to my son, and my advice to him—to the next generation—was to get into biology. When I was a kid, I was interested in electronics. I got into computing—not being interested in it per se because it almost didn't exist then—because it's addictive. I think electronics had this cycle: It would do everything—negative feedback and stuff like that—whereas now it's just commodity and grind them out.

Computer science is coming into its middle age. It's turning into a commodity. People don't know about Carnot cycles for refrigerators, yet they buy refrigerators. It's happening in computing too. Who knows about compilers? They buy computers to play games and balance their checkbooks. So my advice to my child was—I am unfortunately talking to Computer magazine—to go into biology, not classic biology but gene therapy and things like that.

I think that computing is a finite field and it's reaching its apex and we will be on a wane after this. I am sorry to say that, but that's the way I feel. You look at any aspect of computer science—what's being taught today, PhD theses, publications, any metric you can think of and compare it to history—and you realize that aspects of computer science are becoming more specialized.

Computer: Which aspects?

Thompson: Operating systems, in particular, have to carry so much baggage. Today, if you're going to do something that will have any impact, you have to compete with Microsoft, and to do that you have to carry the weight of all the browsers, Word, Office, and everything else. Even if you write a better operating system, nobody who actually uses computers today knows what an operating system interface is; their interface is the browser or Office.

You can have the best and most beautiful interface in the world and the most extensible operating system that ports to anything and then you have to port on top of it a thousand staff-years worth of applications that you can't obtain the source for. You have two choices: Go to Microsoft and ask for the source to Office to port to your operating system and they'll laugh at you; or get a user's manual and re-engineer the code and they'll sue you anyway. Basically, it'll never happen because the entry fee is too high.

Anything new will have to come along with the type of revolution that came along with Unix. Nothing was going to topple IBM until something came along that made them irrelevant. I'm sure they have the mainframe market locked up, but that's just irrelevant. And the same thing with Microsoft: Until something comes along that makes them irrelevant, the entry fee is too difficult and they won't be displaced.

Computer: So you're not precluding the possibility of a paradigm shift.

Thompson: Absolutely not. Anybody who says there's no more innovation in the world is doomed to be among the last 400 people who have stated this since the birth of Christ.

Computer: You're still having fun?

Thompson: Yes, there are still a lot of fun programs to write.

WHAT I DID ON MY WINTER VACATION

Computer: We can't let you go without asking why on earth you traveled to Russia to fly a Mig-29?

Thompson: How often does the Soviet Union collapse? It would be just a shame if you couldn't do something you have always wanted to do as a result. They are selling rides in what was once the top fighter. A mere two years earlier you would only get hints about its existence in Jane's books. Now you can get in, use the laser sights, and go straight up at 600 miles per hour. Who wouldn't do that? When things like that come along, I'll take them. They're fun.

Contact the authors at d.cooke@computer.org, j.urban@computer.org, s.hamilton@computer.org.

Copyright 1999