What is a type error?

[Chris F Clark]

Joachim Durchholz wrote:
 >
 > You can have aliasing without pointers; e.g. arrays are fully sufficient.
 > If i = j, then a [i] and a [j] are aliases of the same object.

"Marshall" <marshall.spight at gmail.com> writes:

> I am having a hard time with this very broad definition of aliasing.
> Would we also say that a[1+1] and a[2] are aliases? It seems
> to me, above, that we have only a, and with only one variable
> there can be no aliasing.

As you can see from the replies, all these things which you do not
consider aliasing are considered aliasing (by most everyone else, in
fact these are exactly what is meant by aliasing).  There is good
reason for this.  Let us explain this by looking again at the SQL
example that has been kicked around some.

>>    SELECT * FROM persons WHERE name = "John"
>> and
>>    SELECT * FROM persons WHERE surname = "Doe"

Some set of records are shared by both select clauses.  Those records
are the aliased records.  If the set is empty there is no problem.  If
we do not update the records from one of the select clauses, we also
have no problem.  However, if we update the records for one of the
select clauses and the set of aliased records is not empty, the
records returned by the other select clause have changed.  Therefore,
everything we knew to be true about the "other" select clause may or
may not still be true.  It's the may not case we are worried about.

For example, in the "imperative Mi-5" Q asks Moneypenny to run the
first query (name = John) to get a list of agents for infiltrating
Spectre.  In another department, they're doing sexual reassignments
and updating the database with the second query (surname = Doe) and
making the name become Jane (along with other changes to make the
transformation correct).  So, when Q select "John Doe" from the first
list and sends that agent on a mission Q is really sending "Jane Doe"
and Spectre realizes that the agent is one and kills her.  Not a happy
result.

In the "functional Mi-5", the sexual reassignment group, makes clones
of the agents reassigned, so that there is now both a "John Doe" and a
"Jane Doe".  Of course, the payroll is a little more bloated, so that
when Q says "John Doe" isn't needed for any further assignments, the
"Garbage Collection" department does a reduction in force and gets rid
of "John Doe".  The good news is that they didn't send Jane Doe to her
death.

The problem with aliasing, we want the things we knew true in one part
of our program, i.e. the Johns on Q's list are still Johns and not
Janes, to be true after we've run another part of our program.  If the
second part of our program can change what was true after the first
part of our program, we can't depend on the results from the first
part of our program, i.e. Q can send Jane Doe into certain death.

The problem is compounded by the complexities of our programs.  When Q
selected his list, he didn't know of the department doing the
reassignments (and couldn't know because they were part of a
top-secret project).  So, since bureaucracies grow to meet the
increasing needs of the bureaucracy, often the solution is increased
complexity, more regulations and paperwork to fill out, semaphores and
locks to hold on critical data, read-only data, status requests, etc.
All to keep Q from killing Jane by accident.  Sometimes they work. the
reassignment department has to wait 30-days for the clearance to
perform their operation in which time John Doe completes the
infiltration of Spectre saves the world from destruction and is ready
for his next assignment.

The key point is that each record (and even each field in each record)
if it can be known by two names, is an alias.  It is not sufficient to
talk about "whole" variables as not being aliased if there is some way
to refer to some part of the variable and change that part of the
variable.  Thus, a[1+1] is an alias for a[2] if you can have one part
of the code talking about one and another part of the code talking
about the other.

To put it one still final way, consider the following code;
        assert(sorted(array a));
        a[1] = 2;
        assert(sorted(array a)); // is this still true?

Because a[1] is an alias of array a, you cannot be certain that the
2nd assert will not fire (fail) without additional analysis.

        assert(sorted(array a));
        assert(a[0] <= 2);
        assert(2 <= a[2]);
        a[1] = 2;
        assert(sorted(array a)); // this is still true!

-Chris