Interview with Ken thompson

Unix and Beyond: An

Interview with Ken

Thompson

Daniel Cooke

Texas Tech University

Joseph Urban

Arizona State University

Scott Hamilton

Computer

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,"].

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.