Slashdot Mirror
Knuth's Volume IV Preview Available Online
ahto writes: "The first section of volume 4 of Knuth's The Art of Computer Programming is available for peer review (and the $2.56 finder's fee for every typo is still there :)." Knuth's series-in-progress made a lot of people's lists when it came to assembling the perfect collection of library books for computer science; now you have a chance to make the next one better. If you can find any mistakes, that is.
Dunno 'bout that -- I've met a lot of Windows programmers who've never read Knuth, and I've met a lot of *nix programmers who've never read Knuth. The key factors appear to me to be age and variety of work (it seems to me that older, systems-level coders are much more likely to have gone through some volume of TAOCP at some point).
Admittedly, most of the older, systems-level coders I've met have been *nix folks -- so it may be that I'm seeing the same trend you are and just interpreting it differently.
Knuth books are the material proof that software patents are stupid. I mean 99% of what you need to create a software is in Knuth Books; every useful algorithme, sorting, searching, tables look up, indexing methods are there, all the basic.
It's the proof that nearly everything has been said in that field, and patenting software is in fact patenting "the function" and not "the organ" !
Could be worse.
Could be Harlan Ellison's edit of Last Dangerous Visions (I'd link to Christopher Priest's Last Deadloss Visions, the story of Ellison's failure, but Priest has taken it to print and forced it off the net...)
--Blair
err, what exactly do you mean by, your average Windows programmer? What is a Windows programmer? If a Windows programmer uses C++ what is he? How about Java? How about Python or Perl? What do you mean by Windows programmer? I suppose you call yourself a Linux/Unix programmer. What does that mean? Do you patch kernels? What do you mean? Knucklehead with a superiority complex, that's what I think YOU are.
It's been a long wait since the first three book of TAOCP came out (in the 80's I suppose). I first saw volume 1 in 1973, so for me it's been an even longer wait...
I've heard a wonderful Picasso story, but I don't know if it's true, or just a story.
...
...
The story goes that in the early 1970s, near the end of Picasso's life, a young couple in the United States, admirers of his work, wrote Picasso a letter. In the letter, they told him that they loved his work, but were young and couldn't afford any of his pieces. They enclosed a check for $50.00, and wrote in the letter (truthfully) that this was all they could afford, and that if Picasso had any piece that he would consider selling for this price, they would like to purchase it. If not, the letter asked that Picasso tear up the check.
The couple sent off the check, and received no reply. Then, over a year later, they received a thin airmail letter from Spain
... containing no letter, just their uncashed check. With an unsigned drawing on the back
which currently resides, framed, on their wall!
You know, I've read the Java Virtual Machine Specifications, and I wrote a small compiler that would output Java classes, and I don't recall any op codes with garbage collection built into them. Perhaps you can share which ones these are?
-no broken link
And that my friend, would be the case if none would have thought of plastic boxes before. You can get a patent on applying known concepts in a way that is innovative. For example using a chainsaw for slicing bread (to mention something patently stupid) could be innovative enough to warrant a patent.
-- Spelling and grammar errors tend to be a sign of erroneous thinking.
something like this begs to be continued beyond the author. I think the majority of you know what I'm leading to.
I don't think that Professor Knuth would agree with that. As some of you may happen to know, we could take TeX and METAfont as examples: nowadays, only allowed modifications are bugfixes which get a new decimal digit, and he dictated that when he will die, the reference code shall be frozen, any further bug will be promoted to feature, and their version number will be \pi and e.
DEK is utterly mad: nobody could stop writing TAOCP because of unsatisfaction about how the books were printed, then study typography and coming out with TeX and MF.
But this is why we love him.
ciao,ps: I'd really love to see him playing his pipe organ
Not only do these things make the book unnecessarily hard to read when you're learning stuff for the first time, because you have to pay attention to the complexity of the coding style instead focusing on the ideas that the code is expressing, but it makes it even harder to use as a reference book when you're no longer in the midst of an undergraduate heavy reading phase and just trying to find out about the kinds of algorithms that apply to the problems you're solving.
If you were writing something like this today, it's a tossup whether the right language to use for the assembly portions would be the ugly but well-known and widely available Intel 8086 assemblers, or Java Bytecode which are a simpler model for a virtual machine.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
WOW.. I've always thought that the Windows program "Paint Shop Pro" by Jasc was as good, if not better, then Adobe Photoshop. It's a great example of "shareware" (trailware?) that's as good, if not better, then some of the comercial stuff out there.. anyway, I double clicked this postscript file, just for the hell of it.. and guess what? PSP can view postscript, and render it with all kinds of nifty options (anti aliasing etc). This program never ceases to amaze me...
Thank you. I will go to FSF and check it out.
E
http://eugeneciurana.com | http://ciurana.eu
Wasn't it Dijksta who originally flamed gotos? http://www.acm.org/classics/oct95/
-- What do you need?
-- Gnus. Lots of Gnus.
Well, actually he did. He laid out the proposed structure for all seven in the series before the first one was published.
He even laid out a rough schedule.
As good as he is, he does share one trait with most of his fellow software types, an inability to
generate a reasonable schedule.
All seven books were supposed to have been completed many years ago.
He's not only late, he's got three more volumes to go!
Folks, let's not be so hard on this guy. Since log_2(1048) is about 10.033, then obviously, about 10.033 mistakes have been discovered in Knuth's books so far.
Always keep a sapphire in your mind
I have a book from an AI class,
Artificial Intelligence: A Modern Approach by Stuart Russel and Peter Norvig (ISBN 0-13-103805-2)
that covers the Markov Chain and Genetic algorithms, but not Monte Carlo.
Monte Carlo is more of a computation/scientific programming random sample approach, whereas the random sample in Genetic algorithms are the functions themselves, and not the data.
(nil)
Why do you say he dissed goto's? The paper of his I rememeber on the subject, said that they were frequently not the best way to do things, then spent the rest of the paper talking about places where they were the most efficent way to do things.
The Doctrine & Covenants, silly!
Got Rhinos?
Only problem with the Cormen, Leiserson, and Rivest text is the strange pseudocode langauge they chose. The indentation style makes it very difficult for me to read the code, which is odd, because IMO pseudocode is supposed to be so free of syntactic details that it is the most readable code. But I frequently had to thotoughly examine it to understand which if was being closed where, and so on.
Other than the pseudocode, I'd agree, it's a good, comprehensive algorithms book. I think it easily fills 3 dense semesters of intensive study.
Try Richard Crandall's Projects in Scientific Computation perhaps? It covers all of these and more in one book.
NetBSD: the cathedral vs the bizzare.
The material in Knuth's books is trivial compared to a one-click button. Now that's genius!!!
mefus
In Open Society, GPL Software frees YOU!
Another one of Knuth's major contributions is the creation of the TeX text formatting package.
The mathematical expression output of TeX is incredibly elegant and has yet been matched by any other text formatting package, especially the (comparably) utter filth produced by Microsoft.
In a pre-TeX world, mathematical typesetting was extremely costly and time consuming. TeX had in fact revolutionized the world of creating scientific documents. It is to mathematic/scientific writing what C is to software development. Its use is widespread that in most universities, it is absolutely required that any kind of academic paper in a science faculty be produced with a TeX-derived formatting package.
The coolest thing is, inventing TeX is something Knuth hardly mentions, let alone brags about. It seems to me that Knuth considers TeX as "something he cooked up a few years ago".
In my opinion, you are a stroker.
The problem isn't (necessarily) understanding it. The problem is using it. Translating from assembler, even MIX, to a high level language takes a significant amount of time.
OTOH, most algorithm books seem to be written for college classes. You get to the part of the algorithm that takes a bit of time and effort to get right and "this is left as an exercise". What I want, and haven't found, is a good reference book. TAOCP was such at a time when bits were expensive, and time was cheap. Things have reversed since then. But nobody has written the book, because textbooks have a reliable market.
I'm not sure that I'd buy an algorithm book if they stuffed everything on some machine readable medium, either. Those things tend to go bad, and to go missing. Just recently I was trying to get a good presentation of red-black trees for C++. There was a data structures for C++ book on my shelf, but when I took it down, the floppy was blank. And I didn't even look for that until after I had read the section on Red-Black trees, and when I got to the part I needed, it said to look on the attached floppy. CD's aren't necessarily any better, they scratch and become unreadable. And with DVD's you are depending on the "good-will" of a publisher. Ask an author about that one. So I want it all on paper, where I can see it. But TAOCP isn't right for a reference book.
I think we've pushed this "anyone can grow up to be president" thing too far.
- The Art of Computer Programming for Dummies.
- The Art of Computer Programming: From the Ground Up. (with Herbert Shildt)
- MAXIMUM STRENGTH! TAOCP
Seriously, though. Thank you, Doctor, for taking the time to get it right.Knuth's books are good. They also take a lot of time to use. If you are designing an algorithm that covers a new area, then they are the right tool. But most work is done within known territory.
The real problem is that I have found NO decent reference book on algorithms. Sedgewick is fair, but it is clearly MUCH more of a textbook than a reference book for a professional. A reference book doesn't leave out the curcial pieces with a cute note saying "the missing part is left as an exercise". That is quite annoying when one is trying to get something done, and just wants to use a well-understood tool. Engineers don't redesign their screwdrivers with every new project, why should programmers be expected to?
If I want to use a particular data structure, then you may be fairly well assured that I have some decent reason for wanting to use, say, a Red-Black tree instead of a Hash on the Heap. It would be much easier to use a hash. There's built in language support. But the Red-Black tree is a better match to the problem. So the nlangedd "reference" books don't give you complete algorithms.
TEACHER! Bitter teacher. I don't like doing make work, teacher. I want to get on with things.
Now it's true that the failures I cited don't really apply to TAOCP. Not that much. But it is quite difficult to use, and to translate an implementation. It can more than double the cost of choosing a particular tool (over what an appropriate reference book would cost).
I think we've pushed this "anyone can grow up to be president" thing too far.
I'm not sure how old mr. knuth is but I hope he's able to complete his task. I admire greatly his project. the way that the science of computing advances faster than any other science would seem to make something like this nearly impossible. as it is Mr. knuth already has plans to go back over the previous volumes to update them for new technology. eventually you approach a point where anything you write down is obsolete the next day. even with something as fundamental as the algorithyms he describes is in need of update.
This leads me to think about what might happen once knuth has passed on. I'm in no hurry for him to die mind you but the text are more important or he wouldn't bother devoting so much of his life to them. something like this begs to be continued beyond the author. I think the majority of you know what I'm leading to. Open sourcing the books once mr knuth is no longer able to maintain them, I'm not trying to be greedy. I would eagerly pay for them (once I feel I'm at a level where I felt i had a chance of understanding them) I'm only worried that unlike the other works described on Mr knuths page (einstein and relativity, feynman and QED, etc...) TAOCP would quickly become useless to future generations. I don't think I, or mr knuth, or anyone else here would like that to happen.
-
"IMHO, if you haven't read Knuth's work, you aren't a programmer."
There are plenty of people out there who've read (and even understood) Knuth's books, yet who still write horrible spaghetti code. This includes at least 50% of the mathematics PhD's who have worked for me over the years. I would barely classify these people as programmers.
At the same time, I have seen plenty of good (even "very good") software engineers who have never even seen Knuth's books.
TAOCP (esp. vol I) is important, I would even agree with you that aspiring programmers "should" read it, but IMHO the knowledge is neither sufficient nor entirely necessary for making good programmers.
I think this expresses wonderfully the difference between the mechanic and the engineer. The mechanic knows how to use his tools, and knows what is relevant to the problem at hand; or he is helpless. Unlike the mechanic, the engineer can adapt his very general knowlege to new problems.
Most people don't want to be able to cope with the unfamiliar; it's uncertain, uncomfortable, and sometimes hard. Most folks prefer not to be asked, and thus not to be capable.
Given all that, it makes sense that some coders see no real need for TAOCP. It is math and general tools for thinking, rather than a Chilton's manual for programming application XYZ. It would take decades to fully understand the most of TAOCP, and most folks want to just get their tickets punched and get a job so they can stop making a pretense of learning.
The cake is a pie
Hopefully it won't be as disappointing as another Trilogy extension that we all know and have come to despise.
Careful. There's a damn fine extended trilogy most of us know and love, written by Douglas Adams.
Now if Knuth told us that he'd originally conceieved the 4th book before the first 3, or that he was getting special effects or merchandising consults to work with him, well, yes, then it would be time to worry...
This is a popular view, but I think it's at least partially wrong; the idea that high-level algorythms are easier than low-level ones. Nothing is easier than building abstract, efficient black boxes into a global system that doesn't scale.
You're going to fail, dude!
Knuth isn't going to have ready either book in time to help you with your project.
Dancin Santa
The acrobat distiller will convert postscript files to pdf files. Additionally, you might already have psview (I think it's called that). Adobe ships it as a postscript viewer.
Ask your average Windows programmer about Donald Knuth. Then, ask your average Unix/Linux programmer about Donald Knuth. I think you will notice an interesting pattern emerge. IMHO, if you haven't read Knuth's work, you aren't a programmer.
"To those who are overly cautious, everything is impossible. "
text? Text? You want ascii text? My God, you are a heretic. Here's an author who essentially took a multi year sabattical to write a absolutely beautiful type system--TeX-- and here you are, asking if there's a text version...
Well, I suppose that technically you could be asking for TeX source-- but then you'd be missing the elaborate postscript drawings that pepper the piece. (Since TeX is for the most part error free, MikTex should not cause any typographical errors..., but you never know.)
Try GSView + GhostScript. GhostScript is an open source PostScript interpreter. GSView is a (shareware) GUI for GhostScript. Both are available on Windows and Linux.
All of Knuth's future plans for the series are spelled out on his webpage.
- Abelson and Sussman: Structure and Interpretation of Computer Programs. This book covers a lot of ground when it comes to programming, implementation of programming languages, and the use of abstraction in software development.
- Cormen, Leiserson, and Rivest's algorithm book is an excellent modern exposition of algorithms and concepts in algorithm development.
- Russel and Norvig's "AI -- A Modern Approach" is an excellent textbook covering logic, search, and AI.
Also very relevant to modern computer science are the following books:- Duda, Hart, and Stork's "Pattern Classification" is also a book computer scientists should know, but rarely do.
- Strang's "Introduction to Applied Mathematics" covers elementary material in applied math that every scientist (computer or otherwise) should know by heart.
- Gershenfeld's "The Nature of Mathematical Modeling" is a neat, if somewhat quirky, book at the intersection of mathematical modeling and computer science.
If you have recommendations of other introductory books with a similar style, say on automata theory, string algorithms, number theory, combinatorics, etc., please do share them.Man, all this time I thought volume 4 was an urban legend.
It's the respective version numbers for those programs that are converging to pi and e (and, as DK has decreed, will reach those values upon his death).
The error-finder's fee, as I understand, is not bounded in any way-- save for The Knuth's ability to walk the walk of a perfectionist };-)
iSKUNK!
If they're only paying for typos, nevermind.
If all this should have a reason, we would be the last to know.
how many assembly style languages, a la MIX (or the RISC based MMIX) have a while loop structure? On a fundamental level, GOTOs or jump instructions are neccessary. Granted, utilizing them in a high level OO language is no good. But to truly understand and see the algorithm just a couple of steps above the machine.. they simply must be there...
Knuth's books are timeless. Java, C++, C, Fortran... it's all pretty irrelevant. If you spend some time with Knuth's books it reduces the rest of the books on programming to piddly details that need little time.
I agree with the comment about gotos. I didn't really understand many of those algorithms until I translated them to more conventionally structured code.
Danny.
I have written over 900 book reviews
(and the $2.56 finder's fee for every typo is still there :)."
Man! I wish that was availiable for Slashdot.. I'd be rich!
air and light and time and space
However I still wait to see someone who had time to work through all three existing volumes, and completed the tackable exercises.
So as a course for computer science, I think this series is a failure, as it covers simply too much. Perhaps one should regard it more as a encyclopedia.
Greetings!
/.-ting.
I learned more this afternoon about PostScript, Ghostview, Paint Shop Pro, Photoshop and Acrobat than in the last two years. I appreciate your comments and suggestions.
I used Distiller to convert the document. It was the easiest thing to do. I always wondered what the little "Distiller" icon did besides vectorizing my fonts; now I know.
Thanks again to all, and happy
E
http://eugeneciurana.com | http://ciurana.eu
This is not a draft of volume IV. This is a draft of a section of one chapter in volume IV, namely section 7.2.1.1.
Dr. Knuth writes: "This is a section of a long, long chapter on combinatorial algorithms. Chapter 7 will eventually fill three volumes (namely Volumes 4A, 4B and 4C), assuming that I'm able to remain healthy."
This particular section deals with generation of combinatorial patterns and was released for public review in hope to winnow the most egregious errors before it's released; the subject is so extense that Dr. Knuth felt this was one of the best ways to improve this 67-page section.
I've read the first four or five pages and it's impressive, as always. Heavy on the math from the first page. Either way this will make for very enjoyable reading (if you're in hyper-nerd mode).
Cheers!
E
http://eugeneciurana.com | http://ciurana.eu
I think it would be hard to learn how co-routines work in anything much higher level then assembly. Also things like how to design a runtime so that nested functions see their enclosing scope's locals, and things like that...
But yes, I don't think finding a shortest path in a graph gains from being presented in assembly vs. Modula-3 or something.
Pretty damn gutsy thing to offer. Imagine if there'd been 30 errors...
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
I disagree with this point of view.
Khalid wrote: "Knuth books are the material proof that software patents are stupid."
All the basics can be found in his works, agreed. But implementing products, whether in software or hardware, involves aggregation of this knowledge into a useful form.
Remember: Knowing the periodic table and the properties of chemicals isn't enough; products such as plastics or drugs are the result of aggregating the compounds and combining them through experimentation and know-how (i.e. the art part). In the case of software, knowing algorithms and programming languages doesn't result in a new product or way of solving a software problem. This product or service only has value to *anyone* if the application of algorithms and programming skills results in solving a problem.
Many of us think that the persons who figure how to solve some problem first (or better than anyone before them) are entitled to manage the discovery and protect the know-how involved (i.e. the intellectual property) any way they consider appropriate.
This freedom of choice is what allows some of us to produce code and licence it under the GPL, or the Apache licence, or patent it, or copyright it, or assign it to a third party, or whatever.
I tend to agree that most (perhaps all?) business methods and quite a few service patents are stupid. I don't agree when it comes to software. Then, I am primarily a technologist and make my living creating software products. If I were a business person I'd may have a more informed opinion of their stance on patents.
Cheers!
E
http://eugeneciurana.com | http://ciurana.eu
Don ain't exactly Picasso, but I'll bet that his signature would fetch more than $2.56 on ebay, paticularly if it was on one of his famous hexadecimal checks...
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
I am so happy to see new books being written about the Forth programming language, and by Knuth no less!
I was begining to worry that Forth was a dead language.
(Score:-1, Really Bad Pun)
MMIX is a 64bit VM instruction set and is as good an abstact machine as any other. We don't need garbage collection built into the op codes as the JVM and .NET VM has. We just need a uniform virtual machine in which we can target gcc's code so we can run the code on any machine. There is already a port to Knuth's MMIX already in GCC. Does anyone know of a VM that jits MMIX?
I've been following the saga of volume 4 for twenty years or so now. In the early 1980s I got a math degree at Caltech, and during my stay there I developed a deep love of combinatorics and combinatorial algorithms that stays with me to this day.
I even had the opportunity to ask Knuth (who gave a talk there circa 1983) about volume 4, and it was clear that he hadn't given up on eventually returning to TAOCP.
The Knuth books have always had a treasured place on my bookshelf, but I never stopped hoping that I might someday see Volume 4. Yes, yes, it's only the first fascile. I've known about the fascile plan for the last few years, but it's still something quite different to see the first one. On my screen. Not next millineum, not next year, not next month or week or day, now.
*sniff* It's enough to almost make a geek cry.
--j
I'm a nature photographer.
It's been a long wait since the first three book of TAOCP came out (in the 80's I suppose). Knuth said it would be a 7-volume series. We always wait for the rest to come out. Here's volume 4. You could check out what will come out for volume 5-7. The contents for volume 4 is there too (including the erratas of vol 1-3).
He said that he'll spend his retirement to write the rest. Wow. Check out his homepage, probably you could help him. If you could give him a "significant suggestion", he'll reward you for 32c. If only ask slashdot offer the same prize for each highly modded post. :-)
Caveat emptor: His book is not for the faint-hearted. It's full of math & logic -- but it's wonderful.
--
Error 500: Internal sig error
My fault-- according to this article Jeff Oldham is converting most of the old illustrations into MetaPost. Anyway, the technical challenges involved in "compiling from source" (so to speak) TAOCP are probably enormous.
The fact of the matter is that what constitutes programming today and who is considered a "programmer" has changed significantly since Don Knuth published his first encyclopedic volume in this ongoing series. At that time most programmers really were extremely knowledgeable about mathematics - programming degrees usually involved equal amounts of advanced math and programming. The Knuth volumes were practically bibles for programmers. I suspect that Knuth may have thought that you could actually distill all of the core knowledge required for programming into such a set of reference books. Just as technology has rapidly changed since that era so has programming. A single reference book on algorithms such as Introduction to Algorithms by T. H. Cormen et al. is more than sufficient for most programmers today - more likely even overkill. I can't help but think that few programmers today (say under the age of 30) would really understand much less truly appreciate Knuth's work - it simply isn't relevant for them. This isn't "good" or "bad" but reflects the changed nature of programming. Ask how many programmers today write low level subroutines to perform sorting etc. versus using an existing pre-written package or software component? Yeah, maybe it is good to know this stuff in Knuth's books but given the rush of other skills/techniques/methods to learn it simply isn't as crucial any more.
Knuth's volumes probably should be on your bookshelf. But for learning about algorithms, I think you are better served with a more modern textbook, which focuses on teaching techniques and approaches. And for any particular specialty (string matching, combinatorial algorithms, etc.), there are also lots of books that are more relevant and more complete.
> I think somebody ought to submit every single "goto" in his book as a typo, and claim a few hundred bucks. I grew up on gotos, yet I find it astoundingly harder to comprehend an algorithm expressed in that fashion.
<sarcastic>
Yep. And he should use the libc and malloc.
Hrmmm, no. He should use a garbage collected language, as memory managment would obscure the algorithm.
And, well, he should use all those nifty things that are present in all 'modern' languages. Lists, arrays, hash tables, strings.
Templates. Yep, templates too. I am sure that many algorithm would be simpler with templates.
Maybe he should use perl. There are so many nifty things that can be done with a couple of perl lines.
Of course, nobody would really know what is going on inside, but, well, the algorithm would be much easier to understand.
<sarcastic>
Seriously, Knuth want his readers to fully understand what a computer is at the software level. As soon as you throw high level constructs in that, you are weakening the point. No computer knows hot to do a (real) loop at the fundamental level, so his formal representation is not going to include loops.
Maybe, in 20 years, C will be totally outmodded. C++ too. May C# will have crunched java. Maybe C# will have morphed in yet-another-basic from Redmond. Maybe impertive langugaes will be mostly dead, and we will writing formal specification in an XML-like language. Or maybe emacs will finally be the OS, and lisp the language of choice. Or prolog. Or functional languages will have won so many competitions that only the fools would not use them.
And Knuth will still be working on TAOCP. At least I hope. And he will still be using an abstract machine language, because he talks about what the machine *really* are...
If it is too hard for you, there are plenty of books out there that don't use assembly.
Cheers,
--fred