What is a type error?

[Joe Marshall]

Marshall wrote:
> Joe Marshall wrote:
> > Marshall wrote:
> > >
> > > Consider the following Java fragment:
> > >
> > > void foo() {
> > >   int i = 0;
> > >   int j = 0;
> > >
> > >   // put any code here you want
> > >
> > >   j = 1;
> > >   i = 2;
> > >   // check value of j here. It is still 1, no matter what you filled in
> > > above.
> > >   // The assignment to i cannot be made to affect the value of j.
> > >
> > > }
> >
> > True, but you have hidden the pointers.  Semantically, the identifiers
> > i and j refer not to integers but to locations that hold integers.  The
> > assignment modifies the location.
>
> What the implementation looks like shouldn't affect how we speak
> of the logical model. In the above code, there are no pointers.
>
> By your definition, "pointer" and "variable" are synonyms. That doesn't
> seem like a good idea to me. (What if i and j end up in registers?
> I have not heard it said that registers have addresses.)

You probably won't like this, but....

The example you give above is a bit ambiguous as to whether or not it
shows `true' mutation.  So what do I mean by `true' mutation?  The code
above could be transformed by alpha-renaming into an equivalent version
that does no mutation:

void foo() {
   int i = 0;
   int j = 0;

   // put any code here you want

   int jj = 1;
   int ii = 2;
   // rename all uses of i to ii and j to jj after this point.

 }

Once I've done the renaming, we're left with a pure function.  I claim
that this sort of `mutation' is uninteresting because it can be
trivially eliminated through renaming.  Since we can eliminate it
through renaming, we can use a simplified semantics that does not
involve a `store', and use a substitution model of evaluation.

The more interesting kind of mutation cannot be eliminated through
renaming.  The semantic model requires the notion of a stateful
`store', and the model is not referentially transparent: substitution
does not work.  These qualities are what make mutation problematic.  My
claim is that this kind of mutation cannot be had without some model of
pointers and references.

There is a further distinguishing characteristic:  Can I write a
program that detects the mutation (and acts differently depending on
whether there is mutation or not)?  It is unclear from your example
above whether you intended this to be possible, but certainly there is
no way for a caller of foo to tell that foo reassigns an internal
variable.  If there a procedure is extrinsically a pure function, then
there is no real meaning to any `mutation' that goes on inside; there
is always a way to turn the internal mutation into a pure function
through alpha-renaming.

>
> Clearly there is *some* difference between a language which allows
> explicit pointers and thus aliasing and one that doesn't. What term
> would you use? First-class variables?

My argument to you in re this statement:
> Again, I disagree: it is posible to have mutability without
> pointers/identity/objects.

is that mutability without a notion of pointers, identity, or objects
is trivially eliminated through alpha renaming and thus isn't the
`mutability' of interest.