ACM ByteCast - Don Knuth - Episode 2

Episode Date: June 2, 2020

In this episode of ACM ByteCast, Rashmi Mohan is joined by 1974 ACM A.M. Turing Laureate Donald Knuth, author of the hugely popular textbook series, "The Art of Computer Programming." They discuss what led him to discover his love of computing as well as writing about computer programming, his outlook on how people learn technical skills, how his mentorship has helped him write “human oriented” programs, the problems he is still working to solve, and how his dissatisfaction with early digital typesetting led him to develop TeX, as well as his interest in playing and composing music for the pipe organ.

This is ACM ByteCast, a podcast series from the Association for Computing Machinery, the world's largest educational and scientific computing society. We talk to researchers, practitioners, and innovators who are at the intersection of computing research and practice. They share their experiences, the lessons they've learned, and their own visions for the future of computing. I am your host, Rashmi Mohan. If you've been a student of computer science in the last 50 years, chances are you're very

familiar and somewhat in awe of our next guest. An author, a teacher, a computer scientist, and a mentor, Donald Knuth wears many hats. Don, welcome to ACM ByteCast. Hi. I'd like to lead with a simple question that I ask all my guests. If you could please introduce yourself and talk about what you currently do, and also give us some insight into what drew you into this field of work. Okay. So I guess the main thing about me is that I'm 82 years old, and so I'm a bit older than a lot of the other people you'll be interviewing. But even so, I was pretty young when computers first came out.

I saw my first computer in 1956 when I was 18 years old. And so although people think I'm an old-timer, really, there were lots of other people way older than me. Now, as far as my career is concerned, I always wanted to be a teacher. When I was in first grade, I wanted to be a first grade teacher. When I was in second grade, I wanted to be a second grade teacher and so on. I finally got to college. I decided I wanted to be a college teacher. And so that's what happened. And I guess I also enjoyed writing because when I was in seventh grade, our teacher was extremely good at teaching us about English grammar. We learned how to make diagrams out of sentences, and this was quite

fascinating. And so by the time I got to high school, I found out that I had more training in grammar than most of the other kids in my classes. So I took every opportunity to do some writing. I edited the high school newspaper, for example. And then in college, I also did, well, I wrote computer manuals while I was an undergraduate. And I was editor of a magazine in college. So anyway, teaching and writing, that sort of defines me. Amazing. And, you know, rightfully so. I think we've all been beneficiaries of your writing. And many of us who have been lucky have been beneficiaries of your teaching as well. But one question I do have is, so teaching and writing, I understand, and a particular interest in writing leads to many different ways of writing. Why computer science? Why mathematics and computer science? When I was 18, I saw this computer through a window. And in those days,

it was kind of a big thing. But I got to open the door and find out how it worked. And I was lucky. I was at Case Tech. It's now called Case Western Reserve, but changed its name afterwards. So they had a very enlightened administration there. They allowed freshmen like me to touch the mainframe computers. And most other universities, I think only maybe Case and Dartmouth and Carnegie were so foresighted. And so us youngsters were allowed to write software for the campus and learn all about the machine. So I fell in love with that machine. In fact, I dedicated my book to it later on. And so at that time, I found out that I had somehow grown up with a peculiar kind of brain that the way my brain organized stuff, it seemed to resonate pretty well with computing machines. And so I would look at these instruction books that came

from the manufacturer. And it seemed to me those books were pretty stupid because it was easy to figure out how to solve the problems better than the way they were suggesting. And so I decided maybe computing was also going to be for me. On the other hand, I had no idea that I'd ever be teaching about computing because there was no such thing. People use computers, but they didn't have any courses in colleges having to do with computers. So that came later. And I also enjoyed my math classes. And so I was a major in mathematics. And I began also as a professor of mathematics at Caltech for several years. You know, it's amazing that you bring mathematics up because I think, you know, recently I was talking to somebody else and they were saying, you know, in order to be really

proficient as a computer scientist, you really need a very strong foundation in mathematics. I mean, technology today is a field that's very welcoming. You know, most people can participate by learning how to program in like one or two languages and with little background and, you know, start to participate in the field itself. As we build like the next generation of computer scientists that are coming into this world, what do you think are the key skills that helped you be really proficient in this field? Would you attribute it to your background in mathematics, or is it traits within yourself that you think helped you be as successful as you are?

