What is a type error?

[Marshall]

Chris Smith wrote:
> Marshall <marshall.spight at gmail.com> wrote:
> > > If the relations are to
> > > be considered opaque, then there's clearly no aliasing going on.
> >
> > Not certain I understand, but I think I agree.
>
> My condition, though, was that relations be opaque.  Since you will be
> violating that condition further on down, I just felt that it's useful
> to point that out here.
>
> > No, such a language is entirely useful, since relational assignment
> > is *more* expressive than insert/update/delete.
>
> Assignment is more powerful *as* assignment.  However, it is less
> powerful when the task at hand is deriving new relations from old ones.

At the implementation level, it makes some things harder, however
as a logical model, it is more powerful. While this is very much a real
world issue, it is worth noting that it is a performance issue *merely*
and not a semantic issue.


> Assignment provides absolutely no tools for doing that.  I thought you
> were trying to remove those tools from the language entirely in order to
> remove the corresponding aliasing problems.  I guess I was wrong, since
> you make it clear below that you intend to keep at least basic set
> operations on relations in your hypothetical language.
>
> > Consider:
> >
> > i := i + 1;
> >
> > Note that the new value of i didn't just appear out of thin air; it was
> > in fact based on the previous value of i.
>
> Right.  That's exactly the kind of thing I thought you were trying to
> avoid.

I was under the impression tat Joachim, for example, did not
consider "i+1" as an alias for i.


> > So we can define insert, update and delete in terms of relational
> > assignment, relational subtraction, and relational union. Type
> > checking details omitted.
>
> Then the problem is in the step where you assign the new relation to the
> old relational variable.  You need to check that the new relation
> conforms to the invariants that are expressed on that relational
> variable.  If you model this as assignment of relations (or relation
> values... I'm unclear on the terminology at this point) then naively
> this requires scanning through an entire set of relations in the
> constraint, to verify that the invariant holds.  You've may have avoided
> "aliasing" in any conventional sense of the word by stretching the word
> itself beyond breaking... but you've only done it by proactively
> accepting its negative consequences.
>
> It remains non-trivial to scan through a 2 GB database table to verify
> that some attribute of every tuple matches some attribute of another
> table, even if you call the entire thing one relational variable.  The
> implementation, of course, isn't at all going to make a copy of the
> entire (possibly several GB) relation and rewrite it all every time it
> makes a change, and it isn't going to give up and rescan all possible
> invariants every time every change is made.  In other words, you've
> risen to a layer of abstraction where the aliasing problem does not
> exist.  The implementation is still going to deal with the aliasing
> problem, which will resurface once you pass over to the other side of
> the abstraction boundary.

Yes, these *performance* issues make assignment prohibitive for
real-world use, at least if we are talking about data management
in the large. This is not the same thing as saying the resulting
language is a toy language, though; its semantics are quite
interesting and possibly a better choice for *defining* the semantics
of the imperative operations than directly modelling the imperative
operations. (Or maybe not.) In any event, it's worth thinking about,
even if performance considerations make it not worth implementing.


Marshall