Donald Knuth Interview 2006

This is a transcript of an interview with the guy by Dikran Karagueuzian, the director of CSLI Publications, videotaped in 2006. Copyright 2006 Web of Stories Ltd., but the version of the transcript on their web site is just unreadable; this is my effort to clean it up a bit. It’s about 63 000 words, so it is probably around three or four hours of reading. Printed, it would be about 110 pages.

Patches to improve the formatting and correct errors are welcome. Please don’t refill the paragraphs, though; it creates unnecessary merge conflicts.

I know lots of people are going to hate the random boldface. But the interview, like any record of an extempore speech, is not really organized into headings, subheadings, and the like. The boldface is my attempt to pull out the main topics of each paragraph so that it’s possible to skim through the document to find a particular topic.

1 - Family history

If you want to go way back, if you go like, 16 of my great-great-grandparents, in 1840 they all would have been in Germany, but by 1870, they all were in America. So if you know, consider all the different lines. My mother; my father’s, the Knuth part of my ancestry was the most diverse, in a way. He came from Schleswig-Holstein, rather near the border with Denmark, and he was the last to come over; during the Schleswig-Holstein crisis in the 1860s; I think it was 1864, probably, he went AWOL from the army; he didn’t want to fight against the Prussians, and he decided to come to America, and knocked on the window one night, and told his parents, I’m out of here, and wound up in Illinois, and then worked, learned to be a blacksmith at that time.

So then his wife was somebody he met in America. She had come — her family had come over earlier from the Hannover area, and she lived in Indiana, all very near Chicago area, and so that part of the family is from a different part of Germany. My mother’s side came; they all emigrated in 1840s, and they were farmers in the area of what is now Niedersachsen; it’s a small town in Germany called Bad Essen, and they, her family came and were farmers in Ohio, near Cleveland, Ohio. So they, yeah, the background then is, my father’s side round Chicago, where he was born and grew up, and my mother’s side from Cleveland Ohio, where she was born.

My dad’s first teaching assignment was in Cleveland, and that’s where he met my mom. Then he got a call to Milwaukee, which was way far from any of their, you know, anybody else in the family, because it was a job that opened up, so he went and took this job at a school that needed a teacher.

2 - Learning to read and school

It all started in Milwaukee, Wisconsin, 1938, I was born. I don’t remember anything about the first few years of my life, but I know a little bit from records that my parents kept that they were kind of unusual at that time, in introducing me to reading. All of their friends said that I shouldn’t, that I would be bored in school if they would do much reading for me, before I actually went to school, but I was — I guess I was the youngest bookworm in the Milwaukee Public Library.

So that’s the first, news I have from the past, because they saved a newspaper clipping. I guess I was like two and a half years old and I had become a bookworm at the Milwaukee Library. I start remembering things more when I get, you know, when I get into school, and I went to a small school at our church.

My father was a teacher there. His life’s work was to be an educator in the Lutheran School System, and their salaries weren’t much to speak of. I think, I think it was something like ten or $15 a month. But it was a very warm, loving community. We were pretty much ignorant of what’s going on in the world, but happy and sort of a stable, nice place to grow up. And when I was in First Grade my dad was the Second Grade teacher, but then he moved on so that when I got into the Second Grade he was the Fourth Grade teacher, and when I got into Fourth Grade, he was the Sixth Grade teacher. And finally, when I got into Sixth Grade, he went on to teach in high school, so, fortunately, I never had my dad as one of my teachers.

In this school we had about oh, I think 20, 25 kids, and our teachers weren’t real strong on Science or Mathematics, they were, but they were pretty good in English. They- like in Seventh Grade, I remember, that several of us would spend time after school, diagramming sentences; you know, take sentences of English that weren’t in the book, and figure out what’s the subject and the predicate, and how do the, you know, how do the phrases go in, so we, our teacher inspired us to know a lot about the English language, and by the time we got to high school, the teachers there in high school really didn’t know that much about English, so that was the only time I remember being bored, because we already knew everything that they were going to teach us in high school.

So the high school I went to, again, was a Lutheran high school. The people who work in these schools are, like my dad, doing it as kind of a mission, or, I don’t know, not, they consider it their life’s calling to be good teachers, and so we really had people who took a genuine interest in us, and were not, not in their job just because it was a job, but because it was something that they felt was an important service to the world. Some people think that the church schools are places where they teach intolerance and you know, that you’re supposed to only be, what do you say anyway? Only, only be appreciating of people who are like you, and so on, but that was absolutely not the case. I think we had a very good experience and it was, there was, one of my teachers was a little bit prejudiced against blacks, but he stood out, and we didn’t pay any attention to him.

So it was a, I think a really nice way to grow up, but nothing world class, in any sense of special, or, you know, special knowledge or unusual.

I think I was kind of a wise guy, I think, I’d often sit in the back of the class and crack jokes, and the teachers didn’t, didn’t really like, the way, you know, my attitude. But you know, they learned to live with it, and I didn’t get, I didn’t get spanked too often.

We had good music also, in the school, for singing, and, but we also had a lot of freedom, so I remember like, we had a circle of four or five friends, and when we were in Fifth and Sixth Grade, we started doing some little projects, like we got hold of a tape recorder, this was in the 1940s, and we tried to write scripts for fake radio programs, and we pretended we were on the radio, and we put on these little shows, and recorded them.

My friends and I started a school newspaper. We called it “Newsweak”, spelled W, E, A, K, of course. And in that paper we would tell stories about things going on in the school, but also we recycled a lot of corny jokes we had seen in books, and had a puzzle page and things like that. But that was when I, I had my first experience in writing, and as I say, we had good English in that school, so from early on, I had a lot of training in things that had to do with languages, and then a chance to do some creative work with things like these skits.

3 - My mother

I should say something about my mom, who was also very important in my life, of course. She was unusual also at that time, because she had a good job. My parents were the first in their families, in the whole history of our family, to have some kind of education. My dad had gone to a teachers training college in Chicago, and my mother had taken one or two years of training as a secretary, as a legal secretary.

And in the, during the Second World War, she got a job working for a man in downtown Milwaukee, who owned and managed several of the skyscrapers in town, downtown, and she became his personal secretary, and later a Trustee of the, of these, of some of the organisations that owned the property, and the time of his death she was, she had been doing rather well, and was asked to be, asked to be the manager of one of the buildings, so she spent her life working in real estate in Milwaukee with the large commercial buildings in the downtown area. And she had started doing this part time work, when I was five or six years old, but still doing everything else at home, as well.

My, but my grandfather was, my great-grandfather was a blacksmith, my grandfather was, my grandfathers on both sides, were in construction work, and maintenance. There was not a family tradition of education, and I certainly was the first one ever to go on to higher levels of education. It’s partly the story of America, of course, that more and more people are going to college, but when I was in high school, at that time still, it was, I think something like 7% or 8% of my classmates went on to college, and that was considered pretty good at that time.)

4 - My parents’ finances

I guess I can say a little bit more about my parents’ finances. Of course they were married during the Depression, and my dad’s first job, when he came to Milwaukee, they decided after a year, that they should cut his salary by $5 a month, and they told him that he would learn thrift, and he would, you know, this would be good for him, to, and of course the church was always having trouble with fundraising, but our family didn’t have an automobile till 1951, which is when I was in Seventh Grade.

We took our first, you know, auto trip at that time, to my mother’s family in Ohio. Before that we had gone once or twice a year by train, and rarely would relatives from Illinois or Ohio be able to come to visit us.

We, my dad would always ride his bicycle to work, and my mother, well, Milwaukee had good public transportation, and in fact it was a very safe city; completely different from now, when, because of drugs and things now, but when I was growing up, I could, I would always ride the streetcar downtown at all hours of the day and night. Now you take your life in your hands doing this. You know, no parent would let their child do any of the things that we were doing.

I was, once I took the streetcar; I don’t know how old I was, but I think it was, you know, maybe Fourth or Fifth Grade, and I took the streetcar downtown, and went to the public library, and I started reading books, and I didn’t know that the library hours, that the library was closing, and the lights went off, so I went over to a window, where I could sit, and I kept reading, and finally the people, you know, and my parents didn’t, were wondering what happened to me, why didn’t I come home?

But somebody at the library found me, you know, just in the stacks, reading the books, and but you know, still they wouldn’t worry too much about letting kids go around the city, and so my mother would take the streetcar downtown to her work, and we never thought of having an automobile until they could finally afford something from the little jobs that my dad would take outside of his teaching experience.

He would; he and his friends got together and they invested in the stock market, what they called penny stocks. You could buy stocks in various mining companies. He met a man at the, I think it was at a, what do you call it? A bathhouse? Or, you know, a public bath, where you can go for a hot bath, and met a man there who introduced him to some people from Colorado who were into mining and so then they decided they were going to make some money this way.

Well, I inherited all these stock certificates now, which make great wallpaper, but they, you know; they’re completely useless. One of the stocks, however, did well. It was called Silver Bell Mine, and we’ve, eventually we went out to Colorado, visited the place, and saw the, you know, we, the stock was sold to Union Oil eventually, and made a little bit of money on that. So, and my parents bought stock in Walt Disney, and that kept doubling and multiplying.

So by working hard and saving money, throughout my mom’s life; she died at almost age 90, and she never retired, she stayed working in real estate, even in her late 80s they had an office for her downtown, and she could come in, maybe three days a week, and, but putting money in the bank, and being a generous person, and contributing to charity and so on, but she had accumulated an estate of more than $1 million, by the time that she died. And this surprised everybody including her.

But they were, my dad was the bookkeeper for the high school, and so he took some classes in accounting, and so he spent a lot of his time actually filling out what we’d call spreadsheets now. And he’d stay keeping track of little transactions with stocks. The, so, I think it’s interesting to see that the way they could, just by being responsible citizens, make a good life for themselves, the way the times were in our country at that period. And this idea of personal responsibility was something I always took for granted, because I got it from my parents. So it never occurred to me that there was any other way to live.

5 - Interests in high school (Part 1)

Back in high school, my main activities in high school, at, it was called Lutheran High School, and then during my Senior year it split into two schools, Milwaukee Lutheran High School, which was the one I’d went to, and Wisconsin Lutheran High School.

1956 was the year I graduated, and that, well, the place where again I didn’t have special, teachers who were specialists in a world class sense, but they were always real interested in nurturing us.

I went on to be a mathematician, but the math, but I didn’t have any interest very much in Math at the time in high school, because my, I would ask questions to my teachers, and they didn’t know the answer. So I could prove that one was equal to zero, and they couldn’t find any mistakes in the proof, and so you know, I couldn’t, and so, why should I go in, you know, go into mathematics? So my main interest at that time was in music, and also in physics.

My chemistry/physics teacher was a wonderful man, who sort of wrote his own textbook, he designed the chemical experiments, and I had a great admiration for him, and he encouraged me to you know, to think some about physics, and although I spent most of my time in music, outside of school.

In fact I, well I played the piano with the high school chorus, I sang in the chorus, I was in the band, I played the saxophone and I played the tuba in the band, and I played, you know, in the All-City, the Milwaukee All-City Band, or Symphonic Band. I wrote music, I arranged music for bands. I had, I had, at the time I took a; I was a big fan of Mad Magazine.

And also of Roger Price, if anybody remembers Roger Price, and he had written a short story called “Milton and the Rhinoceros”. And so I made a take off on Prokofiev’s “Peter and the Wolf”, with the words from “Milton and the Rhinoceros”. I was very naïve at the time; I had no idea about copyrights, or anything, so I took Prokofiev’s music, and I scored it for band, and I took Roger Price’s words, “Milton and the Rhinoceros”, and I made this, this piece for, I don’t know, 20 minutes or something like this, for our, for our high school band to perform. And I proudly gave this to our band director, and he lost it, and I’ve never seen it again.

So I have no idea whether it’s any good, or whatever, but there it was.

6 - Interests in high school (Part 2)

I also started the school newspaper. I was Editor of the paper, and during my Senior year, I would do an all-nighter every Monday night. I stayed up the whole night, getting the paper done by seven o’clock in the morning. We didn’t have a professional way to produce it, so I produced it on a mimeograph machine, which was something that’s way obsolete now, but it uses very greasy ink, and the reason I did that was because we happened to have one at our house.

My dad did part time work for an architect in Milwaukee, printing up the specifications, and you know, he could make a little freelance money this way to supplement his meagre salary, and he also used this machine to typeset music for local choirs, and so I had this machine at home, and also some electric typewriter that he had, or maybe my mother had; anyway we had it at home, so I could produce our school newspaper at home, without having to worry about fancy typesetting, but we had a lot of reporters, and I wrote some features for it, like crossword puzzles, and things like that. So again, I was doing a lot of writing in my spare time, during high school.

I worked on the Yearbook and other publications as well, and friends of mine, friends and I wrote plays that were put on by groups in the high school. So it was a fun time. But I would say at that part of my life I was pretty much a, like a machine, an autom-, I mean I was just, I would just learn, absorb stuff, and take tests and you know, get 100% on the tests if I could, without really sitting back and taking a look at finer things in life, or something like this. I was a, I was a dutiful child who said, okay, you’re supposed to go to school Don, so I went to school, and you’re supposed to learn, so I learned, and I had fun on the side with some of these writing projects, but I really wouldn’t read a book unless it was assigned to me.

Sometimes I would read, I remember, I’m a very slow reader, and I remember Bleak House, by Charles Dickens, with 60, 70 chapters, and I, it took me so long to read it that I had to use it for two book reports instead of one, and I didn’t; so it wasn’t until I was in my 30s before I actually found some of the great literature of the world and read it for my own pleasure.

In high school, well I guess I was a fairly successful machine, because they said that my, okay, in those days they didn’t give just letter grades, like A, B, C, but they gave a number grade, and based on you know, when you took an exam, they would average these scores, and they would grade your homework and it was all based on a zero to 100 system, and they said that my average which was more than 97.5 was a record for the school that hadn’t been achieved before, so I was pretty much a nerd of nerds at that time.

7 - My sense of humor

Rather than sceptical, cynical, I would prefer satirical or something.

KARAGUEUZIAN: Satirical.

KNUTH: But anyway, that’s why I liked Mad Magazine, because it was like crazy type of satire on the sacred cows of the day, and so when my friends and I discovered in high school, you know, we devoured every page, and it was a special, you know, mad about Mad. We, and before that, as I said, I had the corny jokes, but my friends and I tended to be wise-cracking and not to take things too seriously.

Although I said I was a machine, but I did also like to laugh, and so when I was writing for the paper, we always had sections about jokes, and we always had you know, in our Yearbook we had fun things in there that weren’t expected. So I’ve carried that through, as you know, and many; there are lots of corny jokes in the indexes to my books now that people probably haven’t discovered yet, but somebody will ask me, why do I have a reference to Bo Derek in The TeXbook? And it turns out that just all the pages which are cited in the index for Bo Derek is where I used the number ten, so all the way through I’ve had this silly streak of some sort that means I don’t take everything too seriously.

8 - The Potrzebie System of Weights and Meausures and the Alfred E. Neuman crossword

While I’m on the subject of Mad Magazine, I might as well mention that then I did a project in my senior year, which was submitted to the Wisconsin Academy of Sciences, well, no, first to the Westinghouse Science Talent Search, which is now called the Intel Science Talent Search or something, but it’s a nationwide competition, and it was called the Potrzebie System of Weights and Measures. This is a Polish word that was very popular in Mad Magazine, and I decided to base a system of weights and measures that was going to be better than the metric system. It was based on the thickness of Mad Magazine number 26, or something like this, and that was taken as one potrzebie of length. And then we had, you know, a kilo potrzebie was 1,000 of those, and a fershlugginer potrzebie was a million — and a farshimmelt potrzebie one millionth. We had units of time, weight, everything, in the system.

And it won honorable mention in this Science Talent Search, and also was, I did some demos at the Academy of Sciences; it won an award in Wisconsin. I submitted it them to Mad Magazine, and they published it; they paid me $25, for it, and it came out in, during the spring of my Freshman year in college, and this was my first technical publication, so it is listed on my vita, you know, and publication number one is the Potrzebie System of Weights and measures, and it was published later in paperback in one of the Mad reprints, and it, and I used it as a basis of running for student government in college, and it failed miserably, you know, I didn’t get elected.

I also sent a sequel to Mad, which was a crossword puzzle. One of their, the Alfred E. Neuman figure is one of the, was featured on lots of their articles, and this silly boy’s face with the missing tooth, and when I looked at his teeth, I could see, you know, white squares and black squares, reminding me of a crossword puzzle. So I added more white squares and black squares up in his forehead area, and where his hair is, and I filled, and I made that into a crossword puzzle with Mad-type clues, like, you know, “blank, me worry?”, or something like this, and I submitted that, and they rejected that, you know, they didn’t want, but I’ve still got it, and later on when we get to writing,

I’m hoping that I’ll someday publish a book called Selected Papers on Fun and Games. We will not only reprint my first technical article on the Potrzebie System, but also the one that was rejected by Mad, and we will see the; people will decide whether they, you know, will be able to decide now whether they made the right decision in rejecting it.

So yeah, I like to see things sort of out of the box as well as in the box.

9 - Feeling the need to prove myself

My parents were asked whether or not they should advance me a grade, because I was doing well in school. And they; in fact I was born in January, which meant that I was older than most of the kids in my class, because if I’d been born in December, I would have gone to school a year earlier, so I was one of the oldest in my class, and my parents, you know, a lot of kids at that time were being pushed ahead in school, and one of my friends, you know, graduated from college when he would normally have been entering high school.

Well I, but I’m glad that they resisted this, because it gave me this time for all these extra-curricular activities, so I was always into a lot of things. I mean sports; I was a terrible athlete. I’m tall, but my left hand doesn’t know what the right hand is doing, so I would only get in the game after we were already behind by 50 points, and, but I was the scorekeeper.

I was a terrific scorekeeper, you know, so I became manager of many of the sports teams in high school, and also in college. I was manager of the cross-country team, I was manager of the basketball team, I was manager of the baseball team, so I was a six or seven letter man without being able to do anything athletics, you know, whatever.

But I’m sitting there at the score table during the basketball tournament, and- a basketball game, and like, I’m talking a mile a minute to keep the other scorekeeper confused, so that he wouldn’t know, you know, if somebody said, who’s the fouler? And I could tell them, you know, who the foul was on, based on, you know, who it was most desirable for us to have the foul be on, rather than the person who really committed the foul, because the guy’s, you know, very mixed up by the way I’m talking. But anyway, I don’t think I won too many games at the scoring table, but I was the person who went along with the team and kept the scorebooks.

But all these extra-curricular activities were something that I had time to do, because my parents hadn’t advanced me, and so you know, I could do well in my classes but also participate in lots of other things.

Now my, but, you know, so here I am, doing rather well at school, but I’ve still got an inferiority complex. I’m still always trying to prove myself. I’m thinking, you know, maybe I’m not getting it well, and in fact, so I was probably taking, you know, studying hard and getting 100s on these exams, because I’m trying to prove that I knew it. You know; if I was really overconfident, so confident, I wouldn’t have bothered to study. And that was, so that was one of the child’s eyes looking at it. I’m always scared that I’m not going to do well, so I was working hard at schoolwork.

The funny thing was that my; when I was being advised what to do for college, well, everybody in my school took a whole bunch of tests, national tests, and one of the tests was vocational, you know, what job are you cut out for? And I remember that that, according to that test, I should be an architect, and I should not be a veterinarian. I scored extremely low on veterinarian skills, but for architect, that seemed to be the career path that was recommended to me.

But the, and I won scholarships to different colleges, but the people at my high school, the Vice Principal called me in; he said, “Don, I think you’re going to be a failure in college”. He said, you know, you’ve done well here in high school, but college is completely different, and you’re just, you know, it’s just going to be too much for you, you’re not going to, you aren’t going to make it. And, well, so he scared me again, and when I got to college I kept studying.

In fact, just the week before college, the Dean of Students, whoever it was, told us. I went to Case institute of Technology in Cleveland, which was at that time not yet connected with Western Reserve University. So I went to Case, and the Dean of Case says to us, says, it’s a all men’s school, says, “Men, look at, look to the person on your left, and the person on your right. One of you isn’t going to be here next year; one of you is going to fail.” So I get to Case, and again I’m studying all the time, working really hard on my classes, and so for that I had to be kind of a machine.

I, the calculus book that I had, in high school we — in high school, as I said, our math program wasn’t much, and I had never heard of calculus until I got to college. But the calculus book that we had was great, and in the back of the book there were supplementary problems that weren’t, you know, that weren’t assigned by the teacher. The teacher would assign, so this was a famous calculus text by a man named George Thomas, and I mention it especially because it was one of the first books published by Addison-Wesley, and I loved this calculus book so much that later I chose Addison-Wesley to be the publisher of my own book.

But Thomas’s Calculus would have the text, then would have problems, and our teacher would assign, say, the even numbered problems, or something like that. I would also do the odd numbered problems. In the back of Thomas’s book he had supplementary problems, the teacher didn’t assign the supplementary problems; I worked the supplementary problems. I was, you know, I was scared I wouldn’t learn calculus, so I worked hard on it, and it turned out that of course it took me longer to solve all these problems than the kids who were only working on what was assigned, at first. But after a year, I could do all of those problems in the same time as my classmates were doing the assigned problems, and after that I could just coast in mathematics, because I’d learned how to solve problems. So it was good that I was scared, in a way that I, you know, that made me start strong, and then I could coast afterwards, rather than always climbing and being on a lower part of the learning curve.

10 - Why I chose to go to Case Institute of Technology

In high school, as I said, mathematics was just confusing to me. When I got to Case, though, the teachers, the chemistry teacher was, seemed to know chemistry okay, but he didn’t know anything about physics or math. My physics teacher knew physics and chemistry, but my math teacher knew all three subjects, and I had terrific respect for him, because he seemed really smart, and also he was very hard to please. No matter, you know, I could show him what I was doing in calculus, but he would, he never seemed to be impressed, so this was frustrating to me. I’d never had a teacher that I couldn’t impress, you know, so I worked even harder at my math. But he had a good sense of humor, and his name was Paul Guenther. And finally, after two years, I was able to impress him a little bit, and so this was good. But I developed an interest in Mathematics, but I have to go back a little bit.

I, when I was choosing what college to go to, I had won several scholarships, and one of the scholarships would have been to Valparaiso University in Indiana, associated with the Lutheran Church, and it was, but there I would have been a major in music, and the other scholarship was to Case in Cleveland, which was where I would major in physics, and since my mother’s family is from Cleveland, she knew that Case had very high standards, and very few people that she knew were able even to be admitted to Case, and there was, considered to be one of the hardest schools to do. I’d never heard of MIT, by the way, until some years later, or much less Caltech. But Case, to me, was a challenge, where I would really have to work hard and well, Valparaiso, it would be something where I could just do some; music would seem to me much easier. And I decided to go for the challenge, at Case, and I was admitted to; they had a special section for Freshmen, called the Honors Section, where 20 of us were given, were taught each of our classes by the heads of departments. So I really had the, Case’s best, you know, physics teacher, chemistry teacher, math teacher and English teacher.

11 - University life: my basketball management system

I believe it was the first year they had tried this, and I’m not sure how long they continued the experiment, but the teachers, but what they called us the Honor Section, and this just meant that 20 of us just took all our classes together, while other students would tend to mix. I don’t think the other students all spent Monday, Tuesday, Wednesday the same as, the same hours, like we did. And so the classes that I had, then I think they challenged us a little more too, than they challenged the other students, perhaps.

Still, I had time to do you know, to work on the school paper and to, one of the important issues of going to Case at that time was to join a fraternity. The, most of the interesting action on campus would be centered around the fraternity system, and so I pledged a fraternity also in my Freshman year, and I guess I can say more about that.

But I had mentioned that during the spring of my freshman year is when my Mad Magazine article came out, you know, and so that well, that led later to, later on I was editor of a magazine that we founded at Case, called Engineering and Science Review, which wrote about topics in science, and I wrote an article about Potrzebie System for that publication. I was in the music, I was in the basketball; I was manager of the basketball team, at Case.

And I’ll say a few words about that, because after I got into computers later on, I combined that with my managing the Basketball team. So I devised a strange formula that I don’t believe in much any more, but anyway, I had it at the time, where you could compute each basketball player’s real contribution to the game.

Not just the points that he made, the baskets that he made, but really you know, taking everything into account, so for example, if you have possession of the ball in basketball, this is worth something. In fact, when you’re watching a basketball game, if you sort of add one point to the score of the team who has the ball that sort of gives a more fair indication of what the real score is of the game. So possession of the ball is worth maybe one point. You can work it out after the game; you can say, really, how many times, when you had possession of the ball did you really turn over, and fumble it, or you know, how many points did you really get during that series? And so you can work out that it may be worth only seven-tenths of a point or something like this. But anyway, possession of the ball is worth something. So if you fumble, then you’ve lost your team one point, or seven-tenths of a point. So that’s a minus something for you. If you steal the ball, if you recover a fumble, you gain; your team gains possession, so you get credit for stealing the ball.

If you make a basket, in those days it was only two points, you don’t have the three-point shots in those days, but if you can make a basket you get two points, but your team also loses possession, the other team gets possession, so you don’t really; you didn’t really win two points for your team when you made the basket, you made two points, but you have to subtract from that, the fact that you have to get the ball again.

So at the end, according to my formula, the sum of all the players’ contributions would be the amount by which our team won or lost. But it would rate, you know, if somebody makes a shot and misses, then sometimes our team gets the rebound, sometimes the other team gets the rebound, so I, you lose a little bit for taking a shot and missing. So I calculated a huge number of statistics for every player, and I had a spotter, who would call to me, and I could write it down, every little thing, and after the game I would go and punch cards that recorded all these statistics, and fed them into a little computer program that calculated the formula and made a list for every player, what their real contribution to the game was, not just the field goals and all these traditional statistics.

So Case’s Coach, Nip Heim, loved this system, and you know, he posted these numbers, and the Case News Service was always good at trying to plant interesting stories in the local paper, so they sent reporters out to, and we showed, you know, told about this formula, and IBM heard about it. So IBM sent out a cameraman, a camera crew, to make a film of me spotting a game, you know, and there, our Case team playing basketball of course, but then, how I would punch the cards, you know, and put it into the IBM computer. Before they took the shot of the IBM computer, they planted a great, big IBM sign on the machine, so that nobody could fail to miss it, you know, that I was doing this, and then I’m turning the buttons on the console, and getting the numbers out, and it’s getting printed out on the IBM printer, and then the Coach is looking at it and posting this up.

So this was a little movie that I was in, about two or three minutes long. IBM supplies this movie to CBS, and they put it on the Sunday Evening News with Walter Cronkite, and all my relatives in Florida can see me on TV. This was very exciting. Also US News and World Report ran a story about it, and so this was my connection between computing and sports, when I was at Case. This was also a clever way for IBM to get their advertisements in there, rather subtly, but it was a fun.

That was when I first realized how hard it must be to be a movie star, because I had to walk through these scenes six times everything, you know, punch those cards over and over again. So I can see, how could Audrey Hepburn possibly look so beautiful after the sixth take, you know?

12 - University life: the fraternity system

At Case, as I said, I pledged a fraternity. That was one of the things that — I’d met a few Case graduates in Milwaukee, or Case students, before, and they said — oh, Don, fraternities are the big thing at; you’ve got to take that very seriously when you go there. Well, anyway, the fraternity system was maybe a little different then than it is now. It certainly had its pros and cons, but it was a big; it was certainly a focus of my life at Case, because after my freshman year I would live at the fraternity, and with all my fraternity brothers.

The first thing, though, was something we called Hell Week. Raising. This is, or hazing, I mean. I’m sorry, forget that I said raising. And for seven days, all of us pledges, before we could become full-fledged fraternity members, were at the mercy of all the other brothers, who would have their paddles, and also, you know, we were sleep deprived, and basically they were, we were also cleaning the fraternity house, so that’s when I learned about ammonia and painting things, and scrubbing walls, and doing other, you know, fixing the roof, and things like this, that we would be doing, but then, but meanwhile they would also, they would play tennis where we were the balls, and they would, you know, swat us, and it hurt; and do other things to make sure that, you know, we knew that they had the power and we were just unimportant now.

So this is illegal now, and, but it was my equivalent of going through boot camp, I guess, which, you know, I never went into military service. And, you know, I matured an awful lot during that week. After that week, and I’d gotten through without the, you know, this time, I had a confidence that I’d never had before, so it’s hard for me to say that I wouldn’t want my son to go through the same thing. I don’t think he ever did, but it’s a paradoxical thing, in my estimation. Still, that was part of getting into the fraternity, and I have a picture of myself that they took at the end of it, unshaven, and looking pretty beat, but still knowing that I had come through an ordeal, which was something; it’s a question in my mind, how to really give that education to somebody in a way that is legal, would be legal. Now we’d have people suing.

13 - Meeting my wife Jill

At my fraternity, my best friend, who was also in the Honor Section at Case, his name is Bill Davis, he now, by the way, is a mathematics professor at Ohio State, and is very active in internet online education for teaching mathematics, but anyway, Bill and I were bosom buddies during my freshman year, and he, and then also in the sophomore year we both pledged Theta Chi fraternity, and so then we also went through Hell Week together and had rooms next to each other in the fraternity house.

So I started to date a girl at Western Reserve University; her name was Betsy, and her roommate was named Jill, and Bill was dating Jill, so I was — now, Betsy was Catholic, and I was Lutheran, and this was something that we thought, well, our families would never be able to understand, but still I thought that Betsy was pretty terrific, but I was also dating a girl named Becky, a Jewish girl, whose father owned a department store in Cleveland and I was dating some nurses too, you know, there were lots of girls would hang out around the Case area, and, but I was mostly interested in this Betsy, and I was, I decided to, and we’d had double dates with Bill Davis and his girl Jill, and as I said, Betsy and Jill were roommates; Bill and I were roommates.

So I was wondering, you know, how I’d ever be able to make more of a hit with Betsy, and I decided I would have lunch with Jill, to ask her for advice. And so this was probably the, my sophomore year, the spring of my sophomore year, and, you know, she was such a good listener, and gave such good advice, that I started dating Jill instead, and well, I’m not sure Bill ever forgave me for that, but she didn’t really like him, she thought, she said, well, anyway.

Well, anyway, Jill is the one that I eventually got pinned to, and engaged to and married to, and we’ve been married now for 45 years. And Jill and I started having dates in the library, where we would study together, and, you know, I found that I enjoyed kisses for the first time, when they came from her. In high school I was afraid to kiss girls, even when they would stand up.

I mean, I was dating a girl in high school who was about four and a half feet tall, I don’t remember her name any more, but I remember that she was real cute, because, I always liked short girls, because they seemed to, you know, have a good balance, they didn’t fall over as easily as tall ones, and I, being tall, I was, you know, but she was a cheerleader, and she stood on the steps of her house, and with her lips turned up, and I figured I’d got to kiss her, but I’d never done this before, how am I going to do it you know.

