Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
From mathematics to generic programming
Stepanov A., Rose D., Addison-Wesley Professional, Upper Saddle River, NJ, 2015. 320 pp. Type: Book (978-0-321942-04-3)
Date Reviewed: Mar 26 2015

In the 1960s, the need for mathematical engineers was already emphasized by E. W. Dijkstra [1]. Although this title, earned by graduates of some universities in Europe, may be somewhat unfamiliar, “the professional competence of the mathematical engineer, familiar with discrete systems design and knowing how to use formal techniques for preventing unmastered complexity from creeping in” [2] is essential for success in the area known as software engineering. Some of us may still remember the outstanding books published decades ago in the Prentice Hall International Series in Computer Science (founding editor C. A. R. Hoare), but regretfully there are not too many current books of this kind, especially for uninitiated readers who happen to be C++ programmers. This book provides a flavor of what such an introductory text for mathematical engineers might have been. The target audience of this well-written and conceptually clear book is programmers with some mathematical maturity (the concept of proof and high school algebra and geometry). The current need for such a book is clear [3]:

  • Everybody works as a programmer.
  • Nobody really knows how to program.
  • The idea that there is something more to learn does not even cross their minds. If they want to learn, it is a new language or a new tool: Java, Hadoop, Squid, etc.

Stepanov created the C++ Standard Template Library (STL), but the book is not about STL specifics. Rather, it is about a patterned “attitude toward programming” (p. 1) in which “the strands of mathematics and programming are interwoven throughout” (p. 4). Within mathematics, the authors emphasize number theory, for which no specific prerequisites are needed, and the presentation follows the historical developments in generalizing the idea of numbers. The book is centered on the concept of abstraction, and the authors convincingly demonstrate that a generic, more abstract approach is the simplest and most powerful, for example: “Lagrange’s theorem [from group theory] lets us easily prove some important results [from number theory] in much simpler fashion than we did the first time” (p. 101). This concept comes from mathematics (and abstract algebra in particular) and has been known, but perhaps not sufficiently emphasized, in programming for decades:

There are two classes of system designers. The first, if given five problems will solve them one at a time. The second will come back and announce that these aren’t the real problems, and will eventually propose a solution to the single problem which underlies the original five. [4]

Stepanov notes that “generic programming is [...] based in finding the most abstract representations of efficient algorithms” [5]. In this book, Stepanov and Rose stress: “Generalizing code is like generalizing theorems and their proofs. […] So programmers can take a function that was designed for one type of computational object … and extend it to work equally well on another” (p. 84). They also note that Emmy Noether’s approach to expressing theorems in the most abstract terms “Noether provided the theory of what we now call generic programming” (p. 141). Interestingly, chapter 6, on abstraction in mathematics, states that relationships between elements are more important and interesting than the elements themselves; this observation is, among other things, essential in business modeling (which is not mentioned in the book). Stepanov’s observation is even more general and more interesting: “To deal with the real problems you need multi-sorted algebras--families of interfaces that span multiple types” [5].

In discussing programming, nice and useful programming hints (“principles”) are shown throughout. The book is mostly understandable to nonexperts in C++, with the possible exception of chapter 10 on fundamental programming concepts, which is very C++-specific (and arguably not as elegant as the mathematics chapters). The presentation culminates in a rather terse chapter 13 on a public-key cryptosystem based on number theory results shown earlier in the book. And one can only agree with the authors when they state that “every useful program is a worthy object of study, and behind every optimization there is solid mathematics” (p. 235).

In discussing mathematical concepts, the authors time and again show that mathematics is a human activity that is always done in some social and historical context [6], and include nicely written short essays on important mathematical ideas and profiles of quite a few outstanding thinkers, from Pythagoras to Peano and Poincaré. (Quotes from Euclid, including his greatest common measure algorithm, “the first algorithm termination proof in history,” are also provided.) Chapter 9, on organizing mathematical knowledge, presents a highly readable narrative on axioms and axiomatic systems, proofs, Euclid and alternatives to Euclidean geometry, Hilbert’s approach, and Peano’s axioms. However, in some cases, especially in chapter 8 on more algebraic structures, the authors’ bird’s-eye view may be somewhat sketchy.

Program design considerations are often made explicit by the authors, and program correctness and termination proofs based on invariants are used in program development from the beginning. This excellent approach is encouraging, although regretfully in a few cases the authors take the proverbial rabbits out of the magic hat, for example, in the rotate algorithm (p. 205), providing just examples and program tracing for illustration. In this context, it is difficult to agree with the authors’ assertion: “before trying to prove a program correct, we should try to write correct programs--even if our attempts involve trial and error” (p. 176). Proving an existing program is substantially more difficult than developing a program and its proof simultaneously (E. W. Dijkstra and others). Furthermore, the concept of incorrect code is fundamentally different from the concept of incorrect interface (p. 192 and elsewhere): the former means that the result of a function is wrong, whereas the latter simply limits the utility of an otherwise correct function (for example, makes it at times very inefficient). Here again, we may recall the need for abstraction (separation of concerns) articulated, for example, in Dijkstra’s observation: “the problem of discovering [the customer’s] needs and intentions” is an issue totally separate from the one of “mak[ing] the system meet the requirements” [7]. And we still read that “in production code, assertions are typically disabled to avoid a performance penalty” (p. 269).

The book includes many interesting exercises without answers, a nice annotated bibliography for further reading (Dijkstra is not mentioned), and a fine index. I would certainly recommend this book. It would be interesting to compare it with two enjoyable, more advanced texts: one [8] for readers more initiated in mathematics (using Pascal, a simpler and arguably more elegant language) and another [6] for substantially more initiated readers.

More reviews about this item: Amazon, Goodreads, i-Programmer

Reviewer:  H. I. Kilov Review #: CR143289 (1506-0435)
1) Dijkstra, E. W. The programming task considered as an intellectual challenge (EWD273). December 1969, http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD273.html.
2) Dijkstra, E. W. There is still a war going on (EWD1165). December 3, 1993, http://www.cs.utexas.edu/users/EWD/transcriptions/EWD11xx/EWD1165.html.
3) Stepanov, A. Educating programmers: a customer perspective. April 27-28, 2012, http://www.stepanovpapers.com/bjarne_talk.pptx.
4) Kinslow, H. A. Software engineering: report on a conference sponsored by the NATO Science Committee, Garmisch, Germany, October 7–11, 1968. Edited by P. Naur and B. Randell, January 1969, http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1968.PDF.
5) Stepanov, A. An interview with A. Stepanov. Interview by Graziano Lo Russo, http://www.stlport.org/resources/StepanovUSA.html.
6) Taylor, P. Practical foundations of mathematics. Cambridge University Press, New York, NY, 1999.
7) Dijkstra, E. W. Selected writings on computing: a personal perspective. Springer, New York, NY, 1982.
8) Séroul, R. Programming for mathematicians. Springer, New York, NY, 2000.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
General (D.0 )
 
 
General (D.2.0 )
 
 
General (G.0 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date

Flanagan D. (ed)Type: Journal
May 1 1985
How to tell it what to do? The user talks to the machine
Snell F., Computer Science Press, Inc., New York, NY, 1987. Type: Book (9789780881750805)
Nov 1 1987
Softwar
Brenton T., Howson M., Holt, Rinehart & Winston, Austin, TX, 1986. Type: Book (9789780030049989)
Oct 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy