State semantics

The following is a proposal for the classification of types in an imperative language according to the way the state of their objects changes over time.

Immutable. Objects of an immutable type cannot change state during their lifetime.

Stateful. On the other side of the spectrum, an object of a stateful type publish some methods that cause the object's internal state to change when executed.

Bound. (For lack of a better name.) The state of an object x of a bound type remains immutable unless x is explicitly given the same state as some y through explicit assignment x = y. A very popular example of a bound type is java.lang.String. Although Java strings are commonly characterized as immutable, it is actually their associated states that are immutable, since an object of type java.lang.String can be rebound through assignment. In C++, bound semantics are approximated by pointers to constant objects—C++ references, on the other hand, do not have bound semantics since they cannot be reassigned, that is, rebound.

It turns out that bound types are sufficiently powerful to emulate stateful semantics using the following mapping technique: let T be a stateful type and an associated mutable method

void T::f(args);

We construct an associated bound type BT whose internal state is represented by values of T. We replace T::f with the following immutable method:

‎BT BT::f(args)
‎{
‎  T state=this->state;
‎  state.f(args);
‎  return BT(state);
‎} 

so that the expression

‎T x;
‎...
‎x.f(args);

can be rewritten with BT as

‎BT x;
‎...
‎x=x.f(args);

And similarly we can provide a stateful façade to a bound type: let T be a bound type with some method

‎T T::f(args);

We define a stateful type ST whose internal state is represented by values of T, and implement the associated method f as follows:

‎void ST::f(args)
‎{
‎  this->state=this->state.f(args);
‎}

In summary, bound and stateful types are to some extent equivalent, though practical considerations might favor one kind over the other depending on the use context. For instance, bound types are more amenable to interning techniques and can be more easily equipped with locking mechanisms for use in multithreaded environments.