ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinFrom Mechanism to Method - Good Qualifications

Overload Journal #52 - Dec 2002 + Programming Topics   Author: Kevlin Henney

Introduction

When it is not necessary to change, it is necessary not to change. Lucius Cary, Viscount Falkland, 1610-1643.

Change. In every day life it is seen as something either to embrace and face or to resist and fear. It is either as good as a rest or something that leopard spots simply do not do. It is also, when it comes to matters of state, at the heart of procedural programming, making it a principle and principal concern for C++ developers: events cause functions to be executed; objects are created and destroyed; variables are assigned.

But as a path of control flows through our code not everything is about change. In places the flow is smooth and unchanging, and importantly so. It is important that things we regard as constants remain so, giving rise to the oxymoron constant variable. It is important that some functions do not change the objects they are called on or with. It is important that some function results do not allow subsequent changes.

Change Management

In C++ the responsibility of documenting and enforcing the absence of change is given to const, and that of communicating asynchronous and unpredictable change is given to volatile, by far the lesser of the two qualifiers. In combination, the apparently oxymoronic const volatile leaves many developers bemused, but makes some sense when applied to references or pointers that offer read-only semantics to asynchronously changing values.

Ringing the Changes

A simple dictionary class, which allows you to look up a string value based on a unique string key, demonstrates common applications of const with respect to member functions, references, and pointers:

  class dictionary {
  public:
    bool empty() const;
    size_t size() const;
    const std::string *lookup(
    const std::string &) const;
    void insert(const std::string &,
    const std::string &);
    void erase(const std::string &);
    void clear();
    ...
  private:
    ...
    typedef std::map<std::string,
                     std::string> map;
    map content;
  };
  std::ostream &operator<<(ostream &,
                           const dictionary &);
  std::istream &operator>>(istream &,
                           dictionary &);
  ...

With the exception of the lookup function, the function names and semantics correspond to those in the standard library [ISO1998]. Being able to read this interface with respect to mutability helps you determine some of the expected behavior of the class.

Don't Change the Spots

In some cases we can allow change behind the scenes with mutable, supporting discreet change on data members even under the rule of const. Sometimes referred to as the anticonst, mutable's role is to support the occasional discrepancy between a const-correct class public interface and its underlying physical implementation. Rather than modify the interface - and therefore affect the class user - to reflect optimizations such as caching, mutable allows the interface to remain stable and implementation details that do not affect the usage to remain encapsulated.

Let us assume that in using the dictionary class we discover that there is a good chance that we look up a given key many times in a row. We could try to optimize this by keeping a cache. Preservation of the class's perceived interface and functional behavior is assisted by mutable:

  class dictionary {
    ...
    mutable map::const_iterator last_lookup;
  };
  const std::string *dictionary::lookup(const std::string &key)const {
    if(last_lookup == content.end() || last_lookup->first != key)
      last_lookup = content.find(key);
    return last_lookup != content.end() ? &last_lookup->second : 0;
  }

mutable has helped bridge any discrepancy between physical and logical const-ness. However, note that this solution is not appropriate in an environment where dictionary objects are shared between threads. Between each of these two implementation options the type perceived by the class user has remained stable.

Substitutability and Mutability

What is an object's type? Is it the class from which it is created? Is it the functions that can be applied to it, whether global or member? Is it its usage? Is it its capabilities and behavior? Is it the classification that groups similar objects together? In truth, type can mean any one of these, depending on the context. You can see that in some way they are all related - or at least can be - to one another.

Of Types and Classes

If we restrict the notion of type to be the declared class of an object and the functions that work on it, we may have a syntactic notion of type, but we are short of a model of usage - sure I can write code against it that compiles, but what am I expecting at runtime? In the dictionary example, we can see how to write code that compiles, but what result are we expecting from a call to dictionary::lookup? If we say that a class defines the expected behavior from the member and global functions that can be applied its instances, we can equate the syntax and semantics of the class directly with a notion of type that satisfies most possible definitions of the word.