Well, thank you for saying I was successful in a way. Computers are, for so many things, different these days. So there can be people from many different backgrounds who will also be successful using computers in their way. But for the way I do it, the thing that I'm particularly, I seem to be cut out for is programming. And there seems to be a difference between people who, for whom programming comes naturally and people who struggle with it.

You know, they can do it if they have to. But it's something like teaching a dog how to walk on two legs. A dog can learn how to do it, but a dog is much better at four legs. Well, there are some people who can, they can write programs and they can do what they need to do. But then there are these people that have this strange kind of brain I do that for which programming seems most natural thing and you sort of resonate or in sync with how to do it. I found through my life that about one in every 50 people has this strange quirk that they were born to be a great programmer. And that number might be changing in different cultures because kids are exposed to different things when they're young now, but

certainly it's been constant for all my experience. And so the thing I do best is communicate with the people in that 2% of the population who are good at programmers. I try to be a mentor to them. Do you find that it's easy to identify or observe those traits within the people that you teach? Oh, yeah, yeah. We can sort of recognize each other immediately. I mean, we tell different jokes, we use different analogies, and we have high bandwidth conversations of a different kind

than with somebody who doesn't have this same mentality. I was reading translations of Sanskrit works from the 13th century, and some of those guys who were musicians in India, you know, I think that they would have been computer scientists if they were living today. I know that music is also a very significant interest to you, and I definitely want to talk about that in a little bit. But continuing down the same conversation, Don, you're also referred to often as the leading expert on algorithms. Your book, The Art of Computer Programming, is considered a bible for many computer scientists. How did you develop an interest in this particular field of computing, and what did you do to hone your interest and aptitude?

That's what computer programs are. It's putting an algorithm into a concrete form. An algorithm is an abstract thing, and a program is a way to put it into some language. It's like information is an abstract thing, and data is expressing the information put it into some language. It's like information is an abstract thing and data is expressing the information in number. So an algorithm is this idea of first you do this, then you do this, and then you decide whether to go to case one or case two. And this peculiar ability that programmers have is for a way to see the problem as a whole and also at the same time see it at the low, low level. So you know that in order to solve this overall problem, what you have to do is add one to this number in some part of the machine

and jumping levels in between the low levels and the medium levels and the higher levels and the real high levels, going back and forth seamlessly without being aware. This is a skill that seems to be essential for a programmer. And is this something that you feel you iteratively sort of developed or have you seen develop in other people? Is that something that you can get better at? I'm not the right person to ask because I have the skill. So I have to talk to somebody who didn't have it and And then a year later

found that she learned it. I mean, I'm not sure how teachable it is. And since there's a great need for more programmers in the world, it'd be nice if we could teach everybody. But I do know things that I've tried very hard to learn, and I was unable to learn myself. And so I don't think it's just a matter of motivation and trying to learn. I think there, for example, I'm pretty good at algebra, but I'm not very good at geometry. And I've tried hard to develop skills at geometry and visualizing things better,

but I'll never be anywhere near be able to do it the way my wife does or some of my students do. On the other hand, algebra, I don't know if I learned it as a skill or if it was something I did when I was 10 years old or something, but that's the way it is with me. So, in other words, if somebody thinks they can teach anybody anything, then I would say, okay, come and teach me geometry. Yeah. I mean, that's pretty fascinating. And, you know, I'd agree with you. And there are certain things, I think, that can be learned. And then there are

many things that maybe are intuitively something that you develop as it's a talent that you have that you can probably hone to a little bit extent. Yeah, well, I mean, people are different. Everybody has different profile of abilities, it seems to me. Another thing I'm sure I'll never be is good at playing soccer. And I'm tall, but I was never good at basketball. I tried hard, but I did have good at basketball. I tried hard to, but I did, you know, have a good student career as the manager and scorekeeper.

Very, very valuable skills and definitely needed for the team. Okay, I'm going to switch gears a little bit. So I did a little bit of background in terms of, reading up about your career. And I know for a fact that you introduced literate programming into the world of computer science. And I'm just curious as to, it's considered par for the course now, but what is it that sparked that insight in you? Well, I told you that I like to write. And so I came to a point where I had written some software

