Slashdot Mirror
Knuth Releases Another Part of Volume 4
junge_m writes "Donald Knuth has released another of his by now famous pre-fascicles to Volume 4 of his epic:
Pre-fascicle 2c is all about 'Generating all Combinations' supplementing his pre-fascicles 2a and 2b.
Furthermore he challenges us all to do more of his daunting exercises and report our success. He thinks we are way too lazy in this respect! So come on slashdot crowd: Do your homework and get the credit from the grandmaster himself!"
The main reason that I have been hesitant to purchase and slog through these books has been the fact that they are written with an outdated assembly language for a non existant processor. I realize that the point is to learn these algorithms, however, since I rarely if ever code on that level any longer, is there an alternative? Something using a language like Java, Python, or even, ack! , 'C' would be more to my liking.
No flames please. This is just an honest question.
Thanks
Apparently very few people cash the (few) checks Don Knuth writes in reward for bugs. Would you rather have $2.56 or a signed checque from Mr Knuth?
I don't buy that argument. And the business about TAoCP being like the Encyclopedia Britainica, a work for the ages is a bit of a crock. As compendiums of algorithm's go I prefer the one written by Ron Rivest and friends. I can't remember whether it is written in Pascal or C and I really don't mind because I can easily read both.
My ideal algorithms book would be written in a modified version of C# or Java. First I would get rid of the unnecessary braces and semicolons. All they do is to make the code fragments longer. Indentation shows block structure much better, continuation lines are not actually ambiguous in algol like languages.
I would also add in statement of the loop invariants, pre and post conditions which as a formal methods person I regard as an important part of an algorithm.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
I was a junior in college when I first read The Art of Computer Programming, and it really opened up my mind to what computer science is all about. It challenged me to think outside the HLL box. Knuth's work has become a timeless classic because he concentrates on the higher level concepts of computer science that transcend the currently popular architectures.
What really blew me away about Knuth's work is that he implements all of the features found in modern HLL's in his own variant of assembler. Someone who can work through and solve the exercises in his books will find themselves able to write programs in any language, and write them well at that. He does not concern himself with the Language Wars, or the Platform Wars, but instead presents the problems and solutions which are common to all computer systems. Too many programmers have been babied intellectually by their colleges and universities, which taught them how to program in a high level language rather than teaching them the fundamentals underlying computer science. Knuth does a good job in getting down to the underlying problems of computer science without bothering the user with the details of arcane architectures that will soon be obsolete.
For this reason, I look forward to his forthcoming work. I look forward to the new challenges which will expand my mind even farther.
The society for a thought-free internet welcomes you.
Wow. No flame intended, but I never expected to hear Knuth called "this guy". For those that don't know the name, here are a few others you might want to check out: Turing, Minsky, Church, Shannon, Chomsky. Of course, these are just the "theory" guys and I am sure others will add to that list. Seems to me any geek should have at least a Readers Digest knowledge of who these people are and what they've done for us.
Devon
My favorite Knuth quote, when he gave a class a snippet of code to use in their program (not verbatim, sorry):
"Be careful with this code; I have only proven it correct, not tested it."
A demonstration of Hacker Nature:
He wasn't happy with the typesetting on his first book, and decided this should be done by computer, so he wrote a markup language for typesetting.
Of course, he wanted to do it right, so this took him... well... about a decade. And when he was done, he had written TeX. He was very pleased; his publishers thought this was odd, as the new typesetting looked worse than the old.
A few years later, high-resolution laser printers became available; TeX already suppported them, and lo and behold, the new version did look better.
TeX is a huge monster of a programming language/application. Knuth offered a cash prize of $(2^N) for the Nth unique bug report. TeX is now, like, 20 years old, and that system cost him under $1K.
If programmers were Jedi, he would be Yoda.
If programmers were wizards, he was be Gandalf.
He is the serious, friendly grandfather who can kick the butts of all us whippersnapers. So pay attention!
There are many others, but that's a good start.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Knuth is entitled to his opinion. It is certainly true that compilers tend to hide the details of the execution. And translating the prior volumes would be a lot of work, so for stylistic consistency it makes sense to continue to use MIX.
... either the Mac 128 or the Fat Mac [512K]). I forget whether the code was presented in Byte or Dr Dobbs. Byte I think. I'm sure it could have been done better, but it wouldn't need to be done better to provide experimental backing to the theoretical arguments. (I suppose that in a sense the MIX virtual machines also provide this, but I don't consider them any better in principle that any other interpreter, and less good than a compiler.)
That said, I feel it's a mistake. I have seen a large subset of C that was implementable via macros as a M68000 assembler language program. This would be a vehicle that would possess all of the virtues of MIX, while being readily understandable by most skilled programers. (They might not be able to compose in it without study, but they could understand algorithms written in it with reasonable ease.) In addition, the timings would be experimentally verifiable (if you could lay your hands on an old Mac
N.B.: If you don't insist on an actual hardware version of the machine, such as would be provided by the 68000, then I still don't see any advantage of MIX over a selected subset of C.
Additionally: MIX doesn't have much similarity to a recent-generation CPU chip. There are a multitude of reasons that Assembler has fallen out of fashion. Lack of portability was one of the major ones. But an even better reason has been the increasing complexity of the chips themselves. Hand-optimizing has become increasingly counter-productive for most people. (It's also become generally less necessary, but that's a separate argument.)
As always, however, there will be exceptions. There exist specialists who need this kind of skil, CPU version dependant though it be. Somebody needs to design the chips. Somebody needs to desigh the compiler optimization strategies. But even for these people, MIX will be a suboptimal choice.
I think we've pushed this "anyone can grow up to be president" thing too far.
It's a joke. It is "shift right immediate". Knuth always includes some hidden jokes in his books.
Jan
I think that you just don't like his style.
I'm not sure what your point is about Feynman taking time out to play in a band - Knuth takes time out to play the organ if that makes a difference to you.
Given the contents of his books, don't you think that Knuth expresses a significant amount of respect for his readers? Name another author who gives cash rewards for reporting problems with books, or even for offering suggestions for improvements. You might think that this is ego driven since the majority of the checks aren't cashed, but this is a choice made by his audience and not by Knuth himself.
---
Things are not as they appear, nor are they otherwise.
Yes, TeX was quite an achievement. Stable, wonderfully un-buggy, most definitely. Unfortunately, it was good enough to catch on and establish itself before its flaws could be fixed.
My particular take:
1) The Computer Modern fonts are not very pretty unless you have a very high resolution typesetter; even then, the letters look too thin and spidery for my taste. Sure, you can use other fonts. But most users never do, or use even uglier ones, usually sticking with Computer Modern for the formulas. Do any other really complete and compatible math fonts even exist?
2) The programming features were hacked on as an afterthought. The syntax is fine, perhaps even near optimal, for straight mark-up, but for developing actual algorithms, it makes Perl code look self-explanatory. Right up there with Intercal. This means that packages like LaTeX or formats are very hard to modify or extend in any kind of robust way. So everyone uses the default format, borrows one that works from somebody else, or works very hard to roll their own. Making even slight adjustments or fixes is a real nightmare.
3) The whole TeX program is terribly monolithic. Sure, the text description and commentary talks about various stages of TeX, but the code says otherwise. Knuth's optimization of the "inner loop" means there is no intermediate description of the TeX syntax.
The program itself was written in very low-level Pascal. The data structures are defined in terms of byte layouts, with explicit memory management. All sorts of tricky details insinuate through the code. Sure, it runs great even on 1980-era machines, but God help you if you want to re-implement it in a modern high-level language. As far as I know, this has only been done using web2c, which is a hack specially made to translate TeX. What's going to happen when C compilers are as rare as Pascal compilers are today?
4) Likewise for the file formats. Laid out with great care, byte-for-byte. Easy to read, but tough to translate into something higher-level.
My part-time project/dream is a modern re-implementation, where the TeX typesetting algorithms are embedded in a modern (Common Lisp) environment--so you can code TeX formats and macros in a heavy-duty honest-to-god programming language, and have an high-level, truly modular implementation using real data structures that could actually be tweaked and modified to do even funkier typesetting tasks.
Part of me says this will be easy, because something like 60% of TeX: The Program is doing stuff like memory management that Lisp will do for free, and accounting for funky character encodings (EBCDIC and 6-bit Pascal character sets) that probably can be ignored now that almost everyone is now in ASCII, or headed toward Unicode. The other part of me says this will be difficult for exactly the same reason.