Interview with Brian Kernighan
MSM: Since we were talking about translations,
and since you have watched this book be translated, I suspect
you're one of the people that translators come back to when C
goes into another setting-let's say into another language. It
struck me, the more I converse with people-I want to get to this-that
Unix is as much an ethos as it is a programming system. It's
a way of thinking about computing. Have people had trouble with
that aspect of the translation of Unix? What has been the response
when people have tried to adopt Unix into other environments?
Kernighan: I hate to give a non-answer
to the question, but, in fact, I have had relatively little feedback
from any of the translators, with about three exceptions, I think.
The guy who has translated several books into German really does
program for a living. He writes; although he's a professor in
the university, he seems to enjoy writing really grimy books on
how to do things, and so he and I have technical arguments about
things at one time or another. I don't think he has any trouble
translating from English into German, or vice versa. He does
his own translation of German words into English. So, there's
a non-barrier there, if you like.
There are two people that I know, not as well,
who have done the translations into Japanese of different books.
The guy who's done them into-particularly the Unix book and a
C book, is-runs the computer center at the University of Tokyo.
Although he probably doesn't program on a day-to-day basis, I
think he genuinely understands what's going on. My guess is that
he doesn't have a heck of a lot of problems tanslating. Although
one Japanese lifestyle, culture, or whatever, is enough different
in some areas, that maybe it makes a difference. My bet is that
it doesn't make a heck of a lot of difference. I suspect the
computing aspects are pretty close to the same there, as they
MSM: Let's take the English-actually,
let me rephrase the question, because I had in mind more of an
aspect of the portability of C. You wrote the books, and I suspect-maybe
the premise is wrong-that people or institutions have tried to
go over to you to adopt Unix; that you're one of the people to
whom they come back and say, "I don't quite understand how
this works." The queries came to you, or have come to you.
Am I right on that premise? Have there been a sort of set of
difficulties people have encountered when they tried to go over
from one system into Unix? Has Unix proved difficult to port
as a way of doing things, as opposed to simply a piece of software?
Kernighan: I think in a way it has,
although memory grows dim. A lot of this stuff is something that
I don't think about much anymore. Fortunately, I'm not involved
in it as much. But I think there has always been a problem when
somebody new comes to the system. There's a set of shared, I
don't know, conventions; things that, because they work the same
throughout all the Unix operating system and its programs, tend
not to get written down. They're just like folklore; they're
customs. Like keeping to the right as you drive almost. Everybody
knows that kind of thing, and therefore, it tends not to be written
down as part of every single description. It's in one place
and then forgotten. People who come new to this system don't
know that that sort of particular behavior is pervasive, and therefore,
they are perhaps befuddled by it; they don't expect that it will
work. And you could see lots and lots of examples of it. Oh,
fairly narrow technical issues, but for example, the fact that
most programs read from a list of files, or there are no files
from the standard input. And I still remember seeing somebody
who had taken one of my programs-ratfor, the FORTRAN pre-processor-reproduced
the manual page, and had added a bug section which says that if
you just type ratfor nothing happens, not realizing that
if you type ratfor it's waiting to read the standard input.
Okay, so there's an example of somebody who just had missed totally
an important aspect.
An analogous one which is probably more
modern: If you look at DOS, MS-DOS, the notion of wildcard characters
for filename expansion, is part of DOS, but in a very strange
way. It's really not done by the command interpreter, COMMAND.COM
or whatever, the way it would be in Unix, by a shell. But, rather,
it's a service provided by individual programs, and that means
that its properties-some programs don't have it, its properties
might be somewhat different from one program to another, whereas
in Unix it's known that it's done by a single program, in a single
place, and therefore its properties are somewhat more uniform.
That notion that there's the right place to do things is something
that you maybe take for granted in Unix; it doesn't quite come
up the same in other systems. And so explaining that to people,
maybe is difficult.
Another area that I remember endlessly,
when we were doing in what I will best describe as popularizing
Unix, back in the mid and late '70's: People would come in and
they'd say, "Yeah, this is nice, but does the system do X?"
for some X, and the standard answer for all of this was, "No,
but it's easy to make it do it." Unix has, I think for many
years, had a reputation as being difficult to learn and incomplete.
Difficult to learn means that the set of shared conventions,
and things that are assumed about the way it works, and the basic
mechanisms, are just different from what they are in other systems.
Incomplete means, because it was meant as a program development
environment, it doesn't have all the finished products necessarily.
But, as a program development environment, it's very easy to build
a lot of these things. It's sort of like a kit. And if you want
a new thing, you can take the pieces out of the kit and assemble
them to make your new thing, rather more rapidly than you would
be able to do the same thing in some other kind of environment.
So, we used to say that. "Does it do X?" "No,
but it's real easy. Do you want one by tomorrow? I'll give you
one by tomorrow." Every once in awhile, someone would call
your bluff. (Laughing) Sometimes that was fun, and sometimes
MSM: In what you just described, you
used the term "kit," which could be expanded to "toolkit."
And existing notions of tools, and Unix as a set of tools, where
did that image come from? Doug credits you for it in the collection
of research manuals.
Kernighan: I honestly don't know where
it came from. It was in the air in several different ways. I
think maybe Plauger and I were the people who put a name on it,
and maybe some coherence, when we wrote this off our tools book,
and tried to take ideas out of Unix and put them somewhere else.
But I think the ideas had been kind of floating around anyway.
Doug, of course, had published these two papers, in the-I don't
even know where they were papers in, the Garmisch, and wherever
else software engineering conferences in the late '60s, '68 or
'69, that kind of time-where he was talking about things; not
quite tools, but components. If you're going build components,
you need tools, so that's part of it there. I have a vague notion
that Bob Morris was talking about those kinds of things too, because
I remember him giving us a fairly coherent talk at one of the
spring or fall joint computer conferences fairly early. Beyond
that, I don't know. I think that I started giving talks about
tools, and combining programs, and so on, fairly early. '73,
'74 more likely, that kind of time. And then Plauger and I started
to work on the software tools book. And it was, well, what are
we talking about? These are the tools you use when you write
programs. And that came out in early '76. So, presumably, we
were working on that in '74 and '75. I might conceivably take
credit for the name, but probably not the real intellectual idea
underneath it anyway.
MSM: Is this something you learned when you
Kernighan: I think probably yes. I
had spent the summer of 1966 working at MIT, in the group that
was the MIT component of the Multics effort. I spent a summer
there, working ostensibly for Corby, but practically for-I don't
even know for who, officially, but, you know-I was there and I
was working on something, and in fact, it was a tool that took
stuff from the CTSS machine, the 7090, and made a coherent tape
which you could then load on the 645, which had just arrived,
and actually run it as a sort of Multics-y kind of job, although
Multics didn't really do anything. I've forgotten, it was the
merge editor or something; it was basically just, take a bunch
of stuff from here and put it over there. So, I got used to both
CTSS as an environment and some of the noise that was in the air
about Multics, although I didn't actually have much to do with
the pure Multics side of it.
Then I came back and spent the summer
of '67 and '68 here at Murray Hill, first summer working for Doug,
and I built myself-typical summer job, I think-Doug suggested
an idea and I got sidetracked into the tools that were underneath
the idea, or might have been helpful in building the idea, and
I never went off and did anything. He wanted to investigate storage
allocation algorithms, and I started to build myself some list
processing stuff and never finished that. That was much more
fun than (laughing) trying to figure out the properties of storage
allocation algorithms. I think that beyond that, the notion of
tools, or languages, or anything like that, did not show up in
my consciousness until noticeably further on, probably when Unix
was actually running on the PD11, which would be '71, '72, that
kind of time. And even there not really.
MSM: Before or after Doug did pipes? Was pipes
a trigger for this notion?
Kernighan: I think it probably was the
capstone or whatever. I'm not sure what the right image is, but
it's the thing that makes it all work, in some sense. It's not
that you couldn't do those kind things, because I had already
written redirection; it predates pipes by a noticeable amount.
Not a tremendous amount, but it definitely predates it. That's
an oldish idea. That's enough to do most of the things that you
currently do with pipes; it's just not notationally anywhere near
so convenient. I mean, it's sort of loosely analogous to working
with Roman numerals instead of Arabic numerals. It's not that
you can't do arithmetic, it's just a bitch. Much more difficult,
perhaps, and therefore mentally not-more constraining. But all
that stuff is sort of now squashed into such a narrow interval
that I don't even know when it happened.
I remember the preposterous syntax,
that ">>" or whatever syntax, that somebody came
up with, and then all of sudden there was the vertical bar, and
just (snaps fingers) everything clicked at that point. That was
the time, then, I could start to make up these really neat examples
that would show things like doing, you know, running who,
and collecting the output in a file, and then word counting the
file to say how many users there were, and then saying, "Look
how much easier it is with the word count. With the who
into the word count, and running who into grep,"
and starting to show combinations that were things that were never
thought of, and yet they were so easy that you could just compose
them at the keyboard and get them right every time. That's, I
think, when we started to think, probably consciously, about tools,
because then you could compose the things together if you had
made them so that they actually worked together. And that's when
people went back and consciously put into programs the idea that
they read from a list of files, but if there were no files they
read from the standard input, so that they could be used in pipelines.
People went back and did that consciously in programs, like sort.
Sort-an example of a program that cannot work in a pipeline,
because all the input has to be read before any output comes out-it
doesn't matter, because you're going to use it in a pipeline,
right? And you don't care whether it piles up there briefly;
it's going come out the other end. It's that kind of thing, where
we say, "Hey, make them work together. Then they become
tools." Somewhere in there, with the pipes, and maybe somewhere
the development of grep-which Ken did, sort of overnight-the
quintessential tool, as I guess Doug refers to it. A thing which,
in a different environment probably you don't see it that way.
But, in the Unix environment you see it as the basic tool, in
MSM: There are several directions to go here.
One that this brings to mind is, do we take grep and yacc
and get awk?(not clear)
Kernighan: As a bit of an oversimplification,
yeah. I'm not sure that yacc is the right model. I think
in fact sed is the right model. That-because the patterns
are much simpler, and there's less of a sort of-there's a more
sequential structure to the processing in awk which is
much closer to match to way that sed works than to yacc.
Yacc has mystical properties; I mean, certainly it's patterns
and actions, but the patterns sort of spring into action, as it
were, out nowhere. Whereas, it's really obvious what's happening
in sed and in awk. So, I think that's a fairer
example, or a fairer path of evolution. It's much closer. Because,
I've been interested-having seen sed, I was kind of interested
in the notion of a programmable editor, because there were lots
of things people were doing that required text manipulation, and
we didn't have on Unix a programmable editor. We had this thing
called qed which came originally from Peter Deustch, I
guess, or somebody like that, at Berkeley-but Ken had made it
work on Multics and then I think Dennis made it work on the GE
machine that we used. It was a programmable editor, but it was
programmable in some formal sense. It was just awful, and yet
it was the only thing around that let you manipulate text in
a program without writing a hell of a lot of awkward code.
So I was interested in programmable editors, things that would
let you manipulate text with somewhat the same ease that you can
manipulate numbers. I think that that was part of my interest
The other thing is-that I remember as
a trigger for me-was a very, very specialized tool that a guy
named Mark Rochkind developed. He was in group that was doing,
you know, genuine telephone-related stuff, and he had a program
that would let you specify basically a sequence of regular expression
and message-regular expression and message-and then it would create
a program such that, if you pass data through this program, when
it's on instance of the regular expression, it would print the
message. And we'd use it for data validation. And I thought,
what a neat idea. It is a neat idea. It's a really elegant idea.
It's a program that creates a program that then goes off and
validates data, and you don't have to put all the baggage in;
some program creates the baggage for you. The only problem with
it was that it was specialized, this one tiny application. And
so my contribution to awk, if you like, is the notion that
you can generalize this. Technology of making regular expressions
work, to this day, remains (not clear) and many of the database,
and general feeling of data processing that you might get out
of (not clear) repeater, I think that holds much of the first-cut
implementation. I don't remember a lot of that stuff. Again,
it's pretty blurred now.
MSM: It's hard for you to remember just-I mean, how did the three of you get together?
Kernighan: Well, we got together in,
typically, in my office. We'd argue, and invent something in
real time, and that, (laughing) that has been with us ever since.
We'd throw stuff in. Peter is a very, very fast implementer.
He can build things much faster that I can or Al can; and so
we would get some idea and he would typically have it working
almost immediately. Then over the years, I would go back and
clean it up. Sometimes, we-he implemented things and we ultimately
threw them out and probably should have left them in. For example,
right at the earliest times he had a version of awk that
would generate C instead of being an interpreter. That was something
that didn't resurface again for almost ten years. He had in it
several different regular expression machines, one of which would
do one of these very, very fast regular expression searches, if
the set of things that you were looking for was just key words,
without metacharacters. The basic yacc-grep algorithm.
He had implemented that, that kind of stuff. Over the years,
I had tried three or four different internal mechanisms for the
interpreter machine. You try a stack machine and see how that
works, and you try quads or triples or something like that, and
see how that works. You try interpreting the parse tree and see
how that works; that's the one we stabilized on. So, I personally
have used awk, probably excessively, as a vehicle for experimenting
with various kinds of half-baked ideas, both in implementation
and also in language design.
MSM: Let me back up to the beginning.
You were up at MIT in '66.
MSM: And there working with Corbató
on moving from the 7090 to the 645. Conscious of Multics, but
not part of it?
Kernighan: In some sense, yeah. I don't
think I realized quite what it was all about. I mean, I had some
notion that this was interesting. I was using CTSS; that was
the first time that I had used a substantial time-sharing system.
I had played very, very briefly with Dartmouth BASIC, and you
know, it's kind of nice to have the computer talk to you. But
CTSS by comparison was very, very polished. You could really
do nice things with it, and in addition you were right center
of the universe of CTSS; all of the experts were there. It's
very like this is the center of Unix expertise. There it's the
center of the CTSS expertise, and so they could make it do wondrous
things which you would have never found if you weren't nearby.
So, I was interested in that aspect of it, and then there were
some interesting application programs as well. Like, ELIZA was
there; Joe Weizenbaum worked down the hall. Now, he was away,
I don't think I've ever met him.
But-so, you know, I'd meet an interesting girl,
I'd bring her in to talk to the doctor. (Laughing) But, it was
just an incredibly fun place to be. But, the Multics aspect of
it, I had relatively little to do with. What I was doing was
writing a program that ran on the CTSS side, and it created a
output that was usable by somebody else. But I didn't actually
care much about the output side of it. It was just a simple data
processing problem; let's just collect inputs in some sense or
other and put it together in a stylized sort of way. But, it
involved list processing, and it was written in MAD, which was
kind of a neat language. Much better than FORTRAN, which would
have been one of the other choices.
MSM: MAD's the Michigan-
Kernighan: Yeah. Right.
MSM: It was Bruce Arden's, wasn't it?
Kernighan: Yes. Arden, Galler, I don't
know who else. That group.
MSM: You came here in '67, '68. Were your
projects part of Multics projects?
Kernighan: No. When I came in '67, as
I mentioned earlier, Doug had this notion of working on figuring
out what were good storage allocation algorithms, for ML, basically,
that kind of thing; how do you provide quick access to storage
and then release it again. That remains a good problem, to this
day, and Doug continues to work on it to this day. But I didn't
get turned on to by it. But, what I did was to go off and say,
well, if you're going to provide storage allocation-let's say
in a FORTRAN program, which at the time FORTRAN was kind of the
universal language for most people-it would be nice if you could-I
had spent time at MIT working on list processing kinds of things.
There was a list processor called MAD Slip, which was basically
just a bunch of routines that you call from a MAD program that
let you do-you know, create a arbitrary size block of storage
and then link it to some other arbitrary block of storage and
so on-so you could do list processing in a conventional algorithmic
language. And that was kind of neat, and so what I did that summer
of '67 here, was sort of take Doug's vague idea of storage allocation
and go off and build myself a bunch of routines that would let
you, from a FORTRAN program, do list processing. You know, create
a block of storage this big, link blocks together, walk along
lists and stuff like that. And in a fit of absolutely misguided
craziness I spent much of the summer trying make it run absolutely
as fast as possible on this specific machine. So a lot of it
was assembly language programming. It was-except for a learning
experience, I think ultimately a total waste of time. But it
Then the second summer, I came back,
the summer of '68-I spent that summer working genuinely on my-on
stuff that would be related to a thesis. I worked with Shen Lin
on graph partitioning, which is just unrelated to any of the above.
I mean, it did require going out and writing substantial FORTRAN
programs and doing experimenting and so on, but it had nothing
to do with any of the sort of system-y stuff. It was pure combinatorial
experimentation. I did that, and then when I got back to Princeton
they, in their wisdom, said, "Your money is going to run
out in January. Maybe you better write a thesis." I said
Ah! (laughing) So, I wrote a thesis.
MSM: What did you write it on?
Kernighan: Graph partitioning.
MSM: Graph partitioning. I was going
to look it up, but I didn't get a chance to go to the library.
Kernighan: Anytime you want to hear
about graph partitioning, I will be glad to tell you what I know
about graph partitioning. It remains a standard problem. I think
it's an interesting problem, because it shows up in a variety
of guises in real life. In circuit design, which is one of the
reasons that people here were kind of interested in it, and it's
still part, a fundamental part, of a lot of circuit layout problems.
Because, basic idea is to take the components of a circuit and
cluster them-in some sense so that you don't have too many wires
running from here to way over there; rather, most of the wires
are short. But there are constraints on the of clusters,
because the things you are clustering together have to fit on
something, like a chip, or a substrate, or a circuit board, or
whatever. It's a plausible model. Quite a few real problems.
I actually worked on that off and on for probably the next four
or five years, when I got here, and other combinatorial problems
with Shen. But, I gradually drifted out of that stuff, after
two or three years.
MSM: When did you come here in '69?
Kernighan: Real early. February probably.
I graduated. I escaped from Princeton in January of '69.
MSM: It's the only way to describe getting
out of grad school.
Kernighan: Yes. (Laughing) You understand
completely. I really enjoyed Princeton as a graduate student.
It was in some sense the peak of income and the minimum of responsibilities,
and except for a horrific-probably eight to ten months, while
I anguished over what the hell am I going do to for a thesis,
I can't get out of here without a degree. Other than that, it
was idyllic, it really was. Just a lovely place to be.
MSM: Yeah. I kid, but I actually had
a good time as a grad student there. I was married at the time,
but when we'd come back from living in a one room apartment in
Germany, this Butler tract looked absolutely palatial. (laughing)
But, it was like the situation my third year. An NSF fund, and
I was teaching a couple of sections. I don't think I ever had
so much disposable income.
Kernighan: Yep. Exactly. (laughing)
MSM: The rent was forty eight dollars
Kernighan: Yeah. I remember.
MSM: What did you come here to do?
Were you hired into the computing research group?
Kernighan: Oh, yeah. The same group
that I'd been in all along. It's interesting, I had so much fun
here in '67 and '68-just, you know, the people. It was just such
a good collection of people, and I've enjoyed it. I never interviewed
anyplace else; I never even thought of any other place. I simply
said I'd like to work here. And Sam Morgan, in his wisdom, said,
"We don't want any Ph.D. dropouts, so you have to get your
degree finished. But, other than that, sure, we'd love to have
you." That was it, and I came early in '69 and the charter,
or my instructions, were-as they are for everyone else-non-existent.
Do what you want. The hope is that the combination of people
around you, doing things that are interesting-and perhaps ultimately
relevant, but not instantaneously relevant, I don't even know-but
the combination of people around you doing interesting things,
and getting their jollies, I think, from having their interesting
things affect other people, means that there's this sort of gentle
gravitational pull towards doing the same kind of thing yourself.
It's clear the reward mechanism ultimately favors those people
who have an impact on the local community, impact on the Bell
Labs community, impact on AT&T, impact on the scientific community,
in some combination.
MSM: So, it's a question of, "Do
what you want, but when we come to salary review, performance
review, come talk about what the impact of what you've done has
Kernighan: Impact is, I think, ultimately
the criterion, but there's quite a long view taken, and quite
a broad view of what impact is. So, somebody who does purely
theoretical work-but whose theoretical work affects the community
in some sense, either because other people take it and produce
artifacts, or because that person is able to shape a field, or
something like that-that's fine. That's good work. That has
impact. It doesn't mean that you can see it in a telephone or
anything like that; it means that it has had an effect, a positive
effect, on something of substance.
MSM: Now, when you arrived, one of the
things going here was Multics. Were you that involved in it?
Kernighan: Yeah. I was conscious yes,
involved no. I remember watching Ken and Dennis and a couple of
others stroking this giant this giant machine that sat probably
just around the corner here, or maybe it was one floor down, and
sort of being intrigued, but from a distance. I never actually,
I think, ran on it or did anything on it. At the time I came,
it must have been within a few months of disappearing. I don't
remember specifically. But, for all I know, it disappeared between
one summer and when I came permanently. I don't know the date
of that. But I never had anything to do with that. At the time,
I was doing this combinatorial stuff with Shen Lin. When I first
came, I continued to work on graph partitioning and, you know,
I also got interested in the traveling salesman problem again.
He'd been interested for a long time, and I got sucked into that.
We were writing FORTRAN code for that, and I don't think there
was a FORTRAN compiler on the Multics machine. So, we ran it
on the standard GE machine, where there was a perfectly fine
FORTRAN compiler and, you know, operators and all the other things
that you needed to get the job done. So, for the first couple
of years that I was here I spent essentially all my time doing
combinatorial kinds of things and running right just vanilla FORTRAN
MSM: So, that's why The Elements of Programming Style is basically about FORTRAN programming?
Kernighan: Well, that's not why it was.
It's because FORTRAN was the dominant language, and-it really
was the dominant language of scientific computation, and the only
other language that you could pick on that had any overlap with
it, really, was PL/1, because it had this sort of side of it that
was used for scientific computation, and there was a hope that
PL/1 would replace FORTRAN for scientific computation, which of
course never came about.
MSM: Were you around when Multics was canceled?
Kernighan: I guess so, yeah, as I said.
MSM: Do you get any memories of that?
Kernighan: I really don't. I just don't know-
MSM: Sense of mood or-
Kernighan: I just don't remember. It's
completely gone. You know, I-my guess is that the people who
were involved were probably somewhat disappointed, maybe bitterly
disappointed. If nothing else, they had invested a lot of time
in it. On the other hand, I think the handwriting must have been
extremely clear on the wall for quite some while, that this thing
was not living up to its promises. The promises made had been
totally unrealistic, but it just wasn't living up to anything.
MSM: When did you find out what Thompson and
Ritchie were up to?
Kernighan: I don't know. I remember
long discussions right across the hall there--which I think at
the time that may have been Rudd Canaday's office, I don't remember
now-when they would sit and draw pictures on the blackboard, file
systems, different kinds of pictures and talk about it. I wasn't
paying very much attention to that. I remember some distant-well,
I certainly remember the PDP-7 and 9, because of the great graphics
display, and you could play Space War on it. It was the best
Space War, and still one of the best video games ever invented.
But then Ken started to do serious computation, this Unix-related
stuff on it, and at some point he put together a system. I think
it was Doug who probably first pointed out that this was actually
a useful thing, that you could do interesting work on it, but
I still didn't actually do anything with it, certainly not while
I was on the PDP-7. And I did not-I think that I, in some ways,
got involved only peripherally through the B interpreter, which-B
was the language that they had used to experiment in one way or
another. Steve Johnson made a version of the B interpreter that
ran on the Honeywell machine. I started to play around with that,
and got interested, and wrote with Steve a sort of introduction
to B for people, so that people could write B, presumably on the
PDP-whatever-at that point I don't remember whether it moved to
11 or not-but also on the Honeywell. So, I wrote this little
tutorial on B, and I wrote a couple of B programs, and I found
it, you know, easier. It was like going back into MAD from FORTRAN.
It was just easier, because a lot of-it was easier to manipulate
characters, textual kinds of things, you didn't have to worry
about goddamn labels and continue statements and so on. I mean
I still use goto's, but it was just cleaner. You didn't
have to worry about card boundaries, all that kind of nonsense.
It was just nicer. In some sense, maybe that's how I got into
it, through the language side. Then, at some point, the PDP-11
came along. There was an actual useful machine there, and
I literally don't know what I-how I got in, or what I did first.
I must have been pretty early in the game, because I have a single-digit
user ID, as do Ken, Dennis, and Doug.
MSM: Low serial number?
Kernighan: Low serial number. (Laughing)
Mine is 9. It's the last of them. But, there's got to be some
cachet in having a single-digit user ID on the lineal descendant
of the original Unix machine.
Kernighan: Ossanna, I don't know, was
4, maybe, and Robert Morris was 5, and that was it. I mean, Ken
was 6, Doug was 7, Dennis was 8, or something. You know, that
kind of thing. So, I was 9. So, I must have been in, in some
way, fairly early, and I don't know how I achieved that.
MSM: You don't remember what you were doing,
what got you on?
Kernighan: I don't. I really don't.
It may have been that I said, "Gee, I'd like a login or
some way to use this machine," and maybe never did anything
with it. That I don't remember.
MSM: What were you working on at that time?
Kernighan: Probably, still these combinatorial
kinds of things, because Shen and I worked on graph partitioning
and traveling salesmen, and I worked on a variety of circuit-related
things, circuit design related things, with a guy named Dan Shweichert,
that were also combinatorial, and so on, in that period of time.
Those were predominantly FORTRAN programs running on the GE machine,
because that was the general-purpose computing environment.
MSM: What was your first major project
on Unix, and when did it start to become part of your research
Kernighan: The first substantial thing
I can remember was eqn, which Lorinda and I did, and that,
I would guess, was '73 or early '74. The initial development
was very, very short, but you could probably date it almost exactly.
It was written in C, so there had to be a working C compiler,
which was presumably put in in '72 or '73. There had to be
a working yacc, because, you used the yacc grammar.
It was done-in fact, I could find out from this-there was a graduate
student named Wayne Hunt who had worked on a system for doing
mathematics, but had a very different notion of what it should
be. It basically looked like function calls. And so, although
it might have worked, he a) didn't finish it, I think, and b)
the model probably wasn't right. I remember, he and Lorinda had
worked on it, or she had been guiding him, or something like that.
I looked at and I thought, "Gee, that seems wrong, there's
got to be a better way to say it." I mean, then suddenly
I drifted into this notion of, do it the way you say it. I don't
know where that came from, although I can speculate. I had spent
a fair length of time, maybe a couple of years, when I was a graduate
student at Recording for the Blind at Princeton. I read stuff
like computing reviews and scattered textbooks of one sort or
another, so I was used to at least speaking mathematics out loud.
Conceivably, that trigged some kind of neurons. I don't know.
MSM: EQN was the-
Kernighan: That certainly was the first
substantive thing that I did that ran on Unix; was purely, specifically,
only a Unix program.
MSM: Was that the point at which Unix
was being developed on the grounds, on the basis, of being a text
Kernighan: It must have been well into that,
because at that point troff existed, we had typesetter-because
this stuff wouldn't be interesting if you didn't have a typesetter-so
we had a typesetter, and Ossanna had a working version of troff.
So, all of us had had this interest in text formatting for a
long time. When I was at Princeton, I wrote a program to format
my thesis, because I couldn't stand the idea of paying somebody
a couple of dollars a page to type the stuff, because I knew I
was going to do it over and over again. I hated just writing
stuff out by hand, and I couldn't use a typewriter very effectively;
it was just too tedious. So, I wrote a text formatter at Princeton,
which was sufficiently successful that, for a decade later, there
was a student roff agency.
MSM: I don't remember the student roff
agency, but I do remember, back in the mid '70s, when I first
became conscious there was a course on computers and society that
was being taught by a guest brought in from Rutgers because no
one at Princeton wanted to teach the course. It has since disappeared
as a course; I keep threatening to bring it back. It would actually
be a good course; I'd have no trouble getting 1500 students in
for a course like that. But, I remember that the students were
asked to roff their text. I remember about that time,
one of my students, the first of my graduate students in the history
of science, discovered script. He started using green bar paper,
and then never did write a proper thesis, because he thought editing
meant going in and responding to my margin area on the line, and
that's not what I had in mind.
Kernighan: So, I was interested in formatting.
I'd done this formatter, Joe Ossanna had done a formatter. I
think it was either-it may have Ken, it was probably Ken, but
it might have been Dennis-that had done a little formatter that
ran on Unix, and that was the genesis of the patent department
stuff. But, Ossanna took it over, I think, and made it big.
I may be making that up, you'd better check with some of the protagonists.
Doug was interested in formatting, and had built quite a sophisticated
one for the Honeywell or GE machine-somewhere in there, it became
Honeywell. So, there were a lot of us who had our hands in on
formatters, and it was one of those topics that everybody was
intrigued by. But, the eqn thing was the first-something
that sat on top of, or in front of, a formatter to genuinely broaden
what you could do with them. That was the first thing.
MSM: One of the things that I find quite interesting
there, is-I can understand people's being interested in formatters,
because you get the idea that you're going to have a system that
you can type onto, and using a teletype to do it. You say, "Look,
this is a typewriter, if I can get stuff into it, I ought to
be able to be able to get stuff out of it, and I ought to be able
to get it out in any form. Why not use this as a way of editing?
Why not stop this silliness of having to count lines and footnotes
as I encounter them, and keep a record of them off to the side?"
and so on, and so forth. But, eqn and tbl and the
others go beyond formatting, to typesetting. It's going to get
you into the printer's art. I think of Don Knuth, who was in
the midst of writing this marvelous bible of programmers, and
then, all of a sudden, off he goes and gets into a decade of close
studying of the formation of letters. He still hasn't gotten
back to Volume 4. There seems to be an allure. (laughing) What
Kernighan: Well, I will say for Knuth,
I think it's in a large part, a waste of great mind for him to
spend a decade on TeX. It's not that TeX is bad, but it's a waste
of Knuth. I mean, he's capable of much more. I think I understand
it. It's seductive because-first the output is actually appealing.
I mean, you can actually see its utility, and you get a chance
to change something and see how it improves it. So, it's really
appealing in that sense. The input/output relationship is really
quite intriguing. The other thing is that-I think that in some
sense, the problem area is a microcosm of everything you ever
wanted to do with computers. It really has all of the interesting
problems, but they're there on a somewhat smaller scale, so that
one person can encompass it. It's relatively self-contained,
and if you do anything useful, people are just really enthusiastic;
they love to have it.
MSM: Were you learning things, as you
were setting up this text processing system, about computing?
Kernighan: Yeah. You learn-
MSM: Or were you just saying that that had theoretical interest?
Kernighan: Well, yeah, theoretical is
not the right word. But, it genuinely had computering science
kind of interest, because what you're doing is, you're building
compilers, right? But you're building small compilers. You're
building them for relatively simple languages, which means that
you don't have to face, in your language, all of the problems
that may get difficult to build a compiler for a real, conventional
mainstream language. For example, a compiler for eqn is
several orders of magnitude smaller than the compiler for something
like C, or FORTRAN, or something like that. So, the job is intrinsically
simpler; there are a lot more things that you don't have to worry
about. Yet at the same time, retains most of the interest. I
think maybe that's part of it. Then the other thing is that it's
kind of like many other things in computing; you get to go off
and invent your own rules for the game. Especially if you're
building languages, which is a lot of what I've done over the
years. If you're building a new language for something, well,
you can invent the rules. It's not like-if you want to go out
and build yourself a new C compiler, you can't invent the rules.
They're already defined for you. I think that's boring. So,
but if somebody says "We need a new language to make it
easy to talk about, you know, the way that medieval manuscripts
have been illuminated," or something or like that. Well,
gee, define your own rules, because nobody else has done it before.
That, I think, is part of the charm as well. Before you set out
to play the game, you get to define the rules, and if you don't
like the way the game turns out, then you change the rules. That's
always been part of the charm in computing, I think, building
something out of nothing.
MSM: That's a mathematician's approach.
Kernighan: Well, in some sense, yeah.
But it's different from at least pure mathematicians; there is,
in addition, the reward of utility if you do it well. People
come along and say, "Hey, look what I did." Maybe mathematicians
don't get any jollies when somebody says, "Oh, I used your
theorem." But I think people who write programs do get a
kick out of it when somebody comes along and says, "Hey,
I used your program." I know I do.
MSM: I think mathematicians-certainly
when a mathematician's result unlocks someone else's problem for
them, there's got to be an immense sense of gratification.
Kernighan: That's right.
MSM: Plus a validation that what one
has developed is a profound theorem, when it begins to unlock
other people's problems.
Kernighan: None of these things are
profound, but, you know, they make life easier for people. They
make it easier for somebody to get something done. So, I personally
MSM: Actually, one of the things you
were talking about, that I hadn't thought about, is--typesetting
things, which one tends to think of as graphical, is really about
languages. Small languages. It's a question of how to capture
Kernighan: The input side is small languages.
There's a continuing debate between: is it better to have a linguistically,
textually-based description of things, or is it better to have
a visually, graphically-based description of things? People who
have WYSIWYG editors will tell you it's much better to have it
right there on the screen before you, and people like myself,
who've grown up with, and are comfortable with, the textually-based
tools, will tell you there are lots of things you can do with
text that you can't do with the pictures. The truth, of course,
is that it's a combination of both; each has its good and bad
points. I think we started to make significant progress in a
lot of these things when we started to think that what we were
doing was building languages, because then you could start to
think of using the tools that were around for constructing mainstream
languages in these other areas. In addition, the artifacts that
we built with these tools themselves, were in some sense cleaner
and better, because they were linguistically-based. They became
less of a collection of features and more implementation of a
relatively coherent grammar and set of rules, and so they were
easier. Early mathematics-there had a variety of people, I found
out afterwards, who had built tools that were intended to make
it easy to typeset mathematics, and they were always full of restrictions,
like there shall be at most three levels of subscripts, and two
of these and four of those. And the reason was that-
(END OF SIDE 1; SIDE 2)
Kernighan: -to build yourself a language,
that a lot of these funny restrictions don't happen, because the
recursive structure that that tool encourages you to use means
that you tend to get things that just go. So, if you need seventeen
levels of subscript on something, well, you know, it's no different
than two levels of subscript. It's just more than one. And so
a lot of these arbitrary, capricious restrictions, that showed
up in things where somebody was building a program, sort of go
away when somebody's building a language with an appropriate set
of tools, because the grammar does not really make it easy to
talk about restrictions-well, one or two or three-but encourages
you to think of just an arbitrary number. It's not that you can't
have an infinite number of subscripts; you'd run out of something
after a while. But, it's not in the structure of the language.
MSM: Little languages: when did you start learning
Kernighan: I believe it was--I've forgotten
his name, but in Le bourgeois gentilhomme the gentleman
who realized he'd been speaking prose all his life. (laughing)
I should remember his name, but I can't. In some sense, it's
the same phenomenon. Somewhere, somebody asked me to give a talk.
I looked back and realized that there was, in some way, a unifying
theme to a lot of the ways that I had been fooling around over
the years, which is that I had been building languages to make
it easy to attack this, that, or the other problem. In some way,
make it easy for somebody talk to the machine. I started to count
them up, and gee, there were a lot of things there that were languages.
Some of them were absolutely conventional things, some of them
were pre-processors that sat on other things, some were not much
more than collections of subroutines; but, you know, you could
sort of call them languages. And they were all characterized
by being relatively small, as they were things that were done
by one or two people, typically. And they were all not mainstream;
I never built a C compiler. They were attacking sort of off-the-wall
targets. So, I said, gee, well, they're little languages. Then,
once you see that, you can start to look for further targets of
opportunity. Over the years, that's what I've done. You can
push that arbitrarily far, probably too far.
MSM: The way you were describing it
before, when you were talking about yacc, and about, when
you see these things linguistically, but-I forget exactly what
words you used-but, what it triggered in my mind was the sense
that, what's come out this research group as a whole is a body
of theory that seems particularly adapted to precisely this design
of languages. This is the textbooks on the subject of language
design, theory based language design-combinations of three things
taken two at a time. (Laughing) I should say eight or nine things
taken two at a time. But that all fits together, and on the one
hand we say "Yes, of course." But, on the other hand,
"No, not of course."
Kernighan: I think that there's-you
could see the roots of it. The theory-based part of it goes back
to Al Aho, I think, starting here-having just finished a thesis
at Princeton on a particular class of formal languages, having
worked with John Hopcroft, having had Jeff Allman as best friend
all the way through graduate school-when the analysis of formal
languages was the hot topic in computer science. Computer science
didn't really exist in those days, but that was the topic. People
were studying the properties of languages. So, when Al got here,
he was still interested in that, and I suspect that there were
times when his management would wish that he'd get off this damn
language stuff and do something that mattered. Fortunately, in
the best tradition, he never did. Then when he and Steve Johnson
got together, and realized that it was possible-I guess they weren't
the first people to make compiler compilers-But they were-
MSM: They were back in books-
Kernighan: Yeah. And the fact that
Steve called it yet another compiler compiler suggests that this
was again in the air. The difference was that this thing was
sufficiently well-engineered that it was a practical thing for
other people to use. It was not the personal research vehicle
of Steve Johnson or Al Aho, but rather was something other people
could use. And furthermore, that there were these collection
of weird people around who actually wanted to use it, who were
willing to use it, and stress it in ways that hadn't been thought
of, and therefore make it a better tool. If you look back, maybe
it was yet another compiler compiler. I'll bet you can't name
another compiler compiler. That's the only one that has survived.
It's still used, still used extensively, continuously. All kinds
of people, lots of people still discover it, because the job
sufficiently well done.
I think the reason was well done is,
aside from the intrinsic brightness of the people involved, and
the fact that they picked good algorithms and continued to define
them over the years-I think it's the milieu of other people sort
of banging against it, and trying things with it, and building
things with it-build up sort of a collection of things, where
you could look at it and say, "Yeah, this is actually useful
stuff." It's not a academic exercise. It's genuinely a
better way to do things than what you might have had before.
So, this collection of people-enough critical mass, if you like-to
actually prove the concepts, and prove them in the in addition
to working the rough edges off them, and getting them to point
were they genuinely practical tools. We use our own stuff, and
I think that's a critical observation about this group here.
We do not build tools for other people. We do not build anything
for other people. I think it's not possible to build things for
other people, roughly speaking.
MSM: In the sense that, you just sit
and have other people lay out their specs, and then you build
Kernighan: Right. If I build something
for you, even if you spend a lot of time describing to me what
you want, and why it's the way it is, it's not going to be as
successful as something where I personally face the problems.
Now, I may live with you long enough that I start to understand
what your problems are, and then I'll probably do a better job,
but I think that we have historically done the best on building
things that address problems that we face ourselves. That we
understand them so well because we face them, either directly-you
know, I face that problem myself-or it's the person in the next
MSM: This is probably one of those,
either "chicken or the egg," or "a little bit this,
a little bit of that" questions. What drives this, in essence,
is that you're working on your own project, developing your own
stuff, but you're also constantly calling on what other people
are doing. So, as a result, you tend to reinforce one other's
work and you're your own best critical audience. Criticism in
the best sense, because you have a stake, not only in finding,
but in making stuff work. Therefore when you find problems that
are genuine problems-that block you-you want them fixed.
MSM: One can see all sorts of things
coming together now. You've got to have the right people. Those
people have to be working on the right set of problems. And they
have to establish a way of working with one another; one can image
that happening of itself, or one can have a sense of its somehow
being directed. Now, what is it that makes it work here? What
is it that was making it work, back in the early '70's?
Kernighan: I don't think it was directed, or
least if it was directed, it was done in an incredibly deft and
unobtrusive way. Maybe management will tell you that that's worse
Kernighan: If that is true then it is
to their eternal credit. Now, I think, in a sense-I mean, Doug
was management of at least some part of that. I guess Ken technically
was in Doug's department, and Doug is superb that kind of stuff.
Insofar as he manages it, he does by superlative constructive
criticism at the right time, and by going out and trying your
stuff and finding out where it works and where it doesn't work,
and then telling you what was good about it and what didn't work.
To a lesser degree, I suspect that, in some sense, we all do
that. I don't think that this was done by any direct management,
so we can dispose of that part.
Part of it is a confluence of really
good people with reasonably good taste. Particularly Ken and
Dennis, who, as far as I can tell, genuinely have truly deep insight,
and at the same time, good taste, and at the same time, essentially
very close to parallel taste, so that they don't get going in
opposite directions. Part of it is happy coincidence, that technology
had gotten just about the right point where you could get hardware-a
machine to work on-where you didn't have to, in some sense, be
beholden to other people. You didn't have to use that machine
their way because they paid for it, or something like that; that
you could have something that's sort of your own, so you could
furnish your computing world the way you wanted it, the way you
are comfortable with it. If I want to go off and run on a big
IBM machine, there's no way I'm going to be able to do that, because
I can't afford it. I'll have to do it the way which is provided
by somebody else, because they paid for it, they call the shots.
But, if it's a machine that's my own, then I could run it the
way I wanted to, assuming I have the technical background to actually
make it work. It's some combination of those things, and it would
be nice to know precisely what makes it work so that you could
clone it. But, my guess is that it's-in a sense, almost an accident.
You could see other places that have had that same kind burst
of stuff. I think Xerox PARC went through a phase like that,
in roughly in the early seventies, where they produced a bunch
of really, really good stuff, with a different working style,
to some extent, but again, it was a combination of things that
led them to produce genuinely innovative stuff that's had a effect
MSM: You know, I was talking with Shedell.
The guy that did the Paintbrush program, the first Paintbrush
program. I just happened to meet him at a reception at the computer
museum at Boston. We started talking about Xerox PARC: how did
you get your assignment and what was your mission? You know,
there was a great deal of similarity. Well, it was sort of a
general mission to do interesting things and hope they work out,
but look around for something interesting to do and get going
on it. He said he was given two years to find something to do.
He sat there and he played with Paintbrush, which he had done
back in '73, and it was brilliant.
When did you become the group's scribe?
Kernighan: I think at some point fairly
early in game, I started writing tutorials. Sort of, how do you
use it? Gerry Markey, who is now Sandy Fraser's secretary,
said to me one day, "I don't really understand how to use
qed," which was the text editor, and I said, "Well
why don't I write down something that will, sort of, tell you
how to use it." And I wrote a tutorial on qed. Now,
I don't know if it ever did Gerry any good or not, but a lot of
people found it useful. It was a sort of, here's how you get
started on this kind of stuff, and it was a particular style of
writing that nobody that else seemed to be interested in doing.
Which was sort of-not a manual, but a "how to do it"
tutorial. No better word.
I had already written one of those for
my little formatter at Princeton, in fact, so it wasn't the first
time I had done it, but this was, I guess, the first time I, sort
of, consciously did it. I did several like that. I did one on
B; the one on B mutated into the one on C, which then mutated
into a C book. And, you know, a variety of others. I did a "cave
guide" to the Murray Hill computer center, an underground
guide to the Murray Hill computer center, which was (laughing)
sufficiently against the received wisdom that they didn't want
me to publish it. But I published it anyway. Which was, sort
of, one of the useful programs, as opposed to the ones you will
find in the manual. That kind of stuff. I guess, from there
it's not too big a step to writing things that describe what's
good about the operating system, or the environment, or the way
of doing things-these sort of pseudo-philosophical papers that
explain what you could do when you connect programs together,
and what you could do when you had a programmable shell, and that
kind of stuff, which, where I took basically one paper and probably
wrote it about fifteen times. But that kind of thing. So, I
think that's part of where this writing came from.
The other aspect was book writing, which
in the long run is much greater effect. I think you have much
more impact if you have a successful book. I still remember quite
clearly how I got started in that. I was enormously lucky when
I came here the first summer to be in the office next door to
Dick Hamming. I'd heard of Hamming codes because I had taken
a course in coding, error-correcting codes at Princeton. I was
sitting in my office the first day, as we are sitting here, and
this guy came in from next door at eleven o'clock and he said
to me, "Hi, I'm Dick Hamming, let's go to lunch." I
said, "Well, okay," and he dragged in Vic Vyssotsky,
who was right across the hall from me, and we went off to lunch.
Later on I discovered, this was the famous Hamming of Hamming
codes, and the numerical analysis book that I had used the year
before. I think a lot of people had trouble with Dick because,
he was one of these guys who was absolutely outspoken, and not
afraid to give you an opinion on anything, and usually
sort of a controversial, rock-the-foundations kind of opinion.
But, I didn't mind. That was fine, and he was a nice guy.
One of things that he was fond of saying
was that programmers don't know how to write programs. The way
we teach programmers how to write programs is we give them a grammar
and a dictionary and we say, "Okay, kid, you're a great writer."
That's the way programming was taught according to Hamming, and
there's a grain of truth in it. He said, "What we really
need is a book of style; here's how to write well."
I don't remember in detail, but his idea of how to write good
programs was, I think, pretty half-baked at that point. But,
one day he came into my office and he handed me a book and said,
"Look at this!" (searching for book) I don't think
I still have it down there. I used to have it. It's probably
down there somewhere. He handed me this book, and he said, "Look
at this! This is awful!" It was a FORTRAN program. It
went over two pages. What he was talking about was the numerical
analysis in this thing, but what I saw, when I looked at it, was
this horrible piece of code, which is the first example in the
Programming Style book. I looked at it, and said, "Jesus
Christ!" I wrote on it in green, "Jesus Christ"
(laughing) and then it occurred to me. I know what I can do,
because I had somewhere stumbled across Strunk & White, which
is basically an "awful, good, awful, good," you know,
side by side. You could make a book out of that. You go off
and you find awful examples and you show how to do them right.
Bill Plauger at the time was in the next office, and he kind
of got intrigued by the idea. So, we went off and we hunted the
libraries, all the libraries, all of Bell Labs' libraries, and
any other place that we went. Bookstores and everything. And
we found awful examples, and it was easy to find them. There
were just zillions of awful examples, because every programming
textbook was awful. We went off and wrote-basically just collected
these, tried to get them in a coherent form, where an example
would illustrate some principle or guideline on how to write well.
Then we just threw it all together and wrote a book. It was,
I think, certainly a fun book to write. (Laughing) My wife said
to me, "You found your ecological niche."
MSM: I've been looking for a copy.
I can't find it anywhere.
Kernighan: I'll find you one. I can
probably do that. (searching for book) I'm sure I have one down
here, somewhere. Fun book to write, and I think that's how got
I started in book writing, at least. Then Plauger and I wrote
the Software Tools book shortly thereafter, and then I
browbeat Dennis into working on the C book with me.
MSM: You just found you like to write?
Kernighan: I like to write-ultimately,
it was deemed to be good thing at the labs. I think when I first
wrote that book, it was deemed to be neutral. It wasn't like
a positive thing, but I'd only spent about three to six months
on it, so it wasn't a bad thing either. It was just a neutral
thing, and it was only sort of retroactively that it was deemed
to have been a good thing. I think Plauger got fired for writing
MSM: I want to talk about where he went
in a second, but there's an obvious question. When someone takes
other people's style and says, "This is the way to do it,"
and when you talk about its being relatively easy to find examples
of bad code writing-where did you learn to write programs? Where
did Plauger learn to write programs, that your style is good style?
Kernighan: (laughs) Well, it's not clear
the style is good style; it was better than a lot of the programs
that we found in textbooks. All of the examples came from textbooks,
and they were-I mean, we clearly picked on the bad ones. It was
embarrassingly easy to find bad ones, because a lot of these things
clearly had never been thought of. Many of them have never been
executed. I think a lot of them, the professor wrote the book
and said to some of his students, "Why don't you write programs
that will answer these exercises?" and then stuck them in
the back of the book and never looked at them, and a lot of those
were just-they couldn't possibly work, and others were just really
bad. You didn't have to look very hard to realize what was bad,
and from that, you could start to infer what might be good.
I don't think our rules of style are very deep or anything like
that. But, we gradually evolved a set of-well, rules, not in
any formal sense, but little detailed rules that corresponded
to getting your commas in the right places when you write sentences,
and realizing between "which" and "that,"
those kinds of things-and move up to grander things, that relate
to the structure of programs.
MSM: Was Strunk & White more than
just an inspiration, or was this-did you read through Strunk &
White, think in terms of Strunk & White when you were doing
this? You just used an example from it.
Kernighan: Yeah. I think that Strunk
& White was an excellent example of something that we didn't
consciously-I think we must have consciously taken them as the
model, because, the sort of side-by-side, "Here's a good
one, here's a bad one, here's a good one," and what did we
do to get from one to the other, is definitely what we did there.
It's not the same, because English is not the same as writing
programs. But there's an awful lot of commonality. I still reread
Strunk & White every couple of years just to refresh my memory,
what they think about good writing, because that's still the
best English style book I have read. The other thing we tried
to emulate was the brevity, because I think long books are not
necessarily better than short books. In fact, they are sometimes
MSM: Try and convince my grad students of that.
Kernighan: There's lots of reason to
believe that short is better. (laughing) If nothing else, even
if it isn't better, there isn't so much of it.
MSM: You started out using FORTRAN, the old
FORTRAN, which is not a structured language. You spent time optimizing,
writing an assembler. Ultimately you made a transition to what
might be called structured programming, and Plauger went off to
work for a company that is probably the standard bearer of the
structured approach to things. Was that a conscious transition
for you? Or, did you think of it as a transition? Was there
a time in which Dijkstra was on the shelf here?
Kernighan: Yeah. It was-structured
programming, and programming without goto's and all that
stuff was definitely very much a topic of discussion at the time
when Bill and I were working on this book, and noticeably before.
Quite a bit before. We wrote a couple of papers before we got
into the book, or concurrently with the book, I guess. I remember,
somebody or somewhere, I was introduced to the notion that you
could write a program without goto statements if you had
the right kind of language, and B was the first example that I
really used where that was a possibility. And so I set myself
the task of writing a particular program-something that just reported
on job status on the Honeywell machine or GE machine-I set myself
the task of writing that program without any goto statements.
I said that this would be my test case, and it was a program
that ultimately wound up with, I don't know, six or seven hundred
lines of code. I would write it without goto statements,
and I found it an incredible bitch of a job. I finally
got it down to three, and I was quite proud of myself. In hindsight,
you know, fifteen, twenty years later, I cannot image what the
problem was; how could it be so difficult? Because I just don't
do that anymore. You know, it's like training yourself so that
you always get "which" and "that" correctly.
You don't think about it anymore, and you don't realize it's an
issue, you just do it correctly. In that sense it was conscious
for me. I had to work very hard to get to a particular level,
where then, after a while, it became completely unconscious.
And there were other kinds of programming, things that go along
MSM: But you were rather persuaded by the virtues
of doing so?
Kernighan: I think so. The first big
program I ever wrote, truly big, was a COBOL program. COBOL programs
are sort of the antithesis of structure; in fact, the only way
you could write a COBOL program is basically to make it unstructured.
It's just awful. And I still remember, the way that I wrote
that program was, every time I had to make a decision about something-is
this bigger than this?-then I'd say goto, I'd invent a
label, and I had this steadily increasing frontier of things I
hadn't figure out how to do yet. (laughing) The program just
grew without bounds, and I never finished the damn thing. In
retrospect, it's the kind of program that I could probably have
written in a hundred lines in a decent language, and it was just-it
was literally over ten thousand lines at the point where I quit,
at the end of the summer. So, in that sense, I was convinced
that, at least, just pouring in these goto statements was
wrong. Looking at some of the examples in the textbooks, it was
clear that was wrong. I'm not sure that I believed Dijkstra in
any pure sense. I really don't remember when I first read his
famous letter to the editor; it was probably well after I had
been doing this kind of stuff for a while. A lot of that's just
MSM: I started doing this going back
to school in '82. I was taking a Pascal course, and I learned
to program directly, in machine language, or-I guess we had alphanumeric-no,
it was 074, it was clear and out. You just had to know what
the codes were. I remember the first time we were supposed to
have a branch decision, having to search out, have to go see,
and I said, "Where's the goto?"
Kernighan: (Laughing) Yeah. Right.
MSM: They said there is none. You're
not supposed to use it. And then, they explained what this was
all about, and then I remember getting Wirth's book, and looking
at it, and it's got goto's. It usually has goto's,
at least to the error, so he gets all his errors together. So,
here's the ultimate structured programming language, and there's
the author of it using goto's. Like most truths, it lies
somewhere in the middle.
Kernighan: There's a great line in Strunk
& White about, you know, you'll find places where the rules
are broken, but you'll find some compensating merit to make up
MSM: Well, there's Winston Churchill's
remark about prepositions, that it's nonsense up with which I
Another aspect of structured programming, at
least the approach that you were talking about before, is this
use of recursion. I remember when I was reading the proceedings
of the Garmisch and Rome conferences, and I remember now, someone
saying something like, everybody recognizes the virtues of recursive
procedures, and yet, no operating system, no large software system
program, uses them. And it was in Holmdel, someone handed me
a-rules for programmers from another project, and one of the rules
was no recursive procedures. And yet, the Unix systems were-seemed
to take-what was going on there?
Kernighan: I think that there was, for
a long time, a conception-perhaps originally based on fact, but
laterally not at all-that recursion was in some way expensive,
and therefore you couldn't use it; that a recursion procedure,
if nothing else, it was another procedure call, and therefore
procedure calls were more expensive and therefore you couldn't
use it. Now, it wasn't a issue in FORTRAN, where you couldn't
recurse, but it was in PL/1, where you could recurse, and PL/1
function calls were notoriously expensive because of the language
design; it sort of forced you to carry around incredible baggage
to actually say what the arguments were as you went along. So
I suspected it came from that fear that, when you-any extra function
call was going to cost you a lot, and recursion was intrinsically
function calls in place where you didn't have to use them, and
therefore it was a bad idea.
MSM: Was call by value in C? C's calls are
very spare. Was that it was there for? To support recursion
Kernighan: I not sure it was to support
recursion. I think it's simply to support function calls, because
functions, breaking up the job into smaller pieces, I think is
necessarily a better way to do things. But, if you're going to
that, you want to make sure that they are efficient. I think
in part it was a reaction to the PL/1 stuff, where functions were
so expensive that people tended to avoid them. And they don't
have to be expensive, they can be quite cheap. In fact, there
was a lot of effort devoted over the years to various ways to
make the function calling inexpensive so that people would be
encouraged to use it. C compilers to this day go to some effort
to do that. And furthermore, a lot of that is reflected in the
machine architecture, where the machines themselves drive the
subroutine call, mechanism cheap. Part of it was just the machine.
A machine like, say the IBM 360's, 370's, the subroutine calling
mechanism was actually intrinsically expensive; it was badly designed
in the machine. The machines like PDP-11's and their derivatives,
the function call mechanism is actually well-defined, and it's
comparatively cheap, because basically, the machine supports the
notion of a stack in some way-the auto-incremental structure is
one, manipulated stack made it easy to get in and out, and there's
even a-A del had a subroutine instruction; the question is, what
do you have to do before and after it? The DEC machines just
did it right, and IBM machines just did it wrong.
MSM: Have the, just following along those lines-you
said earlier something along the lines that, it was the right
moment, the hardware was coming along. Is there an extent to which
this development, maybe its timing, or its pace, has been hardware
determined? To what you had available? Or has it reached the
point where it's now beginning to influence hardware design?
Kernighan: Certainly the original development
and pace, I think, was very strongly affected by the hardware.
The PDP-11, I never programmed it in assembly language, so I
can't speak intimately of that, as Ken or Dennis could. But,
my belief is that, from a programmer's standpoint, as a dream
machine-that's really a very, very nice machine. And from an
economic standpoint, it was kind of a dream machine too. It would
fifty thousand dollars fifteen years ago, and that was manageable.
That was something where a group of ten people could justify
spending that much money. It was an order of magnitude cheaper
than existing machines that you could buy and you could use for
something So, I think-and furthermore, it was available from
a real manufacturer, somebody who existed, who was in some ways
comparatively easy to deal with, certainly much easier to deal
with than with IBM; and a manufacturer that, perhaps, because
of its origins, made it easy to connect interesting widgets to
the machine. A lot of things combined together to make the 11
a very attractive machine. IBM always played it very close to
the chest about what you connect to their machines; you had to
have these elaborate channel things. It was just horrible. DEC
machines, you could just plug in stuff. It was a whole industry
of weird things you could connect to DEC machines, all of which
made it substantially more interesting. And the fact that it
was small enough that a university department could buy it-it
made it spread. So, it got to the point where, the combination
of the attractiveness of the hardware and the fact that there
was this attractive software that you could get, almost for free,
to go on it, meant that large numbers of university computer science
and related departments would go off and buy the things, and run
them. I think the VAX carried on the tradition, although the
VAX is probably, today, excessively pricey for what it does.
But, I think what we're finding now is that the portability aspect
of Unix mean that in some sense the hardware is almost irrelevant.
There are certain kinds of hardware where Unix and C are not
going live comfortably. But, for the most part, the hardware
is almost irrelevant. I think that, in some sense, is a giant
When I first got into computing, and
for the first ten or so years, up until the mid '70s, at least,
the arrival of a new computer-you were going to go from GE to
IBM, or from UNIVAC to Data General or something-that was just
a trauma beyond words. It would months--it would take years-to
make that adaptation. It doesn't happen that way anymore. Things
are-I mean, you still spend a lot of time as you move from one
machine to another. But, it's a different-it really is a different
order of magnitude. We've slipped in several new machines locally,
and a lot of the software, you just compile it and it runs, and
the operating system environment is essentially identical. You
type the same commands, they behave the same way, the shell is
the same; it's the same. That, I think is a tremendous
step forward. I don't know whether that relates to your original
question, which I've now managed (laughing) to lose from my neurons,
MSM: No, actually, it's always seemed
to me it's sort of-a bit of a contradiction that, the most popular
host machine for Unix, during this period of rapid spread, was
the DEC PDP-11, or the VAX, which is just an extension of the
11. You can look at the manuals, and it's one of the richest
instruction sets, I think, that's ever been put on a machine.
I mean, you've got an assembly language routine for evaluating
polynomials, and all the packed array, decimal packed array stuff--it's
fun to go and play with it. Sort of an assembler programmer's
playground. I can see the attraction of doing it.
But also, the ethos of Unix is you stay
out of assembler. You don't program in assembler. You use C,
and you try to keep the assembler kernel down to just what's necessary
to get things up and running. If I understand it correctly, it's
right there in the bootstrap command. From there on in, you address
it in C, and though I haven't looked at the C compiler, my sense
is that, for portability concerns, if for no other, one would
say they're a pretty restrictive set of assembler routines, and
that in many ways the RISC architecture is better suited in the
Unix system, than this extra rich instructions set. That's what
led to-the instruction set on the VAX says, wasted if you run
Unix. And the irony is that two-thirds of the VAXes are run on
Kernighan: Yep. Absolutely.
MSM: (Laughing) That was meant to be a question;
obviously it failed.
Kernighan: Well, I believe what you
say. I don't think that people write assembly language on most
machines that run Unix, except for some tiny thing that they can't
get at any other way. I have not written an assembly language
program in eons, fifteen years probably, and never to expect to
again; I hope never to have to. You're right; most machines provide
a very, very rich set of instructions, most of which are inaccessible
from your favorite high level language, whatever it is. Now,
packed decimal is presumably there for the benefit of COBOL, right?
MSM: I don't know, (Laughing) I never could
understand what that's for. I simply took Peter Huntington's
challenge once, to do something in packed decimal arithmetic.
Pain in the neck.
Kernighan: But, you're right. There's
no compiler in the world that's going to generate the Horner's
rule instructions. It just isn't going to happen. Poly-q or
whatever it's called; it's just not going to happen. So a lot
of the effort that goes into to building that kind of complicated
architecture is totally wasted. The RISC architecture is, insofar
as they are uniform, are a better match to what you likely want
out of your favorite compiler.
MSM: I've run out of questions for now.
Kernighan: What are you doing for lunch?
(THE END OF TAPE)