What is a type error?

[Joachim Durchholz]

Marshall schrieb:
> No. The variable is the table, not the records.

In your examples, yes.

 > Relations are not arrays.

They are, in all ways that matter for aliasing:
They are a collection of mutable data, accessible via selector values.

> Records are not lvalues.

Agreed, but they have identity. An lvalue is an identity that you can 
track in software; record identity is untrackable in standard SQL, but 
it's real enough to create aliasing problems.

> I would propose that variables have identity, and values do not.

What's a "variable", by that definition?
It can't be "something that has a name in a program", since that would 
exclude variables on the heap.
Another definition would be "something that may have a different value 
if I look at it sometime later", but then that would include SQL records 
as well. Besides, the temporal aspect is problematic, since it's unclear 
whether the "it" some time later is still the same as the "it" before 
(if you have a copying garbage collector, you'd have to somehow 
establish identity over time, and we're full circle back at defining 
identity).

Personally, I say "two things are identical / have the same identity", 
if they are (a) equal and (b) stay equal after changing just one of 
them. That's a nice local definition, and captures exactly those cases 
where aliasing is relevant in the first place (it's actually that 
"changing here also changes there" aspect that makes aliasing so dangerous).
It also covers SQL records. Well, they do have aliasing problems, or 
problems that are similar enough to them, so I'd say this is a 
surprising but actually interesting and useful result of having that 
definition.

> In part this is via the supplied definition of identity, in which, when
> you change one thing, if something else changes as well, they
> share identity. Since one cannot change values, they necessarily
> lack identity.

I agree that immutable values don't have identity (or, rather, that 
identity isn't an interesting concept for them since it's already 
subsumed under equality).

>> It's certainly not storage location:
>> if you DELETE a record and then INSERT it with the same values, it may
>> be allocated somewhere entirely else, and our intuition would say it's
>> not "the same" (i.e. not identical).
> 
> Well, it would depend on how our intuition had been primed. If it
> was via implementation techniques in low level languages, we
> might reach a different conclusion than if our intuition was primed
> via logical models and relation theory.

Sure.

However, since I'm interested in practical consequences for programming, 
I'm looking for definitions that allow me to capture those effects that 
create bugs.
In the case of identity, I'd say that's aliasing.

>> Since intuition gives me ambivalent results here, I'll go back to my
>> semiformal definition (and take the opportunity to make it a bit more
>> precise):
>> Two path expressions (lvalues, ...) are aliases if and only if the
>> referred-to values compare equal, and if they stay equal after applying
>> any operation to the referred-to value through either of the path
>> expressions.
> 
> Alas, this leaves me confused. I don't see how a path expression
> (in this case, SELECT ... WHERE) can be an l-value. You cannot
> apply imperative operations to the result.

It's not SELECT...WHERE..., it's WHERE... that's an lvalue.
And you can indeed use it with UPDATE, so yes it's an lvalue by my book. 
(A given WHERE clause may become invalid or refer to a different record 
after some updates, so it's not the kind of lvalue that you have in a C 
program.)

 > (Also I think the use
> of equality here is too narrow; it is only necessary to show that
> two things both change, not that they change in the same way.)

Sorry for using misleading terminology.
An "alias" is when two names refer to an identical object (both in real 
life and IMHO in programming), and that's what I wrote.
"Aliasing" is the kind of problems that you describe.

> I was under the impression you agred that "i+2" was not
> a "path expression".

Yes, but [i+2] is one.

In the same vein, "name = 'John'" is an expression, "WHERE name = 
'John'" is a path expression.

 > If our hypothetical language lacks record
> identity, then I would say that any query is simply an expression
> that returns a value, as in "i+2."

As long as the data is immutable, yes.
The question is how equality behaves under mutation.

>> On the other hand, variable addresses as tangible identities don't hold
>> much water anyway.
>> Imagine data that's written out to disk at program end, and read back
>> in. Further imagine that while the data is read into main memory,
>> there's a mechanism that redirects all further reads and writes to the
>> file into the read-in copy in memory, i.e. whenever any program changes
>> the data, all other programs see the change, too.
>> Alternatively, think about software agents that move from machine to
>> machine, carrying their data with them. They might be communicating with
>> each other, so they need some means of establishing identity
>> ("addressing") the memory buffers that they use for communication.
> 
> These are exactly why content-based addressing is so important.
> Location addressing depends on an address space, and this
> concept does not distribute well.

I think that's an overgeneralization. URLs have distributed well in the 
past.

>>  > I don't know what "new" would be in a value-semantics, relational
>>> world.
>> It would be INSERT.
>>
>> Um, my idea of "value semantics" is associated with immutable values.
>> SQL with INSERT/DELETE/UPDATE certainly doesn't match that definition.
> 
> Sorry, I was vague. Compare, in OOP, the difference between a value
> object and a "regular" object.

Yes, one if mutable, the other is not.
I'm not sure how that relates to SQL though.

>>>> Filters are just like array indexing: both select a subset of variables
>>>> from a collection.
>>> I can't agree with this wording. A filter produces a collection
>>> value from a collection value. I don't see how variables
>>> enter in to it.
>> A collection can consist of values or variables.
>>
>> And yes, I do think that WHERE is a selection over a bunch of variables
>> - you can update records after all, so they are variables! They don't
>> have a name, at least none which is guaranteed to be constant over their
>> lifetime, but they can be mutated!
> 
> We seem to have slipped back from the hypothetical relation language
> with only assignement back to SQL.

This all started with your claim that SQL does not have identities and 
aliasing problems, which grew out of a discussion of what identities and 
aliases and aliasing really are.
Hypothetical relation languages are interesting to illustrate fine 
points, but they don't help with that.

Anyway, if a hypothetical relational language is what you wish to 
discuss, let me return to an even more general model: I'm pretty sure 
that any language that has
a) collections
b) means of addressing individual items
c) means of changing individiual items
has aliasing problems, and that the indidual items have identity.

(Actually all programming languages with mutation and any kind of 
reference fit that description: the "collection" is the pool of 
variables, the "means of addressing" is the references, and "means of 
changing" is the mutation.)

>>  > One can filter either a collection constant or
>>> a collection variable; if one speaks of filtering a collection
>>> variable, on is really speaking of filtering the collection value
>>> that the variable currently contains; filtering is not an operation
>>> on the variable as such, the way the "address of" operator is.
>>> Note you can't update the result of a filter.
>> If that's your definition of a filter, then WHERE is not a filter,
>> simple as that.
> 
> Fair enough! Can you correct my definition of filter, though?

I can't. You were using the term "filter", and seemed to apply it to 
WHERE but assume something that didn't match WHERE.
I wasn't rejecting your definition but that you applied the term to 
something that didn't match it.

Oh, and personally, I'd say a filter is something that selects items 
from a collection, be collection or items mutable or not. But that's 
just my personal definition, and I'll be happy to stick with anything 
that's remotely reasonable ;-)

> Your English is extraordinary. I could easily conclude that you
> were born in Boston and educated at Harvard, and either have
> Germanic ancestry or have simply adopted a Germanic name
> out of whimsy. If English is not your native tongue, there is no
> way to detect it.

Thanks :-)

But, no, my last visit to an English-speaking country was decades ago. 
Attribute my English to far too much time in technical newsgroups, and 
far too much googling ;-)
I'm pretty sure that my oral English is much, much worse, and that I've 
got a heavy German accent. I'd just try to improve on that if I were to 
relocate to GB or the US (and maybe that's just what made the difference 
for my English: constant striving for improvement).

Regards,
Jo