
Boost : 
From: Douglas Gregor (gregod_at_[hidden])
Date: 20010829 17:48:33
On Wednesday 29 August 2001 03:37, you wrote:
[snip]
> I agree to all three points.
> The problem is, however, that to my current knowledge
> I do not know a solution that satisfies all three points
> simultanously.
I mentioned it because we developed a library explicitly for this purpose. We
required algebraic structure information for userdefined types, but did not
want to force the user to include a large number of specializations. I've
mentioned the library before (the Algebra library).
The Algebra library is based on a language for concept specification
(Tecton), which has been used to specify, amongst other things, formal
notions of algebraic structures, iterators, and containers. Tecton builds
concepts primarily based on refinement (i.e., a forward iterator is a
refinement of an input iterator and an output iterator), and each concept can
specify requirements and/or introduce new notions (i.e., a Monoid concept
would introduce the identity element '1' and state the requirement that 1 * x
= x). Additionally, lemmas can be used to describe additional relationships
between concepts:
If I have Monoid, AbelianMonoid, Commutative, Inverses, and Group concepts,
how do I form an AbelianGroup? An AbelianGroup is a Group whose binary
operation is commutative, so should it refine Group and Commutative? But it's
also an AbelianMonoid with Inverses. Either way, one must make a refinement
decision, and there is a relationship left out: if AbelianGroup refines Group
and Commutative, then we add a lemma stating that AbelianGroup is
AbelianMonoid.
I mention this only to try to describe the logical basis behind the Algebra
library's construction (that I'll try to detail now...).
Let's model concept refinement by inheritance in C++. This is already done
in the C++ standard with the iterator tags (std::forward_iterator_tag derives
from both std::input_iterator_tag and std::output_iterator_tag), and is very
useful: we can check if a given concept is a refinement of anothing concept
just by checking for the base class conversion. So we could envision a set of
tag classes:

struct monoid_tag {};
struct commutative_tag {};
struct abelian_monoid_tag : public monoid_tag, public commutative_tag {};

However, this misses part of the point. A monoid includes the notion of a
domain (i.e., the C++ type) and an operator (i.e., a C++ operator, like '+').
So, for instance, we can't just say "strings form a monoid". We have to say
"strings form a monoid over the + operator with the empty string as its
identity element". Instead of using tags, let's use fullfledged class
templates that represent _all_ of the information we need:

template<typename Domain, typename Operator, int Identity>
struct Monoid {};
template<typename Domain, typename Operator>
struct Commutative {};
template<typename Domain, typename Operator, int Identity>
struct AbelianMonoid :
public Monoid<Domain, Operator, Identity>,
public Commutative<Domain, Operator>
{};

Here, Domain is the type (e.g., std::string), Operator is a type that
represents the binary operator (e.g., std::plus<std::string> could represent
'+' on strings), and Identity is some integer value that can be mapped to
std::string().
Now, if we want to state that std::strings form a monoid over + with identity
element std::string() (represented by the integer 0), we specialize an
"algebra_traits" structure:
template<>
struct algebra_traits<std::string>
{
typedef Monoid<std::string, std::plus<std::string>, 0> structure;
};
Of course, it is possible to use some C++ trickery to implement:
is_monoid<std::string, std::plus<std::string> >::value
... or to retrieve the identity value at runtime,
identity_element<std::string, std::plus<std::string> >::value()
Discussing the implementation of lemmas would take a lot more space. Its
based on the base class injection technique I mentioned a while ago on this
list. The source for the algebra library is posted at:
http://www.cs.rpi.edu/~schupp/entries/SOFTWARE/simpl/download/algebra/index.html
Specifically: axioms.h, structures.h, and properties.h are of interest in
this context.
There is a paper at:
http://www.cs.rpi.edu/~schupp/entries/SOFTWARE/simpl/doc/AlgCpp.pdf
that describes the algebra concepts more indepth.
I've been planning on cleaning up the library for Boost, but only if there is
interest in using it. It's flexibility comes at a cost: it requires a very
good compiler to work properly, and it is somewhat large.
> In my personal preferences, I would drop the static
> assertion 
> if a class offers a %= operator
> in the usual semantics,
> there are good chances that it is already an Euclidian ring,
> so we have already a compile time check for the most usual cases.
>
> I, however, do not know the preferences of other people.
I think that most people agree with you. I personally haven't decided  I
like the safety factor of having the static assertion, but I understand that
it is an annoyance to have to assert semantic properties of a type.
Doug
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk