The Art of Computer Programming (interview with Don Knuth)

http://www.bcs.org/content/conWebDoc/40462

by tjr • 15 years ago

140 25 15 years ago

Jun8• 15 years ago

Even in a casual interview Knuth feeds you enough nuggets to make you think for some time, e.g. the Jevons Paradox he mentions at the end (http://en.wikipedia.org/wiki/Jevons_paradox). His faculties and rate of work does not seem to be affected by age (he's 73!), he's the Euler of CS (although I hope he lives longer than him).

andos• 15 years ago

Now, to be put into that category of one of the best books of the century, that’s a little bit embarrassing as they rank me with Einstein and Feynman - I’m not in that league really, I just didn’t have as much competition - they had to have a token person in computer science!

There might be a little truth here but, nonetheless, his devotion to those books made him a legend of our field. And to think people—well, I!—brag so much about so much less. His humility is disconcerting.

wglb• 15 years ago

I think this is simply extreme modesty. Many researchers in the field often think they have discovered something new. Digging a little further, they discover that Knuth has been there already.

horacio• 15 years ago

Andos, I don't feel his humility (expressed here and elsewhere) is at all disconcerting. I feel it's both endearing and appropriate.

Each of us who have accomplished much less, but have boasted of much more, need only keep Knuth's example in mind as a guide for our future lives.

pingswept• 15 years ago

The American Scientist list mentioned in the opening: http://www.americanscientist.org/bookshelf/pub/100-or-so-boo...

bdhe• 15 years ago

The CS department at Stanford has a weekly Theory Lunch during the academic year and we're fortunate enough to get Don Knuth to speak at least once every quarter[1]. His talks, although they start off from basically very little quickly become intensely technical and mathematical. It is quite astounding to see a man of his age have the kind of passion he demonstrates. Even more so the ability to translate interesting and quirky insights into deep mathematical and algorithmic statements (which is very apparent to those who go to his talks).

[1] http://theory.stanford.edu/theory_lunch/

udzinari• 15 years ago

There is also a very long and interesting interview with him at http://www.webofstories.com/play/17060

huherto• 15 years ago

One of my favorite parts...

Looking forwards, what do you perceive are the biggest issues / challenges computer science faces, now and in the near future?

The challenge of how can we go to sleep at night when there are so many things left to be done! (....) but I think so much more could be done by having better health care records and better ways of describing and visualising combinations of symptoms and combining statistical methods as well as visual methods, this would help doctors to understand things more clearly and quickly.

Not to mention the ways in which computers can help biologists to design better drugs. Everywhere you look there’s something to be done which needs a good programmer to help achieve it. There’s no shortage of challenges and little chance of ever running out of them.

It gets me a little personal validation that we still have many exiting challenges ahead.

cheez• 15 years ago

> It gets me a little personal validation that we still have many exiting challenges ahead.

I read that one of the US Patent Office people quit at the turn of the 20th century because he was convinced there was nothing left to do.

If I have learned anything, it's that for every problem humans solve, a few more pop up that we never thought would exist.

It makes me happy.

jleader2• 15 years ago

It appears that that story about the director of the Patent Office saying there's nothing more to invent is mostly made up, see http://en.wikipedia.org/wiki/Charles_H._Duell or http://www.quotationspage.com/quote/22779.html or the most detailed debunking: http://www.myoutbox.net/posass.htm

yarapavan• 15 years ago

I liked his answer for the question - why don’t you do email?

Someone has to not be tweeting all the time, someone has to be thinking about things which need a long attention span and trying to organise material and build up strong foundations instead of rushing off across the frontier. It takes a long time to put out something that has the right style; I have to really think about it and if I’m going to do it right I have to spend a lot of time focussed on it. And I was being treated like an oracle, lots of people from around the world were asking my opinion about whatever, so after 15 years of email I decided that was a life time’s worth.

a3_nm• 15 years ago

Actually, you can still email Knuth, and his secretary will print the email out. See http://www-cs-faculty.stanford.edu/~uno/email.html

I can understand why he wants to be on the bottom of things, but I don't get why encouraging people to use postal mail rather than email is supposed to help. Email is just a medium, and it's a much more sensible way to move information around. The widespread habit of checking email every 5 seconds is by no means compulsory. I wonder why Knuth says that the batch mode communication he wants to do cannot be done properly with email.

jleader2• 15 years ago

I think it's just that he's trying to raise the barrier to entry a little higher. If you know you'll get a response in a few days or weeks on paper, instead of a day or two later in your email client, that makes you look for other, quicker ways to get the answer you're looking for, which reduces the load on Knuth (and his secretary).

dxbydt2• 15 years ago

Coincidentally, I was thinking of what Knuth said just last week, when one of my comments was downvoted into obscurity for promoting a supposedly obscure/contrived math formula over a lame switch-case :) http://news.ycombinator.com/item?id=2817716 In reality, that formula is neither obscure nor contrived. I actually learnt it in high school ie. it was formally taught and we worked through how to come up with such functions given a set of inputs and outputs ie. essentially a bounded set mapping problem { 1->31, 3->31, 4->30,5->31, 6->30,7->31....}

