a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!

Web of Stories Ltd would like to keep you informed about our products and services.

Please tick here if you would like us to keep you informed about our products and services.

I have read and accepted the Terms & Conditions.

Please note: Your email and any private information provided at registration will not be passed on to other individuals or organisations without your specific approval.

Video URL

You must be registered to use this feature. Sign in or register.


Being creative in the forest


Work on attribute grammars and the Knuth-Bendix Algorithm
Donald Knuth Scientist
Comments (1) Please sign in or register to add comments
Jane McLaughlin Mack
Friday, 20 October 2023 10:40 PM
I’m enjoying the podcasts immensely. I just found and signed up, and I feel so very thankful,...
I’m enjoying the podcasts immensely. I just found and signed up, and I feel so very thankful, to be able to enjoy, Don’s podcasts. So very interesting.

And so there was this… this combination between the… between the… the inherited part of meaning and the... and the synthesised part of meaning. The part that… that comes out of the, you know, from the small to large, and the part that comes from the large to the small.  And… and I said, you know, I can't… I can’t decide which of these two is better. And so Peter says to me, as we're… 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… 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… you get into a loop. It makes no sense.’ But after… after I was arguing to… to him about this, for about 10 minutes, I… I realized I was shouting, because it occurred… occurred to me that he was absolutely right, you know, that… that you could do both, as long as you… as long as you were careful that the way… that the aspects of the meaning you were defining from the top, wouldn't… wouldn’t depend on the ones that were coming up. So… meaning has different parts to it. And so this led to a research… a sub-field of computer science, called attribute grammar. And… 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… students and classes to teach, and everything else, and kids to take care of, etc… I'm a father.
Okay. Now, meanwhile, I had also been… I had also been thinking of another… of another thing in mathematics, called the… called the word problem, and… 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… a way to solve this problem that's now known as the Knuth-Bendix Algorithm. Peter Bendix was a student in… in my class at Caltech, who worked… who worked out a computer program for it… for his term paper. And… and because of some… 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… the Knuth-Bendix Algorithm, type of work, and the attribute grammar type of work. But no time to work on them.  So it's the busiest year of my life. And I'm… I’m editing journals. I was editor of 12 technical journals at the time. I was getting papers to referee, and to… 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 they… if… I'd take care of the kids, you know, change the diapers, and so on, then they go to bed, if they… if they wake up and cry, I put in my ear plugs, this is my time to… to do my Art of Computer Programming writing. I watch TV, old… 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’d figure out, what am I going to accomplish this day? And I'd… I’d stay up until I finished it. You know, I was… I was used to all-nighters from high school, well I started to, you know, to… to work every day until I had finished what… what I had set myself to do that day.

Born in 1938, American computing pioneer Donald Knuth is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humor.

Listeners: Dikran Karagueuzian

Trained as a journalist, Dikran Karagueuzian is the director of CSLI Publications, publisher of seven books by Donald Knuth. He has known Knuth since the late seventies when Knuth was developing TeX and Metafont, the typesetting and type designing computer programs, respectively.

Tags: The Art of Computer Programming, Knuth-Bendix Algorithm, Caltech, Peter Wegner, Peter Bendix

Duration: 3 minutes, 55 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008