Safe optimization

[T. William Wells]

In article <16271 at brl-adm.ARPA>, dsill at nswc-oas.arpa (Dave Sill) writes:
> "T. William Wells" <bill at proxftl.uucp> writes:
> >In article <14522 at brl-adm.ARPA>, dsill at nswc-oas.arpa (Dave Sill) writes:
> >> You are implying that programmers can solve unsolvable problems but
> >> that programs cannot, which is simply not true.
> >
> >Actually, you should keep your referents straight.  I might be
> >implying that humans can solve problems that are unsolvable by
> >COMPUTERS.  The truth of that is a matter of conjecture.
>
> You're absolutely right.  I *have* been assuming that the
> computational power of the human brain is subject to the Church-Turing
> Thesis.  I have no reason to believe that that is an incorrect
> assumption.

Well, since we are bandying about concepts without any real
reference to reality, let me toss this possible reason at you:
computers are discrete devices, the brain is (or at least might
be) a continuous device.  It is undecidable whether aleph-1 (the
cardinal for the power set of the integers, here representing
discrete systems) is equal to c (the cardinal for real numbers
here representing real systems). This suggests that there is a
fundamental difference between these two systems, and that
difference might be reflected in the possibilities open to
digital machines and brains. Anyway, this is empty vaporing and
besides the point, so lets not beat it to death.

> Yes, we've been through all this before.  Your example is exactly the
> kind of thing I've been preaching against.  It is too likely that
> somebody will port such code to a system where the same assumptions
> aren't true.

I think you completely missed the point. Were I to write such a
program, it would be a property of the system the program was in
that the two inputs could NOT be the same; were they the same,
the whole system would be broken. To make this concrete, suppose
that these numbers represented a node and its parent in a tree.
In this case there are two possibilities: the program feeding
the data works, in which case the data read is valid and
everything is OK, or the program feeding the data is broken and
the system fails, regardless of what the compiler is doing.
Porting has nothing to do with it.

>               And without something in the code stronger than a
> comment like "/* of course i can never equal j */", a bug will be
> silently introduced.

The comment is going to be something more like: /* i is the
parent node and j is the child node. */. Actually, the variable
names would be chosen to reflect this.

In the rest of your article you suggest (as others have) the use
of assert() to accomplish what noalias does. Given the problems
with noalias (among other things, the difficulty of understanding
exactly what it does), I would prefer your macro to noalias; but
it does have the drawback, as others have noted, of not being
able deal properly with the real problem: pointers.

Here is why:

	char    *p1;
	char    *p2;

	if (p1 < p2) ...

is not portable unless the two pointers point within the same
object, a condition which is often not the case when one is
trying to specify that the two pointers do not alias.  An assert
macro is going to have to generate comparisons like this to say
that the two pointers are not aliased.

I hope that there will be no further discussion on the noalias
keyword; it is moot since it is gone from the standard.
Sometime in the distant future, when we have given the alias
problem some real thought, perhaps we will come up with a
solution to the problem that does not require clairvoyant
compilers or supergenius programmers. Until that time, let's not
debate irrelevant stuff about aliasing.