What is the theory behind mutable and immutable types?

Question

One of the things that I admire about Python is its distinction between mutable and immutable types. Having spent a while programming in c before coming to Python, I was astonished at how easily Python does away with all the complexities of pointer dereferencing that drive me mad in c. In Python everything just works the way I expect, and I quickly realized that the mutable/immutable distinction plays an important part in that.

There are still a few wrinkles, of course (mutable function argument defaults being a notable example) but overall, I feel that the mutable/immutable distinction greatly clarifies the question of what variables and their values are and how they ought to behave.

But where does it come from? I have to assume that GvR was not the first person to conceive of this distinction, and that Python was not the first language to use it. I'm interested in hearing about earlier languages that used this concept, as well as any early theoretical discussions of it.

Answer 1

If you like the idea of immutability, you should check out a pure functional language. In Haskell all (pure) variables are immutable (yet still referred to as "variables", but there you go). It is a great idea - you and the compiler both know that passing something into a function cannot change it in any way.

Answer 2

In C there is no explicit concept of immutable because the language is based on copy semantic. In Python instead values are always passed by reference and immutability plays an important role to keep the language manageable.

In Python you don't have pointers because everything is indeed a pointer! Imagine what it could mean for a Python program that even number objects could change value over time... you would be forced to play tricks like

class Shape:
    def __init__(self, points):
        self.points = points[:] # make a copy of the list

not only for lists and dicts, but also for numeric values and strings.

So basically in Python some types have immutable instances because they normally are used as "values" and you don't care about identity. In the rare cases in which you need for example a mutable object with a numeric value you need to explicitly wrap it up in say a class instance.

In other languages substantially based on reference semantic like LISP immutability is a choice left to the programmer and not a constraint even if many functions and idioms are supporting it (a big percentage of LISP standard library functions are non-destructive and it's indeed sort of a shame that destructive ones aren't always clearly distinguishable by the name).

So for example strings are mutable LISP but probably not many LISP programs actually modify strings in place because that would mean giving up the nice possibility of sharing and would require explicitly copying strings in many places (in most cases strings are just values, not objects in which you care about identity). Are strings immutable in LISP? No. Are programs mutating them? Almost never.

Not leaving a choice to the programmer is in the spirit of the Python language. It feels great when the choices you are forced to are in line with your idea... less decisions and things are exactly like you wanted them to be.

There are however in my opinion two different dangers with this approach:

1. Problems arise when those pre-made choices are NOT in line on what you would like or need to do. Python is a wonderful language, but with a different dictator could become pure hell.

2. Understanding and making choiches forces you to think and expands your mind. Not making choices instead just puts a cage on your mind and after a while you may not even realize that what you are using is just ONE possibility, not the only possibility. After a while you may begin to just think that "things MUST be done this way": you don't even feel you are forced because your mind has already been "mutilated".