14. Conclusions

The strongest arguments prove nothing so long as
the conclusions are not verified by experience.
Roger Bacon, Opus Tertium

We started this book by characterizing generic programming as an attitude toward programming that focuses on abstracting algorithms to their most general setting without losing efficiency. Throughout the book, we’ve seen examples of this abstraction process in mathematics and in programming. We saw how mathematicians’ attempts to find the most general setting for Euclid’s GCD algorithm led to the development of abstract algebra, an entire area of mathematics devoted to abstract structures, which itself provided the basis for generic programming. We also saw how to use those same principles of abstraction to generalize an ancient algorithm for multiplying positive integers to a fast power function on semigroups, enabling a range of applications ranging from computing Fibonacci numbers to finding the shortest path in a graph to encrypting data in Internet communication protocols. This process—starting with a specific efficient solution and, whenever possible, relaxing the requirements—is at the heart of generic programming.

While the idea of abstraction in generic programming comes to us directly from abstract algebra, as programmers we also care about efficiency. A generic algorithm that runs more slowly than its type-specific counterpart will not get used. That’s why efficiency is also part of the definition of generic programming. We’ve shown examples throughout the book of specific techniques for improving efficiency, from rewriting code to use strength reduction, to using memory-adaptive algorithms, to exploiting compile-time type dispatch so the computer can invoke the fastest available implementation for a given situation. More generally, we have found that attempts to find generic versions of algorithms often lead to simpler and more efficient solutions.

We’ve also seen how the correctness of a programming interface can be just as important as the correctness of the program itself. A correct interface can enable a wider range of applications. It can also bring efficiency benefits—for example, by returning all the relevant computations (the law of useful return) to avoid a duplication of effort. In contrast, an incorrect interface cripples the application by limiting what it can do. For example, we saw how a find function that returns only a Boolean value instead of the position of a found item makes it impossible to see if a second matching item exists. And just as you need to rewrite a program a few times to get it right, so you need to redesign the interface; the correct interface usually won’t be clear until you’ve already implemented an algorithm and explored its use cases.

Another idea that’s essential to understanding generic programming is the distinction between type and concept. In much the same way that axioms in a mathematical theory are requirements that tell us what it means to be a certain kind of abstract mathematical entity (such as a group), concepts in programing are requirements on types; they tell us what it means to be a certain kind of computational entity. Choosing the right concepts for an algorithm or data structure is essential to good programming. Choosing a concept with too many requirements places unnecessary limitations on the range of situations in which an algorithm can be used. Choosing a concept with too few requirements makes it impossible to define algorithms that do anything useful.

Next time you set out to write a program, try to adopt the generic programming attitude. Start with specific implementations of your functions, then revise and refine them to be more efficient and more general. As you refine your code, think carefully about how the pieces fit together and how to provide an interface that will still be useful in the future. Choose concepts that provide just the right requirements for your data, without imposing unnecessary assumptions. And remember that you are the inheritor of a long mathematical tradition of algorithmic thought. In following the principles of generic programming, you are already benefiting from the work of those who came before, from Euclid to Stevin to Noether. By designing beautiful, general algorithms, you are adding your own small contribution to their work.