but when...

Exclusive Excerpt from Volume 4 of The Art of Computer Programming

Finally, the answer to one of computer science's most burning questions, "When is Volume 4 coming out?"

More than forty years in the making, the long-anticipated Volume 4 of The Art of Computer Programming is about to make its debut... in parts. Rather than waiting for the complete book, Dr. Knuth and Addison-Wesley have elected to publish it in installments ("fascicles") à la Charles Dickens.

Dr. Knuth's original multi-volume work has long been recognized as the definitive description of classical computer science. Not simply a technical instruction manual as we so often see today, this expounds on the philosophy of programming. His work's breadth, clarity, accuracy and good humor has earned him mythical status. Who has not been told "Look in Knuth" when faced with one of the more gnarly computing problems. In fact, he has earned a spot in the Jargon File of hacker slang.

Appearing time and again on our Top 10 Books of the Last 10 Years lists, many readers have spoken about the profound personal influence of Knuth's work. Scientists have marveled at the beauty and elegance of his analysis, while programmers have successfully applied his "cookbook" solutions to their day-to-day problems. Over a million copies are in print, translated into six languages.

And we've all been waiting for Volume 4. To get the work out there more quickly, Knuth is releasing it in smaller chunks — approximately 128 pages per Fascicle book. In the final plan, all of these will be rolled up into the complete work of Volume 4 — look for it at Bookpool in the year 2007 (we're not taking pre-orders yet on that!).


Exclusive Excerpt from Volume 4 of The Art of Computer Programming

and who not know Donald E. Knuth


Donald E. Knuth at Wikipedia


Homepage from Donald E. Knuth

S@h Berkeley's Staff Friends Club m7 ©

"There are two ways of constructing a software design; one way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult."

- C. A. R. Hoare
.

---

Knuth (And indirectly Kopka & Daly)
Kemeny & Kurtz.
Kernighan & Ritchie.

Is it just me or do the big names in computing all start with K?

---

> Knuth (And indirectly <a> href="http://www.amazon.com/exec/obidos/ASIN/0321173856/104-0423797-8749539">Kopka
> & Daly[/url])
> <a> href="http://en.wikipedia.org/wiki/BASIC_programming_language#Birth_and_early_years">Kemeny
> & Kurtz.[/url]
> Kernighan &
> Ritchie.
>
> Is it just me or do the big names in computing all start with K?
>

Nope! Bjarne Stroustrup!

---

C++ isn't a language - It's OOP masochism, just like C#, Objective-C, and VB.net! ;-)

.o0(+1 I forgot about Bjarne...)

---

not all remember the good old guys

http://setiweb.ssl.berkeley.edu/forum_thread.php?id=11207

without him we have no Mouse....

Greetings from Germany NRW
Ulli S@h Berkeley's Staff Friends Club m7 ©

> C++ isn't a language - It's OOP masochism, just like C#, Objective-C, and
> VB.net! ;-)
>
> .o0(+1 I forgot about Bjarne...)
>

OOP is not masochism! It's actually quite logical once you've learned the principles! You're a smart guy, why haven't you learned it? :-P It's really not that hard! But, it requires a disciplined mind, as you really have to think things through before you start to code!

---

>
> OOP is not masochism! It's actually quite logical once you've learned
> the principles! You're a smart guy, why haven't you learned it? :-P It's
> really not that hard! But, it requires a disciplined mind, as you really have
> to think things through before you start to code!
>

OOP is nice, but C++ is masochism :o)

I like Delphi better.

Regards Hans

P.S:

I already know that real programmers don't use Pascal ;-)

---

<rant class="[b]BIG[/b]">

OOP is not masochism!
No, OOP is an abused concept... It would take me weeks to illustrate every last failure, conniption, and drawback to it, but I'll put Forth the following instead (Beacuse I see it every !ing day...): Students who go to class and learn OOP as their first language cannot code. It's as if their brains die as soon as they graduate, spending their time either looking at the API or trying to instantiate a class that isn't necessary.

Case in point: Hello World. In C#, it's

public class Hello1{
     public static void Main(){
          System.Console.WriteLine("Hello, World!");}}

Why? Is a class really needed for "Hello World"? Granted, it's not a prime example of unnecessary code, but if this is the first program that a new coder writes, it wouldn't be too far-fetched to assume that every program thereafter will be just as over-objected.

