| From Mathematics to Generic Programming |
|
Authors: Alexander Stepanov and Daniel Rose Despite what you might think mathematics and generic programming are not closely related. Why then a book with a title that connects them? This is a very strange book, and not the book that you might expect from the title. The influence of mathematics on programming is everywhere, but at the moment what is getting most attention is type theory in all its forms. The prevalent idea today is that programs are mathematical theorems about types, but to go into this would take us well away from the subject matter of the book. This book's title mentions "generic programming" and this what you have to introduce into a language that is strongly typed if you want to write algorithms that work irrespective of type. To explain in case you don't already know, some algorithms depend on the type of the data they are applied to. For example, if you want to add two things together then they have to be numbers. Some algorithms don't depend so much on data type. For example, building a linked list doesn't really care what the data type is; it just manipulates references from one thing to another. The trouble is that in a strongly typed language you can't write a general algorithm that works with any data type unless you introduce the idea of of generics. There are many different sorts of generics, but they all serve to allow the programmer to express an algorithm that functions irrespective of type. Now mathematical algorithms are often only loosely typed in the programming sense, and so what could be more natural than a book that explains the idea of generics in a mathematical context. This is not what this book is about. To understand what the book is about, you need to bear in mind that Alexander Stepanov was responsible for introducing the Standard Template Library to C++. So while most of the chapters have nothing to do with programming in any shape or form, when you do find a chapter on programming it focuses on a very narrow view of the subject as typified by an STL-using C++ programmer. Despite this you might find chunks of this book interesting because it is really an introduction to some assorted mathematical topics mostly looked at from the programmer's point of view.
The first chapter that says anything much is Chapter 2, about the first algorithm - though it is arguable that Egyptian multiplication isn't really the first algorithm in any reasonable sense other than the first one in the book. However if you have never considered different ways of realizing multiplication then you might find it interesting. Chapter 3 is about ancient Greek number theory - and yes that is Greek and not geek. This is the reasonably well known story of how the Greeks thought about number as a geometric idea. It introduces, and programs, the sieve of Eratosthenes, considers the greatest common divisor and ends up with the discovery the root 2 is irrational - a fact that destroyed the Pythagorean view of the world. The focus on numbers continues with a look in Chapter 4 at Euclid's algorithm. It includes programs that implement the theory, but there isn't that much general to gain from reading them. On page 37 we are presented with a homespun law - the law of useful returns, which basically says if a function computes something useful then it should return it. Of course, the problem with this law is that what appears useful to one programmer might not to another. It isn't really a law; more an excuse to moan that programmer A didn't write a library routine correctly because programmer B could have made use of some intermediate result if it had been returned. You can invent many similar laws without really trying - what about the law of doing one thing and doing it well and not returning useless clutter.
The book continues in its exploration of mathematics with some programming references. Chapter 5 deals with the emergence of modern number theory - Mersenne and Fermat Primes, Fermat's little theorem and, eventually, modular arithmetic. Chapter 6 is about modern algebra - groups, semigroups, monoids and so on. At the end of this chapter we meet some category theory but not enough to be useful in understand what is going on in some extreme branches of functional programming i.e. it doesn't help with understanding monads. Chapter 7 is more about programming in that it attempts to explain the idea of type in a generic algorithm. Roughly speaking, this comes down to what properties does an object need to be suitable for a generic algorithm to process it. Oddly, the language of objects isn't used much and we seem to be mostly working with primitive data types. This very short chapter isn't going to be very helpful if your real interest is in generics in C++. Chapter 8 gets back onto the math train with a look at more algebraic structures including rings, semi-rings and fields. Again all interesting but not much to do with programming in general. The remaining chapters continue explaining various parts of modern math and trying to make the connection with programmer. Chapter 9 explains the Hilbert approach to math and focuses on the Peano axioms for the natural numbers. Chapter 10 is called Fundamental Programming Concepts but they are, arguably, not really fundamental - iterators, ranges, linear search, binary search and so on. More importantly they are really disconnected with the rest of the book. Next we look at permutation algorithms, extensions of the GCD and a chapter on real worked applications - cryptography, primality testing and the RSA algorithm. All the way through the book there are interesting potted histories of the mathematicians who created the theories being explained. This is really a book introducing you to the ideas of modern math rather than a book on programming. What little programming content there is comes from a C++ view of the world and while this isn't wrong it is very narrow. The book is an interesting read if you want to learn about math and perhaps see it coded in C++. What "to Generic Programming" in the title has to do with it all is a mystery and the few discussions of programming are mostly disconnected from the math, apart from weak analogies that are drawn between them. If you are interested in practical programming skills, don't bother reading this book.
|
|||
| Last Updated ( Wednesday, 18 March 2015 ) |
