Why are tuples immutable?

[Antoon Pardon]

Op 2004-12-22, Jeff Shannon schreef <jeff at ccvcorp.com>:
> Antoon Pardon wrote:
>
>>Op 2004-12-21, Jeff Shannon schreef <jeff at ccvcorp.com>:
>>  
>>
>>>Antoon Pardon wrote:
>>>    
>>>
>>>So show us a dictionary (i.e. hash table) implementation that can do 
>>>this.
>>>    
>>>
>>
>>Why should I, Do you doubt that it is possible?
>>  
> Yes.

I'm not going to show you an implementation, but the rest of
this article should contain enough information.

>>>You'll need to be able to derive the old hash from the new hash, 
>>>of course, so that you can correctly associate the values already stored 
>>>under that key.  And you'll have to be able to do that without referring 
>>>to the pre-modified object again, because dicts can't track every Python 
>>>operation that might modify a key object.  And it needs to deal properly 
>>>with equivalent-but-different-ID list literals, because using literals 
>>>(and not references stored elsewhere) is an important and common dict 
>>>key usage.
>>>
>>>If you can show me how you plan to accomplish this, I'll accept that 
>>>you're right on this.  Until then...
>>>    
>>>
>>
>>I don't have to accomplish all that in order to be able to clean up
>>a mutated dictionary key. All I need to do is go over the keys, see
>>if they hash to the same bucket as they are in now and otherwise
>>put them in the new bucket. Sure that would be costly, but so would
>>allowing arbitrary mutation in a sorted list and resorting everytime
>>or in a heapqueue and reheapifying.
>>  
>
> The problem is that once the object has mutated, you *don't know* what 
> bucket it used to sort into.  There is no point at which a dictionary 
> can see "before" and "after" -- it just sees two different lists.

I don't have to know, I just go over every bucket and in each bucket
check whether the keys in there still hash to the current bucket.
Or in other words I call the items method and use that list to
remake the dictionary. That can even be done with a thin wrapper
around dictionary in python.

And before you start asserting again that the link between the key and
the object is severed in the dictionary if you mutate the key, here an
example to show you wrong.

.>>> class Hlist:
.>>> 
.>>>   def __init__(self, lst):
.>>>     self.lst = list(lst)
.>>> 
.>>>   def __hash__(self):
.>>>     return sum(self.lst) % 0x7fffffff
.>>> 
.>>>   def __repr__(self):
.>>>     return '{' + ', '.join([str(i) for i in self.lst]) + '}'
.>>> 
.>>>   def __len__(self):
.>>>     return len(self.lst)
.>>> 
.>>>   def __getitem__(self, index):
.>>>     return self.lst[index]
.>>> 
.>>>   def __setitem__(self, index, value):
.>>>     self.lst[index] = value
.>>> 
.>>> l1 = Hlist(xrange(3))
.>>> l2 = Hlist([3, 7 , 13])
.>>> 
.>>> d = {}
.>>> 
.>>> d[l1] = 1
.>>> d[l2] = 2
.>>>
.>>> d[l1]
1
.>>> l1[0] = 99
.>>> d[l1]
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
KeyError: {99, 1, 2}
.>>> d.items()
[({99, 1, 2}, 1), ({3, 7, 13}, 2)]

As you can see, the mutated key with its value is among the items.
So the dictionary still maintains a link between the key and the
value even if the key is mutated.

>>>>And yes I know what to do if I want to use mutable keys as objects. I'm
>>>>just argueing against those who think that should be somehow forbidden.
>>>> 
>>>>
>>>>      
>>>>
>>>We're not arguing that it should be arbitrarily forbidden.  We're 
>>>arguing that doing anything else makes it impossible to behave 
>>>sensibly.
>>>    
>>>
>>
>>How does having stable keys in a mutable objects makes it impossible
>>to behave sensible for dictionaries?
>>  
>>
>
> What you are calling "stable keys in a mutable object" simply cannot be 
> done while allowing comparison-by-value.

Yes it can.

>  Sensible behavior for 
> dictionary keys requires that it be possible to compare keys by value.  