Another case: Shuffle a deck of cards. There's no need to create a deck, card, suit, or value class because the job is to shuffle the deck - not describe the cards. .o0(The suit and value can be derived from the card ID via suit=floor(cardnumber/13), value=1+(cardnumber mod 13), so that doesn't matter either...)

What I don't get about C/C++/C# are a few syntactic issues and pointers. The syntax can be fixed with

#define and &&
#define or ||
#define NL printf("\n")

...and all's well. But the use of pointers are as dangerous (if not worse than) GOTOs: I've never been able to fathom how accessing memory contents directly in an environment like UNIX, where the idea is to avoid dealing with the hardware directly in the way that OSI's layers keep to themselves, can be considered acceptable. Moreover, there shouldn't be a reason for it if you could pass and return user-defined types, like a char array, without having to refer to it via its address.

Granted, I've never understood OOP, and I don't think I ever will. That's not a Bad Thing, but due to the fact that I've never seen it applied in ways that FOP/POP can't, I've never seen OOP as a necessary weapon in my arsenal. To me, programs are algorithms: Get input (if applicable), manipulate the data, and spew out the result. Occasionally there's very elegant code (like that trick I learned about swapping the contents of two variables using nothing but XOR), but all in all, it's a series of steps for a CPU - Nothing more.

In fact, programming shouldn't have a do-all and end-all language as its holy grail - That would be a Very Bad Thing.

There are some things that only Logo can do (Sprites), that BASIC can do ($trings and pixel-paint), that C and assembly can do (Zoom! Done.), that SQL can do (Ask questions, get answers), that XML can do (Describe systems and relations), CSS can do (Look good on screen), and that LaTeX can do (Print majestically). Any one language that tries to compete with another's forte is bound to lose ([ahem!] Java). Even when I write my own code, it all begins in pseudo - BASIC, C, SQL, Logo, HTML, and TeX all rolled up into a germ of an idea. From that point on, I weigh each language's strengths and weaknesses, and then start actually coding.

</rant>

It's not the language that makes the application program - It's how you apply the languages that makes the program.

---

>
> OOP is nice, but C++ is masochism :o)
>
> I like Delphi better.
>
> Regards Hans
>
> P.S:
>
> I already know that real programmers don't use Pascal ;-)
>

Have you heard the story about how C was created? It goes like this: Some programmers were sitting having their Friday afternoon beer and started to rant about code languages. They then started a competition about being the one who could create the most ridiculous and incomprehensible language, and the winner was the guy/nerd, who came with C!

I started (recently, I taught myself Basic when I was 16 from a book, later I was married to a systemprogrammer and tried to learn Cobol, but lost my interest, being married to a systemprogrammer!!!!) with Turbo Pascal and later with Delphi, and that was funny! I put some small programmes created in Delphi out on the 'net for people to download and use, if they like them!

Later I learned about datastructures using c++, and that was fun too, but in a more sophisticated way than Delphi! And in c++ there are some options, that are not provided in Delphi, among others hashtables, so...

