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

[kaz@vision.crest.nt.com (Kaz Kylheku)]

In article <slrn523tpg.ce.mdw@excessus.demon.co.uk>,
Mark Wooding <mdw@excessus.demon.co.uk> wrote:

>Erk!  No it isn't.  A pure function is one whose value depends only on
>its arguments.  sin() is pure.  strlen() isn't.
>
>The argument to strlen() is a pointer to a string whose length we want.
>It's the address, not the string itself.  Because the string can change
>between calls to strlen(), it might give different results given the
>same string address.  So the compiler can't just use its general `pure'
>function mechanism for common-subexpression-optimising strlen()

So what, the value of X can change in between calls to sin(X) just the same way.

The strlen() call can indeed be eliminated via CSE. It has no side effects,
and its result depends only on the object being passed to it.

The value of strlen() can be readily reused if no pointer was dereferenced for
the purposes of storing a value since the last time strlen() was called with
the same subexpression, and if no constituent of the subexpression has
changed.

>Now, can a compiler do clever things and optimise strlen() all by
>itself?  You comment that it might spot assignments to the string.  This
>is true, but not all such assignments are visible to the compiler.  For

Yes they are all visible. The compiler can readily decide whether the
expression which is an argument to strlen() _could_ have changed by looking
at the statements that have occured since the invocation of strlen. There are
well known techniques for doing CSE in conjunction with pointers. The most
pessimistic approach will invalidate the register-cached results of all prior
expressions when a pointer has been dereferenced. From this assumption, you
can make finer adjustments. For example, you can deduce that if a pointer
was explicitly assigned to a particular object, only that object can be
modified via that pointer. That's because the rules of C state that pointer
arithmetic is not allowed to take a pointer outside of the object it is
pointed to (with the exception of pointing one element past the end of an
array, in which case a dereference is illegal so it amounts to the same thing
from the optimizer's point of view). Thus when a pointer is dereferenced,
and thanks to careful analysis you know that it cannot affect any constituent
objects named the subexprssion that was previously passed to strlen(), you can
safely use the register copy of that previous result (given that all the
other requirements for eliminating the subexpression have been met, of
course).

>automatic buffers, this /is/ true, but (in my experience) calls to
>strlen() and similar functions are comparitively rarerely used on
>locally allocated buffers.  If the buffer is not local to the function,
>there's no guarantee that (in an extreme case) its address hasn't been
>made available to a signal handler which maliciously changes the
>string's length.
>
>Prove me wrong.

That's easy: if you modify the data in the signal handler, you are violating
the rules for writing a conforming C program. Read what the C standard has to
say about signal handlers and global variables! 

The buffer could be modified by a function call, but in that case, you can do
the same invalidation as you would for a pointer dereference.

One pesky problem are pointers that are never explicitly initialized in the
function, but are obtained as parameters. These can potentially refer to
anything that is not local to the function, and the objects they point to can
overlap. Here is where languages with more powerful parameter passing
techniques and stronger typing have a win over C.