Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?]

[seebs@solutions.solon.com (Peter Seebach)]

In article <01bb8569$9910dca0$87ee6fce@timpent.airshields.com>,
Tim Behrendsen <tim@airshields.com> wrote:
>Peter Seebach <seebs@solutions.solon.com> wrote in article
><4udb2o$7io@solutions.solon.com>...
>> >> In C, we write

>> >> 	int
>> >> 	gcd(int x, int y) {
>> >> 		if (y == 0)
>> >> 			return x;
>> >> 		return gcd(y, (x % y));
>> >> 	}

>> >This is an interesting case, because it is somewhat inefficently
>> >implemented.  If you're interested in speed, you would do...

>> >int gcd(int x, int y) {
>> >    int z;
>> >    while (y != 0)
>> >        z = y; y = x % y; x = z;
>> >    return(y);
>> >}

>> Yes, you would.  But so would at least one compiler I use.  Internally.

>Which compiler is that?  I would like to see the compiler that
>unravels recursion into non-recursive algorithms.

gcc handles trivial tail recursion, or so we're told.

>> >Using my AIX compiler, I get a nominal improvement of about
>> >10%, mostly because the speed of the modulo is much slower
>> >than the inefficiency of recursion.

>> What numbers are students entering that we *CARE* about the 10% speed
>> difference?  Optimization is an interesting thing to look at, but has
>> nothing to do with algorithms.

>That is ivory tower insanity!  :)

It is also the essense of learning the difference between algorithm and
implementation, which are very different arts.

>It has *everthing* to do with algorithms.  You showed me a recursive
>algorithm, I rewrote it to be faster.  The fact that in this case
>it's only 10% is irrelevent; for another algorithm it could have
>been much more (compare recursive v.s. non-recursive quicksort).

>I consider a recursive solution to be a different algorithm than a
>non-recursive one, although I realize that is arguably an
>implementation issue.

For the greatest common divisor, it certainly is.  It's like realizing
that you can say "a %= b" instead of "while (a > b) a -= b;".  It doesn't
change the *meaning*, only the representation.

>Not teaching students about optimization is why we have such
>a code-bloat problem right now.  They think there is no difference
>by coding something.

That doesn't make them identical fields of study.  Algorithms and
optimization are two different things.

>Big deal, one compiler does it, and I would like to see how
>it handles more complex cases.  The point is that in the
>real world, these issues make big differences.

Then real-world programmers will, rather than guessing about what compilers
are and aren't smart enough to do, try several implementations and benchmark
them.

>> Microoptimizing will not fix it.  Teaching people about *real* design
>> principles will.

>What "real" design principles are you referring to?

The basic questions of what data types to use to represent your model, and
what model to use to represent your problem.  If I design a word processor
as a set of operations, each of which is always done in sequence, I may end
up with a loop like
	while (1) {
		update_menu();
		update_display();
		update_cursor();
		...
		process_last_command();
		get_command();
	}

in which each command is processed by setting flags, which each of the various
update functions reacts to.  For instance, when I select "bold", the function
which redraws the entire display every time through the loop gets a flag set
to embolden something.

You could make your display algorithm take less than 1% of the time a "normal"
one would, and this program will *still* suck.

>If every algorithm is written efficiently and correctly, the
>cumulative effect is a well written product.

Unless the basic design is fundementally flawed.

Lest you say that the above is too stupid to be imagined, let's remember how
much harder good design gets as the goals get larger and more complicated.

Further, I have seen *an actual commercial product* whose inner loop is
essentially a large set of nested switch statements to process the cursor
location in terms of which menus are active.  An actual reported bug, since
fixed, was that moving the mouse over a certain button *without clicking on
it* inserted text if you had previously selected a certain other button.

The person who designed that *didn't* design it, and no amount of improvement
in the "efficiency" will ever correct that.

>Agreed.  But a bad implementation of a good design will destroy
>a product just as easily.

I don't think so.  It'll be easier to correct, for once.

>Agreed.  That's why I think that starting out implementing
>algorithms so that they inherently see the flow of the data
>helps to understand these issues.  If you're doing quicksort,
>*data moves* no matter what the architecture is, and the more
>movement, the less efficiency.

Perhaps; however, counting move instructions in the code won't show you how
much the data moves.  A "good" bubblesort may easily have fewer moves.

>If I implemented Quicksort in APL, say (which has direct
>manipulation of arrays in one operation), the student would
>not see the movement, because they would just see the computer
>doing the array "in one fell swoop", but wouldn't really
>experience the fact that the computer doesn't really do it
>that way in reality.

So talk to them about it.  Take the opportunity to clarify something about
APL.

>But why do you look to eliminate recursion in the expensive case?
>It is part of the C standard, it is perfectly valid C syntax.

Because my experience has shown that, often, it produces slow code, and
I can produce better results iteratively.  But I don't worry about speed until
I've shown that my design is functional.

-s
-- 
Peter Seebach - seebs@solon.com - Copyright 1996 - http://www.solon.com/~seebs
Unix/C Wizard - send mail for help, or send money for consulting!
The *other* C FAQ, the hacker FAQ, et al.  See web page above.
Unsolicited email (junk mail and ads) is unwelcome, and will be billed for.