On 18 Aug 2003 10:06:39 -0700, 
	Hannu Kankaanpää <hanzspam / yahoo.com.au> wrote:
> Strings, numbers and tuples are immutable in Python so that they
> can be used as dictionary keys. I admit that one could do away
> with this restriction by just choosing not to alter strings that
> are used as dictionary keys. But allowing this to be done could

Mutable strings also result in a more complicated implementation. One of
Python's principles is to keep the implementation as simple as possible;
think of it as XP's rule of "Do the simplest thing that can possibly work."

Consider this code:

d = {}
s = 'abc'
d[s] = 1
s.sub!('ab', 'cd') # abc -> cdc

Now what?  If dictionaries don't make copies of their keys, then mutating 
the key means that the dictionary now stores a key value of "cdc".  But
because this probably changed the hash code, it's now in the wrong hash
bucket.  When you do d['cdc'], it will look in the wrong hash bucket, find
it empty, and report the key isn't found.

So what's a language implementor to do?  You could have some sort of flag on
strings indicating 'this is in a dictionary: no mutation'.  You could keep a
list of "all dictionaries this string is used as a key in", and when you
mutate the string rehash all of them.  You could make copies of all keys in
dictionaries, but then someone will use a 3Mb string or a tree as a key and
complain that storing keys is slow.  You can then try to figure out when
copying keys is necessary and skip it if it isn't. All of this is more code
to write and more code to be a source of subtle bugs.

Immutable strings cut through all this; you don't need code to handle these
cases because they never come up.

Python's design was influenced by Guido's experience with ABC.  ABC went for
theoretical completeness and paid for it in implementation complexity.
Numbers were rationals, and users complained how they got mysteriously slow
after a lengthy computation. Dictionaries were AVL trees, with O(lg N) best
performance but a fairly high constant.  Python therefore reacted in the
opposite direction, choosing the simplest implementation and avoiding
complexity as much as possible.

--amk                                            (www.amk.ca)
A is for Adam and E is for Eve. B is for bile, blood and bones.
      -- Louis Andriessen & Jeroen van der Linden, "The Alphabet Song"