C++ concept maps

I was going over some of the additions coming to the C++ standard. There’s an interesting thing in there about templates. They’ll be adding a feature where when defining a template class you require that the passed in class adhere to certain ‘concepts’.

concept will be a new key word. A concept will basically specify what kinds of methods the class will need.

The interesting thing to me is they used the word concept. They were obviously directly influenced by the relatively new mathematical theory of “concept lattices” which is derived from lattice and set theory.

In that theory, a concept is defined by an attributes set and the elements it applies to. There is also a ‘context’ which essentially the biggest possible concept. A common example is the context being all the planets in the solar system and some list of properties about the planets. A concept from this context could be, ‘all the planets with moons’. Really to reference a concept you only need the attributes and it’s context, as the elements will be easily derived. I might be fudging this a bit, it’s been awhile.

In this case, the elements will be all the defined classes. The attributes will be members of all these classes. Mathematically a concept is a subset of a context. The interesting things about concepts defined this way is they form a lattice. They are inherently ordered. Most importantly though, they form a complete lattice. That is, all subsets (of the concept lattice) are closed under join and meet, or in this case all abitrary union and intersections of concepts yield a new concept (including infinite ones if that is a possibility in the context, not that this would happen in compsci).

This means that no matter how many weird concepts you have, you can require or exclude them and the resultant set of matching classes is easily determined. This may seem obvious I guess. What impressed me though is that the people coming up with this chose to implement it directly using concrete pure mathematics.

This probably the best example to me of why I like C++.

Complete lattices also have very useful properties. I’d be interested to know if any of them could be used for compiler optimisations when matching a class to a template.

[edit: Damn Wordpress thinks my C++ tag is a C# tag. so I have to use C plus plus]