that people wanted. And there was a question, if you've got a big computer program, how do you communicate that to somebody else? And it turned out that, well, I was inspired by a report that I read from a man in Belgium, goodness, what was his name? But anyway, it's called Holan Programming. And he had an idea where the way to understand a complicated thing like a computer programmer, but also any complicated thing, is to realize that it's just a lot of simple things put together in simple ways. And when you do that, then you can make complicated things understandable. And so once I realized that I could break down my programs

in the same way, then I could be simultaneously a teacher and a programmer. So ever since then, which was 40 years ago now, when I'm writing a program, I'm also thinking of myself as a teacher and a programmer. So ever since then, which was 40 years ago now, when I'm writing a program, I'm also thinking of myself as a teacher. I'm imagining that I'm at a blackboard teaching a student what this program is supposed to do, instead of just thinking of myself as typing in something for the computer. The program that I write then is actually human-oriented, and I can come back to it a year later, and I know exactly what I was thinking about when I was writing the program. And so this turned out to be kind of the most thing for me. Now, I still write on the average of five programs a week. They aren't usually very, very long, but let me see that. Last Sunday, Monday, Tuesday, I wrote a program that's about

900 lines of code, and I'm quite happy with it. And found another bug in it this morning, but it seems to be working pretty well. That's wonderful. What problem are you trying to solve? Well, that problem was to convert a CSP into DL, was the name of the program, that you take a constraint satisfaction problem and convert it to a exact cover problem.

And I have very good solvers for exact cover problems. And so I wanted to try out algorithms for constraint satisfaction by translating that into this DLX language. And then I can watch how it's solved in the DLX language. So it was kind of a translator from one language to another. That's amazing that you're so fascinated by programming and still writing programs. Let me interrupt. I did want to get in a plug for my latest book. Absolutely. Because DLX, well, DL stands for Dancing Links. And last December, I published a little paperback,

well, it's 400 pages, which had Dancing Links in a title. And I'm really happy with it. This is where this exact cover and a lot of other things associated with it are sort of explained for the first time. I've been working on it for years, but this is kind of where I finally wrote it up and tried to present it to the world. And I hope everybody's going to love it as much as I did. If you take the book and you turn to almost any page, you're going to find, I think, a puzzle that you're going to enjoy solving because that book is just loaded with puzzles. It turns out that the best way to express the kind of algorithms that are in that book seem to be to explain them in terms of puzzles. And so I've got many of the world's most famous

puzzles explained there in different ways than they've done before. And so the best I can say is it was so much fun writing this book because I sort of felt all my life I've been preparing. I always enjoy a zombie puzzle. When do you anticipate that it'll be out? It sounds fascinating. No, it came out in December. Okay, great. It's actually in second printing already.

Yeah. If everybody buys a copy, then we'll go to the third printing because I got a few more corrections from readers. Terrific. I hope we were able to help you and aid you along that journey. I'm delighted to have people reading it, but I didn't write it in order to make money. I wrote it because I thought the ideas were really cool. So, I mean, when you talk about writing, I read up another little anecdote about you, which led to another story that I was very fascinated by, which is when your first book got published and you actually saw a digital copy of it. You were unhappy with how it was represented in digital form, and that led you to creating text.

So I was wondering if you could tell me a little bit more about that journey. I mean, starting to see a recurring pattern, you see something that's not working well, and you launch into that problem and try and solve it yourself. Well, the only reason that I decided to work on tech was because I also learned at the same time that the printing industry had gone through a revolution where they went away from metallurgy and printing based on hot lead or on optical or camera work. But the new machines were digital. They were just bits, zeros and ones. So every page, if you see in a book, you put a zero where it's supposed to be blank, and you put a one where there's supposed to be ink.

And so printing had converted from something that I didn't understand at all to zeros and ones, which I figure I understand as well as anybody. So if all that was needed in order to get my book looking nice again was to be able to produce patterns of zeros and ones, then I couldn't wait. I couldn't even sleep at night. It was too exciting to try to solve the problem and make it so that I could enjoy reading my books again. I learned about the digital printing. It was in the spring of 1977. I was chair of a committee at Stanford that was trying to revise the reading list for our graduate students when they take the comprehensive exam.

And one of the books suggested to add to the reading list was a new book by Pat Winston called Artificial Intelligence. And they showed us the proof copies of it, which had been printed on a new machine in Southern California. And I looked at the proofs, and they looked like a real book. But then I found that this machine was actually a purely digital machine. And I didn't believe it, because I had seen poor approximations to type on computers, but they looked awful. But this book, the proofs for Pat Winston's book were terrific. And so a week later, I was in Southern California looking at the machine. That's quite a story. I want to switch gears to your teaching career. I know you have a particular interest in working with students. I mean, obviously, you've had a very long and successful

