4 ms·

I agree that Knuth's exposition is a joy to read, and there are a lot of significant mathematical insights to be had within those volumes. I just wish he could

I agree that Knuth's exposition is a joy to read, and there are a lot of significant mathematical insights to be had within those volumes. I just wish he could get away from MIX/MMIX. I don't find it very useful or interesting as a pseudocode, and I think it gets in the way of understanding.

0x8BADF00D 7y ago
Yeah that’s actually what I found intimidating about TAOCP when I was in undergrad. But I stuck with it, and it was a genuinely good read. I feel like SICP is a better introductory text, though.
- ska 7y ago
  TAOCP was never intended to be an introductory text, so that's unsurprising.
kragen 7y ago
On the contrary, I think it's extremely useful to have the algorithms realized in a form that has a cost model free of handwaving. The books are to a great extent focused on computational costs, and high-level languages obscure those costs. The only exception is that the books only rarely dive into the variable computational costs due to operating on values of different sizes; heapsort, for example, is only O(N log N) time if comparisons take constant time, while, in fact, as key cardinality approaches infinity, key size grows as O(log N). (Which is why O(N) time sorting is possible.) This kind of thing is growing more important as hardware design becomes more accessible; there are probably more people writing VHDL and Verilog now than were writing any kind of software when Volume 1 came out. So I think using a high-level language would get in the way of understanding those costs, and even to some extent how to implement the algorithm in other contexts. If you just want to implement a red-black tree or something, then sure, the MMIX code isn't going to help you. But he also presents all the algorithms in pseudocode, so you can use that.
- pmiller2 7y ago
  There's no reason you can't take into account things like varying key size, memory allocation, etc. in your computational model when it matters. For comparison sorting, the reason it isn't done is that if you're comparing keys of the same length, in the worst case, you have to look at the entirety of both keys. O(n log n) might be misleading, but it's a white lie at best.
  - kragen 7y ago
    There are a lot of very interesting issues there. For example, surely you have to look at the entirety of both keys at least once, yes; but you don't have to do it on every comparison, for example in mergesort where you can store a longest common prefix between pairs of adjacent keys and avoid comparing them byte by byte most of the time, or even storing them. The algorithm is tricky both to implement and to analyze, and I don't think anyone has done it, because there are better options for long keys; but I conjecture that it actually gets mergesort down to a real O(N log N) instead of the O(N log N log N) of the usual mergesorts. I suspect that isn't the reason this kind of analysis isn't usually done, though. If you measure the running time of a standard comparison sorting algorithm on real data on almost any general-purpose computer from 1955 to 1985, you will find that, above very small sizes, it is quite precisely proportional to N log N, where N is the number of records. The extra factor of log N doesn't show up. Why is that? It's because almost all of those computers, even bit-serial designs like the RCA 1802 and the LGP-30, aren't bit-addressable; the smallest amount of data an instruction can manipulate is a character, typically 6-9 bits, but often 32 bits. And almost none of them could manage more than 4 gigabytes of data, because that would have been too expensive. So in practice the average time to compare two separately stored keys does not vary by a factor of 100 or so over the data sets the machine could process, as you would expect from looking at key unique prefix length. It might vary by a factor of 2 to 4, but more often was actually constant. MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data. After 1985, caches and massive parallelism complicate the picture a bit, initially for largish machines (though Stretch too had cache, such monsters were exceptions) and finally for almost all types of computers, though perhaps not yet the numerical majority of computers, which are probably mostly 8051s and Cortex-Ms and things like that. Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern. That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.
dirtydroog 7y ago
Totally agree. It doesn't help at all. Pseudocode would have benn sufficient. Fake machine code? Nope.
- kick 7y ago
  MMIX programs can actually be run, and MMIX has multiple simulators. Actual MMIX chips can be made. MMIX also allows students to reason about the properties of modern chips without experiencing quite the complexity they'd have to deal with normally. This is valuable for many reasons.
  - pmiller2 7y ago
    Yes, that's part of the tradeoff between (what could theoretically be) actual machine code and pseudocode. The other advantage of a language like MMIX is, as another comment stated, you can't ignore things in the cost model. This allows more precise calculations of what the runtime of these algorithms is. OTOH, pseudocode is easier to understand, partially because you don't have to think about some of those extra things that don't actually matter in the cost model. For an expository text (and, TACOP is an expository text), I think MMIX comes down on the wrong side of the tradeoffs.
  - dirtydroog 7y ago
    Things like branch prediction, caches, instruction pipelining? Not really. People want the algorithm, not a difficult to translate implementation.
    - kick 7y ago
      To paraphrase Knuth in what I think was a Dr. Dobbs interview: the book isn't for those people, then; they should make their own book.
