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

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

Joe Keane <jgk@jgk.org> writes:
>That's just bad code.  It specifies a *quadratic* algorithm for a very
>simple operation.  My impression would be that the coder doesn't
>understand some basic things about C programming, or they're just
>inconsiderate.  How hard is it to put the length in a variable?

Perhaps we have different perspectives.
Would a *professional* programmer produce code like that?
No way!

Would it be "bad" if a 3rd semester student produced it?
In my view, no way!

At the moment, I'm bogged down in marking.  Last semester, when the
students were in their 3rd semester, using C, I would have wept for
joy to see code that good.  This semester, now they have had another
semester under their belts, and understand something about big-Oh,
I would expect better code.  In fact, to my joy I *am* seeing better
code, much better code.  But the students are writing Ada this
semester, and I find that our students *do* write much better Ada
than they do C.

>It's a basic fact that, in the idiomatic `for' loop, the test is
>evaluated every time through the loop.

You have forgotten the "as if" rule.
The outcome of the program must be the same AS IF the expression had
been evaluated every time, but when part of an expression manifestly
does not change, the compiler is under no obligation to re-evaluate it.

>If the upper bound is fixed,
>it's really good practice to put it in a local variable.

We *agree* that a *professional* programmer, if using a language in which
the _only_ for-loop is like C's (which I am not knocking; I use "do" in
Lisp and Scheme all the time, and it's like C's "for" only better), would
arrange it cheaply.  By the way, a *professional* C programmer would not
call strlen() at all in such an example.

But coming from an educational perspective, I am unwilling to call
*clear*, *correct* code "stupid", or even "bad".  A student who is
capable of writing code that _good_ is one we can help to improve.

>>The ONLY strlen() optimisation that is needed here
>>is one that is completely general:  strlen() is a pure function and its
>>argument does not change, so the strlen(s) computation can be hoisted out
>>of the loop.

>It's not a pure function.  Whether the argument changes isn't the point;
>it's a local variable and it's clear to everyone that it's not changed.

In the article you quote, I explained that by "argument" I meant the
NTBS that the actual parameter points to, AND IN THIS EXAMPLE THAT
NTBS DOES NOT CHANGE, and that *IS* the point.

>Really.  I expect an optimizing compiler to do a decent job of low-level
>things, such as allocating registers, selecting instructions, scheduling
>instructions, and so on.  If optimization is turned off, the code will
>get slower, maybe two to five times, but a constant factor.

>I don't expect the compiler to work miracles, to turn crap into gold.
>That would include changing a quadratic algorithm to a linear one.  Some
>people may think that it's nifty, but i think it's just a bit disturbing
>and i'd rather have compiler writers concentrate on compiling good code.

Again, we have obviously have different perspectives.
I have one foot in the "declarative programming" community (and if you
think Haskell and Mercury are esoteric, think "SQL" which has _exactly_
the same kinds of optimisation requirements and opportunities).
For example, there is a well-known transformation which routinely
turns a class of algorithms with exponential cost if taken naively
into implementations with polynomial cost.

Do I have to explain that the strlen() optimisation is one that has been
legal for Fortran compilers since the first Fortran standard?  Or that
strlen() is a C library function, and that the C standard very carefully
allows a compiler to take advantage of special knowledge about library
functions?

>You can't blow off a level of indirection so easily.

"Blow off" iks rather offensive language.
The NTBS that the pointer pointers to does not change.
True, that is "a level of indirection", but I *explained* how that
can be handled.

>>In the program fragment under discussion, it was not merely the pointer
>>that was constant, but the NTBS itself.

>I think that you misunderstand the `const' keyword.

Bullshit.  I said nothing about the 'const' keyword.
I said that the pointer and the NTBS were *constant*.
That doesn't mean they are declared "read-only".
It means THEY DIDN'T CHANGE.  That's all.
I defy anyone to show where the pointer or the NTBS changed in my
example.  I didn't mention the 'const' keyword because it wasn't relevant.

>>If I do
>>	n = strlen(s);
>>	/* much code that does not change s */
>>	/* NOT the NTBS that s refers to */
>>	m = strlen(s);
>>it is necessarily the case that m and n will be the same size_t value.

>I'm unclear on that comment, but if there are pointer stores in there,
>the length may be changed, even if `s' isn't changed.

The comment (which should have read NOR, not NOT) *says* there are no
such stores.  You are like someone who is told

	"There are no dinosaurs in this room."

and replies

	"I'm unclear on that remark, but if there are any dinosaurs
	 in this room, one of them is about to bite your head off."

>In your example, it is possible.  But it's based on a lot of assumptions
>and it's not something you should depend on.

You have mistaken just about everything I was trying to say.
I suppose this must be my fault.
I *did* say explicitly that *I* know why naive compilers generate
costly code for this, and that it is not something that I would myself
write.  I have been using C since V6+ UNIX, and have had to live with
naive C compilers for years.

>In many similar examples,
>the compiler *must not* remove the duplicated calls.

Yes, but we aren't *talking* about similar examples.  Again, you are
shifting the argument to attack a position I am not stating or defending.
The strlen() example is a very very specific one; it is *ONLY* in the
specific case of strlen() and *ONLY* in the specific case where the
NTBS is not changing that C suckers students into writing

	for (i = 0; i < strlen(s); i++) ... process s[i] ...

All I am claiming, all I have ever claimed, is that a beginner who
writes *that* code to iterative over an unchanging NTBS is not
writing "stupid" or "bad" code, merely code which is _inefficient_
under _some_ C compilers (admittedly the majority of them).

I refuse to call clear correct *working* *readable* code "stupid"
or "bad".  That doesn't mean I am going to slobber over the author
with praise, or that I am not going to put a fair bit of red ink
on such an assignment.  It just means I'm not going to call such a
student nasty names, and am going to take it as an encouraging sign
that the student has learned how to do some important things _well_.

-- 
Australian citizen since 14 August 1996.  *Now* I can vote the xxxs out!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.