teaching career. What would you say was your defining moment? You said that you, you know, in first grade, you wanted to be a first grade teacher. What was it about that, that whole process of being a teacher that was so interesting to you? I guess when I learned something cool, I like to pass it on to somebody else. And it's especially nice when you see that you have actually succeeded. In other words, the light comes into somebody's eyes and they have now experienced something because you were able to help them learn it. So that's the thrill, really.

I agree with you. I mean, I think even as, you know, a lot of times when I come from an engineering management type of role, and I feel that way as well, when you are able to sort of help people uncover career aspirations and see them success, move along that journey, it's a very rewarding experience. Whatever your career is, you get satisfaction when you see that it's actually paying off and making an effect on people rather than just

bringing in money. Yeah, absolutely. And do you spend a lot of time also mentoring young computer scientists outside of your classes, Don? Well, I've been retired for 30 years, but even so, I go into school four days a week and I have lunch with the students. I worked one-on-one with a lot of students before I retired, of course. More lately, I'm just working with the people I meet. And then, well, of course, I give public lectures. And very traditional around Stanford where every December I give the annual Christmas lecture. That's for 25 years now. And usually, I mean, what is the area of interest that you pick? So it's about the coolest thing I learned that year that I thought more people ought to know about.

And I tried to make it cover important technical material, but without going over the heads of too many people. And Stanford streams these lectures now online, and they're recorded. They've got not only these 25, but more than 100 other lectures that I've given over the years. It's all available through Stanford's website. They're on YouTube. Would you care to share what you spoke about this past Christmas? Dancing Lynx. That was the book that came out. Yeah, I'm sure our listeners would definitely go in and look. We'll add the details into the show notes so they can go and look that up.

I have a question. When we're talking about mentorship, et cetera, especially as a teacher, I think it is a natural extension because students sort of look to you for advice, you know, that knowledge and that experience on to more junior. How do we sort of make that journey of mentorship more formal or more effective? Depends on how many people you're trying to reach, of course. But right now we're getting advances in technology that'll make it possible to reach more people. Still, the one-on-one is where you're able to work, instead of me preaching at somebody

else, much better if I can watch how they do it. And then I can, instead of telling them what they should have done, I'll say, and why did you do that? So in my classes, it's become trendy now for people to have what they call the inverted classroom, where the students are doing most of talking. But that's the way I always ran my classes at Stanford. I was inspired by George Puglia, who put out a great video. Well, of course, it was on film in those days. But in the 60s, he had a little example of a Stanford class that he had taught. And the title of it was, Let Us Teach Guessing. And so he's saying, ask the students to guess.

Instead of lecturing at them, state a problem and then ask them to guess what to do next. And this way, that makes them more interested in it. And then you can go on and continue to have them learn by their own ideas rather than absorbing others. So that's the way I ran my class at Stanford. And we had teaching assistants taking notes of it so that what came out was then written up and came out as reports. And that was eventually published as a book called Concrete Mathematics. In your own mentoring, suppose you have 50 people, but you somehow randomly designate five people, you know, everybody who's sitting in the back row or everybody who's wearing glasses or wearing

something yellow or whatever it is, but have some rule to pick out five people and then tell them not to be nervous. If they make mistakes, so will everybody else, and they're just helping to focus the conversation. And then you can work that way improv rather than with a canned lecture because really people learn more from making mistakes than from memorizing. I think that's very sound advice, especially the random matching of mentor to mentees and the ability to sort of provide an open-ended problem that people then sort of solve together

and make mistakes but learn through that process. I think that's great advice. Yeah, and there's lots of different ways to solve any problem. And also just learning the variety is wonderful. But learning how to recover from error. I remember one time particularly, I was working with a class and we were trying to solve a certain problem. It turned out that no, they came up with the wrong answer. But all of a sudden, I had a flash of insight and I said, oh, hey, you can see that's not the right answer, but can you figure out another problem for which this is the answer? And so it turned out that that was one of the most successful days of teaching I ever had, was when we went down a completely different road because we had an answer. We were trying to find the problem instead of a problem trying to find the answer. I'm not sure if the students enjoyed it as much as I did, But anyway, that's the way I like mentoring.

