From Mathematics to Generic Programming (2011)
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.
Readers who are interested in learning more about the topics discussed in this book may wish to look at some of the references mentioned here. Complete citations are included in the Bibliography.
Generic Programming. The language Tecton, which first used generic programming concepts, is described in “Tecton: A Language for Manipulating Generic Objects” by Kapur, Musser, and Stepanov (1981). The Ada library is described in the paper “Generic Programming” by Musser and Stepanov (1988), and C++ STL in “The Standard Template Library” by Stepanov and Lee (1994). All of these materials are available on www.stepanovpapers.com.
History of Mathematics. A good comprehensive reference, not only for this chapter but also for much of the mathematical history in the book, is Katz’s A History of Mathematics: An Introduction (2009). This general textbook combines thoroughness and mathematical rigor with accessibility to the layperson. An incisive book that explains the historical development of some major mathematical ideas is Mathematics and Its History by John Stillwell (2010).
Rhind Papyrus. To see a reproduction of the Rhind Papyrus, together with its translation, see The Rhind Mathematical Papyrus: An Ancient Egyptian Text by Robins and Shute (1987). Van der Waerden includes a discussion of the Rhind Papyrus in Geometry and Algebra in Ancient Civilizations (1983).
Egyptian and Greek Mathematics. In addition to Katz, two excellent resources are Van der Waerden’s Science Awakening (1963) and the two-volume History of Greek Mathematics by Sir Thomas Heath (originally published in 1921 but available in a 1981 reprint). Both are very accessible to the general reader.
Figurate Numbers. The best introduction to Pythagorean arithmetic is the book by Nicomachus of Gerasa, which can easily be found in the 10th volume of the Britannica’s Great Books of the Western World, edited by Mortimer Adler. This volume also contains the complete works of Euclid and Archimedes.
Basic Number Theory. A good introduction to basic number theory is in Chapter III of George Chrystal’s Algebra: An Elementary Text-Book.
Greatest Common Measure. For general history of Greek mathematics, including the topics covered in this chapter, the best reference is still Heath’s A History of Greek Mathematics, mentioned in the topics for Chapter 3. For a fascinating and mathematically sophisticated account of the mathematical studies in Plato’s Academy, including the algorithm for the greatest common measure, see David Fowler’s The Mathematics of Plato’s Academy, a New Reconstruction. For those interested in reading the source, Plato’s complete works are available in a one-volume edition, with a clear modern translation, edited by John M. Cooper. A good explanation of the GCD may be found in Chapter III of George Chrystal’s Algebra: An Elementary Text-Book.
Decline of Greek Science. An important account of the rise and decline of Greek mathematics is presented in the book by Lucio Russo, The Forgotten Revolution: How Science Was Born in 300 BC and Why It Had to Be Reborn.
History of Zero. Our account of the history of zero is largely taken from van der Waarden’s Science Awakening, pp. 56–57.
Leonardo Pisano (Fibonacci). A short autobiography of Leonardo Pisano has been translated by Richard Grimm. His great work Liber Abaci is available in an English translation by Laurence Sigler. A brief but thorough description of Leonardo Pisano’s number theoretic treatise is given in McClenon’s 1919 article “Leonardo of Pisa and His Liber Quadratorum.” Readers interested in history of arithmetic algorithms may want to read Leonardo Pisano’s original Liber Quadratorum, available in a modern English translation by L. E. Sigler (see Fibonacci in the Bibliography).
Remainder and Quotient. The full treatment of the extension of GCD to remainder and quotient is in Chapter 5 of Elements of Programming by Stepanov and McJones (2009). Floyd and Knuth’s algorithm for remainder appears in their 1990 article “Addition Machines.”
Fermat’s and Euler’s Number Theory Work. A source for much of the material in this chapter is Number Theory: An Approach through History from Hammurapi to Legendre by André Weil. While this book does not assume any advanced math, it is probably too detailed for most casual readers. The classic number theory texts by Gauss (Disquisitiones Arithmeticae) and Dirichlet (Lectures on Number Theory) are still of great value, but would be of interest to serious scholars only.
Euler’s Books. Our biography of Euler also mentions his foundational works on calculus. Although they are not directly related to the topics of this book, they are still worth careful reading. Euler’s first book on the subject, Introduction to Analysis of the Infinite is available in English. Sadly, only the first half of his second book, Foundations of Differential Calculus, has an English translation, and all of his Integral Calculus still awaits an English translation. The book Letters to a German Princess is available on the Internet.
Group Theory. A classic book on group theory is Burnside’s Theory of Groups of Finite Order. Though first published in 1897, it still gives an unparalleled introduction to what group theory is about and includes many more examples than most modern books. It was reprinted by Dover Press in 2004.
Model Theory. Sadly, we are not aware of an introduction to model theory accessible to a layperson. For a more advanced reader, a good introduction is H. Jerome Keisler’s “Fundamentals of Model Theory,” a chapter in the Handbook of Mathematical Logic.
Requirements on Types. Many topics in this chapter are discussed more formally in Elements of Programming by Stepanov and McJones.
Reduction. Iverson discusses reduction in his paper “Notation as a Tool of Thought” (1980). The idea is also discussed in Backus’ “Can Programming Be Liberated from the Von Neumann Style?” (1978). Using reduction for parallel computation was discussed in “Operators and Algebraic Structures” by Kapur, Musser, and Stepanov (1981). Dean’s use of reduction is described in “Map-Reduce: Simplified Data Processing on Large Clusters” (2004).
Simon Stevin. Despite Stevin’s great contributions to science and mathematics, very little has been published about his work. A good overview is Sarton’s “Simon Stevin of Bruges.”
Polynomial Division and GCD. For a refresher on polynomial division and polynomial GCD, see Chapters 5 and 6 of Chrystal’s Algebra.
Origins of Abstract Algebra. A good introduction to Gaussian integers is Chapter 6 of Stillwell’s Elements of Number Theory. The classic text that introduced the general notion of algebraic integers is Richard Dedekind’s Theory of Algebraic Integers. Stillwell’s translation includes an excellent introduction that explains many of the ideas. Leo Corry’s Modern Algebra and the Rise of Mathematical Structures is an exhaustive scholarly treatment of the emergence of abstract algebra from Dedekind to Noether and later developments.
Abstract Algebra. For the reader who wants to take the next step in understanding abstract algebra, a serious but accessible (and historically informed) text is Stillwell’s Elements of Algebra.
Rings. Stillwell’s Elements of Number Theory covers these topics thoroughly and is quite accessible. (While its title might suggest that this topic is covered in Stillwell’s Elements of Algebra, that book focuses on Galois’s work and therefore does not cover rings.)
Social Nature of Proof. The idea that proof is a social process is discussed in “Social Processes and Proofs of Theorems and Programs,” by De Millo, Lipton, and Perlis (1979).
Euclid. Sir Thomas Heath’s translation of Euclid, The Thirteen Books of the Elements, is widely available. This edition includes very extensive commentary by the translator. In addition, there is new reproduction of Oliver Byrne’s 1847 unique edition, which demonstrates all the proofs through visual illustrations. Robin Hartshorne’s Geometry: Euclid and Beyond is a textbook aimed at university math majors, but the first chapter (describing Euclid’s geometry) is quite accessible.
Axioms of Geometry. Chapters 1 and 2 of Hartshorne’s Geometry: Euclid and Beyond provide a good introduction to Euclid’s axiomatic method and Hilbert’s modern version of Euclidean axioms. Hilbert’s Foundations of Geometry is still the definitive treatment of his axioms for Geometry.
Non-Euclidean Geometry. A classic treatment of this topic is Roberto Bonola’s Non-Euclidean Geometry: A Critical and Historical Study of Its Development. A modern (but still accessible) mathematical treatment may be found in Chapter 7 of Hartshorne’s Geometry.
Peano Arithmetic. For readers interested in how arithmetic can be built rigorously from the ground up, Edmund Landau’s Foundations of Analysis describes how to construct integers, rationals, reals, and complex numbers starting with Peano-like axioms. Peano’s magnum opus Formulario Mathematico actually covered many areas of practical mathematics, not just the axioms that became famous. Unfortunately, this great book has never been translated from its original invented language. For more about Peano’s work, see Twelve Articles on Giuseppe Peano by Hubert Kennedy.
Aristotle’s Organization of Knowledge. A good introduction to Aristotle’s life and philosophy is Sir David Ross’s Aristotle. There are several good editions of Aristotle’s complete works, including the two-volume Bollingen Foundation edition and the multivolume Loeb Classical Library edition. Readers interested only in Aristotle’s Categories, the work discussed in this chapter, can choose the appropriate volume.
Concepts. Chapter 1 of Elements of Programming by Stepanov and McJones covers this material more formally and in more detail.
Iterators and Search. Chapter 6 of Elements of Programming covers this material more formally and in more detail.
Permutations and Transpositions. A good introduction to permutations is in Chapter XXIII of Chrystal’s Algebra. Chapter 1 of Burnside’s Theory of Groups of Finite Order, mentioned under Chapter 6, gives more details about these topics.
Rotate and Reverse. The algorithms in this chapter are described in more detail in Chapter 10 of Elements of Programming.
Stein’s Algorithm. Stein’s original paper on the faster GCD algorithm is “Computational Problems Associated with Racah Algebra.” Knuth describes the algorithm in Section 4.5.2 of The Art of Computer Programming, Vol. 2.
Recreational Mathematics. Many developments in mathematics came from studying seemingly frivolous problems, and many distinguished mathematicians became interested in mathematics through exposure to mathematical games. A classic book on the subject is Mathematical Recreations and Essays by W. W. Rouse Ball.
Cryptography. An entertaining history of cryptography is David Kahn’s The Code-breakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. To learn more about methods used in modern cryptography, a standard text is Introduction to Modern Cryptography: Principles and Protocols by Katz and Lindell.
Number Theory. A good modern introduction to number theory, which includes a discussion of the RSA algorithm, is John Stillwell’s Elements of Number Theory (2003). It also includes some material that we cover in Chapters 5 and 8.
AKS Primality Testing. The deterministic polynomial-time algorithm for primality testing is described in Granville’s paper “It Is Easy to Determine Whether a Given Integer Is Prime” (2005).