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

[clodius@hotspec.lanl.gov (William Clodius)]

In article <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> "Tim
Behrendsen" <tim@airshields.com> writes: 

   Peter Seebach <seebs@solutions.solon.com> wrote in article
   <4uah1k$b2o@solutions.solon.com>...
<snip>
   > 
   > 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.

Show me an algorithm, not an implementation of an algorithm, that uses
moves and branches. Your phrasing has been poor on this thread. When
you say you want students to learn algorithms you seem to be really
saying you want students to learn how to implement a given algorithm
efficiently. They are typically two different things. The proper
algorithm can save orders of magnitude in runtime, the proper
implementation smaller, but sometimes important, factors of two or
three. 

   > Something like CWEB might be a good language in which to learn
   algorithms.
   > Scheme might too.
   > 
   > Let's look at a specific algorithm; the infamous gcd(x, y).
   > 
   > In C, we write
   > 
   > 	int
   > 	gcd(int x, int y) {
   > 		if (y == 0)
   > 			return x;
   > 		return gcd(y, (x % y));
   > 	}
   > 
   > or something similar.
   > 
   > What's important here is not any theories people may have about where the
   x
   > and y are stored, or how a stack works, but the concept that you can
   define an
   > algorithm in terms of a previous case.  Learning that the if() may be
   > implemented with "a branch" does not help the student understand how the
   > *algorithm* works, it helps the student understand how the *compiler*
   works.
   > These are distinct things.

   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);
   }

   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.

   My point is that how does a C programmer know that recursive
   implementations are somewhat inefficient?  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.

Actually the efficiency of Peter's implementation depends on the
optimizing capability of the compiler. Many compilers recognize his
example as employing tail recursion and eliminate the recursion by
replacing the recursive calls with the appropriate iterations. This
capability is required for Scheme compilers for example. Did you try
full optimization on your AIX compiler? There are of course problems
for which recursive algorithms can not employ such an obviously
optimizable construction. 

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

Are there really significant differences in the resulting code sizes?
Myself, I believe that code bloat is primarilly due to feature bloat,
and old programs that are not completely rewritten to remove unneeded
code.

   > >If programming is reduced to fundamentals of move, arithmetic,
   > >test, branch, etc it prevents the student from leaning on the
   > >abstraction rather than truly understanding the solution to the
   > >problem.  In other words, if they can express it in the above
   > >terms, you *know* they understand the solution.
   > 
   > 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).

Sounds good to me, but J, NIAL, or NESL might be better. Or a higher
order language such as Scheme or Clean.

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

They have the chance to implement Heapsort, and Insertion and find out
how all three scale with problem size and character. (Let them run a
simple heapsort on a previously sorted array, or a large number of
small arrays.)

   [snip]
   > 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?

Wasn't it Knuth who said something like, "Premature optimization is
the root of all evil"? We should write code that, to the greatest
extent possible is self explanatory, does the job that is needed, and
where computationally intensive parts of the code are expected, an
appropriately chosen algorithm. Then if testing shows a performance
problem, identify the problem routines and clean them up.

<snip>

Followups directed to comp.edu
-- 

William B. Clodius		Phone: (505)-665-9370
Los Alamos National Laboratory	Email: wclodius@lanl.gov
Los Alamos, NM 87545