What is a type error?

[Marshall]

Joachim Durchholz wrote:
> Marshall schrieb:
> > Joachim Durchholz wrote:
> >> Marshall schrieb:
> >>> Joachim Durchholz wrote:
> >>>> Marshall schrieb:
> >>>>> I can see the lack of a formal model being an issue, but is the
> >>>>> imperative bit really all that much of an obstacle? How hard
> >>>>> is it really to deal with assignment? Or does the issue have
> >>>>> more to do with pointers, aliasing, etc.?
> >>>> Actually aliasing is *the* hard issue.
> >>> Okay, sure. Nice explanation.
> >>>
> >>> But one minor point: you describe this as an issue with "imperative"
> >>> languages. But aliasing is a problem associated with pointers,
> >>> not with assignment.
> >> Aliasing is not a problem if the aliased data is immutable.
> >
> > Okay, sure. But for the problem you describe, both imperativeness
> > and the presence of pointers is each necessary but not sufficient;
> > it is the two together that causes the problem. So it strikes
> > me (again, a very minor point) as inaccurate to describe this as
> > a problem with imperative languages per se.
>
> Sure.
> It's just that I know that it's viable to give up destructive updates.
> Giving up pointers is a far more massive restriction.

Oddly, I feel the opposite. While it's true there are many domains
for which purely functional programming is a fine choice, there
are some domains for which it is insufficient. Any kind of data
managament, for example, requires that you be able to update
the information.

On the other hand, there is no problem domain for which pointers
are a requirement. I agree they are deucedly convenient, though.


> > Right. To me the response to this clear: give up pointers. Imperative
> > operations are too useful to give up; indeed they are a requirement
> > for certain problems.
>
> I don't know any.
> In some cases, you need an additional level of conceptual indirection -
> instead of *doing* the updates, you write a function that *describes* them.

But then what do you do with that function? Let's say I have an
employee database. John Smith just got hired on 1/1/2006 with
a salary of $10,000. I need to record this fact somewhere. How
do I do that without variables? Current-employees is a variable.
Even if I have the space to keep all historical data, so I'm not
deleting anything, I still have to have a variable for the latest
version of the accumulated data. I can solve this without
pointers, but I can't solve it without variables.


>  > Pointers on the other hand add nothing except
> > efficiency and a lot of confusion. They should be considered an
> > implementation technique only, hidden behind some pointerless
> > computational model.
> >
> > I recognize that this is likely to be a controversial opinion.
>
> Indeed.
>
> In fact "modes" are a way to restrict pointer aliasing.

I should like to learn more about these. I have some vague
perception of the existence of linear logic, but not much
else. However, I also already have an excellent solution
to the pointer aliasing problem, so I'm less motivated.


> > I heartily support immutability as the default, for these and other
> > reasons.
>
> OK, then we're in agreement here.
>
> >> Some functional languages restrict assignment so that there can exist at
> >> most a single reference to any mutable data structure. That way, there's
> >> still no aliasing problems, but you can still update in place where it's
> >> really, really necessary.
> >
> > Are we speaking of uniqueness types now? I haven't read much about
> > them, but it certainly seems like an intriguing concept.
>
> Yup.
> It's called "modes" in some other languages (Mercury or Clean IIRC).

Cool.


> >> I know of no professional language that doesn't have references of some
> >> kind.
> >
> > Ah, well. I suppose I could mention prolog or mercury, but then
> > you used that troublesome word "professional." So I will instead
> > mention a language which, if one goes by number of search results
> > on hotjobs.com for "xxx progammer" for different value of xxx, is
> > more popular than Java and twice as popular as C++. It lacks
> > pointers (although I understand they are beginning to creep in
> > in the latest version of the standard.) It also posesses a quite
> > sophisticated set of facilities for declarative integrity constraints.
> > Yet for some reason it is typically ignored by language designers.
> >
> > http://hotjobs.yahoo.com/jobseeker/jobsearch/search_results.html?keywords_all=sql+programmer
>
> Oh, right. SQL is an interesting case of getting all the problems of
> pointers without having them ;-)

Oh, pooh. SQL has plenty of problems, sure, but the problems
of pointers are not among its faults.


> Actually SQL has references - they are called "primary keys", but they
> are references nevertheless.

I strongly object; this is quite incorrect. I grant you that from the
50,000 foot level they appear identical, but they are not. To
qualify as a reference, there need to be reference and dereference
operations on the reference datatype; there is no such operation
is SQL.

Would you say the relational algebra has references?

Or, consider the classic prolog ancestor query. Let's say we're
setting up as follows

father(bob, joe).
father(joe, john).

Is "joe" a reference, here? After all, when we do the ancestor
query for john, we'll see his father is joe and then use that to
find joe's father. Keys in SQL are isomorphic to joe in the
above prolog.


> (Some SQL dialects also offer synthetic
> "ID" fields that are guaranteed to remain stable over the lifetime of a
> record.

Primary keys are updatable; there is nothing special about them.


> Seems like SQL is imperative enough that programmers want this,
> else the SQL vendors wouldn't have added the feature...)

I believe you are making a statement about the general level of
education among the user base of data base management systems,
and not a statement about the nature of the relational algebra.


> SQL also has updates.

Yes; SQL is imperative. But no pointers and thus no aliasing.
Plenty of *other* problems, though; no argument there!


> The result: updates with undefined semantics. E.g. if you have a numeric
> key field, UPDATE commands that increment the key by 1 will fail or work
> depending on the (unspecified) order in which UPDATE touches the
> records.

This does not sound correct to me, and in any event does not
appear to illustrate anything about aliasing.


> You can have even more fun with updatable views.

I suppose. Views are something for which the practice has
rushed ahead of the theoretical foundation out of need. The
"right" way to do views is not yet known. Again: plenty of
problems with SQL, but no aliasing. (Actually, there probably
is aliasing with SQL99, since IIUC they've gone ahead and
introduced reference types. (Cue Charlton Heston on the beach
saying "You Maniacs! You blew it up! Ah, damn you!"))


> With a "repeatable read" isolation level, you actually return to a
> declarative view of the database: whatever you do with it, you won't see
> it until you commit the transaction. (As soon as you commit, the
> declarative peace is over and you better watch out that your data
> doesn't become inconsistent due to aliasing.)

Alas, transaction isolation levels are a performance hack.
I cannot defend them on any logical basis. (Aside: did you mean
serializable, rather than repeatable read?)


> Aliasing isn't really related to specific programming practices. If two
> accountants chat, and one talks about the hot blonde secretaire and the
> other about his adorable wife, you can imagine the awkwardness that
> ensues as soon as they find out they're talking about the same person!

Heh, that's not aliasing. That's the undecidability of intentional
function equivalence. <joke>


> The only thing that can really be done about it is not adding it
> artificially into a program. In those cases where aliasing is part of
> the modelled domain, you really have to carefully inspect all
> interactions and never, never, never dream about abstracting it away.

Yes, aliasing introduces a lot of problems. This is one reason
why closures make me nervous.


Marshall