And so I did, but I never realized how good it could be until I kissed Jill, when I was a sophomore.

14 - Bible study at university and a time of personal challenge

I’m not a real involved with the groovy set, I guess, throughout all my student time, and I remember then Jill and I started getting to know each other real well, and we would go to church together on Sundays. She was a Methodist, I, we studied, we went to Bible Study classes at her church on Sunday School. I had never gone to Sunday School, because I went to a Lutheran School as a child. We had something about Bible during the week, so why should I do something, why should I do anything more on Sunday? I’ve had plenty of religion during the week. But she had gone to public school and she, her tradition was to go to study the Bible on Sunday mornings, and so I went with her to church, and I learned something about that.

In college, our teachers were, I was introduced to lots of atheists, and people from lots of different religious experiences and this was something totally different, totally foreign to my previous experience, and I, so I went through a time of personal challenge, where I was trying to say, well, what do I really believe? Up to that time I had just, I had just listened to what my teachers said and passed the exams, and did what was expected of me, but I internalized something about what, you know, is there a God, and if so, how do you solve various paradoxes associated with God?

And I went through that kind of experience during the Freshman and Sophomore years mostly in college, before I became somewhat comfortable with my, with internalizing what I had been taught as a child. And I’m sure that if I’d come from another background, I would have turned out differently, but, and I personally believe now that God is alive in many ways, but I do believe, you know, I do believe that God is somehow, mysteriously, involved with our universe, and that underlies a lot of what I do, and I also know I will never be able to prove it, but I’m thankful that I could never prove it, because if it was proved, I think then I would lose interest in the whole subject; there would be no mystery, and no interest in it.

So I, as they say, the growing up in a religious way took place during this time, when I’m meeting my future wife.

15 - Extracurricular activities at Case

I was on lots of sports teams, the cross country team, baseball. We would have a chance to; we would have a chance to travel to lots of other places then, with the team. That was fun as well. I worked on, I was the founding editor of this magazine, The Engineering and Science Review, and then, active in various other things, for example I was vice president of my fraternity.

There was one story about the newspaper and my fraternity I might as well mention. That we, I was, I would go to downtown Cleveland, where the newspaper was being typeset, and that’s where I first got experience with Linotype machines, and the way real printing was done. And I would be the, at first I was the copy editor, so I would check for errors in the text, before they did the final print run, and I noticed that there was a story about one of our Theta Chi fraternity parties, before Christmas, and it said that we had served hot buttered rum, and, well, it dawned on me that we actually weren’t supposed to serve rum at a fraternity party, and still, it was a linotype machine, and you had to pay for every correction that you made, and you had to keep your corrections to one line, if they had to reset several lines — so I changed it to hot buttered popcorn. And that worked out okay for the — for the story.

Now, so I got more experience in writing, publishing, during that period, and we had the Chair of the English department as my teacher, as freshmen, and we had very good teachers also, you know, in my Western Civilization class, sophomore, junior years, so all the time I was writing. I was writing stories for, I was, you know, writing term papers, but I was also writing for campus publications. And I came to believe that really my education boiled down to 50% mathematics, 50% English; 50%, you know, writing skills, and somehow combining those two things, for the rest of my life is what everything else was somehow a mixture of those two things.

I was in so many extra-curricular activities in fact, that Case has something called the Honor Key, which is based on points. You get so many points for being in the band, so many points for being in a fraternity, not very many for that, but certainly for the newspaper and for singing in the choir, chorus, and participating in other campus things, and if you get a certain number of points then you win the Honor Key, and at, you know, at Graduation Day they’ll mention the four or five students who have won the Case Honor Key. Well, it turned out I had enough points to win the Honor Key, but after three years, and, you know, so I think I had more points, more Honor Points than anybody else had had in the history of Case, so again I was, you know, a machine, saying, “Oh? There are points for this? Okay, I’d better do this.” And I signed up for these things. So I was involved with lots of extra-curricular stuff.

I also had a chance to do a little bit of writing music. I wrote a five-minute musical comedy for our fraternity to perform at the whatever they call it, the oh, I forget what it was; it was an annual thing, where each fraternity would put on some kind of a skit. Varsity Day, or something, I can’t remember what we called it. And we would go to a theatre in downtown Cleveland and perform for whoever wanted to listen in. I wrote this five-minute musical comedy called “Nebbish Land”, based on nebbishes, you know, these were popular in the Greeting Card Industry at the time. And that I still have the score for, so maybe I’ll, maybe I’ll put some of the music for that in my book on fun and games.

16 - Taking graduate classes at Case

At Case I put a lot of time into stuff out of class, but in class, I found a really clever way to, right now, let me brag this way to say, to avoid having to study too hard, for my classes. In the first place, I noticed though, that when I was a sophomore, my grades started to go down, in the first part of my sophomore year. And I ascribed it to too much ping-pong playing and playing cards too much in the dorm, and so; no, I’m sorry; this was the second half of my freshman year. I started having a little problem with my grades, and so I had to give up ping-pong.

But starting in my sophomore — junior year, I found out that you could take graduate courses at Case, and they were easier than the undergraduate courses. The reason is that Case had really strict admissions requirements for undergrads, but they were fairly loose about admitting graduate students. I think they wanted to build up, you know, admit graduate students, so when you had graduate students, in a class, they usually didn’t know as much as the undergrads did, so if you would take a graduate course, you didn’t have as much competition, you know, and the teacher would recycle stuff, and all this. So I started taking graduate classes, and you know, and all these hotshot undergrads would be taking the other classes.

And as a result, I had accumulated also, by the time I was a senior, I had accumulated lots and lots of graduate credits. Now, as a result then, Case did, on Graduation Day, Case did an unprecedented thing that had never been done before, they awarded me a Master’s Degree, simultaneously with my Bachelor’s Degree. And this, the faculty had gotten together and made a, and voted unanimously that this should happen, and I remember, you know, that was another thing that got into the newspapers at the time, that they were awarding a Master’s Degree at the same time as a Bachelor’s Degree. So, but the reason was that I had taken these graduate courses because they were easier. I didn’t, I don’t know if I’ve ever told anybody else this before today, but that was one of the reasons I could do so many other things.

17 - Physics, welding, astronomy and mathematics

I started in physics, and I continued in physics; as I said, I liked my math teacher very much, but I was a physics major, and in sophomore year I had another very good physics professor, and started learning quantum mechanics, and had classes in astronomy, and I also had a class called, I don’t know what it was called, but it was a laboratory class.

All physics majors were required to know how to do things like welding. Now, I was always very bad at lab work, in chemistry lab, I was always the last to finish experiments, and I would break the beakers and get chemicals on my hands and burn them and things like this, and start fires, things; it was bad, but when I got into this welding, this class where I’m supposed to do welding, it was just dreadful. I mean I couldn’t see, you know, I wear rather heavy glasses, and we had to wear goggles while we were welding, but the goggles wouldn’t fit over my glasses, so I couldn’t, you know, so I couldn’t wear my glasses and my goggles at the same time.

So I’m sitting there with these goggles that I can’t see very well out of, and I’ve got this electrical thing, which is thousands and thousands of volts, where I’m supposed to be welding material, but the table is way lower than I am; I’m kind of tall, and so I, and so here I’m holding this thing way out of my range, and I’m supposed to, you know, I’m supposed to get, solder things together, or whatever you call the stuff, and when I was supposed to put, to get one thing attached to another, the teacher would, you know, would pick it up and it would fall apart, by its own weight, so I was failing in welding class. And it was terrifying too, you see, with all this electrical juice going on in there, and me not being able to...

My astronomy class, I found out that it was very frustrating. I could pass all the exams, in fact I got a 100 on every exam in my astronomy class, but secretly I hated the subject, and I decided that I would continue the classes as self-discipline, because I didn’t want the teacher to know that I hated the class. And I figured, you know, I’m not going to be, I have to learn how to do stuff that I don’t enjoy as well as stuff that I enjoy. So I studied very carefully for the exams in astronomy, but I really — and why didn’t I like it?

I’m trying, I believe it’s just because I was just, I couldn’t imagine how, they were so different from mathematics, in astronomy you would never be able to go to the sun and really know what it was like there. You always had secondary information. If I would be an astronomer, I would never, I would, I would have to die before I would know anything, which was really true, because it’s all based on speculation. It’s all based on our best guesses about the way the universe is, and nothing that you can really experience yourself, or prove correct. In physics, the same way, nature is beyond our grasp, and you don’t know.

But mathematics was different. Mathematics had this certainty about it that, where you could finish a problem, and you could say, you know, I know I’ve got the answer. And so I like that. It was easy. It’s much easier; you know, I have to admire the people who, the scientists who spend their life and never know whether they’ve solved the problem or not, they just get supporting evidence for or against it, but to me, anyway, mathematics got more and more appealing, for the reason that it gave me some certainty; just the opposite of the reason why religion was appealing, because it didn’t have certainty, I mean I would feel unhappy of the life where I had nothing certain, and life where I had everything certain. In either extreme, life, it’s hard for me.

18 - My math teacher at Case and a difficult problem

I gravitated toward mathematics. And there was another reason. Our mathematics teacher was very, was a very eccentric guy, and also very hard, my second year mathematics teacher, also hard to please, and he had quite a reputation at Case, because, a couple of years earlier, he had flunked the entire class. He decided that none of them was learning anything; he gave F to everybody in the course, so Louis Green was a legend at Case.

And I was taking his class, as a sophomore, called “Basic Mathematics”, which he had written the textbook for himself. And that was a course where you, stuff like, lot, things that are different from the continuous things that physicists study. And there must, you know, there must be something in the way I grew up that made integer numbers more appealing to me. I, I mean it’s associated with computing, as everyone knows now. Of course computers didn’t exist, or hardly existed in those days.

I’ll speak more about my first view of a computer later, but the, here we are, in Louis Green’s “Basic Mathematics” class, and I’m getting to a different kind of mathematics than calculus, and one day he gave a problem to the class. He said, “Here’s a problem that I don’t think — if anybody solves this problem, I’ll give you an automatic A in the class”. And the problem, now, it turns out, well, I can state the problem, he said, if you, putting parentheses around into a mathematical formula, if you have a formula with five variables, A, B, C, D, E. How many ways can you put parentheses into that formula so that you are combining two things at a time?

So you could say, A, you could say, parenthesize AB, and then parenthesize C, and then D or E, or you could start with B and C and combine that with A, and so different ways to do this. So if you start out with n of these variables, and you put, you combine with parentheses, what, how many ways are there to do it? And this, by the way, is something very dear to the hearts of computer scientists now, because we call it the number of binary trees with n leaves. But Louis Green gave us, as a problem, as a challenge, could we determine this number? And if anybody could, he said he’d give an A to them.

Well. I don’t know to this day whether he knew the answer to the problem or not, but I have found out subsequently that the answer was published in the 18th century, and, and had a long history. And so these numbers are so famous now that one of my friends, Richard Stanley at MIT, has found 128 different interpretations of these numbers, parentheses is just one of these 128 ways. And he’s collected that many ways. In fact I had the honor of discovering number 128 last year, when I was with him in Sweden, but that’s; anyway.

My sophomore year, Louis gives us this problem, and we all knew Louis’s reputation, so we figured, why work on the problem? He’ll never give out a problem that we could actually solve, why should we, you know, why should we waste time on this silly thing? But it turned out that I was on the football, I was in the band, actually, not the football team, and our band was going to play in Detroit, at the football game, on Saturday, but I missed the bus. I got up too late, so I was, so I found out the bus had just left for Detroit, and I had a whole, and I had figured I’d spend all, you know, a wasted day, all day in Detroit.

So I figured, okay, I’ll work on Louis, I’ll spend this day thinking about Louis Green’s impossible problem. And I got lucky, and figured, and found the answer to it, and so I wrote it up on two sheets of paper, and turned it in on Monday morning, and he looked it over, and on Tuesday, he said, “Okay, you get an A in this class.” So I’m still a physics major, but I took his math class, and so I cut class the rest of the quarter, and he lived up to his agreement, and I got an A on my, on the score.

Well, I felt a little guilty afterwards, having cut class, so I served as his grader for his course the following year. But that, what was I going to say? So, but that summer I switched into mathematics as a major, because of my experience with the welding in physics, and because I found that mathematics was something that I would be able to actually prove, prove correctness, and that, this appealed to me. Still, I didn’t study mathematics that much, because I already had the A, and an A was what I was looking for in my college grades.

19 - My interest in graphs and my first experience of a computer

How did I get into computers? I had a scholarship to Case, but it was, it didn’t cover my whole tuition; it just covered part of the tuition, and so I took a part time job. My parents had no money, and I took a part time job working in the Statistics Department. Taking, and one of the things I would do, would run a card sorter, an IBM card sorting machine, which was kind of a fascinating thing. You put the; take these punched cards, and you put them in the thing, and it distributes into different pockets, and then you pull them out in certain orders, and afterwards look at the results, and you draw graphs. And so I was drawing graphs for the Statistics Department.

I guess I should say something more about graphs, while it flashes into my mind. In high school, I had taken time, one summer, working with; I was fascinated by this idea of graphs in mathematics, where you have, you know, as a function, as variable X varies, you have Y as a function of X, then you draw the position that’s Y units above the axis, and it makes a picture. And since I like visual things, I was fascinated by the idea that I might be able to take, start with the picture that I wanted to do, and find the equation that would, when you graph the equation, you would get that picture. And so I played around with graphs. I spent one summer in high school, I had drawn hundreds and hundreds of graphs, where I would take, where I would take an equation like the square root of X? + 5, 5x, minus something else, and I would, and then I would draw the graph.

And I had, and my dad had a little calculating machine, which was a, where I, which could calculate square roots. It actually would print it out. He was an accountant, so it would also print it out on tape, that I could run this machine and it would do the multiplying and stuff for me, and then I would have this function of, and then I would say, instead of X? + 5x, I would maybe change it to X? plus 4x, and draw that graph too, until I would learn how different graphs looked.

I didn’t have calculus, I didn’t know calculus in high school, but I did know how to graph an equation, and that fascinated me, so I had played, I worked so hard on this, in fact, on this orange graph paper that I had, I started to get headaches, it was not easy on the eyes, and I think I started wearing heavier glasses at this time, because I worked on the graphs, but this had given me some experience with graphs, and liked, I liked that kind of mathematics, even when I was in high school.

So now, I got my first, I got my first part time job at Case; I’m supposed to draw graphs for the statisticians. So that’s fine, and downstairs from the sorting machine was a new computer, an electronic brain, as they called it, in those days, and it was the first, it was called the IBM Model 650. This was the, historically, the first computer that was mass-produced; there were more than 1,000 of them. Before that, computers had; no computer had been made more than a few dozen at the most.

And this computer arrived, about midway in my Freshman year at Case, and it was sitting in a room downstairs from the Statistics laboratory, where I was working. So I could peer through the window at this computer, and with its flashing lights it looked rather exciting. And one day a guy saw me looking through the window, and he said, he invited me to come in, and he explained to me how the machine worked, and so it was quite fascinating to me that it could do things much different than this mechanical calculating machine that my dad had shown me.

So I took a look at the operating manuals for the machine, and pretty soon I, he allowed me to punch cards that would go into that machine, as what; you know, I knew how to run a sorter, but now I could actually punch a card that would make a computer program. And I, and so I began to learn something about the inside of this machine.

20 - Learning how to program on the IBM 650 (Part 1)

I read the manuals that came from IBM, and it had; the manuals had example programs in there, and I thought of better ways to write those programs. I thought of, you know, well, okay, this program works, but if you did it this way, it would be even better. And so that’s given me some confidence that maybe I had a talent for programming. Now, if the manual hadn’t had these bad examples in it, I probably would not have gotten interested in programming, because I wouldn’t have this confidence, and I would have been scared and say, oh, I would never think of this.But the fact is, the manuals were pretty stupid, and that’s what gave me the confidence that I should think a little more about programming, because I might be, you know, I might be good at it.

So, you know, I started to learn a little bit about computers in my Freshman year, then when I pledge at the fraternity, one of the fraternity brothers had a problem that he needed to solve, and he was eval — finding the roots of fifth degree equations. And I had learned about a program called the Bell Interpretive System that was, that looked like it wouldn’t be too hard to solve this problem on, and so, since he was, you know, he didn’t really want to do it himself, so for my fraternity brother I wrote a, I wrote something that would, could do one of his homework problems for him, and that was, and it seemed to run correctly the first time. I find it hard to believe, now, but it, as far as I know, it did.

And so he was happy about that, and I, you know, and I got more involved with the people at the computing center, where, when I, when they stared letting me use this IBM machine during the night. And so between my freshman and sophomore year, I was, I had a part time job at the computing center, working for them. Really, they allowed us to write software that other people, other students, would be using.

The first computer program I wrote, and it was the following; I had to find the prime factors of a number. So you would dial in on the console of the machine; there were rotary switches, and you could set the switch to some number, like 100, and then it would punch out 100 is equal to two times two, times five, times five. So we find the prime factors of the number you dial on the console switches.

I still have a copy of my program for that, that I wrote, and it started out something like 60 or 70 instructions in the program originally, and two weeks later I had the program working correctly, and it had about 130 instructions in it, and I think I had removed more than 200 errors, during the time. I mean I not only learned about programming, but about making errors. So what can go wrong when you? Well, anyway, I did, I didn’t really know that much about programming, at the time, but I learned it a heck of a lot by this exercise of trying to find prime factors of a number.

21 - Learning how to program on the IBM 650 (Part 2)

So I learned certain things like, what’s; this was a decimal computer, it worked not in the binary system, but in the decimal system, and you had ten-digit numbers, so I could learn, so it was also very slow, the division instruction in the machine took four milliseconds, that’s a, I think it’s something like four nanoseconds, in other words now machines go a million times faster. But you know, incredibly slow by today’s standards, but, so you couldn’t do that many divisions per second.

And my method of finding prime factors was just to try dividing you know, you can divide by two? No. Divide by three? No. Divide by four? No. Until you find a factor. So now you take the largest ten-digit number that doesn’t have any factors. This program would take a long, long, long time. So one of the things I had to do was make it go a little faster. I wouldn’t divide by two and three and four and five, I could skip over the even numbers if it’s not divisible by two, it’s not divisible by four.

And, you know, I had to do things like that in order to, then I, as soon as I got up to a five digit divisor, then I could stop; I didn’t know then back then, you know, I didn’t realize that at first, but I didn’t have to divide by every possible thing, because if it has a divisor at all, the smallest divisor has to be less than the square root of the number you’re looking at, less than or equal. I think I first thought less than, and then I, then I found I had to change my program to less than or equal.

One of the most subtle bugs was, and it took me, and it took me a hard time to do it, was the following. What if the number had lots and lots of prime factors? Well it turned out there are ten-digit numbers that have, I could only punch eight prime factors on a card, on the answer card, and so I would have to prepare my program, because I mean you can have more than 30 prime factors, so I could, so I had to change my program so that it wouldn’t only punch one card as the answer, but it would also punch up to four cards.

So anyway this was, I’m just trying to explain why this little program of finding prime factors was so instructive for me at the time, and I did it near the end of my freshman year, and I was allowed to spend all night sitting at the machine, turning the dials, turning the buttons, and Case had an extremely intelligent attitude toward undergraduates. They allowed us to go and touch the computers, do everything ourselves, work overnight, sleep in the, you know, in the room, and write programs that would be used by other people on campus.

And Stanford had a completely different idea. If you used the computer at Stanford, I learned later, they had a professional staff that had been sent to them by IBM, of scientists who would do the; you would submit the job to them, they would put it through the machine, and you know, you’d get your answers the next day.

Case, all hands on, we are allowed to all that stuff ourselves, and even, they didn’t worry that we were going to break the machine, you know, we’d learned how to open up the panels, and you know, when paper jams and cards jam, and things like this, or, we could wire the boards and all that stuff. So what if we’re freshmen? That’s okay. And I think Case and Dartmouth were the only two universities that were so liberal for allowing undergraduates to play with the machines in those days.)

22 - Writing a tic-tac-toe program

So I got my summer job at, in the computing center, so I didn’t come home to Milwaukee, except for a short trip that summer. And this was before I had met these girls I was telling you about, in my sophomore year. So I had only the computer to be with, and my second program was to change the numbers from decimal to other bases, but my, but that was a fairly quick.

My third program is the one that I spent the most time on at that time, was to play tic-tac-toe. Now I found out later that a lot of computer scientists have worked on tic-tac-toe, Charles Babbage, the famous guy who, you know, was planning a machine that could do tic-tac-toe in England in the 1800s, Danny Hillis built a tic-tac-toe playing machine out of Tinker toys, that went into the computer museum at Boston. But anyway, I and, I decided I’d write a computer program to play this children’s game, and it was a bit of a challenge.

I wasn’t using Tinker toys, but this IBM 650 had another interesting feature; not only was it decimal, with ten-digit numbers, but it only had 2,000 altogether. So the total memory of that computer was, oh well, let me see, 2,000 times, well what have we got? Five bytes or so? So that’s ten K bytes of memory. Now, right now, if you don’t have ten gigabytes, oh well, ten megabytes, you know, you’re dead. You can’t load Microsoft Windows unless you hundreds of megabytes, but here we had 10,000 bytes, total.

And so I, but I was wanting it to play tic-tac-toe against me. I wrote three versions of tic-tac-toe. One was an expert version, which you know, I pre-planned a strategy that I knew was going to be right. What’s the second version? I can’t remember. But the third version was the most interesting. This was the learning version, where the machine starts out knowing nothing. And it learns by experience. So it, so it remembers all the possible positions on the tic-tac-toe board, just barely enough to fit inside of ten K bytes, and every time it plays a game, if it lost a game, it said, oh, these moves that I made were bad. The moves that the other guy made were good. If it won the game, it said, oh, my moves were good; the other guy’s were not. So it would adjust; it kept; it had one digit for every position, so it would start out like at four, and if you’d win a game it might go five. If you’d lose, it’d go to three. And so then if you had different moves, you’d it would try the ones that looked good in its ranking, and that took me a month to write the program, and I learned a lot playing around with that.

And afterwards I, then I tried the learning program against the expert program, so I would use the expert program to play and train the learning program, so how many times would the expert play against, you know, like I think it was like 120 games or something, then the learning program learned not to lose against the expert.

Tic-tac-toe is a kind of boring game, because if you really know how to play it, every game comes out as a cat’s game; it’s a tie. Nobody wins. But before that it’s interesting. When you make bad moves, it gets really exciting. So then I said, okay, now I’m going to have two learning. I’m going to have the learning game play against the learning game, so both of them start out knowing nothing about the game, and each of them, so originally all their moves are completely blindfolded, and you know, they’re blundering along, but then at the end somebody happens to win the game, or somebody happens to lose the game, so then their strategy changes a little bit.

Well now it turned out that after about 350 games, they would learn how to play conservatively, to draw against each other. It was a very dull game that they finally wound up doing; they played safe moves instead of brilliant moves, but it was anyway, a good learning experience for me, writing this tic-tac-toe program.

23 - Learning about the Symbolic Optimum Assembly Program and the Internal Translator (Part 1)

My family went to a summer camp in, on the shore of Lake Erie for a week, that summer, and, Linwood, it’s called. I revisited it a couple of years ago, to remember. Anyway, it’s on the beach, two weeks we were there, and I would play tennis with my uncles and so on, but I also had brought with me the, a couple of examples of computer programs that I had heard about, and so I had some spare time while I’m at the summer place, to look at these programs. And this made a big influence on my future life, actually.

One of the programs was what they call an assembler, which was, meant that instead of writing in the machine language, you could write in a more symbolic language that would make it easier for, I mean I, when I started my programming I was just programming everything in numbers. And so, if I wanted to add, add a number in location one to the number in location two, I would have to say something like, 20, oh, oh, one, something, anyway, I would have to write all these numbers out, and punch them into cards, and get it to work, and this was all I knew, when I started programming.

But then the symbolic, the assembly program was a new-fangled thing at the time, and allowed me to do it in a way that’s more easier to understand. Instead of choosing a number for every place in my program, I could give it a name, and then the machine would figure out the, you know, what number to associate with that name. And in those days computers couldn’t deal with letters very well, the computers were more set up for numbers, but we were allowed to use capital letters, so we had, so, and in this assembler we could use five capital letters, for a word, and I remember specifically when I used this for my tic-tac-toe program, and I, and I would have to think, what five-letter word would I use to indicate a current part of the program, and I remember, you know, with delight, when I want in my tic-tac-toe program, when it wins, I would go to location BINGO. So I could use the five-letter word B, I, N, G, O, for that part of the program.

Okay, so I’m learning about a symbolic assembler at this time, and so I got the code, all right? So I’m using the assembler, but I was wondering how it did it? How did you know, how, what went on, behind the scenes that would take my symbolic thing that said, BINGO, and put it into numbers that the machine would understand directly? And so I had the listing for this program called SOAP Two, by Stan Poley of IBM.

Then I had also brought with me another listing, from a program called IT, or Internal Translator, and this was a new program; had come from Carnegie Tech, later Carnegie Mellon University, written by four people at Carnegie, and IT took an algebraic language, instead of a machine language. So you’re writing here; it’s a; this is early days, this was before FORTRAN or other high-level languages were known. I’m talking here of 1956, 1957. The idea here then, you can write X = A + B. Ah, well, you couldn’t really write that because we didn’t have plus signs, so we would really write, X one, Z, X two, S, X three, where S stood for plus, and Z stood for equals, and, you know, and every variable was X one, X two, X three or something like this, but anyway, you could put in algebraic formula on your card, and then the machine would figure out, from that, how to compute A + B and store it in X, or whatever you wanted it to do.

So instead of a numeric thing; instead of a symbolic version of a numeric thing, it was algebraic, and you would put your program from the IT language into the computer, and it would flash the lights for a while, and then, punch, punch, punch, punch, and give you a machine language, in the computer’s language. Magic. I couldn’t; I hadn’t a clue as to how this was possible at all, so I got a copy of the program that they had used, to write this IT, translator, and I had a copy of the SOAP program, the Symbolic Assembly, the Symbolic Optimum Assembly Program.)

24 - Learning about the Symbolic Optimum Assembly Program and the Internal Translator (Part 2)

I brought this to the summer place, and I spent nights looking at it and psyching out how this program worked. And, wow, I found; first I figured out how this IT worked, and so, oh yeah, that’s how they can look in the algebraic formula and convert it into instructions, but then, it was terrible style. The program was kludgy. You would read it, and every time they would do something, they did it the hard way. I looked at the SOAP program, the one that came by Stan Poley, it was elegant; it was beautiful; it was like hearing a symphony. It was, whenever it did an instruction, the instruction was sort of accomplishing two things at once. Everything fit together harmoniously; it was elegant code.

I said, boy, I’d love to write programs like this guy can do. And conversely, you know, this clumsy, clunky code that came from the other one, wow. You know, I can do better than that. So a couple of friends and I wrote an improvement of IT, which we called RUNCIBLE; every program had to have an acronym in those days, and RUNCIBLE was Revised Unified New Compiler IT Basic Language Extended or something. We had some reason for the word R U N C I B L E. But we, but mainly we had, we wanted to redo that algebraic language in a way that was more elegant and had more features, and so improve it in, you know, in lots of ways and still stay within our ten K bytes.

And so that was how I spent my first summer at the Computer Center. It turned out that after RUNCIBLE was done, we also, I wrote a user’s manual, for how to write, you know, how to use this program, and curiously, this user’s manual was then used as a text book for students the next year. And so I was in the unusual position of taking a class for which I had written the textbook, when I was a sophomore, one of my classes in computing.

Now, RUNCIBLE, we revised it the next summer, and made it really, lots of bells and whistles, and still with our ten K bytes, but we got a floating point attachment, and we had some other things, so it was, so my friends and I came up with better versions.

So here, this, and I also wrote a SOAP Three, I loved the SOAP Two program we had from IBM, I wrote SOAP Three, which, which improved on SOAP Two, and this was used as the assembler program for other software development that we were doing. So here are Case is allowing about a dozen of us undergrads to write software that’s being used by the other students and faculty of Case, and I, the, Fred Way, who is the director of this program, was very fore-sighted, able to trust the students, and allow, and you know, and to, and we had a, we had lots of fun talking to each other about all these issues, and we did —

New literature of journals — the Communications of the ACM started up in 1958. All of a sudden we saw that there was, there were people publishing ideas from other parts of the world, about how to write programs, and we knew that we had already discovered a lot of these things too, and we had some better science out there. So my second technical publication, after Potrzebie System for Mad Magazine, my second technical publication was about this RUNCIBLE; the method we’d used in RUNCIBLE, to do the conversion of formulas into machine code. And here I sent it to this magazine, the Communications of the ACM, which was, which we had just, began, just, had just begun to come out, and I was totally naïve, not understanding anything about scientific journals or publication conventions.

I had been seeing magazines; I knew what magazines were, and so on, but no people, but there was no idea of credit for something like this. It was just the story that was important. And so, when I wrote this up, I was, I considered myself to be a spokesperson, spokesman for these guys at Case Computer Center, who had been working together to create RUNCIBLE, and I, you know, so I, so I wrote an article about the methods that are used in RUNCIBLE. Nowhere in the article did I mention the names of these other guys, who had been working on it, and I didn’t know that I was going to be getting credit for any of these ideas, I just wanted to describe the ideas, and so this was a, you know, a, I learned later more about, about the scientific conventions of publication, but I was just, you know, I was just a journalist, and I was treating the story as that. So we set the story right when the article was published as part of my collected works a couple of years ago.

25 - Adding more features to RUNCIBLE

In those days, computing was so different from what it is now, not only was the memory tiny, only ten K, and the speed was slow, but also we, the way we wrote programs, well maybe as a result of that, the way we wrote programs was something I would never do today, because in order to pack it into this small memory, we had to do, resort to some trickery that was almost impossible to understand, and therefore highly likely to cause errors.

But one of the things we learned as, early in trying to write software, is that the users of your software always suggest new features, and they’re never satisfied. You give them ten things, and they’ll want ten more, and so we kept adding features and features. That’s called creeping featurism now. But we had only this tiny machine, so how were we going to pack more and more features, when there’s no space for it? And the answer is, we use more and more tricks.

So in this compiler RUNCIBLE, there were four versions of the compiler. You could ask it to produce computer instructions for a machine that did, that had the so-called floating-point attachment, or maybe your computer didn’t have the floating-point attachment, so you either had floating point or not. If you didn’t have the attachment, then you would have to go through a slower routine that would simulate, and pretend that the attachment’s there. Then you could also ask it to compile directly into machine language, or you could ask it to compile into the symbolic assembler language. The symbolic assembler would be able to produce slightly better final product, but it would take longer, because after you got the symbolic, you’d have to take those cards and run them through another program before you could run them. So we had, so either floating-point or not, either symbolic or not, it was four different possibilities.

