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.
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.
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.
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.)
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.
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.
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.)
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.
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.)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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”.
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.)
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.)
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.)
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.)
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?)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)
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.)