What is a type error?

[Chris Smith]

Marshall <marshall.spight at gmail.com> wrote:
> Is it possible you're being distracted by the syntax? WHERE is a
> binary operation taking a relation and a filter function. I don't
> think of filters as being like array indexing; do they appear
> analogous to you? (Always a difficult question because often
> times A and B share some qualities and not others, and
> what does one call that?)

This is definitely a good question.  Nevertheless, I think we're fooling 
ourselves if we decide that we've made progress by defining part of the 
problem out of existence.  The original problem was that when there are 
several ways of getting access to something that is identical (rather 
than just equal), this causes problems for invariant checking.  These 
several ways of accessing data are being called 'aliasing' -- I have no 
comment on whether that's standard usage or not, because I don't know.  
I suspect that aliasing is normally used for something closer to the 
physical level.  The point is that whatever "aliasing" really means, 
what we're discussing is having two paths by which one may access 
identical data.

So there are infinitely complex ways in which this can occur.  I can 
have pointers that are aliased.  I can have integers, which by 
themselves are just plain values, but can alias each other as indices 
into an array.  I can have strings that do the same thing for an 
associative array.  I can, of course, have arbitrarily more complex data 
structures with exactly the same issue.  I can also have two different 
WHERE clauses, which when applied to the same relation yield exactly the 
same set of tuples.  The problem arises when code is written to update 
some value (or set of tuples, in the SQL case, since definitions differ 
there) using one pointer/int/string/WHERE clause/etc, and at the same 
time an invariant was written using the other pointer/int/WHERE/etc, the 
result is that either of:

a) The compiler has to be able to prove that the two are not aliased

b) The compiler has to re-evaluate the invariant from scratch when this 
operation is performed.

(Yeah, there's actually a whole continuum between a and b, based on more 
limited abilities of the compiler to prove things.  I'm oversimplifying, 
and I think it's rather benign in this case.)

So in this sense, a WHERE clause is a binary operation in exactly the 
same way that an array indexing expression is a binary operation, and 
both are capable of aliasing in at least this logical sense.

Now it's certainly true that languages with unrestricted pointers are 
less successful at limiting the scope of re-evaluation of invariants.  
In the array or SQL relation cases, there's a limited set of value/tuple 
modifications that might cause the invariant to need rechecking 
(specifically those that point to the same array, or to the relation or 
one of its views).  A language with unrestricted untyped pointers, if it 
doesn't get lucky with the capture analysis, may have to re-evaluate all 
invariants in the application on any given assignment.  Nevertheless, 
the re-evaluation of the invariant still needs to be done.

-- 
Chris Smith - Lead Software Developer /Technical Trainer
MindIQ Corporation