So we wrote it, we wrote the program in such a way that there was a floating-point set of instructions, and a non-floating-point set of instructions, each of these we had exactly, let’s say, 731 positions of memory for, so you’d swap out those 731 for another, and similarly for the symbolic and non symbolic, you could swap out two parts of the program; each of those parts of the program had to be the exactly the same size, in order to pack it all in.

Somebody asks for a new feature, or we want to extend the language a little more, then we think of a way to do it for the floating point, but then we have to think of a way to shorten the non floating point part of our program, so we kept on revising this program until it was really inscrutable. I mean every, all kinds of tricks were used for that. When I’d have a constant that was used in one routine, I would also make sure that it could be used in some other routine, for some other, completely different purpose. Almost everything in the program had many uses, and therefore a few months would go by, and we’d forget about these tricks, and we would try to change something else, and something would go wrong.

So it was a very shaky, bad way to do software, but it was the way that, the only way we knew how to do at the time, and it was, and people couldn’t believe that we were able to do with such a small computer, to do as many things as it did.

26 - Wanting to be a teacher and why I chose to go to Caltech

I never thought of that as a career. That was my summer job at Case, but there was no such thing as a career in computers, and computers were just this weird thing on the periphery of society. What did I really want to do, as my own career? When I was in grade school, I wanted to be a grade school teacher. I wanted to, you know, if I was in sixth grade I was thinking of myself as a future sixth grade teacher, seventh grade and so on. And in high school, I wanted to be a high school teacher. I always viewed myself as having, as being a teacher later on, and also maybe with a part time job as a musician or something. So I got to college, I wanted to be a college teacher, I got to graduate school, I thought, okay, graduate school teacher.

But I never thought of computer science as a, as part of my career, it was something that I could do in order to make money, to prepare myself for a career that I’d heard about before. It was like, so I was going to be a physics teacher, then I was going to be math teacher, when I switched to math. And I went to, okay, so, when I finally graduated from Case, I had been recommended that I should go to the West Coast, well, no, I chose the West Coast for graduate school, because my family, we would go; finally we had enough money to take vacations in the summer time, and we could drive round, and so we had driven to the different parts of the United States, and I fell in love with California, and so when I applied to graduate school, I applied to Caltech, Stanford and Berkeley. Basically, where should I go to, to do my mathematics?

And I was accepted to all three, and I had scholarships to all three, and, but the, I was specially recommended to Caltech, because of Professor Marshall Hall, who later became my advisor, since at Case we had a visitor, Professor Bose, a great Indian mathematician, who had just, who had been, introduced me to research, and he spoke very highly of Marshall Hall.

Bose, at the time, was doing his famous work about disproving Euler’s conjecture about Latin Squares; it’s an interesting subject, a several hundred year old problem, where people hadn’t been able to construct patterns that are, that are useful in many parts of statistics and combinatorics and Euler and this greatest mathematician of all time, probably, or at least in everybody’s Top Ten, in the 1700s, had conjectured that there was no solution to this problem, and three or four people had even proved that he was right, but there were mistakes in the proof, and so finally, my professor, my Professor Bose and two of his co-workers found that Euler was wrong, and that there were really patterns of that kind. And so Bose got me interested in research, because I was at the Computer Center, and he had a computing problem that he couldn’t solve, and he put me to work on Latin Squares of order 12, and I came back the next morning with five mutually orthogonal Latin Squares of order 12, and this excited him very much, and that was my third technical paper, I guess, was this paper with Bose.

But he recommended Marshall Hall, who was one of the leading mathematicians in the combinatorial mathematics area, and so I liked the idea of going to Caltech.

27 - Writing a compiler for the Burroughs Corporation

During the summer, between Case in Cleveland and Caltech in Pasadena, I had a summer job, of writing compilers, this algebraic, this software that converts algebraic language into machine language. I had a job writing a compiler for Burroughs Corporation. Burroughs was headquartered in Pasadena, I mean the Burroughs Division that was dealing with software was headquartered in Pasadena, and Case had recently installed a Burroughs computer that I liked very much, during my senior year.

Some people from Thompson Ramo Wooldridge approached me and said, Don, we understand that you can write compilers. We’re going to put in a proposal to Burroughs to write a compiler for their machine, the Burroughs 205, for a language called ALGOL, which was just being invented at that time, the Algorithmic Language an International Standard, that was supposed to replace FORTRAN, the most popular language at the time. And so Thompson Ramo Wooldridge was, made a proposal to Burroughs for I believe it was $70,000, to create an ALGOL compiler for the Burroughs 205. The people who made this proposal really, though, were clueless about how to write compilers, so they hired me, a Case senior, to do the job, because they had heard that I knew how to do it. I had done this RUNCIBLE and a couple of versions of other software at Case, so spring of my Senior year, they are showing me, they’re showing me about this machine that Burroughs had, and I started playing around with the computer, and I had learned, got interested in the project, but Burroughs turned them down; they didn’t give them the contract.

So after Burroughs said, no, they weren’t going to do it with Thompson Ramo Wooldridge, well I said, well, wait a minute, I’ve, maybe I’ll write to Burroughs on my own, and I sent them a letter and said, I’ll, you know, for $5,000 I can write you an ALGOL compiler. Now $5,000 was a huge amount of money in 1959, 1960. I mean a college professor was making $8,000 a year or something like this. So I thought $5,000 was an incredibly rich thing, you know, to do. I said to Burroughs, no, I, except that, I can do it in the summer, except I won’t have time to implement all of this ALGOL, I’ll be able to do everything except procedures. I’ll be unable to, you know, which is actually the hardest thing to do in a compiler, which is of subroutines, the ability to extend the language.

Well, they wrote back, you, we can’t have ALGOL without procedures, you’ve got to put procedures in too. And so I thought about it and said, figured out, oh yeah, okay, I see how I can do it, but you’ll have to pay me $5,500, instead of $5,000. So they said, okay. So I spent the summer of 1960, that’s after my, after graduating from Case, I spent the summer writing this compiler for ALGOL, for the Burroughs 205, and I wrote it, but really I had it only in pencil and paper, I didn’t have it ready to go, and then I would take it with me on, as I went out to Pasadena, and work on it there when I was at the Burroughs plant in Pasadena.

So on my way out West; I had a little Volkswagen, that I had gotten from my parents, and I drove 100 miles a day, and got a motel, and sat down, and wrote code, wrote software, and took 30 days to drive from Milwaukee to Pasadena, every day writing a little bit of this software. Then I got to Pasadena, and had all my code, had all my notes, and started putting it on to punched cards, and you know, debugging it and by Christmas time I had their compiler for them, and it was a machine that didn’t sell very well, so there weren’t too many places in the world, but I heard for the next ten years that people in Brazil were still using it a lot.

And so it was a, it was an interesting experience for me, but the most important, from my point of view, was I had $5,500, which was enough to get married. And so in the summer of ‘61 Jill and I got married, and it paid for our honeymoon trip in Europe, which was our first time seeing the world.

28 - Working for the Burroughs Corporation

I got to Caltech as a student, a grad student in mathematics. Again I was scared stiff that I wouldn’t be able to succeed, because the students at Caltech were really, really selective they, at Caltech, the undergrads, one out of three of them was first in their high school class, and the other two out of three were very near the top. And so it was awesome, the people there, but they only admitted 200 students a year in Caltech as undergrads. Graduate students, we had 12 of us in the math program, and they were excellent as well. It wasn’t like at Case where anybody could get into the Graduate School at the time.

So I, so I knew I had my work cut out for me, and I, again I went back into a mode where I did more than I needed to for my classes, but I also liked the people at Burroughs, so I took, and so I took a consulting job at Burroughs, working with their software group, which I had great admiration for. Their software group had, for another computer, the Burroughs 220, had written one of the best pieces of software ever, an ALGOL compiler for the 220, and I got to know the people who did that, and learned a lot from them.

So I enjoyed joining their group, but I wasn’t, but according to the rules, I couldn’t have my, I couldn’t have a fellowship from the National Science Foundation or from the Woodrow Wilson Foundation; I couldn’t have those, that financial support and not be a full time student. Having, you know, it was a no-no to also be a consultant, also be working, working outside Caltech. Wow, your education couldn’t possibly be any good that way. So I renounced those fellowships, and I did become a consultant, and I would spend time over at Burroughs several days a week, and for the next six or seven, seven or eight years, all the while I was down there in Pasadena.

The people at Burroughs were splendid to work with. I was in a group called Product Planning, which designed, had designed, or was, early on was in the process of designing a completely new kind of computer, one that would do in hardware what, what we had been doing in software before. That kind of computer is, is not in, it’s been realized later that it doesn’t really provide a real good cost benefit trade off, it’s better to build cheap hardware and good, and then make software than to build expensive hardware, but at that time it was you know, it was not at all clear what the future would say about that issue. And so we had the most complicated machine ever built, the Burroughs 5000, then the 5500, 6500, that came out later.

And the Product Planning group where I was consulting was the group in charge of specifying the machine. Another group, the Engineers, had to build the machine. It was completely different than any machine done before. And my role as a consultant was to talk to the engineers who were building it and make sure they understood what the designers on the other floor knew.

And so I got, really, to talk to almost everybody in the company, and my role was more of a communications role than anything else. These people, if they went through channels, they would have to go several levels up the hierarchy, and down again, and they couldn’t talk to each other, but they could talk to me, and then I could talk to the other people in the other group, and so I, and so I could provide a valuable service to Burroughs, and they, they would pay me, I think, you know, I think I was getting $5 an hour, or $7 an hour; considered high at the time, but it had no medical benefits or anything associated with it, so from their point of view they were getting a good deal too.

And one of my roles was to check out the designs of the engineers, and see if there were any mistakes in them before they would build the machine. They would first take their designs and put them through a computer program to see if they would simulate, and apparently work correctly, but then, after they thought it was working correctly, then they would show it to me, and I still found several hundred errors in the design that I was able to catch, well you know, very weird cases that could come up, but hadn’t arisen during the simulations, so that the expensive corrections to the hardware weren’t necessary.

You know, really my role in that time, well, communication and trying to find errors, you know, if I could look at somebody else’s program, or design, and couldn’t find any mistakes in it, it was a rare event, and I would feel bad. I mean finding errors was my, was a big treat for me in those days, so far as my work in computers was concerned.

29 - Burroughs Corporation

Burroughs was a company established in the 19th century, and was quite pre-eminent in the banking industry, almost everybody used equipment from Burroughs to do its accounting, and in the early days of computing, Burroughs acquired the Electric Data Corporation, in Pasadena, and they were one of the many companies putting out computers. And, and as I say, not only that, they had very innovative computers, and I liked the spirit of all the employees working there as well.

The — later on, they were acquired by Sperry Rand, this was in the ’70s, I think, and became Unisys, combined with Sperry Rand. So half of Unisys was from the Burroughs Corporation, and half of it was the Sperry, which, the Rand, the Remington Rand, the people who had built the UNIVAC computer. That happened after I was no longer in Pasadena. And they continued to have banks as their primary customer base, but then, in more recent years, the, you know, other companies survived, and there were many, many changes in the computer industry, to that time.

So Burroughs was, you know, Edsger Dijkstra was also a consultant to Burroughs during the 60s, and he would come out to Pasadena, visit periodically, and it was a great company to work for in those days, I think.

30 - My interest in context-free languages

I had no idea that that work connected with mathematics in any way whatsoever. I wear one cap in the computer — when I’m consulting for Burroughs, and I wear another cap when I’m at Caltech as a student learning mathematics. Mathematics was something where we proved things correct; we knew what we were, you know, we knew what the rules of the game were. In the computer field, we just fiddled with something until it seemed to work and we couldn’t find any errors any more. But we never had this idea that it could be mathematically correct.

The only small exception to that was the area of syntax of programming languages. This means the grammar of languages. I mentioned that when I was in Seventh Grade my friends and I loved grammar, and we learned about English grammar. Well, now I was seeing the same kind of things, they were not nouns and verbs, but similar things in the algebraic languages like ALGOL, that I was supposed to write software for, and a theory had been developing called the theory of context-free languages, that was appealing to me, because here was something that I could be, I could use my mathematical cap and my and my computer cap at sort of the same time. You know, my computer science intuition, and my love of grammar and language was; would suggested interesting problems, the mathematics that I knew suggested how to solve those problems. So I, that was one thing where the two worlds, the computing and the math world, were coming together for me.

And I have to say that on my honeymoon, when Jill and I sailed to Europe, I brought along with me a book by Noam Chomsky, which was one of the pioneering things about context-free languages, and I read that in odd moments, you know, when Jill was seasick or something, and I would try to solve the problem about context-free languages. The problem I tried to solve was, is there a way to test whether a context-free grammar is ambiguous or not? Ambiguous means that you could write a sentence that had two different ways to be understood. And I thought I might have a way to resolve this, and I reduced it to several other problems

But I couldn’t solve the problem, in general, and little beknown, you know, I learned several years later that in fact three Israeli mathematicians had already proved that the problem had no solution; that there was no way to solve this ambiguity problem, in finite time. But I didn’t know that during my honeymoon, and I just wanted to mention that, although I do love Jill, there were also other things that I love too, and one of them was the mystery of context-free languages. Another time I guess I should, I have to mention is the time when I forgot about one of our dates, and, when I was playing with the computer at Case Tech, but we won’t talk about that. But she doesn’t let me live that one down.

31 - Getting my PhD and the problem of symmetric block designs with lambda equals two

Here I am then, earning money as a computer person, and enjoying, and then studying mathematics so that I can be a math teacher as a career. And the idea that there could be any connection with this, or there could be, ever be an academic field of computer science or something, never entered my mind whatsoever as a possibility. Very few people in the world had thought of it at that time either.

Now, at Caltech, I — somebody had told me early on in life that you go to grade school for eight years, and you go to high school for four years, then you go to college for four years, and then you might want to go to graduate school for another three years, and get your, and get a PhD. I don’t know who had told me that early on, but somebody had said that it takes three years to get a Ph.D.. And I had believed that and so when I got to Caltech in 1960, I’m thinking, oh, okay, in 1963 I’ll graduate. And I’ve just sort of set my sights that way. Now if somebody had told me it was going to take five years, I’m sure I would have graduated in 1965, but I had always been thinking I would graduate in 63, so I, so I just sort of planned ahead.

It was, it didn’t occur to me, until the day of graduation, that none of my other colleagues were there. You know, Al Hales was there, but just two of our 12 had done it in three years, and I think it was partly that, just that we had set ourselves up that way, to do it.

My thesis, I was working with Marshall Hall, who I hadn’t met before coming to Caltech, but I got to enjoy. His lectures were very disorganized, but he really knew the subject, so he would be teaching us about permutations, what actually I found was that I would take notes of what he said during class, and the problem was to figure out a permutation of what he had said that made sense. What, how to re-order; you know, I mean every important idea had been presented some time during that hour, but they didn’t come to him in the right order, just like now, I’m not thinking of everything in the right order, well he, you know, so his classes were like that, but I learned a heck of a lot this way, by trying to unscramble the notes of what he said in class, so I learned about the things that he was good at.

And I decided that you know, one of the unsolved problems that he posed to us, technical term is symmetric block designs with λ=2. It’s a technical term that really means; it’s something like geometry, except instead of having two, instead of having one line through every two points, you have two lines through every two points. And you know, instead of saying that every two lines intersect in one point, every two lines intersect in two points.

So this is a system called the symmetric block designs with λ=2, and at the time I started working on this unsolved problem I was going to try to find infinitely many such designs, such, symmetric designs, and six were known altogether. And so I thought, okay, but I had a new way to approach the subject, maybe I’d be able to find infinitely many. Well, it, it’s a good thing that I didn’t take that as my final project though, because I believe up to this day only one more has ever been found, so nobody knows that there is only finitely many, but it seems to be extremely hard to construct these designs.

32 - Finding a solution to an open problem about projective planes

Another open problem had been mentioned in one of my classes, having to do with projective planes, a finite kind of geometry, and the projective planes; one of the things Marshall Hall was good at was studying projective planes, and he had developed some of the major theories of it during the Second World War. These have lots of applications in code-breaking as well, and other, and kinds of code making from, you know, transmitting reliable codes.

And I took his class on projective planes, and one of the things he mentioned is that no, that only one projective plane of order 32 is known, and only one is known of order 64, and so, for whenever you had a power of two; two times two times two times two times two, and you’d find, one of the projective plane of that size, basically, that, it was a question whether it was only; that projective plane was unique, or were there other kind of geometries with this size? And I, the first open case was of size 32. And I took a look at it, and I received in the mail, as a result of a computer program that had been written, by R.J. Walker, I think he was in Princeton, and he had found all of the — he had actually found new ones of size 32, by computer, and he, he had a list on this, of all of this, all of the projective planes of a certain kind, which I later called I think a semi-field.

And he had two lists, and both of the lists had 16 solutions on it. And the thing was, so this gave him 32 different projective planes of a size 32, 16 of them were of one kind and 16 of them were of another kind, and that’s all the computer, his computer found. But one of the 16 in the second list was the one that had been known for years and years. So I thought to myself, oh, all I have to do is find a pattern, a rule that would take every one on the first list, and find its corresponding mate on the second list, and then I will have a rule that I can take on and solve the next problem, 64, the next problem 128, and so on, because my rule that worked in the case of 32 would then be a general rule if I could find this pattern.

And so I had gotten this list from him, it was in my mail at nine o’clock in the morning, and I remember riding up in the elevator with Professor Olga Todd, who was one of my professors, and I said, Mrs. Todd, I think I’m going to have a theorem in two hours. I’m going to find a way to match these 16 with these 16. And well, I just had a hunch that it was possible, and sure enough, you know, staring at it a little bit, a little bit, I found a connection, and by noon I had a theorem that had solved many, many cases of this open problem about projective planes.

I showed it to Marshall Hall, and he said, well Don, this is your thesis. Write this up and get out of here. You know, you don’t have to wait and do, you know, do this other hard problem, just do this for your thesis. So I felt a little guilty of solving my Ph.D. thesis in two hours and so I had, you know, I spent another few months refining the result and adding on some related theory.

But basically I could write a thesis of about 70 pages, and then, and that solved the problem that was considered by people in this very small sub group of the world, who were projective planologists, the finite projective plane people, that this was one of the problems that they had thought might never be solved. So I had, so that was nice. And it gave me a thesis.

Now, I, in order to graduate, I also studied — you know, Caltech had other requirements that I had to fill, fulfill too, but one of them, interestingly, had, was that you choose some other classic problem of mathematics, and you see, and you prepare for a month, read up on it, everything you can, and see if you can say something new about the problem, and the problem that I studied was what’s called the Thue-Siegel-Roth Theorem, in which Freeman Dyson had made one of the main contributions, and I mention that just because I know Freeman Dyson is interviewed in this series of People’s Archive, and he’s become a good friend since then, but I read his papers on the subject, when I was a grad student preparing for; I think he had recently, I think he graduated about ten years before I did.

33 - Teaching a computer course at Caltech and being asked to write a book about compilers

In my third year at Caltech I was also asked to teach some classes about computers. A group of people said, you know, Caltech doesn’t teach anything about computers, and we know that you’re consulting to Burroughs, why don’t you, why don’t you think of giving a course, just to, to offer to Caltech? So I had also, then been giving a once only course, even before I graduated at Caltech, and they made the very unusual decision to hire me as an Assistant Professor after graduation.

Usually a university won’t hire its own graduates, except MIT. But usually, you know, it’s considered bad to have inbreeding, because a department can get bogged down in one philosophy, and you usually want to bring in new blood. Well, Caltech, I guess, felt that I was sufficiently strange of blood that they, that it was okay to hire me too.

Now, meanwhile, in the January of 1962, I’m in my second year of Caltech, and in my first year of marriage; we got married in the summer of ’61, so Jill and I had six months of wedded bliss, we started with our honeymoon, and then, and then we had a time before I was approached by Addison-Wesley to write a book about computer science, about computers. And in the January of ‘62, an editor from Addison-Wesley took me out to lunch, and said, Don, we want, we need, we would like to invite you to write a book about compilers.

You know, compilers, this is this system, thing that I had done for Burroughs the previous year, and I had, I just finished, and you know, you have been recommended to us as somebody who knows how to write compilers, and would you think about writing a book like that? So I’m one and a half years into graduate school at the time, and doing consulting for Burroughs, but I, but, boy, I couldn’t get the thought out of my mind. Wow, I love writing a book? I just, you know, I’d been working previously on newspapers, magazines, you know, writing a few articles. I enjoyed writing all the time, and I, and here was the publisher of my favorite textbooks, Addison-Wesley, was asking me to write a book for them.

And so right away I went home and I jotted out the titles of 12 chapters I thought would be good for a book. And then, well, our marriage was still happy, but it was different, because I started concentrating on this book, for the next 40 years.

I thought I could finish the book, you know, rather quickly. I have letters that I wrote in 1964 or five. No, ’64, I wrote a letter to somebody saying, “I’m sorry I can’t visit Stanford University this year because I have to finish my book before my son is born,” you know. And now he’s 40 years old, and I still haven’t finished the book, but that’s just; we’ll get to that. But I thought I, I thought I would finish; I had no idea how long it would take me to, you know, to write this book.

They asked me to write a book about compilers, but I, I thought, well, wait a minute, there’s a lot of other stuff goes on in computer programming that you also need to know before you finish your compiler, so I said, would you mind if I put in chapters about these other aspects of computer programming? And they said, no, go right ahead. Okay, so this book, we, I, we decided to call it “The Art of Computer Programming”. They liked that title.

My original motivation for writing it was not only that I liked the idea of writing books, but because I could see a big need for such a book. There was nothing like it.

In fact, although I had written several compilers, and I knew a lot about compilers, I hadn’t invented any of the ideas in those compilers. I had just applied ideas that I had learned from other people. And so everybody else I could think of, who was able to write a book about compilers, I also, as far as I could see, they were pretty biased and slanted. They would mention their own method, and they wouldn’t mention anybody else’s method. But I was the only person I knew who didn’t have this axe to grind. I had never invented anything myself, I was just a writer, I could present everybody else's idea, in a way that was consistent, and wouldn't distort the picture the way they would, if they wrote it. You know, anyway, this is in the back of my mind, when I'm saying, yes, I want to write this book. I wrote the book because I didn't have any; because I felt that I was, that I was fairly good at writing, and that I would be able to balance the accounts of other people who had had more of a stake in it would.

And of course as soon as I got started writing it, I naturally would discover a few things too, and I had my, and I developed my own biases and distortions. But, and so I didn't succeed in my goal, of making the unbiased presentation, but I have to say that quite frankly, I did believe originally that that was my main reason for writing the book, it was needed, such a book was necessary, and I couldn't think of anybody else who would be able to present the story fairly. Not that I did it in fact fairly myself later, but at least I couldn't think of anybody else who would do it.

And I began to, so I began writing drafts of the material, starting then in the summer of ’62. I had classes of, during the beginning of ’62, but I started drafting material for “The Art of Computer Programming”, and the course that I wound up teaching at Caltech, during my third year of graduate school, was based on these notes that I had made, preliminary to “The Art of Computer Programming”.

34 - 1967: a turbulent year (Part 1)

My son was a year, my daughter was born in December of 66, and my son was born in the summer of 65, so, you know, he's one and a half years old, and she's one month old, my wife, Jill needed a gall bladder surgery, I was scheduled to be a lecturer, a national lecturer, to go around the country for three weeks, in February, and I was also scheduled to do other things like lecture for three weeks in Copenhagen in summertime, in France in May, et cetera, et cetera. I had sent in the manuscript for Volume One, it was, you know, being processed by Addison-Wesley, and the galley proofs were starting to arrive early in 1967, but I was in the middle of writing Volume Two, and I was actually almost exactly in dead center of it, I mean if it has 900 pages, I was on page 450, or whatever it was, anyway, I was almost exactly halfway done the Volume Two, and it was taking much longer than, you know, I thought it should, and I was getting, it was getting very hard to, some of the Mathematics was at the limits of my ability, but I've got this deadline I've got to finish Volume Two, because I had already promised that it would be done years ago. And that's only Volume Two, there were supposed to be seven volumes. Okay, so I'm going around and lecturing, my parents and Jill's parents came to help out around here with the kids, but I had to leave for, I had to leave, and this lecture tour meant that I was in a different city every day. And so in one way it was terribly boring, because the small talk is the same in every city. What can you say in the first, when you first meet somebody? So you know, you get up in the morning, get in the airplane, go, somebody else, somebody greets you, the faculty takes you out to lunch, they ask you, where are you going next, Don? And so on, and how is your book? And then you give your lecture, and then you sleep, and the next day, you're in Atlanta or something. So, but on this trip, maybe it was my first time? No, one of my stops was in Stanford, one of my stops, well, there were, yeah, one of the important stops was in Cornell, and so, yeah, different places, I was in Rhode Island, where there was a college, where nobody understood Computer Science, at all, and the audience just sat there dutifully listening to me and, you know, and not smiling, you know, and then I left, and then I went to University of Pennsylvania, and the students, and the overflow crowd, and everybody is with me and everything, and it's an exciting lecture to give, and then I went to Cornell, and I had two days there. It was a weekend, and Peter Wegner was there. As a professor, I had met him before, in England, or no, he had come to Caltech, anyway, so Peter and I went hiking around Ithaca, on the weekend, and one of the big questions, issues, in Computer Science at that time was how, it was called the Semantics of programming Language. How do you describe the meaning of things in the language? We knew about the grammar, but how do you get the meaning of the language? And I had got this idea that a good way to define a meaning is, if you know the meaning of little things, then you can use that to make, build up, the meaning of larger things, and so on, and continue on, but there was another approach, where you could start with the meaning; you could start at the top, and sort of propagate that downwards, into the meaning of the, into how the context affects the words of the sentence.)

35 - 1967: a turbulent year (Part 2)

And so there was this combination between the inherited part of the meaning and the synthesised part of the meaning. The part that comes out of the, you know, from the small to large, and the part that comes from the large to the small, and I said, you know, I can't decide which of these two is better. And so Peter says to me, as we're walking in this park, he says: well why don't you do both? And I said, well, this is obviously ridiculous. You can't, you know, it; will be circular, if you're trying to go down, and describe the meaning of the bottom in terms of the top, and you're trying to describe the meaning of the top in terms of the bottom, you get into a loop. It makes no sense. But after I was arguing to him about this, for about ten minutes, I realized I was shouting, because it occurred to me that he was absolutely right, you know, that you could do both, as long as you were careful that the way, that the aspects of the meaning you were defining from the top, wouldn't depend on the ones that were coming up. So the meaning has different parts to it. And so this led to a research, a sub-field of Computer Science, called Attribute Grammar. And the idea came while I was on this lecture tour in February. But I had- I get back home, I have absolutely no time to work on Attribute Grammars, because I'm supposed to write "The Art of Computer Programming" in all my spare time, and I have students and classes to teach, and everything else, and kids to take care of, et cetera, now I'm a father. Okay. Now, meanwhile, I had also been thinking of another thing in Mathematics, called the Word Problem, and here the question is, if you had two mathematical expressions, can you prove that there's a way to transform one into the other? And I had stumbled across a way to solve this problem that's now known as the Knuth-Bendix Algorithm. Peter Bendix was a student in my class, at Caltech, who worked out the computer program for it for his term paper. And because of some work I had been doing, these ideas came together and so I also, in 1967, besides these obligations of stuff to do, I had these brand new ideas that were just waiting to be explored. The Knuth-Bendix Algorithm, type of work, and the Attribute Grammar type of work. But no time to work on, so it's the busiest year of my life. And I'm editing journals. I was editor of 12 technical journals at the time. I was getting papers to referee, and, you know, I was taking that job conscientiously. The way I was operating, when I was at Caltech would be, you know, well, okay, the kids, if, I'd take care of the kids, you know, change the diapers, and so on, then they go to bed, if they wake up and cry, I put in my ear plugs, this is my time to do my "Art of Computer programming" writing. I watch TV, old movies on television, while I'm writing chapters for the "Art of Computer programming". I get to school, do my editorial work, send out papers to be reviewed, write to the authors of papers. Every morning, I would figure out, what am I going to accomplish this day? And I'd stay up until I finished it. You know, I was used to all-nighters from high school, well I started to, you know, to work every day until I had finished what I had set myself to do that day.)

36 - 1967: a turbulent year (Part 3)

So not too surprisingly, I suddenly came down with a bleeding ulcer, and I was, you know, I was in the hospital. So I had all these other things going on, no time to do the research that was coming up, and then it turns out that my body rebelled. And the doctor showed me a book of his that described what you might call the Type A Personality, which described me to a T, and said, you know what? Don, you just can't live this way, it's not sustainable. He was a wonderful doctor, he let me read his own textbooks, didn't, you know, didn't just say, doctor knows best, listen to me. He let me understand my condition, and I got shots. He gave me shots to restore the iron that I'd lost from bleeding, some more medication, told me to change my lifestyle, only do this much. So I resigned from all my editorial duties. You know, I wrote to my publisher with a black frame around the letter, saying, I'm sorry, I know you wanted me to finish Volume Two this year, but I'm in the hospital; I can't finish it, you know, I'm doing my best, and I'll continue working. The day that this ulcer occurred, I can tell you exactly where I was in Volume Two, because if you look in the index to Volume Two, there's an index entry called Brute Force, and I was trying to solve an exercise by Brute Force, at the time, and I just put that there as a reminder, so I can know exactly where I was at the time when this low point occurred. But then when I realized that I was doing too much, and I started, and I could still, you know, change my lifestyle and learn about the concept of mañana, and so on, Doctor allowed me to go to Copenhagen and give my lectures there. These were lectures about yet another idea, about syntax and semantics of programming languages, and it was to an international summer school being held in Copenhagen. I hadn't prepared the lectures in advance, but I sort of knew what I wanted to talk about. And so I had a week, I got there a week early, so that I could prepare my lectures to be given the next week. And in Copenhagen they have these wonderful forests, and so I went and sat under a tree, and started planning my lecture. Well, then it turned out that the other lecturer for the first week, Niklaus Wirth, had called up, and he had been on a round-the-world trip, and he had caught dysentery in India, and wasn't able to lecture, so they moved up my lectures to the first week, from the second week, so I had only, I can only be sort of a day ahead of my lecture. On Monday I could prepare Tuesday's lecture, and so on, and go back to the forest and figure out what I'm going to say on Wednesday. And those lectures were presenting original material, that I had, you know, that hadn't been done before. And I was recovering from ulcers, but I was taking it easy, I was trying to, you know, do this all relaxing and so on, and I actually enjoyed being in the forest under the trees, because it was a nice way to do research. And that all worked out, the students were helpful, and helped me solve some of the problems that came up in that day, and so that worked out. Then I went to Oxford, for a conference, where I presented my theorems about the Knuth-Bendix Algorithm, and I was able to write that paper on the plane, for, during the second week of when I was at Copenhagen, and on a trip to France, I had a couple of days to think about attribute grammars. So this was 1967, and it was the most creative time in my life, in the sense that three ideas that I had that turned out to be important in the field of Computer Science, the, certainly the attribute grammars and the Knuth-Bendix Algorithm, plus the third idea about top-down syntax analysis, which is less important, but still not bad, all came out that year, and I had to do them all by stealing a few minutes of time here and there, from the problems that I was really supposed to be working on, which is my family, my book, my teaching. And so I've always wondered whether or not this is, you know, would I have been so creative if I hadn't been under such strain? If I'm designing a Research Institute, would the ideal design be something where you have babies screaming, and people are sleep-deprived, and you know, and are bombarded with responsibilities, and then they would produce better research? Or where they, you know, have a luxurious setup with comfortable surroundings and so on? You know, you read about like Stravinsky's conditions, when he was composing his great music, and, you know, he was in some garret in terrible circumstances. Why is it that the year 1967 was the year when I had so many ideas? Maybe it was just that the time was right for them. You know, you can't go back and change history.)

37 - A new field: analysis of algorithms

In the Fall of '67 there was a conference in Santa Barbara of mathematicians, and, and I, that's how I remember meeting, I think also that, wasn't that the year when there was a conference in Chapel Hill in the Spring too, of mathematicians. So, I, I was meeting a lot of people that stimulated me and we had interesting problems to talk about between each other, but when I got to the conference at Santa Barbara, I realized that this was going to be my only chance to do research, so I sat out the conference. I didn't go to any of the lectures. I just sat on the beach and wrote my paper about attribute grammars at that conference. But I went to the meals, and I particularly remember somebody at that conference asking me what do I do, and I was just deciding, you know, I'm going to become a computer scientist instead of being in the math department. And so I said, well, I'm going to- I think I'm going to be a computer scientist. And so he said- well what, are you a numerical analyst? And I said no, not really, so he, he says, ah, artificial intelligence, and I said- no, not artificial intelligence either. Then he said- well, then you must be in programming languages, and in other words, compiler is what I had been asked to write a book about, and in fact, at that time computer science was considered to consist of three things, numerical analysis plus artificial intelligence plus programming languages. And, and Stanford's department also was sort of organized along those three lines. There were three qualifying exams and things like that. But I said, well, you know, I've done a lot of research in programming languages, and I've been editor of the programming language department for journals, but, but my main interest is different. And so I realized I didn't have a name for what my main interest was. And what is, what was my main interest? Well, see, as I'm, by this time, I'd written 3,000 pages of "The Art of Computer Programming" and typed part of it, and published, and almost ready to publish, you know, reading the galley proofs or part of it. And, and it turned out that what I, what I found was that we wanted the mathematical basis for understanding the quality of computer methods. We wanted to know how good a method was, whether it's twice as good as another one or whether, you know, some quantity of things, you know, not just qualitative of, yes, better, but how much better, some, some way to add quantity to this. And so I, so I used that as the underlying unifying theme of my books, is to find these quantitative, descriptive ways of judging the merits of a computer method, and, but I didn't have a name for it, and, and at this conference at Santa Barbara I realized that if I'm going to, if I have to explain to somebody else what is, what is my field, I'm going to have to have a name for the field, so I, so I made up a name for the field. I decided to call it analysis of algorithms, and I figured, okay, you know, I'm writing a book. I could use that to explain what an analysis of an algorithm is. I, I talked to my publisher and I said, let's change the title of my book. Instead of calling it "The Art of Computer Programming", let's call it "The Analysis of Algorithms". Well, that didn't sell with their, with their focus group, but, but I decided anyway that would be, that would really be my career, to be, to focus mostly on the analysis of algorithms, meaning the quantitative study of how good an algorithm or computer method is. And I used that as when I was asked to give a lecture at the International Congress of, of, what's it called, of Information Processing Societies in, in 1971. My title was the Analysis of Algorithms, and I also was asked to speak at a mathematical, International Mathematical Conference in 1970 in France, and my title there was Mathematical Analysis of Algorithms. So, I was trying to promote this term as a, as a buzzword so that somebody, so that somebody would understand what it is that I do, or that I like, that I hope to do. And, and I'm glad to say that after, after ten years or so, I mean in the late '70s, it started to show up as a category in the reviewing journals and there were books coming out called "Analysis of Algorithms". In fact, even though I, you know, my publishers didn't like that title, there's, there are quite a few books now that, that have that title in them. And, and so, but I got to name the, the area that I work in, but if anybody asked me what does it really mean, I would just say, well, it means whatever I'm interested in, you know, so I could change it for the first few years to, to suit myself.)

38 - The Art of Computer Programming: underestimating the size of the book

I had the Table of Contents sketched out, the 12 chapters, from the first day, and I started filling in, chapter by chapter, and writing, and writing more material, and Computer Science is growing, and I, it turned out I'm very bad, not only at estimating how long it's going to take to do a job, but also I wasn't very, at all good at estimating how large a book I was writing. I looked at my handwritten; I, my manuscript was all written out in hand, and I looked at my handwritten- you know, and my letters seemed a lot bigger than the letters in books, and I'd looked at books, and I've certainly read a lot of books, and so it seemed to me that what I had written would be a fairly reasonable sized book. In fact I had, I got to the end of chapter 12, and after chapter 12, I think it was 64, '65, of this handwritten draft, and I had 3,000 pages. I had accumulated 3,000 handwritten pages. Which I still have the manuscript. And while I was working on these 3,000 pages, I had written to Addison-Wesley saying, saying, they said, how's it going? I said, oh yeah, I'm writing, stuff is flowing, do you mind if I, you know, if I make it fairly complete, I find these other materials? They said, go right ahead. So I accumulated 3,000 pages, and then I took it to a type- to my typewriter, and started typing. Now, I typed up chapter one, which was 400 pages of typescript, or something like that, manuscript, that's double-spaced. Incidentally, I got myself a, an IBM Selectric typewriter. This was very new at the time. I think they said, they told me later that I was the first private individual in California to buy one, instead of a company buying one. This was the typewriter that had a little ball, that would rotate and strike the page, and, but the important thing to me was the touch was much better than any other typewriter I had ever felt. When you hit, when you struck a key on the Selectric typewriter, it would transmit a signal, saying to the ball, to go this way, but you could strike several keys ahead, and the machine, internally, would buffer this, and remember where the keys that you had done, and then they would be sent to the ball, you know, you type t h e real fast, and you can get to the e even before the t has finished printing, but the, it's like, it was designed so that you could do that. So I could type really, I mean like the first time I saw a Selectric typewriter in an IBM exhibit, I typed, you know- now is the time for all men, good men, to come to the aid of the party, faster than I had ever typed anything before. I looked at it; it came out perfect. And so I said, I've got to have one of these typewriters, and so I bought myself a Selectric typewriter, and I had a, and I used it to type my thesis, at Caltech, and I had, I had been a good, I had been, a, you know, a keyboard person, I'd been playing piano for a long time, and I learned machine shorthand the way court reporters do, and so I was, I had played a lot with, you know, a saxophone player and things like this, so this was just another, typewriter. I could use this very well, and so I started typing it, and I typed up my chapter one of the 12 chapters, and sent it to Addison-Wesley, saying, here is, you know, here is the first chapter of my book. And then I got a letter from a person; he was the person who, he was the person who actually had been the first editor who came to talk to me in 1962, but this was 1966, I think, by the time I had gotten to this point 3,000 pages, plus typing the chapter. And so now I heard again from this same guy, but he had been promoted three levels, in the company meanwhile, so now he was way up, and he was saying, what's going on here? You've got this book. Don, do you realize that your book is going to be more than 2,000 pages? You know, and, what? I thought I had a six or 700-page book. I said, you know, I thought, you know, I know, I've read books for years. How can you tell me that this book, that this book is going to be so long? So I went back to "Thomas's Calculus", the original book that I had loved in Freshman in college, and I typed out, you know, they said, Don, you know, I had felt five pages of my typing would go into one page of book, but they said, no, no, it was one and a half to one. And I couldn't believe it, so I took "Thomas's Calculus", and I typed out two pages, of "Thomas's Calculus" on my typewriter. Sure enough, three pages of typescript went into two. So here I had a book that was more than three times as big as I, you know, so I thought. No wonder it had taken me this long to finish the darn thing. But then you know, they said, well we, nobody will be able to afford this book, you know, all publishers have their horror stories about the professor who sends them a manuscript, you know, ten volumes about the history of the egg, or something like this, you know, and it just lays a big egg. And so how are they going to get around this problem?)

39 - Deciding what to do with the book and the success of the first edition

I fly to Massachusetts, and we have discussions about what are we going to do? And so they say, well, maybe we can think of something. Meanwhile, they showed the chapter to a few people, and the people liked it, so they weren't so wary about it, but they said, you know, but I, my editor at the time, Norm Stanton, I saw, I happened to notice at lunch, the notes that he had written to himself, and said, terrific cost bind, and things like this. You know, I mean he was trying to break the news to me gently, but what was I going to do? And you know, he was suggesting, they were suggesting, okay, you leave out this, you leave out this, you know, don't give the answers to the exercises. Instead of having professional illustrations, they'll just use the illustrations that I had put in my manuscript. They said they were charming, and things like this. Well, I thought they stunk. And I, you know, and I said, no, I like Addison-Wesley because the quality of the books has been so superb; the illustrations have been top of the line. This is the reason I signed with you guys. And my editor said to me afterwards, boy, you were courageous in there, standing up to the president of the company, and all this. So they decided, well, maybe we'll publish it as three volumes, and then they changed their mind again, they decided to publish it in seven volumes. So we set up a plan to publish "The Art of Computer Programming" in seven volumes. And that plan is still officially there, but three volumes have been in print now for more than 30 years, and I'm working on volume four. Now, the first, but the reason is because the subject- Computer Science didn't stop there, so the 3,000 pages that I had written described the state of Computer Science in 1965. Well, a few things have been learned since 1965, so we've got to include those too. Well, the book went through several other stages. First they said, you shouldn't put in the answers to the exercises, we'll publish them separately, as a, you know, some people can order them or get them as a paperback. And we'll reproduce them just from the typescript. But after reviewers started reading the book, they said, no, it's actually be better to typeset those answers and put, include them in the book, and so when, in 1968, when the first edition really came out, it was an expensive book, more than all the other books in Computer Science, about twice, I mean it cost, I think $32 or something for Volume One. I forget what the price was; I could look it up, while other books were selling for $10, or something like that. And yet, in the first year, it was adopted as a textbook by more than 50 universities, and you know, so we came out with another printing shortly after, and it became unbelievably successful, although it was not an easy read, it was still, you know, it proved that there was a need for a book of this kind, in the area. So that's the beginning of "The Art of Computer Programming". And in 1968, in January, is when I got my first copies of that book, the, since then, I believe it's something like three or 400,000 copies of Volume One have sold in English, and more than that in other languages, so I couldn't believe how successful that was going to be. But if I had, you know, if I had known in 1962 that I was writing such a big book, and that I would still be working on it when I'm 68 years old, I would, I would certainly have not said that I would go ahead with this. I thought that I was going to finish it before my son was born in 1965.)

40 - Writing fiction: Surreal Numbers (Part 1)

This is, is a unique event in my life. It took place in early '70s. I was, I had met John Conway, probably, certainly one of the greatest living mathematicians. I had met him on a trip to the University of Calgary, in '71, and we had lunch, and he scribbled on a napkin a new theory that he came up with, which I thought was really terrific, and well, it's a purely mathematical theory about a new way to define numbers, not only the integer numbers and the fractional numbers, but also infinite numbers and square root of infinity, and infinity to the infinity, and infinity to the square root of infinity, and one over infinity, and makes sense of all these numbers. So a year later I was on sabbatical in Norway, and a thought came to me in the middle of the night, wow, this theory is so beautiful it would be interesting to tell the story, to write a book that where the characters in the book discover Conway's theory, they find his rules, on a stone tablet, and they decipher the tablet, and they develop all the consequences of this tablet, so that they can prove things about infinity, and so on, by themselves. The point being that this would be a way to teach how to do research, that the students could, you know, not only learn what other people had done, but how to do new things in Mathematics themselves. And it could be taught, and it could be presented in the form of a story, with characters discovering these things, by themselves. And so I thought, this would really be a cool book to have, and it would supplement, it could be used as a supplement; I was thinking of it as actually high school teachers could recommend it to some of their students, so that students could see the way Mathematics is discovered. So, I got the idea of calling these numbers surreal numbers. You have to know that real numbers had, is what we call our numbers that have infinitely many decimal places, and so surreal numbers are even more so, because they, there are surreal numbers between the real numbers. And this was Conway's system, and I thought, so I had this title, "Surreal Numbers", and I had the idea that a theory could be developed by characters in a book. And I woke Jill up, and said- Jill, you know how I've been working on "The Art of Computer Programming" for many years, and I'm still not anywhere near being done with it? Well, I just thought of another book that has to be written, what do you think? And I said I thought I could write this one in a week, and really a week, because it would be short. And so, you know, she said- okay, Don, go for it. This is your year on sabbatical, we're in Norway, why not actually take your week, and go do this project, you know, concentrate on that, and then, you know, then you'll be happy, and we'll live happily ever after.)

41 - Writing fiction: Surreal Numbers (Part 2)

So we made the plans. I decided I would rent a hotel room for a week in downtown Oslo, near where Ibsen lived, so that I could maybe get some of the vibes from his soul. And we planned that she would come and visit me a couple of times during that week, and we could have a little affair in a hotel room. We'd never; we'd always wondered what that would be like. And so I could be an author for a week, and then, you know, and we could have this thing, fool the people in the hotel that here was this woman visiting me to, you know, she's sneaking. So this was what happened, and during the next few weeks I started, you know, I sort of wrote the first page of this novel in my mind, several times, and I had, whenever I was riding a bus or something, I would think of another sentence, so I check into the hotel in January, and it was probably the greatest week in my life. As I said, the time, there was kind of like a muse there, dictating this book to me, and this was, I stayed in a mission hotel, it's a cheap hotel run by strict, by volunteers of the Norwegian Church, they probably were, but anyway we had our affair. And students from America were staying at this hotel, from St Olaf University, in Minnesota, and every morning, in Norway, at the hotels, we have a Norwegian breakfast, which is a huge spread, where you have, it's not like kippers in England, but it's, but we have certainly herring, and many other, you know, eggs, and all kinds of other things, and so I spent an hour every morning eating a very leisurely Norwegian breakfast, which was enough to last me till dinner time, and listening to all the American students talking to each other, and what they're saying to each other, and picking up the, especially, you know, I hadn't heard American English spoken for a long time. We'd been living in Norway for several months, for six or seven months by this time. And so I could remember some of the dialect, and some of the expressions, and my novelette is told in dialog form, so it was important for me to, you know, to have a sort of authentic accent to these characters. So I listened to what the students were saying, and I, you know, ate a lot, and then I would go to my room, and I would start writing the book. And the book is only really, it's something like opera, where opera, you know, has a good music, with a little bit of a plot, and my book was good Mathematics with a little bit of a plot. And so I was developing the Mathematics myself. I had remembered that Conway had written down his stuff on a napkin; I had lost the napkin, so I tried to remember what he'd told me a year ago, and I tried to reconstruct it as the characters in my book were discovering the mathematics for themselves. I was discovering the Mathematics from the same ground rules as they were under, and if I would make a mistake, you know, I would think of something that didn't work, the characters in my book would also then make the same mistake, and then they would recover from it the way I had done. So I, so the book was also an authentic presentation of mathematical research, in this way, as I'm writing it. And so I would start up, and I would end up, in the morning I would, well I usually had something to go on from the previous day. The first day I had been thinking about the first page of the book for some months, so I was ready to start the first page, and I only had to pause when I got to page two, I sort of could dictate page one. And then I would, you know, so I'd start writing, and then I would try to do some more Math, and then I would get stuck. And I would run into a block. There was nothing to, you know, which way to go next? What to do next? And so then I would go outside, and walk around in the streets of Oslo, and it was a wonderful snow free month at that time, and so it wasn't too slippery to walk on the streets in January, and you know, so about an hour, an hour and a half, just meandering around my hotel in downtown, the solution to the problem would occur to me, and I'd get back to my room, write it up, and you know, then have a leisurely supper in the evening, Norwegian style, and then back to my room and do some, do a little bit more writing, you know, get ready to, and then as I said, I couldn't turn the light out because I had to write; I knew what the next day's first few sentences would be, before I could go to sleep. I was really into this book at the time, as you can imagine.)

42 - Writing fiction: Surreal Numbers (Part 3)

I predicted that it would take me a week to do this book, well, after six days I finished the last chapter, and on the seventh day I rested. And it was very interesting. On the sixth day, actually, was one of the days my wife came to visit me, and we went out to see a movie, it was called "Butterflies are Free", with Goldie Hawn, I remember, and then afterwards we walked around the King's Palace in Oslo, and there was a wonderful hoar frost on the trees, and there's these magnificent trees in the Palace grounds in Oslo, and I was just entranced, looking up and seeing the snow-covered tree branches, against the dark blue sky. I'm just telling you this was such a week for me, that, you know, having this inspiration all the time, of writing the book, and then getting; I was in the second last chapter at this time, and going back to my room, I would finish the last chapter, but I'm looking up at the sky, and just seeing these patterns of these ice-covered branches, and it's one of the great moments of my whole life, seeing this, and Jill was on her way back home to our apartment. Then I went back and finished the last chapter, and that was the sixth day, and on the seventh day I rested, but on the seventh day, I tried to write a letter, to my secretary, Phyllis, who was going to type up the manuscript, telling her, you know, how to do it. And I would start a sentence, and I would get to the middle of the sentence, and I couldn't finish the sentence. I'd been writing fluently for six days, and then I got to the end, and the book was done, and my writing was done. I couldn't figure out how to write a letter to Phyllis. Finally I got the letter done, and we sent the manuscript off to her, you know, it's all handwritten. She typed it up and sent it back to me a few months later, and I sent the manuscript to John Conway in Cambridge, England, where he was at the college there. Well, he politely pointed out that I had gotten one of his two rules wrong, that the characters in my book had actually been working on a different system, not the one, you know, his system was actually nicer than the one that I had done. Well, okay, not so bad. We came and visited him in England. We went to Cambridge; stayed at his house a few days, at Easter time, and I learned about what I should have said, you know, and when I went back then to Norway, I took another week, and this time, not in Oslo, but in a remote valley one of the valleys that had actually, during the time of the Black Death, had lost all of its population, and there was a little rest home there, called Solheimen, where a lot of people came to spend a week in summertime, and every one spoke Norwegian there. We ate at common tables, and I would do my best, by that time, to speak to them in Norwegian, but then, most of the time I went through the whole book, and rewrote it with the rules that Conway said I should have used from the beginning, and it came out better. And I also had some other comments from a few other readers, who had suggested, you know, like my wife was a, there were some romantic scenes, and my wife was a consultant on those. And so on. So I took some readers' comments in, and then another week's work, and then I had this book finished, "Surreal Numbers". It's a completely different part of my personality from the computer books. This turned out to be kind of a litmus test for whether or not somebody is a Mathematician or a Computer Scientist. Some people think they're the same, and some people, you know, anyway, I know they're different, because the Mathematicians will look at "Surreal Numbers" and think that it's really interesting, and the Computer Scientists will look at it and say, this is my greatest mistake, you know, why did I waste time on this project? Well, I just got word from the publisher that they want to do the 17th printing of "Surreal Numbers". I'm supposed to send them the corrections, you know, by next week. And it's been translated into eight or nine languages, so there are some Mathematicians in the world who appreciated this little book. It's about 80, 90 pages, I think, of, small pages, but it turned out to be a little thing that you know, I felt was dictated to me. I will never be able to do anything else like it, but it was a great experience while it lasted.

Have you ever had the urge to do another novel?

No, but you know, while I was writing it, you know, I was, like my eyes were open, and like everything; I'm walking on the streets of Oslo, and I'm seeing the birds, and I'm hearing sounds, and I'm, you know, aware of the world, in a way, because I'm writing something that means I'm going to be writing, you know, about what my characters are saying, and so I'm, that automatically makes me much more receptive to the world, so that was another part of this experience, and I can see why a writer, you know, can get a thrill from that, because it sharpens your own perceptions as you're facing the task of trying to put something into prose. Yeah. But no, I mean I, you know, maybe I'll wake up in the middle of the night some time with, you know, but I think, I've always thought of it as sort of a once in a lifetime thing, and as I say, some people say it's my great mistake too.)

43 - The emergence of computer science as an academic subject (Part 1)

When I was writing the first volume, I was at Caltech, and I was advancing in the Math Department, I was still, you know, I was a Mathematician, and in the early 60s, as I said, I never would have believed that computer science, you know, under any name, that there would be an academic discipline of this sort. However, at Stanford George Forsythe had come over in the late 50s to Stanford, and he had, and a very few other people had a vision, that there was something here that was really ought to be a part of every university's curriculum, and it became known as computer science, and he, I consider him the Father of computer science, and a wonderful man, he figured out a way to bring people to Stanford, to build the department, and he started, he scrounged around the whole world. Everybody that he felt would be the best in what he saw as this emerging field, he would invite them to Stanford, and say, please come and join us here. And so he recruited me. And operated on a shoestring. He was able to; he had the support of Provost Al Bowker, who later became famous for many other things, including Chancellor of Berkeley, but Al Bowker was in Stanford Administration and very supportive of Forsythe's ideas and giving him strategy on how to proceed. And so he was able to, even though there was no funding for this, he was able to get somebody to be part time, here, in Math, somebody is part time in Electrical Engineering, somebody part time in SLAC, and more and more people, John McCarthy coming, so that he had the largest concentration of good Computer Scientists anywhere during the 1960s. And next week our Department is celebrating its 40th anniversary, and we're going to be reminiscing about this time, it's actually the 41st anniversary, because the Department began in 1965. And it was, they had, I don't know, half a dozen students, or ten students at the very beginning, and then quite a few later on, but it was, it was, you know, a pioneer in this area of doing computing. Now, I learned about the connection between computing and Mathematics. I said first I studied grammar, and I liked the idea that the grammar of a computer language could be studied with mathematical tools, and I got into correspondence with Bob Floyd, who at the time was in Massachusetts, and I met him in the summer of 62, after I had written another compiler. I wrote a compiler for Univac Corporation, and met Bob in the fall of 1962, actually, and he introduced me to a brand new thing- that you could actually prove things about computer programs. You could not only fiddle with a program until it worked, you could develop a theory so that you would know that the program would work. This was a revelation. I'd never brought my mathematical side and my computer side together. Computer side, I just was an Engineer, fiddling. So Bob said, no Don, look at this. You can actually be sure that your computer program is working, if you look at it the right way. This was a great revelation to me, so I got very, I got friendly with Bob, I visited him in Massachusetts, he visited me in California, and I began to see that maybe there was a possibility for an academic subject of Computing. Forsythe invited me up to Stanford; my sister-in-law was living in San Francisco at the time, so it was a convenient time for us to come up and take a look at the campus, which was of course beautiful, and George said- you know, okay, Don, join us. Oh, I said- no, no, no. I'm writing this book, and I'm going to finish and my, you know, my son's going to be born. We've got to have some stability. But I knew that at some point in my life I'd have to make a decision, where was going to be my permanent home, instead of just, you know- at this time I'm an Assistant Professor. Caltech actually promoted me to Associate Professor after two or three years, and I should say something about tenure, I guess. About that time there was a story in the "Los Angeles Times", that students at UCLA were unhappy because a professor at UCLA hadn't gotten tenure, and I'd never heard of the word tenure before, so I want to Marshall Hall, I said, Marshall, what is this word, tenure? What does it mean, that she didn't get tenure? And he said- well Don, remember when you got your appointment form from Caltech last year, where it said you're appointed Associate professor, you know? And I said- yeah? Well there's a line on there that says, the ending date for your appointment, remember that that line was blank? And I said- yes. Well, he says, that's tenure. You know, your job goes on. Well I'd never heard of the concept before, so I had tenure before I knew it existed, and I'm glad, because a lot of students now are so worried about not getting tenure, that it interferes with their professional development, you know, they're spending more time strategizing about how to get tenure than about how to do good science.)

44 - The emergence of computer science as an academic subject (Part 2)

There I was at Caltech, but I knew that sometime, that I had to make a decision, what shall I do for a permanent position? Because I had never expected I would stay all my life at one place, but I didn't like to move, so I knew there was going to be a time when I should move, and to the place where I would stay the rest of my life. So where should this be? My first offer for full professorship was to Norman, Oklahoma, and then I was offered, that was at '65, or so, and then I got an offer to go to Chapel Hill, North Carolina, but these were unsolicited offers. I started to wonder where I should go, and of course I knew about Forsythe's enterprise here, so I wrote to Bob Floyd, who was my best friend in Computer Science, and said- Bob, what's your assessment about the different parts of the world? And wherever I go, I'd like to be your colleague, so the two of us could go the same place. You know, where would you like to go, and I'll see if it suits me too? So he wrote me this nice, long letter, you know, telling about all the places in the world the way he ranked them, and he put Stanford up at the top of his list, just as I had tentatively put Stanford at the top of my list. And so he said, you know, if I wanted to go to Stanford, the chances are he would like to do that too. So this turned out to be kind of a package deal that when we were negotiating with Stanford later, we'd say, well, you know, there should be room for two of us, if you're going to make an offer for one. But I started to search for a permanent home, and I got, and the main four places that made, where we went through interviews and made offers and so on, the main four places were Harvard, Berkeley, Stanford and Caltech. And this was, as I say, taking place in the middle 60s, in 1967, was when the main interviewing was going on, well '66, yeah, about that time. The firm offers didn't come through until '68. But during 1967 was when there was a lot of correspondence happening. And so I could be a full professor at any of those four places, and it was quite; each one was different. If I was a full professor at Caltech, I would remain in the Math Department. I would be a full professor of Mathematics there, and that would be my career. If I went to Stanford, I would be a full professor of Computer Science; also at Harvard and Berkeley. At Harvard they had almost nobody in Computer Science, and you know, a very few students, very few faculty. My role at Harvard would be to help them build it up. And it was a case where well Caltech and Harvard, you see I knew that at Caltech they wouldn't have a Department of Computer Science for a long time, it was a very much uphill battle because this faculty at Caltech is so strong in Physics and in Chemistry and Biology. The Physicists don't see Computer Science as important, except for how it helps Physics. Biologists the same way, how does it help Biology? They didn't see that the computer scientists might have problems of their own that, you know, that are interesting, not just as a service to other disciplines. And for this reason it looked to me really unlikely that Caltech would ever want to have a Department of Computer Science the way Stanford did. Harvard, the same story; at Harvard they said they wanted me to be a, you know, Professor of Applied Science, and help them build up Computer Science, but I knew that if I went there, I'd be spending most of my time arguing for Computer Science rather then doing Computer Science. And I hated that. I'm not a politician; I don't like confrontation. I don't like trying to persuade people of things, but I like them to come to the conclusions themselves, so that although Harvard was tempting, because I knew that it would be great to have a spokesperson for Computer Science at, where you have some clout there, and people listen to you, I wanted to do Computer Science instead of arguing for it. I had seen a lot of cases where other fields, the Operations Research was a special case in point, where more than half of the papers in the early days of Operations Research were arguing for Operations Research than just doing Operations Research, just presenting the beauties of Operations Research, but saying why we need Operations Research. Well, I wanted to have none of that, so I didn't, you know, sneeze at the offer from Harvard, but I decided, really that that wasn't going to be the life I wanted. I also, then I had Berkeley and Stanford, and I felt all around University of California, Berkeley was the best university in the world from a total standpoint of all fields, and very attracted to the idea of going there, but they didn't have much in Computer Science, like Stanford did. Again, my role would have been to build, more to build things up, and I could live on campus at Stanford. This was a strong attraction to me, to be able to build a house like I have here now, where I can walk or bicycle to the pool every day and not have to worry about commuting. So I, you know, Stanford had already so many good students, and so many good faculty, I could come here and be one of the boys, and, well, men and women; one of the people, and so I took Stanford as my top choice, just as my, my, now, on the other hand, Stanford has standards, and I was pretty young, so why should they appoint a full professor at this age? And fortunately Volume One came out in print, just in the week when the faculty had to approve my appointment. I mean the people in other departments on campus; the Trustees and the other people who had to approve of an unusual appointment to a young person for full professor, and the book came out just in that week, when they needed, when that helped. So they were all smiles, and I got my letter from Stanford saying, yes, you can come here.)

45 - A year doing National Service in Princeton

But I didn't come to Stanford immediately. My first year at Stanford was actually spent on leave of absence in Princeton, New Jersey. Now this was the time of the Vietnam War, some of you might remember, and great ferment on campuses, and I had been deferred from the draft because of being a graduate student, at first, and because of being married, and having bad eyesight, and so I was 4F for a while, and then I, anyway, but I felt that I owed something to the United States for providing me with the freedom to be able to study, and not have to carry guns and defend my territory, so I thought it would be good to give at least a year of National Service, so I said, well what could a person with my skills do for the country? And the answer was, you know, I was recruited into working for code-breaking, cryptanalysis, where people like Marshall Hall, my advisor, had, and other people at Caltech were prominent, because the Combinatorial Math that I was doing was useful in making and breaking codes. So then I, so I went there, and I worked not at the Princeton university, but at the Institute for Defense Analyses, which had a building on the Princeton campus, called von Neumann Hall, actually. And we, and I worked there on classified work with some tremendously excellent colleagues, and the way we did it there was that half of our time was supposed to be doing pure Mathematical Research, and half of it was supposed to be doing this classified work that was relevant to the code breaking, and in our case we were, most of us were also especially good at computer programming, so we would try to make computer programs that could help in code breaking. The work there was secret; I still haven't been able to tell my wife what I was doing that year. And although I met a lot of great people that year, I found out that the secret life is not for me. I'm the kind of person that likes to talk about what I'm doing, and explain and teach, so I worked hard at helping that agency for a year, but then I knew that I should really be an academic, and no more do classified work after that time. And so I can't tell you much about that period, except that the people that I worked with were super, and I published also some papers that people that I worked with, and my roommate there, Ed Bender, and I solved a famous problem in combinatorics where we were able to take what's called plane partitions and find a reason why the number of plane partitions of n has an amazingly simple form. The plane partition is; you can understand it like this. Suppose you have 100 sugar cubes, and you want to put them into a box, and you pack it solid against one of the corners of the box, how many ways are there to do that? And a man named Percy McMahon, M C M A H O N had spent many years of his life solving this problem, and the answer that he got was that there was a fairly simple formula explaining how many ways there are to put n sugar cubes into the corner of a box. But nobody knew a reason why it should be so simple, and Ed Bender and I were roommates, and we spent a lot of our free research time thinking about this problem, and lo and behold we came up with a solution. And Ed and I, Ed is the person who sort of most perfectly blends his research skills with mine, in the sense that the two of us together, I never worked together with any other person on my life where we were sort of such an ideal team. That is, his strong points would complement my weak points, and my weak points would complement, you know, his strong points, my strong points would complement his weak points and vice versa, and we could talk to each other at the same rates and understand each other at the same rates, and so here we are in the same room, solving the problem together, and we each are going to take the next step, and we're getting somewhere. I never met anybody else who, where we were so perfectly attuned this way. In fact, it's so- such a good match that we're afraid to meet each other now, because we know that if we get together we have a responsibility to the world to invent some new idea, and that's too much of a responsibility, you know, it exhausts us, so we haven't seen each other for years. But when we were doing it, we were really hitting it off well. And so we solved this problem about plane partitions during the time I was in Princeton.)

46 - Moving to Stanford and wondering whether I'd made the right choice

People would ask me; I'm in Princeton, and people would say, well Don, where are you from? What should I say? I'm on leave from Stanford; my employment at Stanford had officially started, although I was in Princeton. The reason was it gives me legal ability to acquire the lot, where this house is, before somebody else snatched the lot, so, you know, I have, otherwise I don't get a desirable lot, so I'm officially a Stanford Professor, but not getting any salary, because I'm away at Princeton. And so they asked me where am I from? So I say, I'm from Stanford. And they say, oh, isn't that where the students just burned down the such-and-such a building? And I say, well, that might be true, but I actually have never lived in Stanford, you know, so I spent the year in Princeton, being away from Stanford, then I finally came back here and oh, it's scary, because, you know, I knew that I didn't, and I only wanted to move once in my life, and I thought I had picked the best place to move, because, you know, good library, good climate, you know, I could live on campus, and you know, good students, you know, close to San Francisco. Sounds great, but here I am, and I actually, you know, wonder, now I've put all my eggs in one basket, so I remember you know, driving, the first day I'm here, and we stop at a stop light over on Stanford Avenue, and I said- oh my goodness, how many times in my life am I going to have to wait for this stoplight? And I'm realising now that I don't have any choices anymore. When you have options, when you have many different places you could go, you can always say, oh, how great that's going to be. But then you make a choice, and you've given up all the other choices, and then you say, now, anything that goes wrong can be an aggravation from this point on. And there were other things about Stanford that I didn't know the answer to, but fortunately, you know, all the answers that I really did learn, turned out to be nice, so I've been very happy here. I came to Stanford then in the summer or the late part of 1969, although officially I started in 1968, and I think California made me pay taxes for that year, even though I was in New Jersey.)

47 - Designing the house in Stanford

While we were in Princeton, every Sunday night, Jill and I would talk about what was our dream house. In fact, our first date, when we, at the library in Cleveland, we each, we started talking about our dream house, and it turned out we both had the same dream house, so we both, I mean that's one of the things that we were meant for each other, we had thought of a bean-shaped house. Never got a bean-shaped house, but both of us had been thinking about it, so anyway, we decided that we'd spend every Sunday night, hour, two hours, making plans up for what kind of a house we'd like to have when we move to Stanford. The kids were in bed; we had two children by that time, John was born in '65 and Jenny in '66, so we made notes, and we finally had it was, I think about every room, what we wanted to do, and we came back here, and there are a lot of good architects in the area, and we thought- we'd met a man named Jim O'Neill, who we liked very much, and he listened, and he looked at our notes, and he didn't laugh at them, but he gently pointed out that all of our plans were completely impractical, and you couldn't build these things, and all these triangular corners would just not work, that we had planned. And he had very good sense of lighting, and how houses go together, so we, so he was a very good listener, so he knew what we really wanted, rather than what we had written in our plans. He was good at boiling these down into reality. And so we started making plans. We were, you know, just renting at the time, a house until we could finally build here, but we had the lot already. Stanford has this wonderful idea that you can get an 80-year lease from the university and live on campus, and the only downside is that all your neighbours are Stanford professors, you know, who are, tend to be a little kooky, but there we are. Now, one of the big ideas we had is that we should have rooms that are not all the same. On our honeymoon we had gone to visit baroque palaces, and we had seen places where, you know, there are grand, there are rooms that are large in scale, and rooms that are small, and so why should you have all the rooms about the same size? And, you know, we went to the, we went to Rome, and we saw Roman baths, and we said- oh we've got to have a big bathroom, you know, bathrooms should be big. We figured a bedroom should be small, intimate. So we decided, you know, we said, let's have one big room for Jill to do her artwork, one big room for me, to have a pipe organ. I can talk a little about pipe organs later, if you ask me. But I was, by that time I had been playing organ. I took organ lessons in Princeton, at Westminster Choir College, while I was there. So it would be nice to, you know, have two big rooms, and then small rooms, somehow, but mostly a variety, so that you wouldn't have everything the same. Lots of other ideas about how we could make sure that, you know, we could keep an eye on the kids. We didn't want to have rooms where the kids could run around in circles, because we knew that that's, you know, a danger, and so various other plans. So we're talking to the architect, and he, and one of our key ideas that we thought we had to have was a winding staircase, a circular staircase. It's very romantic. You need a house with a circular staircase. Well, as you'll notice being in this house, we don't have a circular staircase, but that's one of the things that, when Jim drew up various plans, and plans one through 12 all had circular staircases, but he couldn't make the thing work. Finally we decided, okay, he's got this other one, plan number 13, which is basically what we have now, where we have the one, Jill's room on one side of the house, where it gets the north light, my room on the other side of the house. In between, where everybody's, you know, it's space for everybody, an expandable place for children. We were hoping to have more children, and a place where students could stay, various things all put together, in the other part of the house. With the, now he wasn't as good at the small spaces though, as the big. We didn't get the small rooms that we wanted, so later on we actually built a partition in our bedroom, so that it, to make it into two, visually into two parts that are half as big. Still this is the basic idea of the house. We knew it was going to be a house that we would live in the rest of our lives, and we wanted it to be adaptable, for the future, so for example it was a two-storey house; we didn't know if one of us might become crippled for some reason, so we made sure that there would be a place for an elevator, in case we wanted to install an elevator if we needed it to get upstairs. And we could use it as a dumbwaiter meanwhile, for clothing or something. And then the people, you know, the builders came, and at the time the house cost almost $100,000, which was considered way out of line. Now, of course, if you can get a house in Palo Alto for less than $1 million, you consider yourself very lucky, even a very small house. But at that time this was considered a rather large house, and we had to, we didn't have enough money in the bank to pay for everything, but we, so we didn't put in the wood panelling until a year later, and by that time the price of wood had doubled. And we didn't put in the organ until four or five years later. If you look in my book, in the index to Volume Three, you'll see, Royalties, comma, Use of, and that refers you to a page where there's a picture of organ pipes. And, you know, the fact that my book had been selling well, meant that I got about a dollar for every copy that people bought, and, you know, that book has been amazing. It still sells more than ten copies a day, every day of the year.)

48 - Volume Three of The Art of Computer Programming

Volume Three is this, is this book about, about sorting and searching, a field that was, that was changing greatly at the time I was making the final version of that. So, I'm thinking about, I'm thinking about sorting and searching as I'm in Princeton. You know, I've finished Volume Two and I'm ready to come to Stanford, and, and, but, but I'm getting new ideas about sorting all the time because the field is changing. So, after I arrive at Stanford, I have to teach courses and start brand new things that I've never done before, so it took a while, and I wasn't able to finish Volume Three until I was in Norway in 1972. That was my sabbatical year. It wasn't really a sabbatical year. I called it a sabbatical year, but it's, it's a leave of absence. I'd been three years at Stanford, and I, I thought, oh, it would be great, professors are supposed to get six years and then a sabbatical, and then six years and a sabbatical. I thought, maybe I'll go on a four year cycle. I'll go three years, a leave of absence, then three years and a sabbatical. That was okay with Stanford's rules. And so, I got an offer from the University of Norway to spend a year there as a guest professor and I didn't need financial support from Stanford, so I could, so I could do that, run a leave of absence without the, without, you know, the problem of, of who's going to pay for it, and I loved Norway. We had visited there in 1967, believe it or not. That was another thing that happened in 1967, and so I fell in love with that country. In fact, the Norwegian National Anthem, vi elsker dette landet, we love this country. And so, I, I went to Norway and that was where I, I completed Volume Three and began to work on Volume Four. The, during that year I gave lectures at the university every Wednesday, and stayed at home and did my, my book writing and reading and taking care of my kids the rest of the time. So, finally then Volume Three came out and it was, it was, it added a new dimension to this whole idea of analysis of algorithms, because when you start talking about the, about the topics that are in Volume Three, it turned out that, that there were many - even though the, it's talking about particular things, sorting, searching - the lessons that you're learning apply to many, many other things, and so, and so that was why Volume Three was, was especially important for me, that it, the paradigms, the methods that we use to study algorithms of all kinds seemed all arise in the context of sorting, so I could make a unified story about it, but also, but from teaching general principles while being able to illustrate them around the special theme of sorting and searching.)

49 - Working on Volume Four of The Art of Computer Programming

Then I come back home and I'm thinking, okay, I'm ready, I'm going to do Volume Four, and I, Volume Four is about Combinatorial Algorithms. Now, combinatorial means, deals with zillions of combinations of ways to do things, and, and as a result there's, there were many, many problems where people, people had been wanting computers to solve, because they couldn't solve them. So many cases had to be done. You needed a computer to do it, yet nobody could figure out how to do it efficiently. And so, a good idea could, could make a method run more than a million times faster, and I was collecting all these good ideas but people kept having more and more good ideas. And so, there's something in the field called Combinatorial Explosion, which means to most people that the size of a problem is growing, is growing huge, very rapidly. To me, Combinatorial Explosion meant the research on combinatorial methods was growing explosively. In 1974, five and six, when I'm working on Volume Four, more than 50% of all the papers in all the technical journals were about things that belonged in Volume Four. So, in other words, it's like sitting on top of a kettle that's boiling, you can't control it. If I'd write something one week, it would be obsolete the next week. It's like, you know, trying to write a book about the internet today, or something, you know. So, it looked impossible to finish Volume Four. I was doing my best, you know, and gathering material for it and reading section, making lots of notes, and upstairs I have hundreds of folders of, of these notes. I started and I had 30 folders and they were well-organized, and then I made folders called X1, X2, X3 until I got up to X15, not well-organized but just extensions to the system, and then as new material came in I started throwing it into a pile, saying I hope to have time to read this some day. So this field is growing very fast.)

50 - Poor quality typesetting on the second edition of my book

The publishers of my book are happy with the sales and so on. They say, now, let's come out with a new edition. Let's come out with a new edition of Volume Two, and they, and they, and I had, I had thoroughly revised it. Another one of my projects in Norway was to go through page by page and they had it on tear sheets, and you know, I tore up the other book and then I said, okay, now add all this copy. So I rewrote more than half of it for the second edition. And so then they, they sent me back the galley proofs for the second edition and I was shocked, I, I couldn't believe it. It looked awful. The quality of typesetting was, was abominable. It was a pain to read. You couldn't look at this because they had changed the printing technology in the meanwhile. The, the books in the first edition were typeset on a Monotype system, a lot of handwork involved, and the books in the second edition were printed with, with a photographic method instead of, instead of lead type, and, and the, the letters weren't positioned very accurately on the films and some of them were darker than others. There was no quality control. The subscripts were in a different style than the, than the letters in other parts of the formula, so the math looked especially atrocious. Anyway, I didn't want, I didn't want my book to look like this. I couldn't stand to have, to have such a thing coming out as my work, when I, you know, when the first edition had been the quality that I loved from my calculus book in college. And so I was extremely upset. I didn't know, you know, what I was going to do and I went and took another trip to Boston and I talked to the, to all the people there and they sympathized with me and they said, well, maybe they could go through some undercover people in Poland who might be able to make a better copy of the old typefaces and, and do a better job, but the proofs that I got from that were, were awful too. And they were contracting out to the people who were the best in the world at this new technology. The old technology was dying out. You could still get some places in Hungary that would, that would use it and maybe in India, would do Monotype setting of mathematics, but the people had died who had this skill. And the, the printing industry had gone to the new technology because it worked fine for newspapers and magazines.

For the typesetting?

For the typesetting; and for mathematics, nobody cared. Mathematics had always been considered penalty copy that, you know, that, that you do. It had gotten, Addison-Wesley actually had the best mathematics they, they had a man named Hans Wolf, who had learned his typography in Germany, set up his type shop to do all Addison-Wesley's books, right next door to Addison-Wesley headquarters in Massachusetts. And that's why I had liked his books, because he had, he had, you know, taken the old technology and, and perfected it, and, and he was retired, you know, and all the people and the, you know, the apprentices, they, they disappeared from the scene. So, I was at quite a loss, and meanwhile, I was at Stanford. I was Chair of our committee to design comprehensive examinations. The, the students are supposed to take two examinations before they do their Ph.D, one is comprehensive and one is specialized. So the comprehensive, they're supposed to know a little bit of everything, and the specialized is in their own field, whatever it is, artificial intelligence or whatever. And so, every year one of my committee's duties is to read the new books in the fields and to, and to see which ones to recommend for the reading list for the students the following year, and a book came out by Patrick Winston, which was only in galley proof form, but this, but it was a book on artificial intelligence that was typeset in a new way, and the, the typesetting had been done in Southern California on an, on a machine that was completely digital. It wasn't lead type, it wasn't photographs, but it was, it was pixels. It was bits like we now have in all of our printing equipment now, but at that time it was, you know, the digital printing at that time was not considered good quality, but this, at this machine made by Triple I Corporation-Internat- I can't remember what III stood for, but its headquarters was in Southern California. This machine was used to typeset the book by Pat Winston, and they sent galley proofs for my committee to look at, and I looked at this and this was produced by a computer and it looked gorgeous.)

51 - Deciding to make my own typesetting program

I was about to do my first real sabbatical, by going, and I was planning to go to Chile in 1978 and learn Spanish, and, so, but in February of 1977 I see these proofs from Winston's book and I know that it's done with pixels, with bits, and that is a computer science solution. That means these pixels are zeroes and ones, these are in every part of the, in every tiny little part of the page you say, ink, yes or no, and yes or no, zeroes and ones, that's a computer. So, so printing had suddenly been reduced from a problem for metallurgists or from a problem for optic, people in optics, you know, photography and lenses to a problem in computer science, a problem about zeroes and ones. All of a sudden printing, high quality printing was just a matter of writing a computer program. And now, if anybody in the world can deal with zeroes and ones, it was me, right? Anyway, I'd been studying, you know, looking at galley proofs for ages, and my father had printing presses in the basement, I didn't mention that. So, I'm interested in type and I also, you know, see now that it's a computer science problem. So I changed my whole life plan. I wrote to the people in Chile saying sorry, I have to stay in California because we have special equipment here that I'm going to need to do my work with during the next year. I'm going to try to figure out a way to print my book by making it myself out of zeroes and ones instead of using any photographic or metal methods, and then, then I'd have perfect control over it, and if technology changes again, I'll be able to survive the change because I'll have the thing in digital form. And that was within a week of seeing the proofs of Pat Winston's book in February that I, that, I made this decision to stay at Stanford for my sabbatical year and work on typography.)

52 - Working on my typesetting program (Part 1)

In the beginning of 1977 I spent the first three months writing part of Volume Four. I, you know, I completed all my reading for Volume Four and I was ready to finally type some pages, and I typed up a hundred and some pages, but in the meanwhile that was that overlap of the period when I had discovered about digital typography, that you could get good quality from computer output. And so, my plan had been to go to Chile and spend a year working on Volume Four, my, my first real sabbatical, and I cancelled that to stay at Stanford and I stopped working on Volume Four, put that on hold starting in April of '77 and began to say, well, let me spend a year writing computer programs that will make my book look okay again. And so, first I thought, I had seen some people at Xerox Palo Alto Research Center playing with letter forms, Butler Lampson especially, I remember sitting in front of a computer monitor and he had a big capital B on the screen and he was looking at spline curves along the edge that would trace the edges of the B, and I thought, okay, that would be pretty easy, I'll, I'll just capture all of the letter forms from my book, I'll go over to Xerox and use their equipment and, and I'll write a program that reproduces the format of "The Art of Computer Programming", and I have a year to kill, so I'll do this. Well, the first thing that went wrong was Xerox said, oh yes, it will be fine if you come over and use our equipment, but then we own all of the fonts that you produce, and I said no, no, I wanted these, you know, these are mathematics that- I mean I come out of here with a bunch of numbers that say where the edges of these letters are, but these are just numbers. How can you own these numbers? You know, the numbers belong to the world. But so I, anyway, I decided I would work at Stanford instead. Stanford didn't have very good equipment. The, we had some old TV cameras, and if you changed the lighting by a little bit in the room, the letters would get 50% darker. So, there was absolutely no way to get consistency between one day's work and another day's work, and consistency is really important for, to get good looking letters.)

53 - Working on my typesetting program (Part 2)

I decided to go to Stanford instead and there, at that time, Stanford had a really great artificial intelligence laboratory up in the mountains presided, presided over by John McCarthy. He welcomed me to come up there and do anything I wanted and it was a great place to work for the year that I spent, but we didn't have very good, very good equipment compared to what they had at Xerox. We had TV cameras that, that I could use, but if they changed the lighting in the room just a little bit, the letters would change drastically from thin to thick or vice versa, so there was no way to get consistency from one day to the next. I should, I should mention that my publishers had sent me beautifully printed copies of, of previous editions of my book. What I mean by beautifully printed is, the way the books are actually produced, are kind of interesting. With monotype, they set in lead and they print one copy, and then they take that one great copy and photograph it and print offset off of the, off of the film that they've taken, and that was getting great results, but they had saved the original copy that came off of the lead, so they sent me 50 pages of the, of the real, absolutely definitive versions of what had been used to do the previous edition of my book. So I took these to the, to our TV cameras at the AI lab, but I couldn't get any consistency at all. So I, so I didn't know what to do about this. I was talking to Jill and she said- well, she could make some good slides, she could, she could photograph these pages and we could make 35mm slides and they would be sharp, and we could see what we could do with, with that instead of working with a TV image. So, we tried that and then I got my home projector, and I, and I projected the 35mm slide from the end of the corridor onto a wall and so that it would be large enough, and I could trace on a piece of paper what the letter forms were. But the images were very fuzzy. When enlarged that much, you know, we didn't have any way to magnify things now, like film scanners or anything that didn't exist. Certainly we had no such equipment. So I'm sitting there looking at these, trying to trace the letters and figure out what are the shapes and, and suddenly it occurred to me, you know, these letters were actually designed by a human being who had something in mind, and if I could only psyche out what that person had in mind, I could, I could write mathematical formulas that would match that person's intentions. This was a weird, a weird dream, but anyway, this was what, I was naïve and I thought this would be fine, and as I had said, when I was in high school, I played a lot with graphs and the relationship between shapes and, and mathematical formulas that make those shapes. So, so as I'm sitting there with my pencil and paper trying to, trying to trace the outlines off of these blurry slides being projected on the wall, you know, I noticed a lot of regularities. For example, I noticed that the letter n was exactly twice the width of the letter i, and the letter m was exactly three times the width of the letter i, and okay, great, you know, there was consistency there, that if you have a word like minimum, all of those vertical strokes are coming exactly at the same spacing. Also the u was, you know, the same width as the n. So it occurred to me then that if I could figure out, you know, what all these principles were that the type designer had done, it wouldn't be too much of a problem to capture that in mathematics. Okay, so instead of using- so then my whole focus shifted so that I wasn't going to just copy the output of a previous design, I was going to try to, to discover the intelligence behind it, and program the intelligence into the computer, so that you could tell a computer, draw a letter m, and it would draw a letter m, and I, but I could say, now make it a little bolder, now make it a little taller, a little narrower, and it would adapt everything correctly. Now this was a weird concept to type designers. Type designers always, you know, approached it with a completely visual approach and no mathematics, probably thank goodness, because they came up with beautiful design, but at any rate, I naïvely thought that this was going to be easy, and of course my whole, my goal, it was to have Volume Two ready for the printer after my sabbatical year. I had one year to write these programs and to, and to capture the letter forms and figure out how to typeset them.)

54 - Research into the history of typography

I wasn't going to go into this whole project blindly, I wanted to, I wanted to avoid the mistake that almost every engineer makes when they approach something with technology and that is to say, well, forget the past, it's all a new world, throw, throw the old stuff out and redo everything. So I didn't want to, in any way detach myself away from the old traditions. I had these ideas about using mathematics to capture the past, but I didn't, but I didn't want to throw away the past so I did lots and lots of reading in the library, and I studied. And Stanford has one of the best collections of books on fine printing, called the Gunst Collection in its, in its department of rare books. And so I spent lots and lots of time looking at all the books I could get my hands on, on typography. Also, my wife and I were members of the Associates of the Stanford Libraries, and we went on a trip to Sacramento where we could see the Gutenberg Bible and various other typographic specimens. There was a show put on there at the Sacramento Bee Office about history of typography and beautiful things, and we visited people who lived in the mountains and had their own printing presses and, and collected books on typography. So this was a two day trip into Gold Country, and we, and I'm staring at all of the letters that I see, and saying, how could I capture this in, in a computer? This was all taking place in the Spring of 1977.)

55 - Working on my letters and problems with the S

In June of 1977 my sabbatical begins, classes are over, I'm ready to go on this and I, and I had sketched out ways to do lower case alphabet, A to Z, and with mathematical specifications and I thought great, this will, this will solve my problem because, you know, I can make the letters all different sizes with slight changes in the specifications. A good type design doesn't just make nine-point letters, nine tenths of a tenth size of a ten-point letter, but they also make them a little bit wider, subtle changes in the, in the greyness of the characters and, but I could design my program with these parameters to do the variations and draw each letter to each size properly. This is a very natural thing for a computer scientist to, to do because we're used to specifying things with parameters all the time. I mean we, we have a job to perform and we, we have certain things variable, and we twiddle those dials and that will give us a different output. What, but I found out to my surprise that when I was talking later to people in the graphics industry, I, they hadn't heard the word parameter before, and they thought it meant perimeter and, and I mean, it was something that, you know, but computer people think it's just as natural as anything. Well, so I came up with 25 of the 26 letters in the middle of June and they weren't beautiful but they were pretty close to, to being okay to my eyes at the time, but then there was the letter S, and I couldn't figure out how to draw a blasted S. And, I- it has a very peculiar shape where it changes over from curves, sort of, curves left, then right a little bit, and then back and forth, and what's going on in this shape. None of my mathematical formulas would, would handle it, and I spent several days without sleep up at the lab, you know, trying different things and every time it would just look very ugly. And after, finally, I had to come home and, you know, and, and go to bed and I showed my results to Jill and she said to me, well Don- why don't you make it s-shaped? That was her solution to my problems. Well, oh man, what was I going to do? So, but, but finally after, I don't remember how many days it was, counting the nights, anyways, it seemed like an eternity, I, I got the idea that if, that I could go back to a geometry problem that the Greeks might have enjoyed about ellipses, where if you have an ellipse in it, and you try to make it, the ellipse just big enough so that the tangent, as it's coming down, meets things in a proper way, it, we- become a problem that would be interesting to Euclid or somebody, although I don't think it was, would appear in his work. And that would be a way to actually figure out, the ellipse would be for part of the S, and when it comes to this tangent, then we go off on that tangent and go to the other part of the S, and so I had finally a mathematical formula that I could, that looked like an S, and I could change some of the parameters and it would look like a slightly different S and so on. But before I came up with that formula, I was thinking, well, maybe I could change my book, you know, and try to avoid using the letter S entirely, but then I, you know, I'd have to leave Stanford. So it was, I would go, you know, visit Safeway and they had a funny looking S, you know, and I would see all the different S's everywhere, but to finally solve the problem of the S, right, but incidentally, I never did solve the problem of the dollar sign, though. The dollar sign that I have is still pretty ugly and, and I'm waiting for some new idea to come along, but I never was too much interested in dollars really, so I didn't bother to spend too many days on that.)

56 - Figuring out how to typeset and the problem with specifications

So then I had 26 letters, but I had to go on and figure out how to typeset, how, how to put them on the page next, so I stopped working on fonts and I, and I started to just figure out well, how am I now going to specify my book. This was what, you know, I, this was very early days, now there's all kinds of software that does this, but nobody had it in those times, except there were some good programs written for the newspaper industry, especially in fact for "US News Report"and for "News Day", and, and so the people who had written those programs were students of friends of mine, and, and so I went and talked to them. I looked at the programs that were available. I looked at the programs that had been used to typeset the Volume Two that I'd thrown away. That typesetting was done in Belfast by, by a company that was top of the line as far as commercial mathematics setting was concerned, and they, they knew their business but they just didn't have good fonts to use for the output of their system, so I, so I looked at that system, and I looked at a system that was developed at Bell Laboratories and, you know, every, every other system for this, and I, then I sat down and I took ten sample pages of my book and I said, you know, as soon as I get those, these pages working then that'll handle all of the formats that I need, you know. In fact, these were just fragments of pages, but I have, have lots of different kinds of things going on in my book, from ordinary copy to, to math formulas and algorithms, computer programs, table, tables and figures and all these different typographic features, but it, it boiled down to four pages of stuff, with changing a lot in it and I, and I sat down and I said, okay, here's how I would like to specify those four pages of, of sample text for a typesetting system that would work. And I stayed up all night one night typing this trial language for, for capturing my book, and, and then the only problem was to imagine a computer program that would go from this input to zeroes and ones on the page. That would, that would do it. And so, then I stayed up another night writing up the rules of this language and showed them to some friends a couple of weeks later, revised those rules. Then it was the middle of July and time for me to go to China. I had, with some other people, my, my wife and kids and, and three other people, we took a trip to China. This was kind of early days for China. Mao had just, had died less than a year before, but we were invited to spend three weeks at, in various parts of China and see the country, and, and it was kind of a unique opportunity, and also for, for my kids, they were some of the first children from the USA to be allowed into the, into mainland China at the time and so we had, so that was my summer plans. So I had two student assistants that summer, and I presented them with my specifications for, for my typesetting language, which at the time I called TEX, now we pronounce it Tech, but you know, first it was called TEX, you know, and I, and I assumed that when I got back from China they would have the computer program working. Then I, you know, then I can go on and do the next part of my work. Well, I had a great time in China and I came back, but to my surprise, they hadn't even gotten one page out yet, one test page done, and, well, another student had made some progress on the question of hyphenating words, but I was a little bit surprised that, that it turned out to be so difficult, when I thought my specifications were so clear. Well, this was my introduction to the reason why so many software projects fail, because people think that specifications are clear, but, but really, as soon as you try to translate some specifications that seem clear to a human being and, and explain those to a computer, you know, there's all kinds of questions that come up that you never anticipated. So, here the students are, and every time they, they come to, to a new part of my specifications, a question arises and they can't ask me because I'm, I'm off in China. So then they have to meet with each other, and say, what did he mean by that, you know? What did he think? And so on, a get-together. And so they solved that, and they, they'd work for another half an hour and they'd come up with another such problem, you know, over and over again. So, it was miraculous they got done as much as they did, that, you know, while I was gone. Anyway, they did show me the program that they wrote and that, that gave me an idea for architecture or structure that I could use when I had to write the real program myself later. So then they go back to school, and I come back and I start, and I start programming in earnest.)

57 - Working on the programming for TeX and using a structured program for the first time

I started programming in a, in a way that I hadn't done before. During the '70s, a style of programming was developed called Structured programming, which made it easier to, to produce reliable programs, programs that you could understand as you were writing them, and, and I had done some experiments with it on a lower, on a smaller scale, but this was going to be my first large program written with this methodology of Structured programming. And the new thing was that as I'm writing the program, I didn't feel the need to test it, to test each part of it as I was writing it. I could just write and write and write and assumed that after it's all written, it'll be pretty close to working. So what actually happened is that I, I started writing in September or October, and I didn't test, I, I didn't actually enter any of the program into the computer or test it or debug it until the next March, so all these months are going by, and, and I didn't feel the need for a prototype or any, any, I mean, when most programmers write something is they'll put, they'll put something together and then that's only part of the program so then they'll mock up the missing parts to have something that pretends that these other missing parts are there before they write them, but then, then later on when those parts are there, then they can continue, and they, and they build up more confidence all the time. Well, with structured programming, I already had pretty much confidence, so I didn't feel the need to dummy up these extra parts, and that saved me a lot of time because all the time that I would take to write, to write the dummies, I no longer needed. But, sometimes I have to admit a few twinges of doubt, you know, you had five months going by between the time I wrote the program to the time I'd get to really try it out, but you see, I couldn't. One of the things I would have had to dummy up was the whole, the whole question of fonts. I couldn't do typesetting without the fonts, and I had to write those, I had to do all those fonts as well, and that was, you know, three, three months of that five was to get the fonts going.)

58 - Why the designer and the implementor of a program should be the same person

Getting the first version of TeX to work, I also had to get the fonts ready, the letter forms, and after, after five months I had something I could finally test, and I, but after, after two days I realized why my students hadn't gotten any further than they did, because I had to keep changing the language constantly, every, several times an hour as I was beginning to write the code, and if the students, several of my friends have tried to, to direct software projects where they set the specifications and they say to the students, write the code, and it never works, and now I know why, because the students would have to schedule an appointment. Every few minutes they have the students working on it, they have to schedule an appointment with the professor to, to discuss what the issue is, and then the professor would have to, you know, take 15 minutes to get in the frame of mind to understand what the problem is, or he'll say, oh yes, do this, and then the student can go back and work for another five minutes before another question comes up. So it just takes forever. When you do enough, working on a first generation software like this I think it has to be done, the designer and the implementer have to be the same person.)

59 - Converting Volume Two to TeX and how an implementor/designer should be the first user of his programs

By the time, by Easter time then at near the end of my sabbatical year, I finally was able to typeset a few, a few sample pages of, and got my, my test program going, but I didn't have Volume Two done by any, by any stretch of the imagination. Still, it was- enough was in place that I could see that it was going to be possible. I guess I should mention that I had no idea that I was designing a typesetting system that anybody else in the world would ever use, besides me and my secretary. My idea was that, that I would teach Phyllis, whom I, who was my secretary for almost 20 years, and I dedicated one of my books to her, that's a long story there, but anyway, so Phyllis and I were going to be the users of this TeX system, and I tried to make it so that she, you know, I knew she'd be able to learn it, but I tried to design it just, just good enough to do my books and no other books. So, so the next phase was however, for me to go through the entire manuscript, the Volume Two, and I wrote a program that converted from the Belfast system to my new system and that would be, that would be a close approximation, and I started in. Well, it was several months of work, it's a 700 some, 700 or 800 page book, but another, I learnt another important lesson during this time. Not only should the designer of a system be the first, that would be for the implementer, also has to be the first user, because I'm actually using the system, I'm always getting ideas about how to make it better, and if, and if I'm not a heavy user, but just a designer, I don't have the experience to know why those features are useful. So I kept track of all of the changes that I made to the system at this time, and I also knew how many pages I had been typesetting of Volume Two. And I went through and, and made a graph of it afterwards, and it's almost a perfect straight line. Every four pages I typeset, I got a new idea, you know, I'd do, I'd do 200 pages, what is that, 200 divided by four, have a computer, 50 new ideas, right. So, and it's a straight line until I got up to about 500 pages, and then it's flat. After that it was all boring. The last, you know, I mean after, after a certain point there was no learning curve anymore. I knew all the things that needed to be improved, but, but those many changes that I made at the beginning, were, were certainly important for all future users of the system, although I didn't know that there would be any users of the system at the time.)

60 - Writing a user manual for TeX

However, the AI lab is a very open place, there's, there were dozens of people and lots of visitors, and no doors closed, and so people are looking and saying, what are you doing, Don, and they, they see this interesting stuff coming out of the printing machine, and so, pretty soon it became known that I had a system that would typeset something that looked almost like a real book. And, and one of the visitors was Guy Steele from MIT, and he said, Don, I want to port, you know, I want to port this system, I want to modify it so we can use, we can use it also at MIT. I thought, oh my goodness, should I have other users, you know, but then, by this time I could see that other, you know, that there were enough people expressing interest in it, that, that I had better write a manual, and expand that. It wasn't going to be just Phyllis and me using, using it. So, then during the summer of '78, I wrote a Users' Manual and it was a little bit interesting that the, our computer was extremely unreliable up there. The people, the people, we had four really brilliant computer scientists improving the operating system every day, but, but because they were improving it every day, it would, every day it was also crashing because they would make mistakes, and so, so I wrote the entire User Manual during computer downtime. I'd go up, you know, I'd go up there and the computer, you know, at nine o'clock in the morning and the computer would crash at 09:30, so I, I opened my tablet and I'd write another chapter, the computer comes up ten or eleven o'clock, and I can, you know, do a little more work until, until it's ready to write another chapter. So, I learnt another lesson there and that is, if you have a system that's always improving, nobody gets to use it. And I and I'll talk a little more about stability of software later on. The, the budget for, for operating system work ran out the next year, and so three of these four people went to Livermore to work on another system, another project, and the fourth guy, Marty Frost stayed and his job was not to make any more improvements, but just to make sure that it was stable, that the system was stable and reliable. And so, so that was the greatest thing that the system wasn't improving any more after, after '78. And I dedicated a book to Marty also.)

61 - Working with The American Mathematical Society and giving the Gibbs Lecture

I got my Users' Manual ready and had visitors from the American Mathematical Society. They were, they were, they had horrible typesetting problems. They're the largest publisher of mathematics in the world, and they, they tried to do their best with their journals, but their journals were looking terrible, just like, you know, just like my books. They were, they were upset about that situation, so they had heard about rumours of my system. Even their, their most prestigious publication, "The Mathematical Reviews", which they had typeset by a really expensive company, that company couldn't do all of the operations that they wanted, so they came, visited me for two weeks and took a look at my system and I, and I showed them some mock-ups of how we could maybe typeset journals as well as "The Art of Computer Programming". I was invited then to give, to give, something called The Gibbs Lecture of the American Math Society. Every year it's one of the main invited lectures to the main annual meeting, and the lectures are usually given by a pure mathematician, but every four years they take somebody who's more applied, so Einstein had given one of these lectures, you know, all the various glorious mathematically oriented, mathematically oriented physicists had done, so it's quite a thing to get, to be invited to give a Gibbs Lecture. I decided my Gibbs Lecture would not be about what they expected in computer science, but I was going to talk about typography, so my Gibbs Lecture was about mathematical typography. And I still, I still didn't have my fonts all done though, for Volume Two, I just had enough done that I could test my system, but there was still a lot of work to do to get the, to fine tune and to make it look like, like a high quality thing. Still, I could give the Gibbs Lecture in, at the end of, well, it was the beginning of 1979, and it was a big hit with the, with the audience, so I knew that there was also a hunger out there for, you know, for, for people being able to do better typesetting of the mathematics.)

62 - Developing Metafont and TeX

Somebody suggested that I call it Metafont, because it wasn't my, yes, it wasn't something I, I made up myself and I can't, I think it was maybe Bob Filman, but I can't remember for sure, but as we were looking at these things up at the lab, there was lots of visitors and people talking to me all the time, and that, that was a nice name because of the parameters. I'm not designing just one font of type, I'm designing a font that varies with the specifications, you know, it varies substantially with different specifications, and the, and so there's lots of like words, like metamathematics means going a little beyond mathematics or metaphysics, metaphysics really meant after physics in Greek, but the word Metafont turned out to be kind of appropriate. Now, it's something like morphing, in a way that you can go from one shape to another, that's why I'm thinking metamorphosis here, and, but the, my first programs for fonts were, each, each letter was drawn by a specific computer program written in computer language. I had to change that so, so that I could devise a special language just for fonts, so that it was easier to make changes and, and to make the design. Instead of writing computer code, you know, the language like ALGOL, I could write now in this Metafont language, and then I would have an interpreter that would read the Metafont language and draw the shapes instead of the original way, which was calling subroutines that would, that would draw the shapes. So, it was a completely different kind of a language than had existed before and, but I came up with the first design of a Metafont language in 1979. Now, as the number of users grew from one person to ten people, I needed to change the system because they had different, you know, they'd discovered different bugs, they needed different, different facilities. Then it grew from ten to 100, and again, I had to add more stuff to the, to the language. By this time it was called TeX instead of Tex because there was already a system called Tex, and the, Honeywell refused to give us permission to use that name, even though their system was an operating system, not a typesetting system. We couldn't do that. So, we said, well, this isn't Tex, this is TeX, this is Greek, Tau Epsilon Chi, it's not, it's not an English word at all, it just happen to look very much like the English word Tex. And well, we told all the users to pronounce it TeX, and, but their lawyers didn't think that wasn't much, enough of a distinction, so we left it on paper that, you know, if they want to sue us, you know, we wouldn't, we didn't get an official registered copyright, we just have it as a copyright, not a registered copyright. Metafont on the other hand, is a registered copyright. Nobody was complaining about that name. Well, I was going to say, as we get, as we get ten times as many users, then we need, then I have to go back and retool the system. This can, this can be too long a story, so I'd better start summarizing. The first version of TeX, a prototype version, was called TeX 78, because it, it saw the light of day in 1978, then there was Metafont in '79, but these are quite different from the Tex and Metafont systems that we have now. These were the first versions. I have another policy that I recommend, and that is if you're doing a first generation piece of software, get it working, do your best, try to get it so that it's perfect and then get a lot of experience with it, then throw it away and start over. Scrap it and don't worry about being compatible with the old, because there are going to be many, many more users in the future than you ever had in the past, even though there might have been thousands of users in the past, there will be more, you know, tens of thousands in the future and they'll all thank you for having a better, a better system. I don't do it- the second one I keep though. And now there's so much invested in it that, that I'm sure that I would never want to use a system that, you know, that I never want to change again to a system that's incompatible with the one that I've been using for so many years now. Okay, this is, this takes us then to the point where suddenly we have users from around the world, and even now a meeting of people coming to Stanford to take a look at this system and to try to get it running and not- at first it was running at MIT but, but then it was, it was running at hundreds of different kinds of computers all over, all over the world.)

63 - Why I chose not to retain any rights to TeX and getting it transcribed from SAIL to Pascal

From the beginning I decided that I wasn't going to retain any rights to this system, except the right of, of nobody should, should, should diddle with it. They, anybody could use my system free of charge as long as they didn't make any changes whatsoever. It had to be entirely compatible with the system that I had, and, and I wanted, so I didn't want to charge for anything. If I had, if this had been the only thing I had worked on in my life, I would have probably, I would certainly had a different idea, but I, but I had seen the way proprietary things had been holding back the printing industry for years and years. There were five or six different commercial systems for describing pages of text, and they were, everybody thought they were the systems that everybody in the world would use, and they, and they were totally incompatible with each other and they, and you couldn't use different fonts with different systems. It was all, it was all a mess. So, I was thinking that in the earlier days of computer programming languages, IBM did not keep FORTRAN as a, as something that was an IBM-only language, they allowed, they allowed dozens of other manufacturers to make their own FORTRAN versions, and as, and that was, that was a big boon to the, to, to use of computers. I, I could see that the same would happen in, in the printing industry if, if I didn't retain proprietary rights to, to the use of this system, and I also made all my code available so people, people could read it and see what I had done and find mistakes for it, and I paid people if they found an error. So, thousands of volunteers sprung up all over the world, helping me get this, get this system better.

Is this when you invented the Weave and Tangle?

So, the literate programming idea, the Weave and Tangle came about shortly afterwards in 1982. First of all, I had written my program in a, in a Stanford-only language. It was called SAIL, Stanford Artificial Intelligence Language. It's something that not many people could do, but I, you know, so, so in order to run at first on other machines, it was difficult unless they'd happen to have a PDP10 Computer which is, with a SAIL compiler. So, in the early days that's why MIT was, were one of the first users, and there were, there were quite a few installations of this computer and system, but not, but it was, it wasn't on very many different machines, so I don't think on IBM mainframe you could run, you could run it. So then a student transcribed my code. This was Iñaki Zabala, transcribed my code into Pascal, I think David Fuchs and Art Samuel also worked with him on this. Anyway, lots of people were working on this, I didn't do it myself, but they, they transcribed my, my program from the SAIL language into Pascal language and then that would run on, on every computer and that's, that's where we had hundreds of, of, of different users and then we started having a, having annual meetings of the people who were from around the world to trade information.)

64 - Tuning up my fonts and getting funding for TeX

After I had so many users, I realized that the, the original, my original designs were too naïve. They had, I had to go, I had to retool them and, and so the, as I was doing it, I, I came across the idea of literate programming at the same time. But I have to postpone that a second first because meanwhile, with the old systems, with the TeX 78 and Metafont 79, I also wanted to tune up my fonts, you know, so that I could, so that I could really match the, the letter forms, and I'd been reading a lot of, I'd been reading a lot of things about font design and learning more about history of letters, and so I, I was also talking with and meeting people at, in industry, like Linotype and you know, Mergenthaler, and so they introduced me to, to type designers and especially I got to know Chuck Bigelow and Matthew Carter and eventually, Hermann Zapf, who were the three of the four leaders in the field. The fourth man Frutiger, I never did meet. He was, he was ill, but, but I could have if he had been, if he had been healthy. But, but, so, so they helped me get the worst glitches out of, out of my, my designs and when I had the, the Metafont 79 I could, I had the benefit of their comments to, to revise my designs. I also, I also had to buy a typesetting machine, and so I took trips around the world to different places, to where they had different experimental type typesetting machines, and when we finally got one, it was called an Alphatype, which had the highest resolution of any machine that I, that I could get in. It was also, we could afford it. It cost us, I don't know, $40 or $50,000. I think Addison-Wesley paid for $20,000 of that. We were running on a shoestring, but, but it turned out later we got, we got good Research Funding. I was supported by the National Science Foundation to do research in algorithms, and that was including, as far as they knew, that was what I was going to do during my sabbatical year and I said, you know, my research on algorithms is going to, going to have the following seven parts to it. And the first six parts are, I'm going to study algorithms for, you know, various combinatorial problems, and the seventh part was, I'm also going to work on algorithms for, for typesetting so that I can explain the research that I'd done on the first six parts of my grant. And really, I spent all my time on, on part seven, pretty much because I had the other research basically done already, so I could, I could still have the other thing on my, on my progress report, but I was working full-time on, on this typesetting. And, so they were supporting it through the backdoor. And later on, System Development Foundation learnt that. Well, I met with NSF people and we were open about the need for it, and they said, why don't I make a proposal to another division of NSF for, to work on digital typography after the, my Gibbs Lecture and so on. Then people knew about it, and so I got, so I got NSF support also from another division, but then the System Development Foundation was a special thing that they were trying to spend a lot of money wisely that had been left over from the System Development Corporation's Sage Project in Southern California, and they, they supported things like Stanford's center for Music and Acoustics, and they gave me $1 million to, in the words of their Chief Financial Officer, who, what you call him, he said he wanted to give me this money so that I could finish the work on TeX and get back to "The Art of Computer Programming". So, so I had good funding eventually, but in the early days it was, it was, we were not flush with money by any means. So, I get advice from the top- the world's top designers, they look at the letters and they mark it up with red pen and, and then I fix it until it satisfies them. And I get this Alphatype Machine, and in order to run the Alphatype Machine I had to write my own software for the insides of the machine. It had a little, tiny 8-bit computer in it with six levels of interrupts and I had to write my own assembly program for it, and, and it had very little memory in. We had to transmit from our mainframe to this computer with little Zilog machines. So, it was a heck of a lot of fun, but also very frustrating too, because this, this machine is deaf and blind, and it took a lot of work to get it going. Finally I was able to typeset on the Alphatype, and I had pages that looked like, that looked like, you know, high resolution and much better than the ones that I did. So, I, I, I, after all this work, I started in 1977 and, and continuing on much longer than the year that I thought it was going to take, I finally had Volume Two all ready and printed on the Alpha Type and I could send it to Addison-Wesley for them to photograph and, and print by offset.)

65 - The second attempt to print Volume Two of The Art of Computer Programming

I was expecting to be, the greatest day of my life when the book arrived in January of 1961, '81, 1981, I was expecting that would be the greatest time to, to open this book and, you know, celebrate. I finally had the project done. Well, it was one of the worst days of my life. I opened the book, and I didn't like it at all, what I see, I mean I had, you know, the, it was the old binding, and, but when I looked at, and I, and I opened it, and it just looked completely different, and I had, you know, from the proof that I'd seen, I had thought that it was going to be, it was going to be fine, but I, I felt so, I could feel this huge rush of heat as I'm looking at it saying- oh no. I had spent all this time and, and I got this, and I tried to, the people were saying- nice job Don and so on, but I couldn't believe them, you know, I, and inside of me I said, my gosh, I'm way far from being done with this and getting something, you know, something decent. The worst thing was the numbers, I mean, most of the pages looked okay if you, if you're not too fussy, but as you're paging through the book, and you're looking for a certain page or you're looking at the numbers, or your eyes are focussing on numbers, and I, and I debugged the A, B, C, D and E, but the zero, one, two, three, four I didn't spend much time on and, and boy, those numbers just were very ugly. So I had to go through another, first I couldn't get the letter S, now I couldn't get a two or a five, and so I would, you know, all the 25 mile hour limit speed limit signs I would see on the road I would say, how did they do that? And, so, anyway, I'm depressed by this, knowing that there's still so much to do. The, but I've got lots of users around the world who don't know that I'm depressed about it, and so I'm trying to, but my font designers then said, look Don, the period of apprenticeship for a type designer is always five years, you've only been working on this for two years, how can you expect to have, you know, have succeeded after two years. So, they were very kind to me and, and through the grants that we had now, I could invite them to Stanford and spend, and, and, and spend time with, with them and, and learn, learn from them what I should've done. And this is when I found that the people in the graphic, the graphic artists are just about the nicest people in the world as far as I've met so far, anyway. So it was a great, great thing. I couldn't keep up with all my teaching at Stanford though, I'm not on sabbatical but I found that doing software was much, was much harder than writing books and doing research papers. It takes another level of commitment that you have to have so much in your head at the time when you're doing software, that, that I had to take leave of absence from Stanford from my, from my ordinary teaching for several quarters during this period.)

66 - Literate programming

Meanwhile I was also coming up with the definitive version of TeX and this idea of literate programming. So now let me go back to the story of Weave and Tangle that you brought up a minute ago. In retrospect, I, I think the greatest benefit to me personally out of all this work on typography was the idea of literate pro- that I decided to call literate programming, which is a way of treating computer programs as literature, where, where the pr- a computer program is something that human beings are, are supposed to read and you write that for people to read, rather than for a computer to read, and so as I'm writing programs, I'm being a teacher. I love to be a teacher. I'm, I'm not just teaching a computer, I'm teaching a, the reader of my program and I'm, you know, I'm hoping someday there will be a Pulitzer prize for the most literate program, etcetera. I started out experimentally doing this because a friend of mine, Professor Hoare, at Oxford said, Don, people don't ever read computer programs. Oxford University Press was interested in maybe publishing some computer programs, examples of how it should be done and so that, instead of just having, just having this sort of, this hidden documents that the computer programs would be out there for people to study and comment on, the way other kinds of literature are, you know, musical notation; people, you know, people publish scores of symphonies, they don't just listen to the symphonies, so why can't we publish, you know, computer programs? And he planted this idea but, but it scared me because really, computer programs in the real world are so full of compromises. A professor of computer science couldn't admit to having written such a thing. We can write short programs that are really, that are, that really look like little gems and we can pretend that when we write a large program, it's all, it's all this jewel-like character, but, but in fact, I don't think any large program would, you know, the authors wouldn't have been proud to have other people to read it as it was done at the time. So, I'm also saying, how can I write a program so that people could enjoy reading it? So, eventually this idea of literate programming grew where I could see a format, by which a program could be presented to other people and the great thing that came out of this was that also, I as the writer of the program would be able to understand it better. So, eventually I had this system where I would typeset, where I'd write a program in this web language and then I would, then I had two computer programs going from it, one of it goes from the web language to, to a computer code in Pascal language at that time, and the other goes from the web language into a document that I can read with things nicely typeset in it, cross indexes and expository developments. This, this system is what I, it provides weekly delights for me to this day, I'm writing programs in, in CWEB, which is the descendant of the original web system, and I, it's a continual source of pleasure to me, to be able to program in this way that I feel is so right.)

67 - Re writing TeX using the feedback I recieved

I rewrote TeX from scratch using literate programming and added, you know, changed a lot of the things that users had found awkward, added, added the features that they needed, and, and the system TeX 82 came out as the definitive one and it's still almost identical to what we have today except for more features for, for European languages. The, so I was finally getting to a system that I could believe would be stable, and had some reason to- During this time I wasn't working alone, by any means, I had not only my, my research assistants but also I had lots of volunteers from the Stanford community and we would meet every week on Fridays, well, at lunchtime we'd bring bagged lunches but we often stayed two, three hours, and as I'm developing the new system TeX 82, there are 22 chapters to the manual, and as I'm writing each part of, of the manual, I'm discussing with the group, what should it really be, I mean, what, all the issues that, you know, it's like I get sentiment from, from lots and lots of people and, and it would not only be Stanford people, but there was always visitors to campus and so we had people from around the world participating in these sessions, font designers as well as mathematicians and these sessions continued as we were refining the Metafont language in later years. So, here I had a great exposure to, to a lot of varieties of opinion, but I had to make the final decision. I, I knew that we had this, I talked about creeping featurism before, that every user wants to have their own thing, and I also know about design by committee, where if you have a committee who's responsible for something, everybody on the committee has to feel that there's some part of the language they can point to, and the language you get as a result is usually pretty disunified. So, I was going to insist that I be the filter for all the ideas and I, and I implement everything and, but I did allow a lot of people to express their opinion and finally I reserved to myself, the decision. The decision of the judge will be final, basically, yes. I wrote the program so that it would last forever, and not, not be always improving, because of my experience that I had with these improving systems, so I wanted to, I wanted it so that if somebody creates a document with TeX 82 in 1982, he can run it also in 2002 and get the same output on every computer in the world, and pretty much that ideal has been realized. Now, I also published the program in a book. The entire code is, is, you know, a 600 page book, "TeX, The Program", it's, I think more people in the world understand that program than any other program of its size, because it was written in this literate manner, and it was, it was, you know, in all countries, people were looking at this and finding out how it works and seeing exactly how they could use similar techniques in their own program. This was done without royalties and, and the only royalties that would come in for people buy the Users' Manual, and, and those royalties are shared with the TeX Users Group, this international group of users for their projects on promoting the use of the language.)

68 - The importance of stability for TeX

This was, this was kind of the birth of, in some ways, of open source software movement, which, which has gotten very popular recently, but it's different from the so-called GNU public license that is a very successful today for most of the open source thing. It's different in one way, that the, one way that's very important to me, and that is that this open source GNU public license software is, comes with the saying that anybody can change it, not only can anybody use it, they can modify it to their hearts' content. I don't allow people to change TeX, unless they call it something else. So, if you, if you make, if you give it any other name whatsoever, then you're free to change it, but if you call it TeX, then it's got to be exactly the same as everybody else's TeX and the one that I personally have, have given, I have special programs that are used to validate whether or not you've implemented TeX correctly. And so, that's different from the open source. In fact, somebody once looked at one of my fonts and said, oh I can improve that, I'll change the spacing a little bit, and as a result one of my books, all of a sudden, didn't typeset the same, and, and, but the, one of the early distributions of Linux included his so-called improved font, and, and I all of a sudden found out from my co-author that, that, you know, that he was getting different paragraph behavior, and we traced it down to somebody, you know, making what looked to him, like an improvement. That's what happens when you have complete, you know, when anybody can modify and they, like the Wikipedia nowadays, you know, it's, you can go to Wikipedia and you can look at any article, and there's a little button you can press saying edit, and you can change anywhere in that article and it's there, it's in Wikipedia. They don't even ask you who you are, making the change. I think that Wikipedia's enormously successful, but it's so brittle, you know, if I was, if I spent a lot of time writing an article for the Wikipedia, and I wanted to make sure nobody screwed it up, I would have to check that article every day to make sure that it was still okay, and you know, after I've done that I want to move on and go on to other, other things in my life. With TeX, I wanted stability especially urgently because people are depending on it to be a fixed point that they can build on, so in that respect, I differ from the GNU public license.)

69 - LaTeX and ConTeXt

I developed TeX so that it would support many different formats that would be at a higher level, so TeX is a fixed point that people can build on, and one of the main ways that people have built on it, is LaTeX and different versions of LaTeX improving over the years. Another very important system goes way beyond LaTeX, called ConTeXt, I don't know how they pronounce it, it comes in a Dutch, in Holland they have very interesting pronunciation in Holland, and, but certainly, way most popular is LaTeX, LaTeX, the author never has decided how to pronounce it, and, and I don't use it myself, but I know that lots of people really think it's exactly the language that's most convenient, you know, for them to use. So, so I developed the basic system so that it would support many different styles for special projects. If somebody wants to write a dictionary between Chinese and Icelandic, they can make their own format that would make this really convenient for them, and there's many, many scholarly versions and for all kinds of versions, so I, I tried to make it easy to build different structures upon. When I have special formats that my wife and I use for family history reports and for our recipes in the kitchen and things like this, each one looks different when you type the computer file, but TeX is the engine underneath in all cases.)

70 - A summary of the TeX project

The whole thing started in 1977 when I was working all by myself and then in '78, we started having other users, '79 we had Metafont, you know, in '81 was the publication of Volume Two in the new format. Many users coming through this time and I've also contacted the good font designers. Then I have to redo all the fonts and I have to have a better language for fonts too, so in 1983 and '84 I had a major revision of Metafont language and, and that's when Hermann Zapf came out to spend some weeks here and we, and he taught me a lot about, you know, things I needed to know as well as help me refine the new version of Metafont language. Richard Southall and Chuck Bigelow joined our faculty for several years. We had a generous donation from the people in Silicon Valley. I was hoping that we might have a permanent project between Stanford Art Department and Stanford Computer Science Department. This turned out to be too difficult to, because we needed more than one faculty person to do it, and Chuck would have been good, but there was just too much for one person to handle, but we had more than a dozen students who have a masters degree in typography, basically, and they're, they've been extremely important in the, in the industry since then. We had this class in font design at Stanford in 1984, co-taught by myself, Southall and Bigelow. Unfortunately, the video tapes seem to, it was all on video, but I think the tapes were erased, but these guys, Bigelow and Southall gave brilliant lectures and I thought they were, you know, they were archived, but somebody seems to have lost them or re, re used them. But that was a big point in the development because I was implementing the features of Metafont one week before they were introduced by the class, and, and this was when the Sun Microsystems- the Sun workstations were just new and brand new software for this, and we were also teaching the students how to use the Sun workstations in order to prepare their Metafont programs and so we had a very exciting time where they were working day and night to make this course happen and it was a huge success. That font language finally stabilized in '84, that manual for Metafont was written and then I had to do my final revision of the, of the fonts, of the, to make them look acceptable, and for this, anyway, let's say I finished that in 1985 and, and so finally, after eight years I was able to bring my typography project to a conclusion. It was supposed to be a one year project for my sabbatical year.)

71 - A year in Boston

Now it was time for my real sabbatical. My real sabbatical year was quite special and it started in the Fall of 1985 and, and I went to Boston. Jill and I went to Boston, and, and the reason it's quite special is because I had promised Jill that this would be her sabbatical, not my sabbatical. It was, some people think it was generous of me, but actually it was just less selfish than I could have been because this was after 24 years of marriage, I was giving her one year out of 25, and so, so this year in Boston, I did the cooking, I did the shopping, I did the, the cleaning and she wrote books, and, and you know, she'd had lots of projects that she'd been saving up and I had my chance to learn how to do these things that she had been providing for me patiently for all the years. It was easier to do it this year than any other year because I, both of our kids were now in college and so I didn't have to, I only had to, you know, take care of her, I didn't have to take care of John and Jenny as well. Although, the kids did come to visit a couple of times, you know, so I learnt a little bit about quantity cooking, but mostly I just learnt how to cook for two. And we lived in downtown Boston in Back Bay and it was very, very pleasant to, I had to walk six blocks to grocery stores and I had just a little backpack so I could carry a few groceries every day, but, and the apartment wasn't too hard to clean. Anyway, it was a very interesting year and I was incognito. I went over to MIT one day only and just to look up a book in the library, but I didn't tell anybody that I was there, I met Nick Trefethen once, who was walking on the Charles River, but anyway, it was a year when I, when I did completely different things. The only computer-related thing I did, we had an internet connection in our apartment so that I could communicate to Stanford to finish the typesetting of my books on typography because the five volume series of books was published by my publisher to contain the results of all of the work that had been done on typography, so the first volume is the User Manual for TeX, the second volume is the program for TeX, the third volume a User Manual for Metafont, fourth volume, program for Metafont, fifth volume, all the programs for the computer modern fonts, the, the letter forms in my books, and, and so during that year I also saw those five books through the press located conveniently right there in Boston.)

72 - Writing a book about the Bible: 3:16 (Part 1)

The other thing I started working on at that time was a completely off-the-wall project that, that became another book later on called "3:16". "3:16" is a, is a book that's different from any other book that's ever been written and there are either two reasons why this happened. One is that it was a stupid idea to write such a book, you know. Anyway, well, what's the other reason that it could be different? Anyway, that, you know, that the time was finally ripe to write such a book, I suppose. Anyway, I, "3:16" is, is a study of the Bible from a, from a different perspective than has been used before and it's a, and so, I have to explain it a little bit. The computer scientists find it very natural, when they're studying a complicated thing, to look at random parts of that thing and then probe those in-depth and try to learn something about the whole by having a few parts that they understand well. It's like the Gallup Poll where the Gallup Poll would come and interview several people, you know, and after interviewing a thousand people they'll speak for, you know, for what they think millions of people are like and Nielsen ratings and so on, are based on sampling. Well, I would use sampling when I was grading papers. If somebody gives me a term paper, I don't have time to read all 50 pages of the term paper, I'll choose a random page or so, and then I'll see what that leads me to. The student doesn't know in advance which page, which page I'm going to do. So, anyway, sampling is something that comes naturally to a computer scientist. One day in the '70s I said, well, you know, what would happen if I tried this on the Bible? I would, that's a complicated thing. What if I looked at random parts of the Bible and just to see what people- go to the library and see what people have said about those, about those parts, I, instead of somebody telling me what part of the Bible to look at, I would just take an ordinary part, you know, one, one that was, wasn't pre-planned and I would see whether or not I could learn something that way. And I found it was really interesting to do this. In fact, I did it with a group of people at our, at our local church, and we decided that we would go through and we would study chapter three, verse 16 of every Book of the Bible, so we started with Genesis 3:16, and then Exodus 3:16 and we continued through until we got to Revelation 3:16 and, and I told you that I had gone to Lutheran schools as a child, so I had been exposed to the Bible, but I never really felt that there was any part of it that I knew well. This way I would, I would have some 60 verses of the Bible that, that I would really have nailed. I could say I knew Genesis 3:16 rather thoroughly because I could go to Stanford library and I could check out all the commentaries on the Book of Genesis and there was only a few pages to read that would tell me what, what's important about Genesis 3:16. So, the sampling idea was not, was a big, was a big win, not so much for understanding the Bible so much, but for understanding the secondary literature, for understanding the commentaries about the Bible. You could, you could pretty well see how opinions changed during, during the centuries about, about these different verses and, and you could see that people, a lot of people had different insights and other people hadn't done their homework very well, and so on, but you could, you could get a pretty good idea on these thousands and thousands and thousands of books written about the Bible as to, as to what their slant was if you just happened to know a, a few of the, a few parts to probe into. Anyway, this, this was a surprisingly effective way to learn something about the Bible and, and so, it's one of these moments again, where I wake up in the middle of the night, and I say, hey, this would be, this would be a, a good book to, to, where I could take these things that I had learned in the library about the 3:16 verses and explain them to other people, that, you know, it was, it was a story that I think other people would enjoy learning about as well.)

73 - Writing a book about the Bible: 3:16 (Part 2)

So I wrote to Hermann Zapf, who by then was a good friend, and I said, Hermann, I got this idea for a crazy book called "3:16", can you do the cover for me. I want you to make the most beautiful three that's ever been designed in the history of the world, and the most beautiful colon, the most beautiful one, the most beautiful six and then I can have my book and it it will look great, saying 3:16. And, so Hermann wrote back enthusiastically saying, you know, and he'd also taken a couple of the verses of the Bible, that he'd found in his German Bible and he, he did it with his calligraphy, and he's one of the greatest calligraphers of all time, and then he said, you know, Don, I know hundreds of calligraphers around the world, I could, I could get those people to, to contribute a page to your book, and each one, each one could do these, these verses. Well, as I said, graphic designers turn out to be the nicest people in the world, and he was going to introduce me to even more of them this way. So, he, while I'm in Boston, and cleaning house and things like this, I also go to the Boston Public Library and to the Christian Science Bible Museum and over Harvard Andover Theological Library and, and study, and copy down all the different translations of these verses that I can find and, and read as, and you know, start reading the commentaries on the verses, so that I can really research the, the subject much better than I had done cursorily in the '70s. And, Hermann made, made the calligraphy for the, the verse John 3:16, which is the one that, the reason we chose 3:16, it's the most famous verse in the Bible by its number. People in the Super Bowl always hold up signs saying John 3:16 and it's sort of a capsule review of the gospel and, and I chose Hermann to be the calligrapher for that verse, and he, he provided me with a sample page, showing his, his rendition of John 3:16. So, while I'm in Boston, I get the sample page printed at a good printer, and, and then Hermann and I drafted a letter to these 60 calligraphers around the world, the best in their, in their respective countries, inviting them to contribute their pages for the other, for the other verses. So, this was a project that I had time to do while I was in Boston, and, and I spent a lot of time in the Boston public libraries and these other libraries, reading what I could, about what people, what people's comments were on these, on these verses, that I, this, I was, by the time the end of my sabbatical, the end of Jill's sabbatical occurred, which I was in the middle of the Old Testament, let me think, I was just, yes, I was just getting into Song of Solomon at that time and then we drove across country to get back to California and, and I stopped off in Yale for a couple of days to use the, the divinity school library there, and did the book of Isaiah and Jeremiah and I stopped off in Pennsylvania, you know, Pittsburgh Theological Seminary, different places coming across country, working on this. And then I got back to Stanford and I still had a, a few more years to go through the New Testament and we got great libraries out here, Stanford Library, Berkeley Graduate Theological Union Library, and so it was a weekend project for several more years after that, to see what the story of these 3:16s would, would be.)

74 - Writing a book about the Bible: 3:16 (Part 3)

I got the artwork though, from the world's calligraphers. That all arrived while we were in Boston, and it was coming in, it was, it was like Christmas every, every day, because we would get another beautiful letter from somebody with, with their contributions to the book. And so, the artwork was so great, I tried to make the quality of my accompanying texts somewhere that would approach the quality of the artwork I was receiving. I spent some time then, on weekends for the next several years, and then it occurred to me, I had better digitize this art, because the world was getting a little more digital all the time, and a company called Adobe Systems had been founded and I called up, I called up John Warnock, the cofounder of Adobe and by a serendipity, he answered the phone. I tried it many times since then, it never worked. But this day, you know, he answered the phone. I said- John, I've got this, I've got some great artwork and, and I think I'd like to capture it in digital form and we want to make a poster which puts the artwork in a different size. Is it possible to do this with any computer software? And he said- John, he said Don, I've got just the thing for you, we have a program we're working on called Photoshop, and, and we've got, you know, Streamline, you know, it turned out to be a kind of a dud, but that's what he, you know, he liked it at the time and, and he said, so, come on out and use our equipment, bring your artwork with you. So, during the summer of 1989 I went over and I was, I was the night watchman at Adobe Systems. I worked in their art department and I had about 50 Macintoshes in a room every night when most people were home. I could, I could be running my, Photoshop was really not anywhere near beta test stage yet at that point, but, and I got to work with the man, Tom, I just called him Tom, from Michigan, who, who was the main implementer and, so we got some of the bugs out of Photoshop at that period, but anyway, I could use the artwork from my "3:16" book at Adobe and after, after several, a couple of months, I had, I had it all in form that I like, ready to, ready to do the, Macintosh were very slow at the time, and dealing with a file of two or three megabytes was a heroic effort. You could start Photoshop going on a, on a filtering operation on one machine, and then five minutes later, it would be ready for the next operation, so that's why I could go to another Macintosh, it's something like a chess master playing a simultaneous tournament. You make a move on one board and then, you go to, you know, you go on to the next thing. So, but I'm getting this artwork slowly through the press this way and it takes also a long time to transmit these files to the, to the printer, but they had, they had what they called a RIP in those days, a raster image processor, and you could, you could print the films that I could use for the, for the book, and I got a, I went to Singapore to see the book through the press, and, and I was expecting that, that the, that I might have one or two readers who, who were touched by the book and liked it, and that would make my, make the whole project worthwhile and my wishes were fulfilled within a week of the publication. It was amazing. I was expecting, you know, to have a lot of negative reactions to the book, actually, because why, why is a computer scientist doing something that he has no right to be doing, writing about the Bible, you know, would I, would I read a book by a theologian about programming, you know, and the only thing I could, I could do that a theologian couldn't do, is I can, I can in my book, commend theologians for having done their work well, in many cases. You know, I can, I can give a testimonial while they can't do that because they obviously have an axe to grind, but, but as an outsider, I can at least direct people, saying, you know, here's something really cool that, and so that's one thing that I could do. But anyway, I, I found this weekend project was kind of an enriching thing and I am so glad it turned out so well as it, as well as it has.)

75 - Giving a lecture series on science and religion at MIT

On the subject of religion I wanted to, I might as well go ahead a little bit and say that, you know, not only did I, okay, so I'm publishing this book and I'm thinking that people are mostly going to say that Knuth is off his rocker because he's publishing a book about the Bible and what he does well is computer science, are we going to be able to trust him anymore and so on. But the reaction was, to my face anyway, was quite the opposite and a lot of people seemed to like the book. And the most surprising thing was at the, in 1999, or actually it was a year earlier when I got a letter from MIT inviting me to give a series of lectures about science and religion, and, well, this is something I'm obviously unqualified to do but it was hard to just turn down the letter and say forget it because, well, it was sort of something that I thought about a lot during my life and I thought maybe some of the experiences I had could be relevant to other people who are wrestling with the same things in their minds and so if I was ever going to talk about these things in my life that was one thing or would I feel incomplete if I didn't do something about it. On the other hand I certainly didn't want this to be my career where I'm, you know, not going out on a religious circuit or something. But on balance I figured, okay, let's think of it as a win-win situation, I'll go and hope that the Force is with me and I can say something of interest to people and if I was ever going to do it one off and once in my life where could I, where better than in Boston where I had spent most of the time in the library studying and looking at these theological works and where I got an audience at MIT, you know, ideal place to have an, to make an influence if there's any such place. But they had asked me to give a series of six public lectures, an hour and a half each, and that's, you know, I have some standards where I didn't know if I had that much to say obviously. So I decided okay, what I'll do is I will prepare only half of these lectures and the other half will be Q and A, will be just improvised responses to what the audience says. And so if it doesn't go well so what, I tried, I did it and it's over with. And if people think it's valuable then that's so much the better. But I could, I wouldn't mind spending a few months in Boston again, being a nice place to be and I had some things I wanted to look up also in the libraries while I was there, so I said yes and I went then in the fall for three months at the end of 1999 to relearn the Boston experience. This time I didn't live in Back Bay, I lived near Harvard Square, across the street from the Observatory, and I took my bike every morning along the Charles River to MIT and got a lot of, made a lot of friends there, you know, younger people that I hadn't known before, doing computer science. And then I gave my six public lectures and a couple of others too about a computer I designed and things like that, other projects that were going on. And I got to, you know, to also to go to New York City a few times and I visited Will Shortz and was able to make use of being in the East. But here I am giving these public lectures, the night that, let's see the day, I think my first lecture I was competing with Jesse Ventura who was also giving a lecture in Boston that same day but I still had standing room only in this hall, about 400 people, it's not that big a hall but it was amazing to me, and they came back the second week as well. And we had, the lectures were sort of in the late afternoon, about three or four times, and then a pause and then another three or four times at weekly intervals. So in these lectures I didn't present the answers to any of the deep problems, I just said well, look, I think computer science is wonderful but it's not everything in life and so there's other things that deserve attention. And some of the paradoxes that I was confronted with, how did they affect me and sort of asking the audience maybe next time it's their turn to give the lecture and, you know, so it was more of like a focus group or something, no, it was more just like saying let's for once in our life talk about things that aren't our subject of expertise but just how we balance these issues. And so I had great comments from the audience and great, it was very stimulating to do these question/answer sessions and I also learned a lot from the people that I met there because there were people from many different backgrounds. It was, again, kind of a plus thing but certainly nothing that I wanted to do for the rest of my life, I've got to focus on "The Art of Computer Programming", that's where I can do something unique.)

76 - Back to work at Stanford and taking early retirement

At the end of 1986 my sabbatical was over and I was still working on this book, "3:16", on weekends but it was back to my normal professor life. Of course I got to Stanford and I plunged in as always and resumed teaching my classes and I had great graduate students and- however I was having almost no time to work on "The Art of Computer Programming" and I don't know if any of the people watching this also go on their sabbaticals but one thing that happens when you get back home is people keep asking you- oh, aren't you glad to be back home? And they kept asking me this for the next year and the next year after that and I, you know, I would always smile and say, you know, yes but really I didn't feel quite so good to be back home because I wasn't getting anything done on "The Art of Computer Programming". And time is ticking here, I'm 50 years old, I've got lots of work to do yet on "The Art of Computer Programming". So at this time I'm 50 years old in 1988, so, like I go through a whole year and I'm making two days of progress on "The Art of Computer Programming", at that rate how long, you know, I'll have to be 150 years old before I'm done writing the book. So I decided really this wasn't a sustainable situation anymore, what I would have to do is figure out how to spend the rest of my life and finish "The Art of Computer Programming". So I came to a reluctant decision in the summer of 1988 that I should retire very early from Stanford and I should devote the rest of my time to finishing what I really do best, "The Art of Computer Programming". You know, since 1962 I've been gathering tens of thousands of papers, read them, made notes on them, organized this, all the things I think are really important to have in a book and I wasn't having any opportunity to really get that stuff ready. So I wrote a letter to our chair of our department and I said Nils I would like to retire as of January 1 1990, a year and some months from now, and I don't feel right about, I don't like the idea of a professor who's going to just write books and not do the rest of the job that you do at a university including not only teaching and advising students and serving on committees but also fundraising and many other, correspondence, answering people's queries. And I said, so I go and see why, but still I have to write "The Art of Computer Programming" or I'll never really be happy and it's going to take me many years of work, so I'm asking that you find a replacement for me at Stanford, I wouldn't want to take a salary for something, for not doing the work of- And then, so we met with the Dean and the Provost and they first tried to convince me to just carry on as I was and I said no, really, this book is a special thing that I think makes it different from all the other hundreds of professors that you've got, you know, this book is a little bit more important than all the other professors' books, I'm telling them. Well, the Dean checked around with some people and he said well, the books are pretty good anyway so he thought maybe he could get somebody to endow a chair by which I would, I have only the responsibility to write the books. I said no, rather get somebody else to do what I was doing instead and then let me take early retirement. Well, early retirement at age 52 was not possible, what was possible was that I could take a leave of absence for three years until I was 55 and then I could retire. But that's what happened, January 1, I didn't anymore have to serve on committees or raise money. On the other hand I deeply regretted not being able to teach anymore and similarly advising graduate students, that was something that has always been a special joy. In order to account for the teaching we decided that I would give semi-regular lectures called Computer Musings, which would be open to the public and anybody could come, no credit would be issued for these lectures but I would talk about whatever I thought was cool to talk about and something that wasn't covered in Stanford's curriculum, and periodically, we were going to shoot for once a month, I would do these lectures. And I could have a title and that's great, I don't know if I'm the only Stanford professor who was able to choose his own title but I became Professor of The Art of Computer Programming, and that's my official title. And that's The Art with a capital T. And that didn't mean I had a salary but it meant that I had a nice title and very nice stationery and I became Professor Emeritus of The Art of Computer Programming, officially then when I was 55 years old. This gave me medical insurance and also I have, in fact, a secretary and an office and all the library access and everything I needed to do the books right. But I'm not in anybody's inner loop where they're depending on me to do something, like I can take a day like today and never show up and nobody will be the worse.)

77 - Taking up swimming to help me cope with stress

I felt very stressed about this time and I was having all kinds of symptoms of flaky health and didn't know what was on and I think it was because of the anxiety of this big change in my life since I'm going from one phase to another. And so I even talked to a psychiatrist a couple of times at my doctor's recommendation because the doctor thought I was having too many symptoms. And the psychiatrist said well, you get so many stress points for this and so many stress points for this and you've got way too many stress points so why don't you try swimming regularly. And I had never really done much exercise up to that point, I was always sitting and writing or, you know, in Boston I could do a lot of walking because we didn't have a car there but most of the time, you know, I never understood why physical education was a required subject in college, I just, you know, I was the score-keeper but I didn't really ever play basketball myself. But it was a required subject so I had to do some of these callisthenics or whatever. Well now I could see that really the way the human body is designed it's okay to have your heart moving a little bit every once in a while and I started swimming three or four times a week in 1990 and all of a sudden my back was feeling good, I was feeling good, other problems were clearing up and, well- I was also discouraged though that Stanford hadn't found a replacement for me and they still haven't. I mean they did some searches but the professors they identified decided to stay where they were and so really that part of the bargain Stanford never lived up to.)

78 - My graduate students and my 64th birthday

At this time in 1990 my final two or three students finished their PhD and so that gave a me a grand total of 28 students, mathematicians say that 28 is a perfect number. It's just a bit of a joke but if you consider all the divisors of 28 it's 14, 7, 4, 2, 1, and that adds up to 28 so it's called a perfect number. And remarkable 28 students, 28 different personalities from many different parts of the world, about half of them went into academic careers and half of them are in industry. For example, the people who worked with me on TeX, Michael Plass became one of the key programmers for Xerox in their DocuTech systems and many other of their desktop publishing system. Frank Liang went on to be one of the key people in Microsoft Word and many of the students that I had in the typography program, again, were very, have leadership roles in the software industry for printing. Bob Sedgewick was chair of Princeton Computer Science Department, Jeff Vitter chair of the Purdue Computer Science Department, now Dean there, so I have a lot of academic students. Others are back in their native countries, in Spain, Brazil and, so all in all I'm really grateful that I had so many great students who pretty much taught me as much as I taught them. While I could take credit for their successes, it's really their, they were great and are great. Only one of my students was a sad case and he seems to have committed suicide after an unhappy life but 1 out of 28 I think is a pretty good score card. And I still see at least half of them because they're in this area now. It reminds me, I might as well mention a huge surprise on my 64th birthday when people came from all over the world for a two-day celebration and Jill had kept it totally secret from me and I just couldn't believe, every time I'd look another way I'd see yet another amazing person who came. Why 64 years birthday? Well, to a computer scientist the number 64, the powers of 2 are the most important numbers, so after 32 then the next interesting number is 64 and after that 128 is the next interesting number. So I doubt if I'll have another more appropriate birthday time and so we call it my millionth birthday since in the binary number system you write 64 as one followed by six zeroes. That's when I got to see lots and lots of my students, so the thought came up now.)

79 - My class on Concrete Mathematics

Now I'm retired but then I still can't go full time to work on "Art of Computer Programming" because there's other projects that I really have to finish, for example, I told you about the "3:16" book which I was doing on weekends, I wanted to get that done. And so I was doing that, at this time it was just at the end of the '80s, it was published I think beginning of 1990. And then I had introduced a class at Stanford called Concrete Mathematics, I started it out in 1970 I think, maybe 1971, probably, well, it might have been in the fall '70 or spring of '71. Anyway a brand new course in the curriculum because there was no- Students at Stanford couldn't learn the kind of mathematics that I found necessary for computer science work. And I'd been thinking a lot about what it was that I had needed as writing the first parts of "Art of Computer Programming" that I hadn't been taught myself in school. And there was also a big to-do at that time about, some people were complaining mathematics was getting too abstract, that it was too detached from reality so I could make a little joke about that by calling it Concrete Mathematics, although I said that the word concrete doesn't really mean the opposite of abstract, it's a combination of the word continuous and discrete. We had this course Concrete Mathematics, the students were enthusiastic and I gave it over and over again. Sometimes we had guest lectures when I'm on sabbatical or when I'm away somebody else would come and teach it on the model that was established. And one of the ways I always did teaching at Stanford, I was inspired by George Pólya where I let the students do the talking in class instead of me telling them what's in the book. I assumed they all know how to read and so when they're in class we're going to do things that aren't in the book. So I would always run my classes by, almost as if it were a language class instead of a computer or math class where I would present a question to the students and the students were supposed to figure out how to solve the problem or at least to make the next step towards solving a problem, or to try and fail and then we would learn how to recover from failure. You know, you don't find books saying how to recover from bad guesses and so we could learn that in class. In order to, so that the students didn't have to take notes in these classes I always had my teaching assistants take notes of what the students said and then they would quickly publish these notes afterwards and as a sort of a transcript of the session.)

80 - Writing a book on my Concrete Mathematics class

So by the time 1990 rolled around I had almost 20 years of these transcripts of class discussions that had taken place in this Concrete Mathematics course and it was natural and almost sort of mandatory that this legacy be passed on to other generations, so I wanted to write the book, "Concrete Mathematics", describing how the course had evolved and what had been learned. One of the most conscientious teaching assistants was Oren Patashnik who had not only transcribed the class sessions but then he had drafted, I think, almost all the chapters of the book as handouts to the students so that they could use it in one of the years that I wasn't teaching. So I could go from his notes and rewrite them but using his insights into pedagogy as I did this book. And Ron Graham who was the most successful teacher of the course when I was gone, he'd come in two or three times and the classes, the people loved him so much when they took it that the Concrete Maths class for those years would have annual reunions afterwards. And he also then started teaching it at Princeton as well. So I had then this Concrete Maths book with two co-authors, Oren Patashnik and Ron Graham. Usually when I write a book I finish about one page a day, I mean if the book is 365 pages long it takes me a year, if it's 500 pages long it takes me a year and a half. In this case I overdid it and I got the 600 page book done in little less than a year and it was not a sustainable working style but I really wanted so much to get back to "The Art of Computer Programming" that Jill gave me a year where I didn't have to be quite as, what you'd call responsible a husband as, you know, I would be allowed to be, you know, less of a human being for a year so that I could get this project done and then I could make up for it some other time. So anyway that was a crash project, which was done under some strain but I had the stimulation of the beautiful mathematical material that I was writing up and of Oren Patashnik's draft which was in a refreshing style that we could make this book a sort of California book. One of the most fun things about the Concrete Math book is a feature that I had copied from Stanford's, well, early '70s Stanford University had a really innovative thing for prospective students. They put out a book called "Approaching Stanford" that was written by former students and in the main part of the pages of "Approaching Stanford" it would have this, what you would expect to find from a university, telling how great the place is and the weather and all this- faculty being great and the students and everything. And then in the margins there's this graffiti where the students are saying what it really is, you know, like Stanford dorms are like a zoo without a keeper or something like this, but they had the true clues about what it's like written by students. And Stanford put this out and sent this out with its literature to prospective students. And so I thought, okay, let's do this with the math book too, let's have graffiti in the math book, let's let the students comment on what they think about the subject and, you know, it turned out that this idea certainly has caught on because the book "Concrete Math", let me say first of all, if anybody finds an error in any of my books I pay them for it, you know, if they're the first to find the error I send them a check. And any errors in this graffiti were caught immediately, it was clear that all the readers were reading the graffiti, the errors in the rest of the book, you know, maybe it would take three or four years before somebody finds it but if there's anything at all that they could comment on in the graffiti section that was done. And also the book has been translated into about ten other languages and in almost all the cases the translators also translated the graffiti, they thought this was a vital part of the book. So the book doesn't take itself too seriously but it's still, it turned out to be a way to contribute also to the content of the book because one of the comments could be, could say, you know, you'd better skim this next few pages because you don't want to bother so much with it until you've been through it once before. And then there were other, some of them were pretty corny jokes but we censored them a little bit and so it was, anyway, on balance that was- So we have a California book about mathematics, a book that shows the informal style of Stanford classes as well as what I think is a personal manifesto of the way to do mathematics, the way I think that I love to do, work with the kind of maths that I needed to study computer programs at any rate.)

81 - The Stanford GraphBase and updating Volumes One to Three of The Art of Computer Programming

I finished the "3:16" book, I finished "Concrete Mathematics", I still can't get going back on "The Art of Computer Programming" because there's one more thing I have to do and it's called the Stanford GraphBase. And this is a collection of literate programs that are to be used for standard examples that would be used in Volume Four of "The Art of Computer Programming". So that took another couple of years to get that done right, it was necessary to have this out first before the book was there so that the, I'd be able to finish other projects with other people around the world contributing since they could use the Stanford GraphBase to help. Finally then, about 1995 I'm able to open the door of the room where I had been throwing all the new material for "The Art of Computer Programming" for 15 years. While I'm working on TeX I really had no time, much to think about it so when I get something in the mail relevant to Volume Four, Volume Five or so, I would just throw it into a pile and then I had boxes and boxes, so finally it had accumulated to about 17 linear feet of material. And besides I had all of the material I had collected in previous years, so I decided I just had to reorganise it all and that took another year, more than a year to go through everything, every scrap of paper that had come in and put it in a good place, make a computer index so that I could find everything, make, put it into thousands of little file folders and also correct all the errors known in Volumes One, Two and Three. People had been writing to me, I had letters from 1981, 1982 that I hadn't answered yet, reporting on errors in Volumes One, Two and Three, so I wrote checks to all these people with interest from the day of the, you know, I had a little computer program that computed these interest rates and I had a mistake in it so I think I paid a bit too much interest there. But anyway I sent out hundreds of checks and had a bigger, errata list for "The Art of Computer Programming" for Volumes One, Two, and Three and this I could typeset with TeX and have it typeset correctly. All these years people were still buying the books at a steady rate in the book stores, they're buying like Volume One, Volume Three, they're buying the edition that was done in the '70s but, you know, like the 30th printing, the 40th printing. And it's still, each of the books are still selling at a rate of about 4 000 books a year, something like that. And Volume Two was the edition of 1981, the one that I couldn't stand the numerals in but the mathematical material was okay. When my "Computers and Typesetting" series of books, those five volumes came out, that was all done with the new fonts, with the correct typography and so on. With my "Concrete Mathematics" book I was able to use a new font designed by Herman Zapf and for the "3:16" book I had another font that I'd worked on so I had- So it was only "The Art of Computer Programming" that had ugly typography by this time and still I didn't want to, you know, it's been taking me so long to get back to writing Volume Four, how could I stop and redo Volumes One, Two and Three without waiting still longer. So, to the rescue came Silvio Levy who lives in Berkeley, who was very active in many projects of Mathematics and he's now the librarian at the Math Sciences Research Institute. But he was a big fan of TeX and he and I created the CWEB system of literate programming using C as a programming language instead of Pascal. So Sylvio, some- the errata list, finds One, Two and Three and he decided, pro bono, that he would typeset Volumes One, Two and Three in TeX and he would ask the publishers to pay him a nominal amount for this to which they, of course, readily agreed. And he and his wife, Sheila, did the proofreading and they did a marvellous job going through all three volumes and incorporating all the errata in my errata list. And then it didn't take me long to, I mean it took me three or four months, but not really anything near what it would have taken for me to do all the work myself, so that we could have, finally, as 1997/1998, we could finally have "The Art of Computer Programming" brought up to date with decent typesetting and with all the 20 years of improvements that had been in my files, now incorporated into the text.)

82 - Getting started on Volume Four of The Art of Computer Programming

I'm ready then to start finally the work on Volume Four but it still isn't out, right, so what's happening? Well, in fact, about 400 pages of it are out now in paperback and it takes me more than a day a page, I'm not able to convince myself to settle for just reproducing things that I find in my files but every time I look at something I see that there's a chance to improve it, and that takes me another few days. So I'm adding a lot of material that doesn't appear in the literature as I'm writing Volume Four. I can't sustain that either I know but I tell myself that the parts of the book I'm writing now are so fundamental that they're different from the parts that will follow and that next year I will just be putting together things that are not very highly original. But, in fact, like tonight I'll be finishing the index for a new section and this is about 60 pages and out of the 60 pages I think they're, you know, well, 15 pages of it is stuff that hasn't appeared in the literature and quite a few different ideas are there, and the same in these 400 pages of Volume Four that have come out, I can't resist going beyond the sources that I see when it's such a fundamental part of the subject. So I'm not the, at the rate I'm going it's pretty clear that I won't I finish the whole project until I'm 90 years old. So, even though I'm not putting on, you know, I'm not going beyond the table of contents that I jotted down on that day in January 1962 when I was asked to write a book on complilers, I still have sort of that table of contents, the field has grown dramatically and there's so much good stuff I can't resist putting in. The, let me see- So that's my life right now, pretty much going through my files for Volume Four. All the things I'm reading, I keep on reading more things in the library but then that suggests ideas that I put together and I contact people around the world for their help in trying to debug the ideas and to check that I got things straight. And hopefully I'll be able to continue this for a long time. It's fun because I get to put together the work of authors that didn't know about each other's work, so then I get a chance to make a natural connection between those things and I love to find a way to present material. I know that I'm getting to be an old man now and my style isn't as sprightly as it used to be when I'm young but I still have the 3000 pages of manuscript I wrote in the 60s that I can use those sentences to make, to keep a little bit of youth in there. Still I know that the material is not an easy read, people will maybe keep it in the bathroom or something like that or they'll have the book on their shelf just to prove that, just to imply to somebody that they could understand it. The subject is not, there's no Royal Road to some of this material, some of it is inherently difficult but pretty much I'm enthusiastic about the way things are going. When I, like this morning I was making the index and I see parts that I had to struggle with when I wrote but now when they come out it looks like a good story that I didn't- and the struggle, the fact that I was struggling with it doesn't seem too obvious to me now.)

83 - Two final major research projects

Now I'm still able to do small research problems that I can solve in a day or so but I knew that I'd never be able to work on a major difficult problem, you know, as I'm working on "The Art of Computer Programming", it's hard for me to give that up. So I found myself working on two big projects, one of them at the end of the 80s and one at the beginning of the 90s, which were sort of monographs. And the first one, a project called "Axioms and Hulls" where I was studying interesting problems in geometry, in convex geometry, and I got to work on that while I was in Singapore getting the book, "3:16", printed, this turned out to be a little book of 100 and some pages. And then I started looking at the problem of random graphs, a very fascinating phenomenon where sort of a big bang occurs when you start out with points that are totally disconnected and then you choose two points at random and add a connection between them, and you keep doing this. And as soon as you pass the number of connections, about half the number of points, suddenly almost everything almost always becomes connected, a large part of it becomes connected that's called the Giant Component. And I had been studying this problem with Boris Pittel, a visitor to my research project at the end of the '80s and we got some preliminary results that seemed kind of exciting mathematically, and so I was writing up the paper and I realized that there were even more results around the corner, in fact, the more I looked at the problem yet another beautiful pattern seemed to emerge. So, as it turned out, it was it finally developed into not only was I studying the Giant Component but we wrote a research paper which was a giant paper, it filled the entire issue of a journal. And I had three co-authors, Boris Pittel, who I already mentioned and Svante Janson, Tomasz ?uczac from Poland. We all kept finding more things about this subject and challenging each other to do yet another amazing step in the exploration of this phenomenon that was coming through. So, in a way it was like having written two more PhD theses at the end of my research career, these two monographs, the one on Axioms and Hulls and the other one about the Giant Component. And this was then my swan song, you know, after which I said, okay, now I've been there and done that and all the fun problems now I'll leave to other people if I can't solve them in a day. Or I try to give myself an hour but after an hour sometimes I think well, maybe another hour I'll be able to do it. So from now on if I think of a new problem and I can't see how to solve it I will pass it on to somebody else and say, don't you think this is a cool thing and let them have the fun of solving it.)

84 - My love of writing and a lucky life

As you can see from my comments that I'm addicted to writing, I love the idea of communicating ideas to other people. I think, in every case, the books that I've written were things where I had learned about some phenomenon that I thought was just too good to keep to myself and so I wanted other people to share in the joy of reading it. So it turns out then that I have more than 20 books in print now and that's, you know, so many that I doubt that there's anybody in the world who's read more than half of them. And I sometimes think what tragedy it would be if there were ten people in the world like me because we wouldn't have time to read each other's books, you know, it doesn't scale up. Still, you know, there's a story behind every book, there's a story behind every paper that I wrote and it was not a, you know, I don't understand this idea of publish or perish because I never wrote any of these papers because I felt that I needed it for my career or something like this. It was always because I thought there was a cool idea that was just waiting to be communicated. A guy asked me two or three weeks ago, it was a project that he's doing for his grade school teacher, he was supposed to take videos of some people that he knew just a little bit and ask them the following question; if you could do one thing over in your life and do it differently, what would it be? And, you know, I'd never been asked that question before and after five minutes I gave up. I mean I'm probably getting forgetful at my age but I just couldn't think of a single thing in my life that I regretted, it was, I mean I just feel too absolutely too lucky. I came along riding the crests of different waves, I mean I was born at just the right time when computers were beginning to arrive in the world and I just happened to have this background, this combination of skills that made my peculiar way of thinking in harmony with what you need in order to make a machine do tricks. So if I had been born ten years earlier, ten years later the whole thing would be so much different. I was early enough in the computer field that the problems were easier then and I could solve them. We creamed off of the easy ones, now those people who are younger have only harder ones left to go or have to look at problems in completely new areas which of course are very exciting, with things like robotics and other types of applications that are now opened up because the fundamental, easier problems have provided now another level of interesting problems that are attackable. But I just can't imagine being luckier or having had a, even though many of the things I did throughout my life weren't popular and not everything turned to gold, I just can't think of anything I would rather have done differently, and so it was very hard for me to answer this boy's question.)

85 - Coping with cancer

Last year I learned that I had cancer and hopefully now we found it at a very early stage so that it won't be, it won't prevent me from getting too much more of "The Art of Computer Programming" written but I didn't know at the end of last year how bad the cancer was. And so I just want to mention a little bit about this story because it's something that happens to- everybody's going to die but you never know what is going to finally do for you and everyone's going to have to face this kind of thing once in a while so I just want to mention a little bit about how it affected me last year. I'm now at the age where I attend a lot of funerals of people who I've known and my colleague, Bob Floyd, died a couple of years ago and I have, every once in a while, wondered about how to face death. It's certainly inevitable but I always found that I was ready to die if I had finished a book but not a week before finishing a book. You know, that would be too, too terrible if I couldn't finish the project. Then when it was done then, okay, it's all right again for a little while. After my father died in the '70s I was confronted with this issue and had to sort of resolve it in my mind as to how I should take it and I remember it took about a month before I could go an hour at a time without thinking about death and the questions, but I thought it through then and got a little more comfortable with it. Now in recent times I've known of a lot of cases where someone died and we said, oh, but it was a happy ending because just a week before they were able to meet with their children or their friends and sort of get their affairs in order, you know, they had time for kind of a nice summing up and everything was as good as one could hope for. So, well, the reason I'm saying this is because last year after I had the diagnosis of this prostate cancer we scheduled surgery for December, but I had meanwhile been invited to give important speeches in Europe, especially at the 150th anniversary of the founding of the ETH in Zurich, the main Swiss Federal Institute of Technology, I think it's like the MIT of Europe. And so I was a featured speaker there and interviewed by all the media and so on and I didn't, of course I didn't tell my hosts anything about this surgery that was going to be taking place, but it was just like, you know, my talk went well, the people were all enthusiastic about the things I'd been doing, I didn't have an enemy in the world, I was sort of at a summit. So if I was going to die in December in this surgery it would be one of these happy endings that I had known about in the other, even more than that because here I was, I mean there were profiles coming out about my work and following my talk, at Zurich I got an honorary doctorate, it was like my 31st honorary doctors degree, more than Ronald Reagan has received, not as many as Bob Hope but still it was, you know, amazing for computer science. So I'd achieved all the, everything except finishing "The Art of Computer Programming" that I could have hoped to achieve in life. And then after Switzerland I flew back and had a week with my children and grandchildren where we all were, had a great time, and so if I was going to die this again would be just the perfect way for it to end. And so the way I looked at it was really that I've had every possible advantage and gift, so if I was going to die in the surgery that would be okay, that would be just, you know, a sort of a- I wasn't expecting that I should be upset if it didn't go well, but if it did go well, then I would just say okay, this means that I have a chance to do some more as a gift but not as a right, not as something that I'm entitled to if you can understand what I'm saying. And so, and it's not just something that I was saying but, you know, I really, when I went into the hospital I didn't have any plans as to what I would do when I would get home again afterward, I just thought okay, if I get home I'll think about it then. And so I'm in this surgery for four or five hours and unconscious and then all of sudden I hear happy noises and people saying, oh, you did fine. Okay so, well great, I'm still alive, maybe I can go a little further. It's no fun being recovering from surgery but still everything went as well as could be expected and here I am today and I'll be starting a little bit of radiation therapy next month as a precaution but the prognosis looks pretty good. So every day from now on where my health is good I consider as something that, as a special gift, gives me a chance to do some more of what I do best, is trying to take the things that people in computer science have discovered and put them together into a story that can be understood by some of those who can't understand the original papers.)

86 - Honorary doctorates

I used to say that I accepted these doctor's degrees in order to make my mother happy. And I think it did but after she died I still accepted them so I knew that it meant something to me as well. But I do think I don't have time to travel very much now but I have travelled for the purpose of these- I guess I should write a book about commencement addresses because I've sat through so many college degree ceremonies, but it's important to the field of computer science because we're a new kid on the block, computer science hasn't existed for more than 40 years while other subjects have been going on for a long, long time. And so when a university decides to award a doctorate in the field of computer science this is good news for the field, that places are giving more credence to the idea that we have a field that stands on its own with respect to fundamental problems that it is working on. So for me this, since I was one of the earliest, you know, from the generation where somebody can give me an award where I can sort of represent the field of computer science, so I consider these degrees are more primarily for the field rather than for me personally. My friend Bob Floyd always said that it was getting the first award was the hardest, after that, people are always hesitant to give an award to somebody who's never received an award before but after the first one then it's all coasting. And he said he was going to, he never got a PhD himself but he was going to get it by the green stamp method, if he had enough letters addressed to him as Doctor Floyd then he could submit that to some place and they would give him an honorary doctorate.)

87 - The importance of awards and the Kyoto Prize

I think awards are important in a person's life to validate that other people appreciate the work that goes into, you know, the things that I do are fun but there's also parts of them that aren't fun and it's pleasing to know that it's appreciated, so getting an award is certainly a fine tradition. The first one of importance to me was to get the Medal of Science from President Carter and this was totally unexpected but it was my great privilege to be sitting next to Richard Feynman when he got the Medal of Science from President Carter. And when he, when, just before I went up to get it he went like this with his elbow and said, okay Don, here's your big moment. Well, he's one of my huge heroes, I knew him at Caltech and so this was a big day for me for sure. Then some other prizes where I could represent computer science, there was a prize called the Harvey Prize in Israel, again, these are prizes that are open not only to computer scientists but also to chemists, physicists, biologists, people of all scientific disciplines. Some other prizes also were open to people from humanities, I'm glad to say one of my doctorates is a doctor of letters, I mean after I worked on Metafont I ought to have a doctor of letters I figure. So this has been something that, I guess deep down, gives me some satisfaction and encouragement to keep going. The biggest prize of all of course was the Kyoto Prize which was about ten years ago and that's a prize that is probably the best a computer scientist can hope for, it recognises a lifetime achievement in the field and it is offered to somebody in technology every three or four years. I, at that time, I was able to bring my family and my wife's family and my sister could come and my mother and father-in-law and sister-in-law with my kids and spent several weeks in Japan so it was also a good thing for the whole family. During that time, I was in Japan for three weeks, I gave 13 lectures on 13 different subjects, eight of which were prepared and five of which were improvised. I got to meet the Emperor and Empress of Japan, you know, and wow, she is an extremely impressive person. I got to meet my hero, Nob the greatest puzzle expert and we could go to a hot baths together with him and his family and so we could experience many, many parts of Japan and this was another important highlight of my life.

And there's a nice, if I'm not mistaken, a nice tie-in to the beginning of your career as it were in grade school in Milwaukee. You donated some of the prize to your grade school.

That's right, the Kyoto Prize also comes with money, it's not as rich quite as the Nobel Prize but it's enough to convince the world that they thought twice before they gave the prize. And so it amounted to about $400,000, and Jill and I didn't want this to ruin our life because we were happy without the money so we didn't know what we, if having this would be best. So we used 100,000 to pay for the trips of our family and 100,000 went to my school where I had started the first grade through eighth grade and 100,000 to Stanford and 100,000 to pay for a new pipe organ at the church where I go here in Palo Alto.)

88 - The pipe organ (Part 1)

My father was a church organist and he was, in fact the day I was born he was called to the hospital from the church service. And part of the training of a Lutheran schoolteacher is also with music and he's quite good at music. He played in the Chicago Worlds Fair, he gave a recital in 1934, whatever the year was, he gave several recitals I have programs of and I inherited some of his organ music. When I was young I studied piano but my piano teacher also knew something about the organ so when I was 12 years old I had a year of organ lessons instead of piano lessons, and so I learned a little bit about the instrument at that time. And I met E. Power Biggs, he came to Milwaukee to give a concert that year. He sat in, I rode in the car with him to the recital actually, I didn't know how famous a man he was, but he was the man who brought organ music to recording in America. So that was it though, I went back to piano, in high school I was playing the piano with the, accompanying the band. In fraternity at all the parties I was playing piano and we would sing a lot of songs, mostly Broadway shows, tunes. And I enjoyed playing the piano, you know, it took me, for example when we went to Norway for my first time away, instead of renting a TV set we rented a piano and Jill and I played four hands music with each other every night. So I've always liked piano but in the 1960s when I'm at Caltech, somebody, we were singing in the choir and somebody called me on Saturday and said Don, our organist and choir director has just come down with a detached retina and he's in the hospital, is it true that you took organ lessons once when you were a teenager and can you fill in at tomorrow's service? So I went to the church and I tried to remember how to play and on Sunday I played the service and then, at that time, in order to recover from a detached retina, you had to sit still for some months with your head in, sort of rigid while the thing was healing, it was the way they did it. So for the next six months I was the organist of a church there. In Pasadena there was a great tradition of fine organ playing, a man named Clarence Mader and many of his students were in the churches around there so they had some of the best in the country actually at the time. And so I started attending recitals of organists, they also invited the best organists from the east to this chapter of the American Guild of Organists and I began to realize that there's a lot of really great literature for the organ. So I met a few people who had organs in their home and I thought that was a cool thing. So when I had my year in Princeton a large number of the best organists in the country were headquartered in Princeton and I had heard some of them in Pasadena while I was there so I took classes at Westminster Choir College where these people were associated in Princeton. I audited the classes, I found it was kind of strange as a full professor going back to taking lessons again where somebody would tell me what to do, this was quite a come down for somebody who'd been used to being king of the- but anyway I had an excellent teacher in Princeton and she gave me lots of good music that I could begin to learn. So the idea was planted in me that pipe organ music is one of the great pleasures of life.)

89 - The pipe organ (Part 2)

Since then I decided, okay, I got royalties from my books so I can use this to acquire an organ in my home and so when we built this house we told the architect of this dream that I would like to have a music room in the house where we could have a pipe organ. And so even though we didn't have the money to pay for it at that the time we put it into the plans so that it would support three tons of weight in the front room. And I went round talking to organ builders, the finest organ builders that I knew at the time were in Denmark and a friend of mine, Peter Naur at the University of Copenhagen, I visited him during the year we were in Norway and spent a week talking to different organ builders in Denmark. And boy, the gorgeous instruments that they built, very few in America. If you're interested in anecdotes this is the only time in my life I drank a cup of coffee and maybe that was the wrong country in which to drink a cup of coffee, but that was the only time, but after that I didn't want to try again. But the story is this, I was at this organ builder and he didn't speak English very well and I didn't speak German very well, we tried to communicate in German and he served me coffee and I didn't know how to refuse so I took the coffee. And every time he, but it tasted awful to me so every time he would be looking at me though I either took a sip a little bit or I'd at least rattle it in my cup so that he would know that I was paying attention to the coffee. But then I did pour it into a plant at the end when he wasn't looking, but that was my experience anyway. But he's a great organ builder in Hillerød near Copenhagen. Well, I didn't wind up though with a Danish organ because although I got a proposal from the man that I liked the best it turned out that the way the labor laws are set that you can't set a fixed price for anything, it depends if inflation occurs then you have to pay more. And it was going to be two years in advance so I would have to, you know, saying well, no matter what happens to the economy I'm obliged to pay the current salary in Danish currency. And there was a big problem about shipping, so it turns out that the Danish solution wasn't the best. I did though meet up with Larry Abbott and Pete Sieker, who have a shop near UCLA, on one of my trips to southern California, and they built four organs a year very fine and I had known, in fact they had built one of the ones that I had seen in Pasadena when I was previously. And so I worked with them and came back to Stanford and meanwhile here I had worked with our own church and our church in Menlo Park had gotten a new organ and so I was on that committee and visited a lot of American organ builders at the time and learned something about the process of specifying an organ. I got lots of books from the library and saw what the specifications were of the organs that Bach had played on and many organs from the Netherlands and different parts of the world. That was a good background and at Stanford we have four organs and I could play on each one and listen carefully to the different notes, get a feel for how they balanced and then communicate as well as I could to Abbott and Sieker down in Los Angeles. So finally they finished the design and their shop isn't tall enough to hold the organ, it was in three pieces, they brought it in the truck up here and installed it. It's only lived here in my home but it's quite a nice, quite a fine organ for in a person's home. Usually a home organ has to be so small that you can't get very many different kinds of tone quality on it but they were able to make it so that I have dozens and dozens of different combinations that work well.)

90 - The pipe organ (Part 3)

Many Stanford students have given recitals here including Walter Hewlett who's now one of the big people in the Hewlett Foundation and director of Hewlett Packard, he was the son of the original Hewlett. So it's been nice to have this also as now considered one of the Stanford organs. I'm no great shakes as an organist but as a computer scientist I'm okay, so this gives me an intro where I can go many places in the world and people will show me their pipe organ and allow me to play. And I don't have to be that good because I'm just a computer scientist, I'm not supposed to be a musician. So I've played on the most, in fact in Zurich last November I had an hour to play the fantastic organ at the Fraumunster, the best organ in Zurich. I could play the organ at Wanamaker's Department Store in Philadelphia, the largest in the world and organs in Netherlands, the famous one at Haarlem. And, well, in Kyoto there was a very fine organ with four ranks of pipes that were based on Japanese instruments, quite intriguing. I guess the, I hardly ever play in public, the only time really was in Waterloo, Canada, where the professor of organ there and I put on a program of organ duets and so some pretty interesting music was written for two players, usually at one organ but in one case at two organs. And that was, I mean I practiced pretty hard before that occasion so that was kind of the high point of my organ playing of my life.

How frequently do you play these days at home?

I play in spurts, so sometimes I'll go for more than a month without touching it and then I'll sit down and I'll play for three hours or something like that. You know, it's a, I should really, you know, I shouldn't penalize myself, I usually think oh, Don, you're behind on this project, you can't afford to take time off and play. So I shouldn't argue that to myself, I should allow myself to do it a bit more. But I enjoy music very much and the pieces that, there are some pieces written for organ that are so good that you never get tired of them no matter how often you play them.)

91 - An international symposium on algorithms in the Soviet Union

I said that Analysis of Algorithms was what I wanted to call my life's work, this is so, the field that I considered that, most of what I'd done, including in writing "The Art of Computer Programming", is to find a quantitative way to say how good a computer method is, algorithms. So since I knew that algorithms was my great, you know, of all the things that I enjoy and do, that this was somehow, had to be number one, I was delighted to learn that the word algorithm comes from Arabic, Al-Khwarizmi where Khwarizm is a region of Uzbekistan, now, but at the time there was, it's the, there's a lake, I mean the Aral Sea used to be called Lake Khwarizm. And it's a part of the world that's pretty much forgotten, it's usually to the east, north, south or west of whatever map you're looking at. If you look at a map of Iran it's north of there, if you look at a map of Romania or something it's east of there, if you look at India or Afghanistan it's west, you know, south of Russia, it just doesn't appear, it's sort of a forgotten part of the world. But I found out that that's where the word algorithm comes from, Khwarizm. It means the person from the Khwarizm area, actually there was a district of Baghdad which was the Khwarizm district where maybe, you know, like the Armenians lived in one place and they would call it the Armenian place, but this was the Khwarizm quarter of Baghdad. So I thought, okay, it would be interesting to go to Khwarizm sometime in my life and I looked up in the atlas and, oh no, it's in the middle of the Soviet Union, how am I ever going to get there, there's no roads going into it either showing from any, you know. So I mentioned this to my friend Andrei Ershov who was visiting from Russia, from the Soviet Academy of Sciences. Well, he wasn't my friend at the time, I didn't know him very well, but he was a friend of John McCarthy and we were at a party at John McCarthy's house. And I said to him, you know, algorithms, the word comes from this part of the world and it's in the Soviet Union, we should celebrate this some time, wouldn't it be nice to have some kind of a pilgrimage where computer scientists of the world can got to Khwarizm and celebrate the birth of this subject. And he said, hey, that sounds like a great idea. So he goes back home and he does all the work arranging it and getting the Russian Academy of Science to sponsor an international symposium on algorithms to last two weeks and to take place in the Khwarizm oblast, the district of Uzbekistan that everybody has forgotten. So not only did I get to go to Khwarizm but when I get off the plane I'm greeted by 200 children carrying flowers, and, you know, and interviewed on local television. And it was the first time anybody in the world had shown interest in their part of the world, so we had, you know, the tremendous hospitality of the people in the Mid East is amazing. In fact, you know, the hosts were so generous I said jokingly well, how about providing me with a- not concubine but anyway, you know, I'm sure he would have believed me and done it unless I had really assured him that I was joking. And we could visit, right near where we were is a kind of museum city of Khiva, which is really where the author, al-Khwarizmi was from, well, I'm not sure but anyway it's a kind of a preserved city which shows all the great things of that culture. And at this conference half of the people were Soviet Union and half of them were from the rest of the world and we could just meditate on the significance of algorithms, so it was another highlight of my life I guess, to be able to accomplish that little visit and see that corner of the world. Amazingly we met children in this village, many different nationalities, blonde, blue-eyed kids, some of them with Korean ancestry and we visited the cotton farms and picked cotton. We saw lots of, you know, I got myself a cap like the people wear in Khwarizm so that when I'm working on algorithms I can be properly dressed.)

92 - The Knuth-Morris-Pratt algorithm

There was a story really behind every paper that I wrote pretty much and this one is a kind of interesting story. The algorithm itself has became famous but not, I'm not sure, well, I haven't had to use it myself for the last 20 years but it's in all the textbooks and it makes a nice instructive example of if you're trying to search through a long piece of text and you're looking for a certain word- suppose I'm looking for the word, well, the, or something like that, it would be foolish to look for that word, let's look for Dikran or something. Okay, so I can go until I, so the obvious way is you start at every place in the text and you say is it a D? oh yes; then you look at the next letter, is it an I? is it a K? no, this is the word direction or something. All right well then go to the next place and start over again, is that a D? Well all we observed was that you already know that it's an I, it's not a D so you might as well skip ahead a little further before you make your next test. Well, there's more to the story than that though, you can have more complicated words, like you were looking up the word Didymus or something where there's a couple of Ds and so you'll have- But the interesting thing in this case was that a professor at Berkeley, Steve Cook had proved a very amazing theorem. He said that if you could, if you took a certain kind of computer that's very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer. In other words if you take a particular limited computer and if it can solve a problem at all then there's a fast way to do it on a real computer. So one of the problems that we could solve with this funny computer was to decide whether a string of letters was a palindrome, whether or not it read the same backward and forward, no, sorry, was a concatenation of palindromes, so a palindrome followed by another palindrome and so on. It was just a curiosity, I mean nobody really cares about concatenations of palindromes but there it was, and so according to Cook's theorem, since there was a way for this funny machine to recognise these palindromes, then there must be a fast way to recognise these concatenations of palindromes on a regular computer. But I couldn't think of any good way to do it on a regular computer, it just seemed to me that that was going to be a much harder problem. So, I thought I was a pretty good programmer but here is this theorem saying that there's a way to do it and I can't think of the way to do it. That was the first time that I was sort of stumped this way by somebody saying that he had a good way and I couldn't think of it. And so I took an afternoon, or maybe an afternoon/evening and I worked out in great detail on a blackboard the way Cook's construction would have finally given me a way on my regular computer to do it fast. And all of a sudden, ah ha, of course, that's the trick. And so I was smoking out the idea as to how this general theorem would apply to a real programming problem and it occurred that this would also solve the problem of searching in the text. So I mentioned this on a trip to Berkeley where I met Vaughan Pratt and he was the one that made most of the crucial insights, I was just the one that wrote it up afterwards and then we found out that Jim Morris had discovered the same idea a few months earlier and used it in software and that other people had looked at this program and didn't understand it so they took it out. But, anyway, it's a nice method for efficient searching text but also good, instructive, to teach principles of computer science so it's become famous and associated with my name. But I've got 160 papers and each one of them has a, some kind of a little twist to it that made it interesting to work on.)

93 - My advice to young people

If somebody said what advice would I give to a young person, they always ask that funny kind of a question. And I think one of the things that I would, that would sort of come first to me is this idea of, don't just believe that because something is trendy, that it's good. I'd probably go the other extreme where if something, if I find too many people adopting a certain idea I'd probably think it's wrong or if, you know, if my work had become too popular I'd probably think I'd have to change. That's of course ridiculous but I see the other side of it too often where people will do something against their own gut instincts because they think the community wants them to do it that way, so people will work on a certain subject even though they aren't terribly interested in it because they think that they'll get more prestige by working on it. I think you get more prestige by doing good science than by doing popular science because if you go with what you really think is important then it's a higher chance that it really is important in the long run and it's the long run which has the most benefit to the world. So usually when I'm writing a book or publishing a book it's different from books that have been done before because I feel there's a need for such a book, not because there was somebody saying please write such a book, you know, or that other people have already done that kind of thing. So follow your own instincts it seems to me is better than follow the herd. My friend Peter Wegner told me in the '60s that I should, for "The Art of Computer Programming" I shouldn't write the whole series first, I should first write a reader's digest of it and then expand on the parts afterwards. That would probably work for him better than me, much better, but I work in a completely different way. I have to see something to the point where I've surrounded it and totally understood it before I can write about it with any confidence and so that's the way I work, I don't want to write about a high level thing unless I've fully understood a low level thing. Other people have completely different strengths I know but for me, you know, I wrote a book about a few verses of the Bible, once I understood those verses and sort of everything I could find in the library about a small part of the Bible, all of a sudden I had firm pegs on which I could hang other knowledge about it. But if I went through my whole life only on, without any in depth knowledge of any part then it all seems to be flimsy and to me doesn't given me some satisfaction. The classic phrase is that liberal education is to learn something about everything and everything about something and I like this idea about learning everything about an area before you feel, if you don't know something real solid then you never have enough confidence. A lot of times I'll have to read through a lot of material just in order to write one sentence somehow because my sentence will then have, I'll choose words that make it more convincing than if I, if I really don't have the knowledge it'll somehow come out implicitly in my writing. These are little sort-of-vague thoughts that I have when reflecting over some of the directions that distinguish what I've done from what I've seen other people doing.)

94 - My children: John

Since the beginning I've tried to be a good father and not just an absentee or something. I did spend a lot of time on writing my books but I also spent a lot of time with them. One of my favorite papers was inspired by them on a trip that we took in California, it's kind of a joke paper called the "Complexity of Songs" and what we tried to find was the longest song that you could have without knowing much. And, you know, we would start out with songs like, "99 Bottles of Beer on the Wall" and that didn't take much to memorize enough of it to sing for a long time and then we went on to other, you know, There's a Partridge in a Pear Tree. Anyway I could study each of these songs from a mathematical standpoint to see how much, how long a computer program it would take to generate the song to last a long time. And my kids were part of this inspiration because we were on a trip to Pinnacles National Monument and we were in the car and instead of saying, daddy when are we going to get there, we were singing songs. And then we ran out of songs and so we thought of this and it led to an interesting mathematical problem and finally we came up with the final solution which was yeah, yeah, I like it, yeah, yeah, I like it repeated endlessly and that was the best solution to that problem. I'm happy that I have some grandchildren now as well, four boys. It seems that something in my mother- if she were alive today she would have, I think it is ten grandchildren, great grandchildren, all boys. So there's something funny going on here, it doesn't seem quite random. But my son has, amazingly enough, became an athlete, his dad is a complete slouch but John, when he was at Stanford was a world class Ultimate player and was, you know, the most valuable player at nation-wide tournaments. And then he became part of a semi professional team and they came in second in the world several times, and he being left-handed was apparently, that was an advantage of somebody playing Ultimate, but a really difficult game, lots of running and strategy going on. So people would come to me and I'd meet a lot of people in other countries that know my son and never heard of me, and this is very interesting because of his athletic ability. But he also turned out to be a terrific teacher working with younger students and he's been a high school math teacher now for more than ten years. He went through Stanford's program called STEP, Stanford Teacher Education Program and then taught local schools here, now he's teaching in Colorado, and won award as the best math teacher in Colorado at a private school or something like that. So he's in his element, this is what my father was and, you know, I've always felt that teaching is the thing that I, is my role. I teach through books because this way I reach a lot more people, John doesn't like to write, we talk to him instead of getting letters home. There's such a need in this country now for people who are dedicated high school teaching and it's such a thankless job because of modern high schools. He was teaching kids who were on drugs and pregnant with huge family problems and he didn't have the situation that a lot of teachers have where people have guns in the school. But considering the challenges and the low salaries that teachers get it seems we need a real revolution in society so that the people, that people who have the motivation to be good teachers are also properly rewarded and get some credit for what they're doing. I've met a lot of heroic teachers from Richmond, California, for example, who teach computer science there and it's a hard life. They have to be supported by their spouses and so does my son. His wife works for Sun Microsystems, telecommuting and that means that they can make ends meet.)

95 - My children: Jenny

I'm very proud of my daughter who, right now, is not in a profession, she's raising her two kids and she's quite active in La Leche League. She and her husband lived at Oxford for several years and she was- put on a lot of programs there while raising her kids and always has many projects going. She also did things like coordinating the exhibit of the artwork for my book, "3:16", which travelled around the world. She's working on projects of creating museum displays and she's an excellent proof reader and writer and right now, blogger. So it seems that I've got these other parts of my life that I wanted to mention too-

What did she study?

She went to Brown University and she found out that if she took a computer class at Brown that people would expect, her name was Knuth and people would expect her to really excel and that so she, that scared her out. I think actually she's very good at sciences but instead, Brown University is unique in the freedom that it gives to students to choose their own curriculum. They sort of, roll your own style there which is well developed, and when she got there she started reading the catalog at the letter A and in her freshman year she took Art, Anthropology, Asian Literature, African History, everything she saw in the catalogue that interested her but she never got to the letter B. But she wound up as an Anthropology major at Brown and then she was going to do her thesis in American, well, sort of the Anthropology of America. And she had some, also some excellent studies of the native houses in Antigua where she had gone on a dig and she studied the evolution of forms in the, what do you call it, the models in clothing stores- the-? I'm trying to think of the word.

Mannequins.

Mannequins, yeah right. So studying the shapes of mannequins, you know, through the ages and so indicating some kind of interest that she was going to do. And she made a big study of, also of river systems and how people dealt with flood control and trying to keep rivers alive, quite a broad range of interests. She never found the right adviser for her and when her husband got a position at MIT then she took classes at Harvard and she could have finished there but then he got a job at Oxford and so she's never finished her formal education but she's done a lot of interesting contributions through writing and I think right now she's got her hands full and doing well. But in high school she showed strength in science. I always thought that she, well, she was very quick and we play games a lot and she always beats me and so does John.)

96 - Working on a series of books of my collected papers

The fact that I started swimming in the 90s also had a nice other secondary effect and that's where I met you at the pool one day and you said, why don't I, why don't we publish a book about literate programming, this idea that you're so hot on. And I think, in fact, in Japan such a book had come out already, that someone in Japan had decided to write such a book. And I was, you know, I had plenty already on my plate but then you went and got one of my best students John Hobby to make a plan as to what such a book would contain and so then I was sold on it. And in fact I got so hooked on the idea that I was thrilled by the thought that I could have the papers that I'd written, collected together and published during my lifetime. As a person who uses libraries a lot I certainly make great use of collected works of scientists and I know many volumes that I consult frequently of the papers of mostly mathematicians, but physicists and others. But these are almost always collected together after the guy died and sometimes 100 years after the person died. So here was something where you were actually proposing to take several of the papers that I wrote that had literate programming as a unifying theme and put them together in a book. That, once I realized how satisfying this would be, you see, I have these 160 papers and I have reprints of them all and they're all in different sizes and shapes and colors and I always thought if my wife wanted to surprise me some day she could have them nicely bound and then they wouldn't all be in such chaotic form. But here you're saying no, not only could it be nicely bound it could be, in fact, reprinted and I could even correct the mistakes that I knew about in these papers. And you were going to do all the work yourself and you had Beth Bryson taking care of it so she sent me the cleanest copy. I mean I've never had a case before where somebody had worked with my papers and presented me with something that I didn't have to almost totally redo, this was before I met Silvio Levy. And so I got a book that was amazingly attractive to me as well as sort of fulfilling one of my dreams that I didn't know I had. And then it developed then that all of my papers would appear in subsequent volumes organized by the different topics, and so far, six of those eight volumes are finished. And I must say how happy it makes me to have them all in a consistent format and with the errors that I know about, sucked out of them and put into context and sort of recast the way I wish I'd written them in the first place. It gives me a chance to, I mean they're not true to the historical record, if somebody wants to know what error did I make in a certain year, you know, they can look it up in the journal, but if they want to know what excited me and why I wrote the paper and what I think is important about that paper in the future, they can look at the book, at these collected works that you've prepared, so there's six of eight are done. The one that I'm dedicating to Bob Floyd is coming up next and it's about the design of algorithms and the last one that I'm saving for dessert is the one about fun and games that I've already referred to. And so, as I was going through my priorities as to what would I do if it was told that I only had a certain number of days to live, it occurred to me that I really would very much like to have those last two volumes of the collected papers finished. So I hope that that works out. I've got, the part of Volume Four that I'm working on right now I have to do first, but then I'm going to do these other two collected papers, get them finished and continue on Volume Four after that point, is my current thinking. The one book on typography is a particular pleasure for me because it has lots of great illustrations in it, but the book on analysis of algorithms is, you know, that's my main life's research work and having all those papers put together in one place is something that, you know, gives a lot of fulfilment.)

97 - Why I chose analysis of algorithms as a subject

Speaking of analysis of algorithms quickly I should say that, you know, I named the subject and I like it but I didn't mention the thing that was sort of key in the beginning, why I thought that it would be rich enough to serve as a life's work. And the reason is that when I was working on a compiler in 1962 I took a day and I looked at an algorithm called hashing, more specifically hashing with- it's called linear probing, a certain kind of hashing. And I'd heard that some students in Princeton had looked at this algorithm and they couldn't figure out how fast it was going to run. And I had a few hours to kill so I took a look at it and I got lucky and I saw how to analyze it and prove exactly how fast it was going to run and this changed my life. I said, wow, this was lots of fun working on this problem, figuring out and so it turned out to be a beautiful mathematical problem although it had come out of a totally practical computer science domain. And I knew that there were many other problems in the theory, what's called queuing theory, that are just special cases of certain kinds of algorithms that had, and already this was a buzz word, queueing theory, the study of the way queues behave. And that's just a special case of a certain kind of algorithm, so if I consider the entire class of all interesting algorithms then it's bound to be full of problems just as interesting as queuing and hashing for which I knew that they were there. So that's why right at that point I said mm, that wouldn't be bad for a life's, to spend a lifetime on it because you have a huge number of problems, not only do they have beautiful mathematical structure that ties together, you know, hangs together in nice patterns, but also there are customers out there so that when you solve the problem the people say hey, thanks for solving the problem, Don. So it's a great field to embark in and that has turned out to be the case.)

Code used to originally pull the above

#!/usr/bin/perl -w
use strict;
use LWP::Simple qw(get);

my @ids = (17060..17156);

for my $id (@ids) {
    my $url = "http://webofstories.com/play/$id";
    my $page = get $url;
    my @lines = split /\n/, $page;
    my ($title, $body);
    for (0..$#lines) {
        if (not defined $title and $lines[$_] =~ /<h3>/) {
            $title = $lines[$_+1];
            for ($title) { s/\s+/ /g; s/^\s*//; s/\s*$// }
        }
        if ($lines[$_] =~ /<div class="transcriptText">/) {
            # Usually it's a single line‚ but in e.g. 
            # <http://webofstories.com/play/17066> it's actually multiple 
            # paragraphs (missing the <p> tags in HTML!)
            for my $endline ($_..$#lines) {
                if ($lines[$endline] =~ m|</div>|) {
                    $body = join "\n", @lines[$_+1..$endline-1];
                    last;
                }
            }
            for ($body) { s/[\t\r ]+/ /g; s/^\s*//; s/\s*$// }
        }
    }
    my $____ = "-" x ((length $title) + (length $url) + 4);
    print <<EOF;
[$title]($url)
$____

$body

EOF
    sleep 1;
}