Re: [boost] Re: Review Request: dlw_gcd.zip

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-08-29 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 user-defined 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 full-fledged 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 run-time,
  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 in-depth.

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