From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: clodius@hotspec.lanl.gov (William Clodius) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/08/08 Message-ID: X-Deja-AN: 173012034 sender: clodius@hotspec.lanl.gov references: <31FBC584.4188@ivic.qc.ca> followup-to: comp.edu organization: Los Alamos National Laboratory newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-08T00:00:00+00:00 List-Id: In article <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> "Tim Behrendsen" writes: Peter Seebach wrote in article <4uah1k$b2o@solutions.solon.com>... > > 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. Followups directed to comp.edu -- William B. Clodius Phone: (505)-665-9370 Los Alamos National Laboratory Email: wclodius@lanl.gov Los Alamos, NM 87545