svat 7y ago
Only a very tiny part of the books is in MIX/MMIX (by my count from 3 years ago; details here: https://news.ycombinator.com/item?id=14520230 https://news.ycombinator.com/item?id=14520230) — if you don't care about it just ignore those programs/sections; it doesn't get in the way of anything. (Similarly you can ignore the mathematics if that's not what you want. You'd be skipping past a big chunk of the book in that case, though.) On the other hand, MMIX is actually a very nice architecture for a programmer to write assembly/machine code for — it has lots of registers, etc. It's more pleasant to write in MMIXAL than x86 Assembly or (I imagine) ARM or even RISC-V. So if you just want that part of the programmer experience, it's a great way to have some understanding at all levels.

0x8BADF00D 7y ago

Yeah that’s actually what I found intimidating about TAOCP when I was in undergrad. But I stuck with it, and it was a genuinely good read. I feel like SICP is a better introductory text, though.

ska 7y ago
TAOCP was never intended to be an introductory text, so that's unsurprising.

kragen 7y ago

On the contrary, I think it's extremely useful to have the algorithms realized in a form that has a cost model free of handwaving. The books are to a great extent focused on computational costs, and high-level languages obscure those costs. The only exception is that the books only rarely dive into the variable computational costs due to operating on values of different sizes; heapsort, for example, is only O(N log N) time if comparisons take constant time, while, in fact, as key cardinality approaches infinity, key size grows as O(log N). (Which is why O(N) time sorting is possible.) This kind of thing is growing more important as hardware design becomes more accessible; there are probably more people writing VHDL and Verilog now than were writing any kind of software when Volume 1 came out. So I think using a high-level language would get in the way of understanding those costs, and even to some extent how to implement the algorithm in other contexts. If you just want to implement a red-black tree or something, then sure, the MMIX code isn't going to help you. But he also presents all the algorithms in pseudocode, so you can use that.

pmiller2 7y ago
There's no reason you can't take into account things like varying key size, memory allocation, etc. in your computational model when it matters. For comparison sorting, the reason it isn't done is that if you're comparing keys of the same length, in the worst case, you have to look at the entirety of both keys. O(n log n) might be misleading, but it's a white lie at best.
- kragen 7y ago
  There are a lot of very interesting issues there. For example, surely you have to look at the entirety of both keys at least once, yes; but you don't have to do it on every comparison, for example in mergesort where you can store a longest common prefix between pairs of adjacent keys and avoid comparing them byte by byte most of the time, or even storing them. The algorithm is tricky both to implement and to analyze, and I don't think anyone has done it, because there are better options for long keys; but I conjecture that it actually gets mergesort down to a real O(N log N) instead of the O(N log N log N) of the usual mergesorts. I suspect that isn't the reason this kind of analysis isn't usually done, though. If you measure the running time of a standard comparison sorting algorithm on real data on almost any general-purpose computer from 1955 to 1985, you will find that, above very small sizes, it is quite precisely proportional to N log N, where N is the number of records. The extra factor of log N doesn't show up. Why is that? It's because almost all of those computers, even bit-serial designs like the RCA 1802 and the LGP-30, aren't bit-addressable; the smallest amount of data an instruction can manipulate is a character, typically 6-9 bits, but often 32 bits. And almost none of them could manage more than 4 gigabytes of data, because that would have been too expensive. So in practice the average time to compare two separately stored keys does not vary by a factor of 100 or so over the data sets the machine could process, as you would expect from looking at key unique prefix length. It might vary by a factor of 2 to 4, but more often was actually constant. MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data. After 1985, caches and massive parallelism complicate the picture a bit, initially for largish machines (though Stretch too had cache, such monsters were exceptions) and finally for almost all types of computers, though perhaps not yet the numerical majority of computers, which are probably mostly 8051s and Cortex-Ms and things like that. Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern. That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.

dirtydroog 7y ago

Totally agree. It doesn't help at all. Pseudocode would have benn sufficient. Fake machine code? Nope.

kick 7y ago
MMIX programs can actually be run, and MMIX has multiple simulators. Actual MMIX chips can be made. MMIX also allows students to reason about the properties of modern chips without experiencing quite the complexity they'd have to deal with normally. This is valuable for many reasons.
- pmiller2 7y ago
  Yes, that's part of the tradeoff between (what could theoretically be) actual machine code and pseudocode. The other advantage of a language like MMIX is, as another comment stated, you can't ignore things in the cost model. This allows more precise calculations of what the runtime of these algorithms is. OTOH, pseudocode is easier to understand, partially because you don't have to think about some of those extra things that don't actually matter in the cost model. For an expository text (and, TACOP is an expository text), I think MMIX comes down on the wrong side of the tradeoffs.
- dirtydroog 7y ago
  Things like branch prediction, caches, instruction pipelining? Not really. People want the algorithm, not a difficult to translate implementation.
  - kick 7y ago
    To paraphrase Knuth in what I think was a Dr. Dobbs interview: the book isn't for those people, then; they should make their own book.

svat 7y ago

Only a very tiny part of the books is in MIX/MMIX (by my count from 3 years ago; details here: https://news.ycombinator.com/item?id=14520230 https://news.ycombinator.com/item?id=14520230) — if you don't care about it just ignore those programs/sections; it doesn't get in the way of anything. (Similarly you can ignore the mathematics if that's not what you want. You'd be skipping past a big chunk of the book in that case, though.) On the other hand, MMIX is actually a very nice architecture for a programmer to write assembly/machine code for — it has lots of registers, etc. It's more pleasant to write in MMIXAL than x86 Assembly or (I imagine) ARM or even RISC-V. So if you just want that part of the programmer experience, it's a great way to have some understanding at all levels.