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

["Tim Behrendsen" <tim@airshields.com>]

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

That is ivory tower insanity!  :)

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.

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.

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

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.

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

What "real" design principles are you referring to?

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

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

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

> >The student learns Quicksort [in APL], 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.

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.

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.

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

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.

-- Tim Behrendsen (tim@airshields.com)