But I was really amazed when I saw that SetiSpy by Roelof [url=http://www.cox-internet.com/setispy/](May he rest in peace!!!)<a> was created in Delphi!!!

---

>

BIG[/b]">

OOP is not
> masochism!
No, OOP is an abused concept... It would take me weeks to
> illustrate every last failure, conniption, and drawback to it, but I'll put
> Forth the following instead (Beacuse I see it every !ing day...):
> Students who go to class and learn OOP as their first language cannot code.
> It's as if their brains die as soon as they graduate, spending their time
> either looking at the API or trying to instantiate a class that isn't
> necessary.

Case in point: Hello World. In C#,
> it's

public class Hello1{
     public static void Main(){
         
> System.Console.WriteLine("Hello, World!");}}

Why? Is a class really
> needed for "Hello World"? Granted, it's not a prime example of unnecessary
> code, but if this is the first program that a new coder writes, it wouldn't be
> too far-fetched to assume that every program thereafter will be just as
> over-objected.



I try to break your quote here: You are absolutely right, but you take an example from a totally objectorientet language so everything comes out as classes! When I wrote my first Turbo Pascal "Hello World", it came out as:

----------------------------------------------------------
PROGRAM HelloWorld;

BEGIN
write('Hello World');
END.
----------------------------------------------------------


In c++ it was:


//---------------------------------------------------------------------------
#include
#include

//---------------------------------------------------------------------------
//USERES("opgave1_1.res");
//---------------------------------------------------------------------------
void main()
{
cout <<"Hello World," << endl;
cout <<"Jeg har nu skrevet et program i C++." << endl;
getch();
}


The developing tool I use for C#[url=http://www.dealtime.com/xPO-Visual_Studio_NET_Professional_2003](Visual Studio)<a> create the classes it self, so what's the deal?



Another case: Shuffle a deck of cards. There's no need
> to create a deck, card, suit, or value class because the job is to
> shuffle the deck - not describe the cards. .o0(The suit and value can
> be derived from the card ID via suit=floor(cardnumber/13), value=1+(cardnumber
> mod 13), so that doesn't matter either...)


But I still like the idea of having the deck of card as classes, but you are right, shuffling is just a function for a deck of card. If you have your deck from somewhere else, then use it and shuffle is in your shuffle-function!


What I don't get
> about C/C++/C# are a few syntactic issues and pointers. The syntax can be
> fixed with

#define and &&
#define or ||
#define NL
> printf("n")

...and all's well. But the use of pointers are as
> dangerous (if not worse than) GOTOs: I've never been able to fathom how
> accessing memory contents directly in an environment like UNIX, where the idea
> is to avoid dealing with the hardware directly in the way that OSI's layers
> keep to themselves, can be considered acceptable. Moreover, there shouldn't
> be a reason for it if you could pass and return user-defined types, like a
> char array, without having to refer to it via its address.


I agree!! Pointers are tricky and that's why Java doesn't have pointers. Actually, c++ is not taught as a must do in my business academy, where I got my computer education (in Danish: Datamatiker!), anymore, only in a short course; Java is the main language now!

> Granted, I've never understood OOP, and I don't think I ever will.


I don't agree! If you put yourself up to it, you'll learn it faster than many!


That's not a Bad
> Thing, but due to the fact that I've never seen it applied in ways that
> FOP/POP can't, I've never seen OOP as a necessary weapon in my arsenal. To
> me, programs are algorithms: Get input (if applicable), manipulate the data,
> and spew out the result. Occasionally there's very elegant code (like that
> trick I learned about swapping the contents of two variables using nothing but
> XOR), but all in all, it's a series of steps for a CPU - Nothing
> more.


No, but I guess you have done all your programming yourself, and then there is nothing wrong with doing structured programming! Then you'll all the time know what you're doing where in the code. But try to be hired to a company and be presented with a file of 5000 - 10000 lines of structured code and asked to find a semantic fault! Or just to figure out what the code is doing! That's sadism! I prefer not! Then I prefer my OOP, so I can see the classes, how they are defined, the variables and the functions! And I can test them one by one!


In fact, programming shouldn't have a do-all and end-all language
> as its holy grail - That would be a Very Bad Thing.

There are
> some things that only Logo can do (Sprites), that BASIC can do ($trings and
> pixel-paint), that C and assembly can do (Zoom! Done.), that SQL can do (Ask
> questions, get answers), that XML can do (Describe systems and relations), CSS
> can do (Look good on screen), and that LaTeX can do (Print majestically). Any
> one language that tries to compete with another's forte is bound to lose
> ([ahem!] Java). Even when I write my own code, it all begins in pseudo -
> BASIC, C, SQL, Logo, HTML, and TeX all rolled up into a germ of an idea. From
> that point on, I weigh each language's strengths and weaknesses, and
> then start actually coding.

It's not the
> language that makes the application program - It's how you apply the languages
> that makes the program.
>

Again, I don't disagree with you! Get the work done! This discussion about OOP versus Structured Programming is almost a religious as Mac versus PC, so let's rest it! For me it's a waste of time to rant on one method or the other! I've learned OOA, OOD and OOP, so for me it's just as sensible as when I design a database, I make it a relational database! But, for your information, the small program I put out for downloading, started as OOP and reading into RAM from a textfile, and writing from RAM to a textfile when saving, it developed to almost structured coding and with working directly with the database! So, I'm not religious about it!

---

> Have you heard the story about how C was created? It goes like this: Some
> programmers were sitting having their Friday afternoon beer and started to
> rant about code languages. They then started a competition about being the one
> who could create the most ridiculous and incomprehensible language, and the
> winner was the guy/nerd, who came with C!

Actually if you speak with Kernighan and/or Ritchie they will tell you C was written as a joke. They were sitting around Bell Labs complaining about Fortran and all it's failings and somebody said as a joke told them to write a better language if they didn't like Fortran.. So the did!!

NA for the record C is not an OOP. C++ is.. The idea behind pointers was to store like objects in memory and call then any way you wanted. (i.e I store data in a structure and then later point to that structure already in memory). The C++ Object Classes were born of this beleif and took a data pointer one step further. If we can store data and in memory in a structured way why not store code in the same manner. So I create an Object it gets placed in memory and later call that object already in memory ( Though this always sounded like an external subroutine to me ).

Then we went one step further and put whole libraries of code in memory (Windows DLL and Unix DSO). If I remember reading correctly I beleive MIT is working on placing whole Computer's in memory.

I still prefer to code in C and not C++, but then again I still remember the step up it was from FORTRAN.

---

I'd rather speak my mind because it hurts too much to bite my tongue.

American Spirit BBQ Proudly Serving those that courageously defend freedom.

> Actually if you speak with Kernighan and/or Ritchie they will tell you C was
> written as a joke. They were sitting around Bell Labs complaining about
> Fortran and all it's failings and somebody said as a joke told them to write a
> better language if they didn't like Fortran.. So the did!!
>

Thanks Celtic Wolf for refreshing my memory! I didn't quite remember the story!


> NA for the record C is not an OOP. C++ is.. The idea behind pointers was to
> store like objects in memory and call then any way you wanted. (i.e I store
> data in a structure and then later point to that structure already in memory).
> The C++ Object Classes were born of this beleif and took a data pointer one
> step further. If we can store data and in memory in a structured way why not
> store code in the same manner. So I create an Object it gets placed in memory
> and later call that object already in memory ( Though this always sounded like
> an external subroutine to me ).
>
> Then we went one step further and put whole libraries of code in memory
> (Windows DLL and Unix DSO). If I remember reading correctly I beleive MIT is
> working on placing whole Computer's in memory.

Yes, it really speed up things to have it all in RAM!
>
> I still prefer to code in C and not C++, but then again I still remember the
> step up it was from FORTRAN.
>

Yes, FORTRAN is a bitch! Then c is easy compared to that!!!

---

Actually, C++ isn't even "pure" OOP..

You can easily break out of the OOP constraints and code in a non OOP way...

For real OOP, you need to look at a launguage like Smalltalk.

(Yes, I know this is a "religious debate" with C++ diehards!)

---

>...you take an example from a totally objectorientet language so everything comes out as classes!
You're right - Bad example. I couldn't think of anything else, so I lazily Googled "C# Hello World Example".

Back when I was working at the lab at NCC, we had a number of Javans banging their head against a wall on one program: Given a height, find out the time it takes for an object to fall to the ground. This was really easy, because the professor only wanted accuracy to the second. So, being the programmer that I am, I wrote the program to see if it "wasn't possible" as the students claimed...

REM Using Chipmunk Basic and very sloppy code...
[b]input[/b] [i]height[/i]
[i]gravity[/i]=-9.8
[i]elapsed[/i]=0
[b]while[/b] [i]height[/i]>0
     [i]height[/i]=[i]height[/i]-([i]gravity[/i]*[i]elapsed[/i])
     [i]elapsed[/i]=[i]elapsed[/i]+1
[b]wend[/b]
[b]?[/b] "Splat!",[i]elapsed[/i];"sec."

When I finished, one of the Javans came up to me and asked (verbatim) "I don't see the acceleration class anywhere in the API".

I really wanted to dope-smack him one. The point is that it seems a little bit silly to have to instantiate a class in order to print something to console....

>But I still like the idea of having the deck of card as classes, but you are right, shuffling is just a function for a deck of card. If you have your deck from somewhere else, then use it and shuffle is in your shuffle-function!
OK - I can accept a deck class with card objects. I get that. But suit and value are attributes of each card object - That is that each card being unique, they will have an identifier. Nine out of ten, that identifier will be a censecutive serial number, and from there suit and face value are derived.

Here's a better example than the deck of cards: You have a hammer (noun/object). It can hit things (verb/action), but a hammer doesn't hit things on its own - Somebody/Something has to swing the hammer. And to top that off, if I swing the hammer and hit my thumb, I yell out in pain, but if I hit a plonkee on the head, they die from concussion (Don't try this at home). Where is it written that hammer.hit&mdash;>plonkee.life=0 ?

OOP is very good at describing noun/verb agreement, relations between concepts via inheritance, but it falls short of real-world descriptions. Let's say I want to refer to the flat tire I have on my car's front left. Is it car.wheel.left.front.air_pressure=0 or car.wheel.front.left.air_pressure=0? In all honesty it shouldn't matter because I could more easily ask SELECT tire FROM car WHERE owner=me, front=flat, left=flat;, and I don't have to worry about the left tires inheriting the puncture from the two front tires or vice-versa.

>I guess you have done all your programming yourself...
If you exclude the two times I went to the ACM competition, then yeah.

>But try to be hired to a company and be presented with a file of 5000 - 10000 lines of structured code and asked to find a semantic fault!
I hate libraries and headers. I read them and it's like trying to read APL .o0(Difference being, I know a little APL...)

>...I prefer my OOP, so I can see the classes, how they are defined, the variables and the functions! And I can test them one by one!
I really liked VB 6's approach. It was clear and consice about what goes in and what comes out...

[b]Function[/b] Modulo ([i]x[/i] [b]as real[/b], [i]y[/i] [b]as real) as real[/b]
     Modulo=[i]y[/i]*(([i]x[/i]/[i]y[/i])-[b]int[/b]([i]x[/i]/[i]y[/i]))
[b]End Function[/b]

Then when you looked it up, it said "Takes in two reals, puts out a real". I really liked how the function's value was returned, too. No messy return statement - Just put the value into the function's name like any variable.

>This discussion about OOP versus Structured Programming is almost a religious as Mac versus PC, so let's rest it!
UNIX v. BSD v. Linux, x86 v. ppc v. 68k, csh v. bash v. korn, one- v. two- v. three- v. no-button mice, the number of spaces for a tab... [sigh] The list goes on and on and on and on and on and on. But that's why it was enclosed in <rant></rant>s - Pay no attention to the man behind the keyboard in the dark corner... ;-)

>>C is not an OOP. C++ is.
I know that. C is a programming code, C++ is a poorly entered grade, C# is Db, and Objective-C is objectionable. :-D

But enough ranting and raving for one day - I've got an AppleScript to tackle and some LaTeX to revisit...

It's gonna be a loooong night!

---

OK - Last rant on this topic, I swear!

Actually, C++ isn't even "pure" OOP..
Pure OOP can't do anything short of describe objects. You need to have verbs to go with your nouns.

That's it. I'm done: By a unanimous anonymous party of one, this language debate is hereby declared as finished.

We now return to our slated topic: Knuth's Art of Computer Programming.
.o0(Don't you expect the title to have read Knuth, Zen, and Art of Computer Programming?)

---

OK..

In Vol 1 (1976 version)

He laid out the following for volume 4..

Volume 4. Combinational Algorithms
Chapter 7. Combinational Searching
Chapter 8. Recursion

It does seem that he took a very stange turn with Volume 4. I guess todays programmers don't need to understand the "art". Most seem to be too far removed from the underlying methods as memory grows, CP speed increases, and M$ technology becomes the thing taught in school. People are too concened about the color of their widget than how well the code under it really works...

Yes, I do remember when a multi-user system with 128kb of memory and networking actually worked!

Can many programmers today even define recursion, and much less tell you why it can be a good thing?

---

Can many programmers today even define recursion, and much less tell you why it can be a good thing?
From Wikipedia: Recursion: See Recursion. fig. 1

The only time I've seen recursion applied (and well) in code is a Fibonaci number generator. I'm sure there are other applications that I'm not aware of.

.o0(Hmm... not a bad price... think I might get all the volumes...)

---

> The only time I've seen recursion applied (and well) in code is a Fibonaci
> number generator. I'm sure there are other applications that I'm not aware
> of.
>

This is an example of creating a [url=http://www.siteexperts.com/tips/functions/ts20/page1.asp]maze<a> with recursion! It's done in javascript, but the principles are well explained!

---

Watch out, folks: Lena is on a roll tonight! :-D

---