Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Is Knuth's TAOCP worth the time and effort?

news.ycombinator.com

Post reply on HN
Print view View original

151–160 of 192 posts

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#151

Post by zlg_codes »

scrlk wrote: post #76

D. Richard Hipp used TACOP to implement a B-tree for SQLite: > "Nobody ever taught me about a B-tree. I had heard of it. When I went to write my own B-tree, on the bookshelf behind me, I’ve got Don Knuth’s The Art of Computer Programming, so I just pulled that down, I flipped to the chapter on searching and looked up B-trees and he described the algorithm. That’s what I did. Funny thing, Don gives us details on the a…

This is the first article or interview I've enjoyed reading in months. Thanks for sharing!

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#152

Post by iso8859-1 »

zlg_codes wrote: post #151
scrlk wrote: post #76

D. Richard Hipp used TACOP to implement a B-tree for SQLite: > "Nobody ever taught me about a B-tree. I had heard of it. When I went to write my own B-tree, on the bookshelf behind me, I’ve got Don Knuth’s The Art of Computer Programming, so I just pulled that down, I flipped to the chapter on searching and looked up B-trees and he described the algorithm. That’s what I did. Funny thing, Don gives us details on the a…

This is the first article or interview I've enjoyed reading in months . Thanks for sharing!

The interviewer is on HN: https://news.ycombinator.com/user?id=adamgordonbell

My favorite episode is https://corecursive.com/remote-developer/

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#153

Post by adastra22 »

stonogo wrote: post #150
adastra22 wrote: post #139

Earlier quoted context omitted.

There wasn’t anything useful in these books I didn’t already know from an extensive binge into CS theory and practice. There was no new insights either. There was a lot of useless knowledge that wasted time to cover, like how to optimize for his totally made up machine language.

All machine languages are totally made up.

Sure, but the span of machine languages that are in actual use occupy a small cluster of possible design space. MIX, the language invented by Knuth, is not within this cluster. Maybe computer architectures in the 1960's looked like this, idk. I wouldn't know: I'm not that old.

But it's also a weirdly esoteric, crusty machine language. If it was a Turing tape machine, or an idealized stack machine, that I'd understand. Those are invented architectures that are amenable to analysis and in which the analysis (e.g. maximum stack size, maximum tape use) reflects fundamental properties of the algorithm.

But MIX is just this weird thing that neither resembles CPUs you are likely to use, nor is it particularly useful for analysis.

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#155

Post by dorfsmay »

dctoedt wrote: post #136
dorfsmay wrote: post #95

Earlier quoted context omitted.

Memento Mori. You should imagine that you are forced to sell it every day. Eventually you'll either sell it (or donate it (your local library might appreciate it)) or start reading it.

> You should imagine that you are forced to sell it every day. Semi-serious question: Which of the following do you mean: A. Every day, you should imagine that you are forced to sell it; or B. You should imagine that you will, every day, be forced to sell it. (I teach law students to spot and fix ambiguities in draft contracts; this would be a nice practice example :-) )

A.

OP imagines that there is a point in the future where they read the book without commiting to it. Selling/donating it would put an end to that possibility and force OP to imagine a future where they cannot read it, and hopefully helps them assessing one va the other, and prioritizing accordingly.

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#156

Post by dwheeler »

dmvdoug wrote: post #131
dwheeler wrote: post #90

Earlier quoted context omitted.

"Wrong" is too strong. The fundamental bases it used are not generally used today, but it was the first of its kind and inspired much. Many of its details are still fine. If you are interested in the underlying goal of Principia Mathematica, I urge you to check out the Metamath Proof Explorer (MPE): https://us.metamath.org/mpeuni/mmset.html By itself, Metamath doesn't have built-in axioms. MPE uses Metamath to first…

Yes, it was a tad tendentious, but I don’t think anyone really buys the logicist program anymore. Don’t get me wrong, PM is marvelous and there’s no gainsaying its enormous historical impact. If your characterization of Metamath is correct, I don’t think that’s in the spirit of PM at all. One of the major problems PM had was the rejection of (what later became) the Axiom of Choice in favor of Russell’s convoluted the…

If you believe the big advantage of Principia Mathematica was that it starts with a very few axioms and then manages to formally and exactly prove many things, then MPE is a worthy successor. I'm in that camp.

However, if you think the main point of Principia Mathematica was the very specific set of axioms that they chose, then that's different. The PM authors chose to use a "ramified" theory of types, which is complex. It does have sets, it's just not ZFC sets. Few like its complexities. Later on Quine found a simplification of their approach and explained it in "New Foundations for Mathematical Logic". There's a Metamath database for that "New Foundations" axiom set as well (it's not as popular, but it certainly exists): https://us.metamath.org/index.html