Yeah, I mean, that's a wonderful, a very inspiring and positive story. I'd like to go back to your own interest, though, which is in music. You mentioned that briefly earlier. Do you spend a lot of time playing music or listening to music? So that's my main avocation is enjoying music. And that, again, was something that started when I was very young.

My father was not only a teacher, he also taught music. And I learned to read music when I was young. And then through high school, I played tuba in the marching band. I played saxophone in the symphonic band. I played piano to accompany the choir. During the 60s, I got inspired by pipe organs because the organist at the church where I was going suddenly took ill, and I had taken one year of how to play the pipe organ when I was 12 years old. And so I got this phone call on Saturday saying, Don, can you play the organ tomorrow morning? Our organist is going to be down for six months with a detached retina.

And in those days, the only way to cure that was for him to lie still for six months. And so I got back to playing the organ regularly, and I fell in love with the music that had been written for it. At that time, I was in Pasadena, California, where some of the best organists in America happened to be located because of mentoring. There was a man named Clarence Mader in the 1920s who had been an extremely good teacher, and so a lot of his students were in the Pasadena area at that time.

So I got very interested in music for the pipe organ, and later I got a pipe organ for the music room in my own house, in fact. And so that was a long time love of mine. I also had a rare idea that there ought to be a certain kind of a piece written for a pipe organ, but I knew that it would take a long time to bring it off. But for 50 years, I was sort of thinking about writing such a piece. And then finally, it was seven years ago, I decided, hey, Don, you're getting pretty old. You're 75 years old. Now, if you're

ever going to finish that piece, you better get to work on it. So I spent five years from age 75 to age 80. On a lot of weekends, I went and worked on writing this piece, which is called Fantasia Apocalyptica. And it's a different kind of a sound, and so it's experimental, and some people will probably hate it, but I personally am glad to say that I think it's something that I am very glad that Tanner was able to bring off. And so the happiest day of my life was on my 80th birthday when we had the world premiere of this piece. It lasts an hour and a half, but it actually breaks down into 22 parts that are each pretty short.

And you can watch those one at a time on YouTube if you're interested. So the name is Fantasia Apocalyptica, and it's been performed in its entirety now. We had three performances. The first one was in Sweden. The second one was in Canada. The third one was in Czechia. And now we're having the American premiere in October of this year. Well, congratulations. That's a tremendous achievement. And definitely, I will definitely go back and listen to it, as well as share the link with our listeners. I'm sure a lot of people will be very interested. Thank you for sharing. By the way, it's not just organ, but it's multimedia.

So there's also three video tracks that go with it. So it's been captured very beautifully, these performances. I was quite thrilled that Google actually sent a team of four people up to Sweden to record the world premiere with the word best state-of-the-art 360 projectors, and we also had surround sound, special audio. So we got a digital recording of that performance that was state-of-the-art at the time, and all the bits are now in Stanford Archives waiting for some graduate student to put them together and make a beautiful VR experience out of it.

Thank you so much for sharing that, Don. I mean, that's an incredible, incredible story. I look forward to listening to the piece. I think we have time for our last question. So, for our final bite, I know you prefer not to predict the future, as you say, but I would love to know, what is it that you're most excited about now, like the immediate? What is it that is keeping you super excited right now? Oh, well, I'm continuing to write The Art of Computer Programming. It's something I started in 1962, and I'm still having great fun writing new copy. I mean, the reason I found a bug in that program this morning is because I finished another page of The Art of Computer Programming.

And as I was writing that page, I had to check it out and found this book. So as I said, The Art of Computer Programming was written for the 2% of the world who are resonating with computer programming. I'm happy when I see their eyes light up. And the page I wrote this morning, I think is actually going to be understood by even three or 4%. Sometimes there's no way for me to make something extremely simple, but I make it as simple as I can. And I could have made it a lot harder. Don, it's been an absolute honor to be a part of this conversation. We look forward to reading your new book. Thank you for taking the time to speak with us at ACM ByteCast.

It's been a pleasure for me. Thanks so much, Rashmi. ACM ByteCast is a production of the Association for Computing Machinery's Practitioners Board. To learn more about ACM and its activities, visit acm.org. For more information about this and other episodes, please visit our website at learning.acm.org. That's learning.acm.org. slash b-y-t-e-c-a-s-t