3 ms·

consider the alternatives. it could have been written in PL-1 and rapidly become dated. or it could have been written in a slightly higher level custom language

consider the alternatives. it could have been written in PL-1 and rapidly become dated. or it could have been written in a slightly higher level custom language and that would also have to be taught and would be less clear about what was going on under the hood. or a kind of pseudo-code that would also admit ambiguity. or it could have been rewritten in pascal, and then java, and then javascript and then rust. given the timespan and the focus on complete analysis of running times and not just asymptotics, in the end maybe it wasn't so terrible a choice.

jcranmer 3mo ago
Well, even as-is, it turns out that the kind of assembly language that Knuth originally wrote it in itself had a very short lifespan. MIX assumes a single accumulator register for arithmetic, which hasn't been a common processor architecture since around the 1980s. MMIX is redesigned to be more RISC, but it also uses a dynamic register window concept (which itself I think was only used on Itanium, and we all know how that architecture went down). And unfortunately, for a lot of modern algorithms, you're going to have dive into SIMD-like algorithms, something MMIX doesn't have. Also, a lot of modern processors have a decent suite of bitwise operations (e.g., count leading/trailing zeros/ones, popcount) that is also missing from MMIX. The programming languages that are in favor may change from decade to decade, but so to does most of the assembly language techniques.
- compiler-guy 3mo ago
  Sparc and Xtensa also have register windows, although each has a slightly different implementation. They were all the rage for a while, because they make procedure calls fast but turn out to have subtle issues in highly-multithreaded scenarios.
  - jcranmer 3mo ago
    The Sparc and Xtensa register windows are fixed-size, not dynamic like Itanium's.
- GeorgeTirebiter 3mo ago
  MMIX uses register windows to make stack frame pointer offsets unnecessary when referring to PUSHed arguments. Don is trying to make the algorithms understandable and correct, and by hiding some details that are handled efficiently by compilers (keeping track of FP and offsets), it benefits the human reader. Don's first computer was the IBM 650 https://en.wikipedia.org/wiki/IBM_650?useskin=vector https://en.wikipedia.org/wiki/IBM_650?useskin=vector see also http://ed-thelen.org/comp-hist/KnuthIBM650Appreciation.pdf http://ed-thelen.org/comp-hist/KnuthIBM650Appreciation.pdf so MIX was a simplified version of the 650 because, well, it's well-defined and simple -- and Don knew a popular IBM machine very well. And there's this, in Vol 1: This series of books is affectionately dedicated to the Type 650 computer once installed at Case Institute of Technology, in remembrance of many pleasant evenings. MMIX is for all you youngsters who think RISC is all the rage ;-) and I think he does an admirable job creating a fully-defined machine that does use more modern hardware techniques. The fact that he fully defines his underlying machine is exactly correct, because it lays the foundation for precisely expressing the algorithms, and for giving Time and Space (runtime) estimates. I believe it's fundamentally incorrect to think of these abstract machines as 'assembly language' but rather, I think, they define a stable foundation onto which accurately described algorithms can be expressed. You're supposed to 'play computer' and follow along -- step by step -- to understand the deep details of the algorithms.
  - jcranmer 3mo ago
    I mean, a virtual ISA (think PTX, LLVM IR, WASM) is going to do a better job of giving you an abstract machine than something like MMIX. Virtual registers and call arguments/return values as nary arguments rather than fixed registers give you most of what you want, and it's easy to augment it with a large slice of primitive operations that is a superset rather than subset of assembly languages. (There's another criticism to level at pseudo-assembly language, which is that modern high-performance processors are superscalar with cache hierarchies, which makes the analysis of execution time itself difficult from the kind of first principles that Knuth is working at. I can appreciate why Knuth is working differently from the more traditional big-O notation of typical algorithms classes, but it does need to be acknowledged that it does sap the treatise of its supposedly timeless quality.)

jcranmer 3mo ago

Well, even as-is, it turns out that the kind of assembly language that Knuth originally wrote it in itself had a very short lifespan. MIX assumes a single accumulator register for arithmetic, which hasn't been a common processor architecture since around the 1980s. MMIX is redesigned to be more RISC, but it also uses a dynamic register window concept (which itself I think was only used on Itanium, and we all know how that architecture went down). And unfortunately, for a lot of modern algorithms, you're going to have dive into SIMD-like algorithms, something MMIX doesn't have. Also, a lot of modern processors have a decent suite of bitwise operations (e.g., count leading/trailing zeros/ones, popcount) that is also missing from MMIX. The programming languages that are in favor may change from decade to decade, but so to does most of the assembly language techniques.

compiler-guy 3mo ago
Sparc and Xtensa also have register windows, although each has a slightly different implementation. They were all the rage for a while, because they make procedure calls fast but turn out to have subtle issues in highly-multithreaded scenarios.
- jcranmer 3mo ago
  The Sparc and Xtensa register windows are fixed-size, not dynamic like Itanium's.
GeorgeTirebiter 3mo ago
MMIX uses register windows to make stack frame pointer offsets unnecessary when referring to PUSHed arguments. Don is trying to make the algorithms understandable and correct, and by hiding some details that are handled efficiently by compilers (keeping track of FP and offsets), it benefits the human reader. Don's first computer was the IBM 650 https://en.wikipedia.org/wiki/IBM_650?useskin=vector https://en.wikipedia.org/wiki/IBM_650?useskin=vector see also http://ed-thelen.org/comp-hist/KnuthIBM650Appreciation.pdf http://ed-thelen.org/comp-hist/KnuthIBM650Appreciation.pdf so MIX was a simplified version of the 650 because, well, it's well-defined and simple -- and Don knew a popular IBM machine very well. And there's this, in Vol 1: This series of books is affectionately dedicated to the Type 650 computer once installed at Case Institute of Technology, in remembrance of many pleasant evenings. MMIX is for all you youngsters who think RISC is all the rage ;-) and I think he does an admirable job creating a fully-defined machine that does use more modern hardware techniques. The fact that he fully defines his underlying machine is exactly correct, because it lays the foundation for precisely expressing the algorithms, and for giving Time and Space (runtime) estimates. I believe it's fundamentally incorrect to think of these abstract machines as 'assembly language' but rather, I think, they define a stable foundation onto which accurately described algorithms can be expressed. You're supposed to 'play computer' and follow along -- step by step -- to understand the deep details of the algorithms.
- jcranmer 3mo ago
  I mean, a virtual ISA (think PTX, LLVM IR, WASM) is going to do a better job of giving you an abstract machine than something like MMIX. Virtual registers and call arguments/return values as nary arguments rather than fixed registers give you most of what you want, and it's easy to augment it with a large slice of primitive operations that is a superset rather than subset of assembly languages. (There's another criticism to level at pseudo-assembly language, which is that modern high-performance processors are superscalar with cache hierarchies, which makes the analysis of execution time itself difficult from the kind of first principles that Knuth is working at. I can appreciate why Knuth is working differently from the more traditional big-O notation of typical algorithms classes, but it does need to be acknowledged that it does sap the treatise of its supposedly timeless quality.)