Why are tuples immutable?

Jeff Shannon jeff at ccvcorp.com
Wed Dec 22 18:54:17 CET 2004

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 
>Why should I, Do you doubt that it is possible?


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

>>>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 
>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.  Sensible behavior for 
dictionary keys requires that it be possible to compare keys by value.  
Overall sensible behavior for lists also provides a strong suggestion 
(though not an absolute requirement) that lists should normally compare 
by value.  Your suggestion requires that lists *not* compare by value, 
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.  
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. ;)

>>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.  If you allow 
mutable objects as keys, then key objects *WILL* mutate underneath the 
dictionary -- it's blindness to think otherwise.  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 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), and your so-called comparison case of 
an informally-organized non-language-standard data format, done on top 
of language features rather than as part of the core, in which mutations 
are not only less surprising but much easier (i.e. actually possible) to 
compensate for.

Jeff Shannon
Credit International

More information about the Python-list mailing list