So anyways, Knuth gave an interview maybe 10 years back where he lamented the lack of dexterity in math in American undergrads. He said even Stanford has to offer "remedial courses in math" for CS undergrads, because there is an "interest vs ability" mismatch. At that time ( during the 1999-2000 tech boom ), a lot of Stanford undergrads were indicating CS as their major. So they clearly had the "interest". But upon testing them, it was clear they didn't have the "ability". Hence this interest vs ability mismatch, and a need for remedial math courses at Stanford. At the time, I was studying CS with a bunch of Russian, European, Indian & American classmates. I found that Russians & Eastern Europeans tend to favor clever 1-line math code. They themselves were trained in physics and math & looked at CS problems as essentially a laborious function-mapping exercise. Whereas the Americans invariably wanted "readable code" and ended up writing verbose switch-cases and if-elif-endif clauses ie. essentially unrolling for-loops. Knuth's Concrete Math ( http://www-cs-faculty.stanford.edu/~uno/gkp.html ) was a sort of bible in my days. You had to know generating functions and recurrences and even stuff like complex powers. Like for instance i^i ( i raised to i ) leads to an infinite set of points with real and imaginary parts, scattered all over the 2D plane. You had to know cosets and Lagrange's theorem and set partitioning using cosets. Nowadays people simply enumerate everything as there is no penalty ( in performance terms ), so CS problems have a "select 1 answer from set of possible answers" flavor, rather than "contrive a function to compute the answer" flavor.

kenjackson• 15 years ago

I just upvoted your old post. :-)

I did disagree with the solution (many who see the code would get confused), but it certainly was a positive contribution to the discussion, which is always my bar for upvote/downvote.

And I love Concrete Mathematics. I wish people would say Knuth is the author of TAOCP and Concrete Mathematics. And Ronald Graham is another great computer scientist. With that said I do distinguish computer science from programming.

dxbydt2• 15 years ago

"I just upvoted your old post. :-)"

Thank you!

"many who see the code would get confused"

I honestly don't think we should dispel confusion by dumbing things down to the point where all discrete math is squeezed out of the CS curriculum and all you have left is lame switch-cases and explicit enumeration so there is zero confusion but also zero insight into the problem. Some of the candidates we interview these days are a symptom of this very problem. Lemme give you 2 examples ( actual interviews questions we asked candidates ).

1. write a function that returns the sum of the first one thousand odd numbers.

Expected Answer:

function foo() {

  return 1000*1000;

}

The candidate's answer :

function foo() {

  sum = 0;

  count = 0;

  i=0;

  while(true) {

    i++;

    if (i%2==1) {

        count++;

        sum += i;

    }

    if( count == 1000 ) {

      return sum;

    }

  }

}

Now, the candidate is a LAMP expert and can do magic with linux sys-admin tools, but really, this is such an incredibly lame solution. Yes, its "correct" and very clear and nobody will get confused looking at his solution. But what's more clear is that this person has never had a single course in discrete math. Sum of n odd numbers is n^2 is taught on day 1, its so fundamental and basic and even if you forget the actual result, it takes just 5 minutes to derive it from first principles ( just write the sum forwards to backwards, then write it again backwards to forwards, then add the two expressions, hey voila there you go! ). When we show him the expected solution, he is genuinely surprised and says we've pulled a fast one on him. "Its a trick question! ". He says he's never been taught anything like this in the classroom. That's just sad.

2. Find all the integer triples that form right triangles whose smallest side is less than a million.

Candidate's answer :

for i from 1 to 1000000 {

for j from 1 to 1000000 {

for k from 1 to 2000000 {

  if i*i + j*j == k*k then print i,j,k;

}

Again, this is the "correct" solution and its eminently readable, but it is supremely inefficient and super-lame. Its like the candidate has never given any thought to the actual problem, and is just throwing loops and conditionals at it. I will refrain from giving the expected solution here, but any student of discrete math can generate pythagorean triplets in a much more efficient manner than the lame solution given above.

A little dose of Knuth's Concrete Math goes a very long way.

kamechan• 15 years ago

ron graham is more of a mathematician than a computer scientist. i had him for a professor. he is very entertaining.

shasta• 15 years ago

Knuckles = "o-o-o-oo-o-o-o" ...

zvrba• 15 years ago

"Readable code" is VERY important when you have to deliver a working product to a customer. Especially when you're working in a team.

To quote Dijkstra: "The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague."

The longer I work in the industry as a part of a team, the more I appreciate this saying.

kragen• 15 years ago

There's a much longer interview with Knuth posted originally at http://www.webofstories.com/play/17060. The transcript is probably interesting reading for anyone interested in the man; I imported it into Git and started formatting it into paragraphs at https://github.com/kragen/knuth-interview-2006, although I haven't finished.

I think it would be worthwhile for more people to (a) clone the git repository to reduce the risk that this primary historical source will be lost, and (b) reformat more of the transcript if they feel like it.

sebkomianos• 15 years ago

"I’m jealous of astronomers, for example, because people respect astronomers for doing astronomy because it’s interesting just for its own sake. I studied computer science because it’s interesting to study computer science."

Probably my favorite part of the interview.

adharmad• 15 years ago

"I was born to be a computer scientist - I have a way of organising stuff in my head that just seems to make me a good programmer. I think everybody can learn to use computers, but only about one person in every 50 is a geek in the same way as I am. That means we can push the envelope and can resonate with the computer. The way we think helps to make it easier for us to know how to construct a machine."

One of the few people who can state it as a fact, without sounding arrogant.

The Art of Computer Programming (interview with Don Knuth)

Related Stories