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 <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>,
Tim Behrendsen <tim@airshields.com> wrote:
>> But your concept of what the "fundemental operations" are is completely
>tied
>> up in how specific hardware you've seen operates.  Algorithms exist in
>terms
>> of abstract operations, not moves and branches.

>Please name me the hardware that does not use moves and branches.

That's not the *point*.  Can you name me hardware with no protons?  Can you
name me hardware students are likely to learn on that doesn't use 5 volt
power on the chip?

However, the algorithm is *NOT DEPENDANT ON* moves and branches.  I can
do quicksort.  In my head.  On paper.  I can sit down, with a pencil, and
implement quicksort.  You can say "these operations correspond to moves and
branches", but really, moves and branches are corresponding to more general
operations.  If you teach the students that it's all moves and branches, they
end up with more understanding of the specific hardware you teach them on, and
current trends in CPU design, *and less of the algorithm*.

I think algorithms should be taught on paper.  *Away* from implementations
on computer.

Believe me, you understand quicksort much better after *DOING* it than you
can from writing any reasonable number of implementations.

>> 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.

It doesn't *matter*.  The realization is that, for non-zero x and y, the
greatest common divisor of x and y is conveniently the greatest common
divisor of y and (x mod y).  *THAT* is the algorithm.  The rest is fluff
and nonsense.  You can do that operation on paper, too.

>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.

So?

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.

>My point is that how does a C programmer know that recursive
>implementations are somewhat inefficient?

The C programmer doesn't.  And at least one compiler has been known
to optimize tail-recursion into iteration, sometimes even in the 2-function
case.

>Recently the C/C++
>Users Journal had a little bite-sized article about a
>general looping algorithm, where you could specify the number
>of nested loops in a dynamic fashion.  It was implemented
>recursively.  I wrote a letter back reimplementing the
>algorithm non-recursively, and got like a 40% increase in
>speed.

Neat.  And?  The key here is that, once they showed you *the algorithm*, you
could implement it however you want.  The algorithm itself does not depend on
your speed.

>These sorts of issues are where code bloat comes from, and
>it comes from naive implementations of "valid C syntax".

No, they aren't.  All of those put together wouldn't explain code bloat.

We are seeing programs that are a factor of ten, or more, larger than we think
they are.  These would have to be *mind-numbing* idiocy.

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

It's worth observing good programmers rewriting.  A good programmer will
add features and cut the size of a program slightly; a bad programmer will
bloat it hugely to add the feature.  (Assuming the original program to be
mediocre.)

A good design will save more space and time than any amount of optimization of
a bad design.

>> But it also prevents them from learning the abstraction, and truly
>> understanding the *principle* of the solution.

>If the C abstraction is good, more abstraction must be better
>then.  How about we teach everything in APL, where we can
>*really* abstract away the details?  No data types, full
>array operations.  Talk about easy quicksort!  I can write it
>in one line of code using a handful of operations (my APL
>is *really* rusty, so I can't give the example).

I sorta favor lisp, which I don't know, but which is elegant and readable.

>The student learns Quicksort, there is no question about it.
>But what have they *really* learned?

They've learned the algorithm itself.  If you want to teach them about
optimization and efficiency, go right ahead, but distinguish O(n) vs O(N^2)
type efficiency from the kinds of efficiency you're talking about.

Remember, that O() includes arbitrary constant multipliers and additions.
8N is just the same as N in complexity.

I think it's a cool idea to teach people how to turn an 8N into a 4N
algorithm.  I don't think it's part of the algorithm, I think it's a different
thing.

>> Nonsense.  A well designed and considered abstraction will generally lend
>> itself to an efficient and elegant implementation.  An ill-considered
>> abstraction will spend more time on cruft than it will on solving the
>problem.

>Like recursive algorithms?

I'm not sure what you're referring back to.  Recursion is one of the first
things I look to eliminate if I have an expensive implementation of what I
know to be a good algorithm.  But if the cost is small, it tends to stay,
because it's frequently obvious how it's supposed to work.

>Agreed; but there are general principles that can be learned
>across *all* architectures.  See follow up to Dan Pop post for
>example of this.

Sure, there are.  And these, I think, can reasonably be taught.  But that
teaching doesn't need any assembly.

-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.