What is a type error?

[Joachim Durchholz]

Marshall schrieb:
> Joachim Durchholz wrote:
>> 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.

Sure, the data itself cannot be managed non-destructively.

However, the programs that operate on the data need not do destructive 
updates internally. That way, I can have pointers inside the programs 
without giving up aliasing.
(Aliasing is really, really, really important. It's the reason why 
mathematicians can handle infinite objects - they copy just the alias, 
i.e. the name or description, instead of the object itself. It's one of 
the things that make abstraction useful.)

>>> 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?

I pass it to an engine that's imperative.

However, that engine doesn't need to do aliasing anymore.

In other words, I'm separating mutability and aliasing, so that they 
can't combine and explode.

 > 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.

As I said elsewhere, the record has an identity even though it isn't 
explicit in SQL.
(SQL's data manipulation language is generally not considered half as 
"clean" as the query language; I think the core of the problemsis that 
DML combines mutability and identity.)

> 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.

Pointers are just the most obvious form of aliasing. As I said 
elsewhere, there are others: array indexing, by-reference parameters, or 
even WHERE clauses in SQL statements. In fact, anything that selects an 
updatable piece of data from a collection is an alias, and incurs the 
same problems as pointers, though they may come in different disguises.

>> 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?

Yes.

> 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.

Agreed. They are both references ;-P

>> (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.

Right - I was wrong with identifying keys and identities. In fact the 
identity of an SQL record cannot be directly obtained (unless via those 
ID fields).
The records still have identities. It's possible to have two WHERE 
clauses that refer to the same record, and if you update the record 
using one WHERE clause, the record returned by the other WHERE clause 
will have changed, too.

>> 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?)

Possibly. There are so many isolation levels that I have to look them up 
whenever I want to get the terminology 100% correct.

>> 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.

Me too.
On the other hand, they are so immensely useful.
Simply don't create closures with mutable data in them. Or, to the very 
least, make sure that no aliases outside the closure exist.

Regards,
Jo