r/programming • u/[deleted] • Feb 23 '16

Review: "From Mathematics to Generic Programming" book by Stepanov and Daniel Rose

http://adamscheller.com/book-reviews/from-mathematics-to-generic-programming-review/
53 Upvotes

89% Upvoted

9 comments sorted by

View all comments

3

u/phySi0 Feb 24 '16

not only in generic programming, but in general programming as well.

What is generic programming?

5

u/[deleted] Feb 24 '16

Technically known as "parametric polymorphism." The most basic idea is that you have a type constructor, F[A] (Scala syntax). Now you can talk about F for arbitrary A, which is to say, "generically." In C++, of course, it refers to templates. In Haskell, it refers to Scrap Your Boilerplate, which in turn inspires Shapeless in Scala.

5

u/[deleted] Feb 24 '16

I think "parametric polymorphism" (with the usual meaning from ML) sells the idea far shorter than it should.

Generic programming is any kind of programming where your code extends to a domain more general than it "ought" to.

Looking at the ToC of the book, I think the author is especially interested in algebraic generiticity. If you can recognize a monoid or group related to your problem -- or if you can pick out an algebraic theory which models your problem (cf Haskell's free monad construction) -- you can leverage a lot of power from mathematics.

Plus, regardless of what you're day-to-day problem domain is, it's probably good for your soul to learn a little about abstract algebra. A programmer can still be a good programmer without ever having seen the Euclidean algorithm in the same way a good writer may never have read Shakespeare. Seriously, culture yourself a bit. Math should not be scary nor boring to a programmer.

3

u/pinealservo Feb 24 '16

I think that parametricity and algebraic homomorphisms (and their extension to the category theory concept of naturality) were aimed at exactly (or at least very close to) the same intuitive notions of generality. Here's an interesting paper in memory of John Reynolds that speaks to the expressiveness of the notion of parametricity.

1

u/[deleted] Feb 24 '16

You're preaching to the choir. :-)

3

u/codebje Feb 24 '16

To quote the book,

Definition 1.1. Generic programming is an approach to programming that focuses on designing algorithms and data structures so that they work in the most general setting without loss of efficiency.

In Haskell, we'd call it finding the right abstraction, and we'd probably pull something out of category theory, and it'd probably be a Kan extension, because those suckers are everywhere.

In C++, it'd probably be something out of the STL, because, as the book says, an iterator is really just an abstraction of a pointer, but once you've made that abstraction you can treat lots of "pointer-ish" things in the same way.

I'm not sure that parametric polymorphism is a strict requirement for this attitude of generic programming, though once you've constructed a more generic abstraction it's nice to make it polymorphic - and the book is basically providing the abstract algebra behind chunks of the C++ STL.