More Metamath databases are listed here, along with some other info: https://us.metamath.org/index.html

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#157

Post by m463 »

Jtsummers wrote: post #41
djtango wrote: post #40

Earlier quoted context omitted.

the hard ones are unsolved research problems? I haven't read the book, so he poses research questions as exercises to the reader...?

Yes. He has a system for assigning difficulty ratings to exercises. I don't have the books at hand, but the highest level were open research problems, potentially suitable for PhD work and the like.

> He has a system for assigning difficulty ratings

He's like a depth-first system guy... I suspect he only planned the 7 volumes because it was a requirement to start out wide.

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#158

Post by svat »

stylepoints wrote: post #50
svat wrote: post #30

A little bit of history about the book series may help understand what is in it. In 1956, Knuth graduated high school and entered college, where he encountered a computer for the first time (the IBM 650, to which the series of books is dedicated). He took to programming like a fish to water, and by the time he finished college in 1960, he was a legendary programmer, single-handedly writing several compilers on par wi…

So it's like the principia mathematica equivalent for computer programming

In some ways, it's the opposite: Knuth is super practical and any theory is only in the service of whatever is actually relevant to writing better programs and getting answers. See e.g. this older comment of mine comparing CLRS and TAOCP: https://news.ycombinator.com/item?id=21924265 — where others may say O(lg n), Knuth will say that a trie search inspects an average of lg N + 1.33 bits for a successful search and lg N − 0.11 for an unsuccessful one.

But then again, as a result of all this work from him, pulling together and categorizing and cataloguing and analyzing all the disparate ad-hoc “tricks” that programmers had come up with, Knuth basically put (this area of) computer science on good foundations and made it a respectable academic discipline. So in that sense he successfully executed a Principia-like project.

To put it another way, the computer programming/algorithms world is generally divided into hackers who derive satisfaction from elegant ways of bending computers to their will, and theorists who are happy to talk asymptotics, treat their problems abstractly as a branch of mathematics, and often never write a single program. What sets Knuth apart is that he straddles both words: is firmly a hacker at heart, but is able to bring prodigious theoretical skill to bear on the area.

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#159

Post by svat »

2OEH8eoCRo0 wrote: post #109

The fact that it's not called The Art of Software Engineering is interesting. If computer programmer was a good enough title for Knuth and Thompson then it's good enough for me.

I like the (overlapping) definition of “software engineering” from Titus Winters (https://abseil.io/resources/swe-book) and Russ Cox (https://research.swtch.com/vgo-eng) respectively, that it is “programming integrated over time” and that “Software engineering is what happens to programming when you add time and other programmers”. In that sense, TAOCP is at something like the extreme of computer programming that is not software engineering: it's about programs for specific problems (don't need to be continuously changed with time), and by a programmer who works alone, does not involve other programmers or reuse their code/libraries.

Re: Ask HN: Is Knuth's TAOCP worth the time and effort?

#160

Post by svat »

adastra22 wrote: post #153
stonogo wrote: post #150

Earlier quoted context omitted.

All machine languages are totally made up.

Sure, but the span of machine languages that are in actual use occupy a small cluster of possible design space. MIX, the language invented by Knuth, is not within this cluster. Maybe computer architectures in the 1960's looked like this, idk. I wouldn't know: I'm not that old. But it's also a weirdly esoteric, crusty machine language. If it was a Turing tape machine, or an idealized stack machine, that I'd understand…

When Knuth wrote MIX, it was indeed a mix of existing machine languages (https://retrocomputing.stackexchange.com/a/18176) and very similar to them — but an improvement over them for pedagogy, e.g. even something as simple as his abstracting away the detail of whether the machine is a binary or a decimal computer.

Of course decimal computers and self-modifying code, and a lot of other things besides, went out of fashion, so he designed MMIX to replace MIX, during 1999–2011. The MMIX update to TAOCP started being put online in 1999 and was published in 2005 (Fascicle 1) and all the individual programs were finally put in book form by Martin Ruckert in 2015 (MMIX Supplement). The design of MMIX is close enough to (some/many) actual CPUs of the present/future — it's basically a RISC architecture like MIPS or RISC-V; in fact Knuth closely worked with Hennessy and Dick Sites in designing it. Yes it is “nicer” in some ways to write programs in than real CPUs (e.g. it has a whopping 256 registers, handles alignment automatically), but that's a fine choice for pedagogy IMO (avoid dealing with register spilling etc, while still being able to look into machine-level concerns like pipelining etc).

Maybe you read TAOCP at some point before 2005 (or missed the “don't bother learning MIX” part of the preface), in which case your complaint is valid (and of course it's not very convenient to read some parts from a different book), but IMO the machine language being a weird one has not been a problem for over two decades.

Post reply on HN