No problem here.

> Overall sensible behavior for lists also provides a strong suggestion 
> (though not an absolute requirement) that lists should normally compare 
> by value.

Again no problem.

>  Your suggestion requires that lists *not* compare by value, 

No it doesn't. It only requires the dicipline of the programmer
not to mutate the objects while it is used as a key.

> and provides very little practical benefit in return for complicating 
> all other list-comparison code everywhere.
>
>>>So prove us wrong,
>>>    
>>>
>>
>>I don't have to prove you wrong. If you want to argue something,
>>you have to provide reasoning that shows you right.
>>  
>>
>
> You're the one that's saying that the current behavior is flawed.  

No I'm not. I'm saying your understanding is flawed. I'm argueing
against what you thinks happens, not against what actually happens.

> You're the one making the extraordinary claim that things could be done 
> better.  I'm not even claiming that *I'm* right -- I'm claiming that GvR 
> and Tim Peters are smarter and far more likely to be right than either 
> of us. ;)

I have claimed things could be better, but that was caused by what
people told happened. With my current understanding I say I can live
with the choices they made. It's not the choice I would have made,
but it is a case where there is no clear winner and people in the
end have to make a value jugdement, and each will weight various
consequences differently.

I also find the suggestion in the documentation to only use objects
as keys when they are immutable, to be overly restrictive. But that
is a problem with the documentation, not with how python actually
works.

>>>by implementing something that behaves 
>>>sensibly in the face of mutating keys (which compare by value, as lists 
>>>do, rather than by identity).
>>>    
>>>
>>
>>You are confusing two things with each other. That is 1) a mutable object
>>that is a key and 2) a mutating key. Even if an object is mutable it can
>>be stable for some duration and thus unmutating. There is IMO nothing
>>wrong with using such mutable objects as dictionary keys or in other
>>structures that require an invariant. Requiring that such objects be
>>immutable and thus can't even mutate during periods they are not so
>>used, creates an unnecessary burden.
>>  
>
> Requiring that programmers track which objects have been used as 
> dictionary keys somewhere and may still be in a dictionary creates an 
> unnecessary burden, and one which *WILL* be forgotten.

Nonsense! This is like saying that requiring programmers to track
which objects are used in a sorted list somewhere and may still be
in a sorted list creates an unnecessary burden.

There is an answer to that. If you need a specific value, and thus
an objects that is stable and there is a chance you need to mutate
the object in an other context, you make a copy. Dictionaries are
just one case for this kind of situation. If I have a function with
a list as parameter and I mutate the list in the function while
the caller expects the list to remain stable over the call, I already
have the same kind of problem. And who knows how many times the list
is passed as argument and assigned to other variable before the
mutation actually happens. Surely requiring the programmer to track
all that is an unnecessary burden and only immutables should be
allowed to be assigned or be passed as argument.

> If you allow 
> mutable objects as keys, then key objects *WILL* mutate underneath the 
> dictionary -- it's blindness to think otherwise.

Sure bugs will be made, but these are just the same kind of bugs that
can be made with mutables anaywhere. I see no reason why dictionaries
should have special protection buildin while the rest of python offers
none.

> That means that dicts 
> would need to handle that in *some* way -- at bare minimum, throwing a 
> meaningful error.  In essence, you're saying that programmers should 
> mentally enforce invariants, rather than having the language enforce 
> them.  Which has about as much chance of success as C's malloc/free() 
> has of never being misused.

And has just as much chance of

  def func(l=[]):

never causing surprises again.

Python requires its own methods of discipline and suggesting that
keys should be immutable because requiring some kind of discipline
from the programmers is unthinkable is IMO just idiot.

> And I still say that there's a big difference between the invariant 
> condition of a *core language feature* that is used everywhere 
> internally in the langauge, and which therefore requires rock-solid and 
> blazing-fast performance, making restrictions to prevent cases where it 
> cannot behave unsurprisingly (because mutating keys, however they're 
> handled, *will* surprise people),

Python has enough other features that surprise people. If surprise
is such a bad thing, you shouldn't program.

-- 
Antoon Pardon