SourceForge.net LogoThe Eiffel Compiler / Interpreter (tecomp)

doc/papers/lang/immutability

Immutability

Why immutability?

The reason for the need of immutability is best explained with an example.

We want to make a class HASH_MAP[VALUE,KEY->HASHABLE] which can map keys of type KEY to values of type VALUE. The statement

   hash_map.extend(value,key)

shall enter that specific pair into the map. If KEY is a reference type (e.g. STRING), you can modify the object after inserting it into the hash_map. That screws up the hash_map, because the key will generally have a different hash_code and the hash_map is no longer able to locate that specific key value pair.

If you are the author of HASH_MAP, the only defense against such a use is to make a deep_twin of all the entered keys. This is in many situations an overkill, because users of HASH_MAP don't have the intention to change the keys after inserting key value pairs into the map. They just don't have a possibility to express that in the Eiffel language and the compiler has no means to verify that.

If it were possible to express that all keys entered into the map must be immutable (e.g. HASH_MAP[VALUE,KEY-> immutable HASHABLE], the designer of HASH_MAP does not need to deep_twin all entered keys. Moreover the compiler can verify that all users comply.

The current situation

Eiffel from the beginning up to ECMA Eiffel has no way to express immutability of objects. Recently EiffelSoftware has added IMMUTABLE_STRING to its base library. The design of STRING and IMMUTABLE_STRING shows the design pattern needed to express immutability.

There are the 3 classes

RS has only queries and no commands to change the content of the string. RS is a common parent of S and IS

                  RS
                 ^  ^
                /    \
               S     IS

i.e. a STRING is a READABLE_STRING and an IMMUTABLE_STRING is a READABLE_STRING. If you have an entity of type RS, you cannot modify the string, but in case that an object of type STRING is attached to the entity, somebody else might modify the string.

We have the following conversions

The design works well and does prohibit the modification of IMMUTABLE_STRINGs. Unfortunately 3 classes are needed to have a mutable and immutable variant of a type.

An improvement

Definition: Objects are changed via commands. Queries do not change the (visible) state of an object. Immutability of an object means the impossibility to call commands on it.

The above used design pattern for immutable strings can be built into the language to make it more expressive. We add the modifiers immutable and readable to types and get the possible declarations

     t:  T               -- an entity of type T
     rt: readable T      -- rt allows only queries
     it: immutable T     -- it allows only queries
 
     -- T           conforms to readable T
     -- immutable T conforms to readable T
 
     -- attachments with shared objects
     rt := t             -- allowed, because of conformance
     rt := it            -- allowed, because of conformance
 
     -- conversions
     t  := it            -- attach deep_twin of `it'  to  `t' 
     it := t             -- attach deep_twin of `t'  to  `it' 
 
     t  := rt            -- attach deep_twin of `rt'  to  `t' 
     it := rt            -- attach deep_twin of `rt'  to  `it' 
 
 

A readable entity gives the following guarantee:

An immutable entity gives the following guarantee:

Since this language extension is an extension, it will not break existing code.

The property of readability and immutability have to be deep, i.e. an immutable/readable expression can return only immutable/readable results.

Discussion

Feel free to comment on that topic at http://sourceforge.net/projects/tecomp/forums/forum/1034481.

 Local Variables: 
 mode: outline
 coding: iso-latin-1
 fill-column: 60
 outline-regexp: "=\\(=\\)*"
 End:
Table of contents

- Why immutability?

- The current situation

- An improvement

- Discussion


ip-location