What about template type parameters? These are constrained by syntax usage but not by class. That is, after all, the idea of templates: They are generic and not locked into specific class hierarchies. In the STL, the compile-time requirements for syntax usage are supplemented by operational requirements. For instance, an object that is CopyConstructible [ISO1998] satisfies a set of requirements that goes beyond the simple syntax of a copy constructor, so that std::list<int> is CopyConstructible whereas std::auto_ptr<int> is not. These syntactic and semantic requirements together form an equally valid concept of type.

What seems to be common across these notions of type is that a type names and describes a particular model of usage and external behavior for an object. In the case of a class, the type name exists explicitly in the source code, the usage is defined by the functions in its interface (according to the Interface Principle [Sutter2000]), and the behavior is described outside of the compiled class interface (comments, unit tests, external documentation, word of mouth, class author's head, etc.). In the case of a template type parameter, the type name is not truly in the source code, the usage is defined by expression syntax, and the behavior is again implied and beyond the code.

So, how do const and volatile qualifiers relate to our notion of type? OK, if we're being practical: How does the const qualifier affect our notion of type? When const is applied to an object, whether directly on a value declaration or indirectly via a pointer or reference, it changes our view of that object. To be precise, it restricts what we can do with it. In other words it affects the model of usage, and hence the type. For instance, a plain int supports assignment operations, such as =, +=, and ++, whereas a const int does not. A std::string supports modifier functions such as clear and append, whereas a const std::string supports only query functions. Therefore, the typical class public interface is really two interfaces: The interface for const qualified objects and the interface for non-const qualified objects.

Of Type Hierarchies and Class Hierarchies

Relating classes together with derivation forms a class hierarchy. From the perspective of an external user of the class hierarchy - as opposed to someone implementing or extending it - only public derivation is of interest. What is the best advice for forming inheritance relationships? Substitutability or, to be more precise, the Liskov Substitution Principle (LSP) [Liskov1987]:

A type hierarchy is composed of subtypes and supertypes. The intuitive idea of a subtype is one whose objects provide all the behavior of objects of another type (the supertype) plus something extra. What is wanted here is something like the following substitution property: If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2, then S is a subtype of T.

In a nutshell, class hierarchy should follow type hierarchy. This recommendation is more detailed than the more common is-a or isa- kind-of recommendation, which creates a taxonomy ensuring that each derived class is a kind of its base class. LSP is more detailed because it considers explicitly the behavior of the types involved.

Notice that - without actually having it officially stated - the implicit conversion in C++ from pointers or references from derived to base underpins an assumption that LSP is followed. The compiler knows nothing of the expected semantics of your classes, but it knows in code that where a base instance is expected a derived instance can be supplied. You drop LSP at your own risk.

There is another assumption that LSP is a recommendation only for organizing inheritance between classes in OO systems [Coplien1992, Sutter2000]. Notice that, if you read the recommendation carefully, there is no mention of classes. LSP is about relationships between types. Substitutability as defined applies not only to class hierarchies, but also to other notions of type based on models of usage [Henney2000a]: conversions [Henney2000b], overloading [Henney2000c], templates (so there is no need for a generic variant of LSP [Sutter2000]), and mutability.

We can relate mutability directly to const and non-const, and substitutability to the relationship between them: For a given class, a non-const object is a subtype of a const object because it may be used wherever the const version is expected. The non-const type also supports the interface of the const type. Pointer and reference conversions work in the way that you would expect: To go from non-const to const is implicit, whereas to go the other way, against the grain, requires an explicit conversion, a const_cast. Compare this to the implicit derived to base conversion with inheritance, and the explicit static_cast (or safer dynamic_cast) to go the other way.

Returning to the dictionary class, we can take some artistic and linguistic license to consider it to be two types with a subtyping relationship between them:

  class const dictionary { // not legal C++
  public: // const member functions only
    bool empty() const;
    size_t size() const;
    const std::string *lookup(
    const std::string &) const;
    ...
  };
  // globals taking const dictionary
  // references only
  std::ostream &operator<<(ostream &,
                           const dictionary &);
  ...
  class dictionary : public const dictionary { // not legal C++
  public: // additional non-const
    // member functions
    void insert(const std::string &,
                const std::string &);
    void erase(const std::string &);
    void clear();
    ...
  };
  // additional globals taking non-const
  // dictionary references
  std::istream &operator>>(istream &,
  dictionary &);
  ...

From this, it is clear that when we see const dictionary in code we are looking at the as-if type represented by the first fragment, and when we see plain dictionary in code it is the second fragment, which builds on the first.

Specialization

Where there are subtypes there is specialization. Specialization can be with respect to extension, i.e. the subtype extends the interface of the supertype with more operations. It can also be with respect to constraints, i.e. the subtype's operations are more specific with respect to behaviour or result types.

In a class hierarchy classes typically acquire more operations the further down the hierarchy you descend. The guarantees of behavior can also become more specific. For example, if a base class function guarantees that its pointer result is null or non-null, an overridden version in a derived class can satisfy substitutability by never returning null. Conversely, if a base class function requires that its pointer argument must never be null, a derived class version can legitimately liberalize this to also accommodate null. The specialization of result also applies to return type: Assuming that the return type is a class pointer or reference, an overridden function can redeclare the return type to be a derived class pointer or reference.

This much is standard in OO: Runtime polymorphism offers us the method for such specialization, and virtual functions the mechanism. What of const and non-const? There is no concept of runtime polymorphism related to mutability. However, overloading offers us a compile-time variant of overriding: We can overload with respect to const-ness. In this compile-time view of polymorphism (the foundation of generic programming in C++) selection is performed with respect to const-ness for member functions on their target object and functions in general with respect to their arguments.

Given two member functions of the same name and similar signature, differentiated only by const-ness, the const version will be the only viable option for const access to an object. For non-const access, both functions are in theory available, but the compiler will select the more specific version, i.e. the non-const one. The most common reason for such overriding is to specialize the return type, e.g. operator[] on strings should allow scribble access for non-const strings and read-only access for const strings. In our dictionary class, a more STL-based approach to lookup demonstrates this approach:

  class dictionary {
  public:
    typedef map::const_iterator const_iterator;
    typedef map::iterator iterator;
    ...
    const_iterator find(const string &) const;
    iterator find(const string &);
    ...
  };

Viewing this again in terms of const-based type and subtype gives us the following interfaces:

  class const dictionary { // not legal C++
  public:
    const_iterator find(const string &) const;
    ...
  };
  class dictionary : public const dictionary { // not legal C++
  public:
    iterator find(const string &);
    // more specialized 'override'
    ...
  };

Conclusion

In C++, const divides the novice from the experienced: on one side lies a source of confusion; on the other a means of clarification. Explicit annotation of modifier from query functions can benefit a system, and this is a concept that can be expressed in C++ using type qualifiers. Thus volatile and const - as well as mutable - are unified under the heading of change, even if the names are not as well chosen as they might be.

Qualification relates to the notion of type in terms of usage and behavior, and with it subtyping and all its accumulated practices and understanding. One valuable property of subtyping is substitutability. Although it is often clear from the context, we sometimes need to clarify what kind of substitutability we are referring to, i.e. substitutability with respect to what? In the case of const it is substitutability with respect to change.

References

[Coplien1992] James O Coplien, Advanced C++: Programming Styles and Idioms, Addison-Wesley, 1992.

[Henney2000a] Kevlin Henney, "From Mechanism to Method: Substitutability", C++ Report 12(5), May 2000, also available from http://www.curbralan.com.

[Henney2000b] Kevlin Henney, "From Mechanism to Method: Valued Conversions", C++ Report 12(7), May 2000, also available from http://www.curbralan.com.

[Henney2000c] Kevlin Henney, "From Mechanism to Method: Function Follows Form", C/C++ Users Journal C++ Experts Forum, November 2000, http://www.cuj.com/experts/1811/henney.html.

[ISO1998] International Standard: Programming Language - C++, ISO/IEC 14882:1998(E), 1998.

[Liskov1987] Barbara Liskov, "Data Abstraction and Hierarchy", OOPSLA '87 Addendum to the Proceedings, October 1987.

[Sutter2000] Herb Sutter, Exceptional C++.

Overload Journal #52 - Dec 2002 + Programming Topics