Afterword

We recap the main themes of the book: regularity, concepts, algorithms and their interfaces, programming techniques, and meanings of pointers. For each theme, we also discuss its particular limitations.

Regularity

Regular types define copy construction and assignment in terms of equality. Regular functions return equal results when applied to equal arguments. For example, regularity of transformations allowed us to define and reason about algorithms for analyzing orbits. Regularity was in fact relied on throughout the book by ordering relations, the successor function for forward iterators, and many others.

When we work with built-in types, we usually treat the complexity of equality, copying, and assignment as constant. When we deal with composite objects, the complexity of these operations is expected to be linear in the area of objects: the total amount of memory, including remote as well as local parts. Our expectation, however, that equality is at worst linear in the area of its arguments cannot always be met in practice.

For example, consider representing a multiset, or unordered collection of potentially repeated elements, as an unsorted dynamic sequence. Although inserting a new element takes constant time, testing two multisets for equality takes O(n log n) time to sort them and then compare them lexicographically. If equality testing is infrequent, this is a good tradeoff; however, putting such multisets into a sequence to be searched with find could lead to unacceptable performance. For an extreme example, consider a situation in which the equality for a type must be implemented with graph isomorphism, a problem for which no polynomial-time algorithm is known.

We noted in Section 1.2 that when implementing behavioral equality on values is not feasible, we can often implement representational equality. For composite objects, we often implement representational equality with the techniques of Section 7.4. Such structural equality is often useful in giving the semantics of copy construction and assignment and may be useful for other purposes. Recall that representational equality implies behavioral equality. Similarly, while a natural total ordering is not always realizable, a default total ordering based on structure (e.g., lexicographical ordering for sequences) allows us to efficiently sort and search. There are, of course, objects for which neither copy construction nor assignment—nor even equality—makes sense, because they own a unique resource.

Concepts

We use concepts from abstract algebra—semigroups, monoids, and modules—to describe such algorithms as power, remainder, and gcd. In many cases we need to adapt standard mathematical concepts to fit algorithms. Sometimes, we introduce new concepts, such as HalvableMonoid, to strengthen requirements. Sometimes, we relax requirements, as with the partially associative property. Often we deal with partial domains, as with the definition-space predicate passed to collision_point. Mathematical concepts are tools to be used and freely modified. It is the same with concepts originating in computer science. The iterator concepts describe fundamental properties of certain algorithms and data structures; however, there are other coordinate structures described by concepts yet to be discovered. It is a task of the programmer to determine whether a given concept is useful.

Algorithms and Their Interfaces

Bounded half-open ranges correspond naturally to the implementation of many data structures and provide a convenient way to represent inputs and outputs for such algorithms as find, rotate, partition, merge, and so on. However, with some algorithms, such as partition_point_n, a counted range is the natural interface. Even for algorithms for which bounded ranges are natural, there usually exist natural variations taking counted ranges. Limiting ourselves to a single variety of interface would be a false economy.

Three rotation algorithms, described in Chapter 10, correspond to three iterator concepts. For every algorithm, we need to discover its conceptual requirements, the preconditions on its input, and any other characteristics that make its use appropriate. It is rarely the case that a single algorithm is appropriate in all circumstances.

Programming Techniques

Using successor, a transformation that is strictly functional, allowed us to write a variety of clear and efficient programs. In Chapter 9, however, we chose to encapsulate calls of successor and predecessor into small mutative machines, such as copy_step, since it led to clearer code for a family of related algorithms. Similarly, it is appropriate to use goto in the state machines in Chapter 8 and to use reinterpret_cast for the underlying type mechanism in Chapter 12. Instead of restricting the expressive power of the underlying machine and the language, it is necessary to determine the appropriate use for each available construct. Good software results from the proper organization of components, not from syntactic or semantic restrictions.

Meanings of Pointers

The book demonstrates two ways of using pointers: (1) as iterators and other coordinates representing intermediate positions within an algorithm, and (2) as connectors, representing ownership of the remote parts of a composite object. For example, in Section 12.2, we discussed the use of pointers to connect nodes within a list and extents within an array.

These two roles for pointers determine different behavior when an object is copied, destroyed, or compared for equality. Copying an object follows its connectors to copy the remote parts, so the new object contains new connectors pointing to the copied parts. On the other hand, copying an object containing iterators (e.g., a bounded_range) simply copies the iterators without following them. Similarly, destroying an object follows its connectors to destroy the remote parts, while destroying an object containing iterators has no effect on the object to which the iterators point. Finally, equality on a container follows connectors to compare corresponding parts, while equality on a noncontainer (e.g., a bounded_range) simply tests for equality of corresponding iterators.

There is, however, a third way to use pointers: to represent a relationship between entities. A relationship between two or more objects is not a part owned by these objects; it has an existence of its own while maintaining mutual dependencies between the objects it relates. In general, a pointer representing a relationship does not participate in the regular operations. For example, copying an object does not follow or copy a relationship pointer, since the relationship exists for the object being copied but not for its copy. If a one-to-one relationship is represented as a pair of embedded pointers linking two objects, destroying either of the objects must clear the corresponding pointer in the other object.

Designing data structures as composite objects with ownership and remote parts leads to a programming style in which the primary objects—those that are not subparts of other objects—reside in static variables, with a lifetime of the entire program execution or, in local variables, with a lifetime of a block. Dynamically allocated memory is used only for remote parts. This extends the stack-based block structure of Algol 60 to handle arbitrary data structures. Such structure naturally fits many applications. However, there are circumstances in which reference counting, garbage collection, or other memory-management techniques are appropriate.

Conclusions

Programming is an iterative process: studying useful problems, finding efficient algorithms for them, distilling the concepts underlying the algorithms, and organizing the concepts and algorithms into a coherent mathematical theory. Each new discovery adds to the permanent body of knowledge, but each has its limitations.