4 ms·

Definitely a product of his times (like everyone). Let me put it this way: to my knowledge, Knuth is the only programmer from his times, still writing, programm

by svat 8y ago

Definitely a product of his times (like everyone). Let me put it this way: to my knowledge, Knuth is the only programmer from his times, still writing, programming, and writing about programming. So you get a 1960s perspective from someone who's seen (and programmed in) 2018; that's not very usual. (BTW I'm not sure that Knuth would wholeheartedly agree with “If you can afford recursion, then you should use recursion”. Perhaps he'd consider the program half-written. That's in some sense the crux of what I think is different.) Let me put it another way: I thought I knew how to generate all permutations of a set of numbers. When I saw questions about it on Stack Overflow or Quora, I answered. When I opened Volume 4A, it disposed of what I knew in the first half-page, and proceeded to discuss the problem for over 50 more pages. I thought I knew about backtracking, having written backtracking programs hundreds of times (always implemented using recursion). Knuth's section on backtracking obliterated everything I knew (and with no recursion in sight). So I'm looking forward to when he gets around to writing about recursion, to see what I can (un)learn about something so fundamental.

taeric 8y ago
His dlx algorithm makes heavy use of recursion. As do many of his cweb programs. In one, he comments it as "textbook" stuff. Your point on him being one of the main programmers from his time still programming is fair.
- svat 8y ago
  Ah but see, his DLX program is not written using recursion! Look at his CWEB program dance.w from his website (or if you don't have cweave handy, download the program from here: https://github.com/shreevatsa/knuth-literate-programs/blob/master/programs/dance.pdf https://github.com/shreevatsa/knuth-literate-programs/blob/m... and click around on the hyperlinks) — all the backtracking happens inside “main”; there are only two subroutines “cover” and “uncover”, and neither of them is recursive. Here is what he says in the (very early) draft of fasc16a (only 2.5 pages written): > We've already seen hundreds of examples of recursion in previous chapters. Early on, we encountered sequences of numbers that were defined by relating each member to earlier members after getting started; these “recurrence relations” were sometimes simple formulas like […], sometimes more involved like […], and sometimes considerably more elaborate and complex. We also found that basic data structures for trees are inherently recursive, because all but the simplest trees are composed of subtrees. We discussed numerous instances where problems of sorting or searching or optimization could be solved effectively by a “divide and conquer” approach, with which a large problem is reduced to smaller problems of the same kind. > Yet we didn't dwell on the recursive nature of those concepts. We transformed them into equivalent notions that could be dealt with directly and nonrecursively. Because “at bottom” a computer operates by means of the physical properties of electrons, which are not recursive. > For example, in Algorithm 2.3.1T we traversed the nodes of a binary tree by using an auxiliary stack A, not by using the recursive definition of symmetric order to define that algorithm in terms of itself. Don't want to quote the whole thing (though there isn't much), but from the sample I feel I'm going to learn from a new perspective (new to me, anyway).
  - taeric 8y ago
    This is near causing dissonance for me. I'm certain I had seen a version of his where he did use recursion. Rereading, you are definitely correct that he doesn't. I know he has program in one of his books where he uses recursion to print the contents of a tree. Maybe I was just confusing that. (Don't have my books handy.) That said, this is definitely going to make me study those programs more. Hilarious how off I was in my memory. (The use of goto statements like he does in the main routine cracks me up, btw. Curious to know if these made a measured difference. With Knuth, I would assume so.)
pnathan 8y ago
I spent meaningful amounts of time this summer with TAOCP. The unusual ways of thinking, the diligence, and building solutions from the ground up were astounding. There are ways of thinking in there that, I think, can be ported into the modern world which would revolutionize the systems they touch.

by svat 8y ago

taeric 8y ago

His dlx algorithm makes heavy use of recursion. As do many of his cweb programs. In one, he comments it as "textbook" stuff. Your point on him being one of the main programmers from his time still programming is fair.

svat 8y ago
Ah but see, his DLX program is not written using recursion! Look at his CWEB program dance.w from his website (or if you don't have cweave handy, download the program from here: https://github.com/shreevatsa/knuth-literate-programs/blob/master/programs/dance.pdf https://github.com/shreevatsa/knuth-literate-programs/blob/m... and click around on the hyperlinks) — all the backtracking happens inside “main”; there are only two subroutines “cover” and “uncover”, and neither of them is recursive. Here is what he says in the (very early) draft of fasc16a (only 2.5 pages written): > We've already seen hundreds of examples of recursion in previous chapters. Early on, we encountered sequences of numbers that were defined by relating each member to earlier members after getting started; these “recurrence relations” were sometimes simple formulas like […], sometimes more involved like […], and sometimes considerably more elaborate and complex. We also found that basic data structures for trees are inherently recursive, because all but the simplest trees are composed of subtrees. We discussed numerous instances where problems of sorting or searching or optimization could be solved effectively by a “divide and conquer” approach, with which a large problem is reduced to smaller problems of the same kind. > Yet we didn't dwell on the recursive nature of those concepts. We transformed them into equivalent notions that could be dealt with directly and nonrecursively. Because “at bottom” a computer operates by means of the physical properties of electrons, which are not recursive. > For example, in Algorithm 2.3.1T we traversed the nodes of a binary tree by using an auxiliary stack A, not by using the recursive definition of symmetric order to define that algorithm in terms of itself. Don't want to quote the whole thing (though there isn't much), but from the sample I feel I'm going to learn from a new perspective (new to me, anyway).
- taeric 8y ago
  This is near causing dissonance for me. I'm certain I had seen a version of his where he did use recursion. Rereading, you are definitely correct that he doesn't. I know he has program in one of his books where he uses recursion to print the contents of a tree. Maybe I was just confusing that. (Don't have my books handy.) That said, this is definitely going to make me study those programs more. Hilarious how off I was in my memory. (The use of goto statements like he does in the main routine cracks me up, btw. Curious to know if these made a measured difference. With Knuth, I would assume so.)

pnathan 8y ago

I spent meaningful amounts of time this summer with TAOCP. The unusual ways of thinking, the diligence, and building solutions from the ground up were astounding. There are ways of thinking in there that, I think, can be ported into the modern world which would revolutionize the systems they touch.