Re: Number/Algebraic concepts (was RE: [boost] RE: rational.hpp)

From: Doug Gregor (gregod_at_[hidden])
Date: 2001-01-12 16:28:08

On Friday 12 January 2001 01:07, you wrote:
> On Fri, 12 Jan 2001, Moore, Paul wrote:
> paul.m> > "while (m != IntType())" is much better. Even better
> paul.m> > would be for boost to have some sort of number_traits
> paul.m> > class that defines one() and zero() functions.
> paul.m> [snip]
> paul.m> I think I'll assume that IntType(0) and IntType(1) are the zero and
> one for paul.m> IntType. The only reason for using IntType(0) rather than
> IntType() is a paul.m> sense that "explicit is better than implicit", and
> as I need IntType(1), paul.m> there's no point in *not* using IntType(0).
>
> Let's just take the plunge and do the right thing :)
>
> To do this *really* right we need to define a concept such as Integer...
> and while we're at it we ought to define concepts for the various other
> kinds of numbers, such as floating point or reals. To be really generic,
> we should start at the bottom, with the basic algebraic concepts, and then
> build up from there. Below are some suggestions for some of these basic
> algebraic types. Perhaps someone with more expertise in algebra could also
> make some suggestions.

In the course of our research into concept-based optimizers, we have been 
working on this particular problem. While our web page for the research 
project is a bit lacking at the moment, some information about our approach 
is available at http://www.cs.rpi.edu/research/gpg/Simplicissimus. 
Additionally, our (algebraic) concept specification and checking code is 
available at http://www.cs.rpi.edu/~gregod/Algebra.tar.gz. It has only been 
tested under newer versions of g++ (2.95.2 and GCC 2.97 snapshots)

Now I'll attempt to explain our approach, and the reasons behind it. First of 
all, our requirements were for extensibility (integrating new concepts and 
new types should be easy) and static checking (we do a lot of template 
metaprogramming based on concept-checking). 

All of our concepts were originally specified in the Tecton concept 
description language described at (http://www.cs.rpi.edu/~musser/Tecton/). 
The paper titled "Examples of Tecton Concept Descriptions" contains some 
examples of the algebra hierarchy as described in Tecton.

Each concept maps directly to a C++ class. Refinement of concepts is handled 
by virtual public inheritance. The C++ classes are templated based on the 
parameters the concept is instantiated with. The following class represents 
the Abelian group concept:

template<
    typename Domain, 
    typename Op,        
    int      IdentityID, 
    typename InvOp, 
    typename BinInvOp 
>
struct AbelianGroup :
    virtual public Group<Domain, Op, IdentityID, InvOp, BinInvOp>,
    virtual public Commutative< BinaryOp<Op, Domain> >,
    virtual public ImplicationsOf<
                     AbelianGroup<Domain, Op, IdentityID, InvOp, BinInvOp>
                   > 
{ ... };    

Operators are all mapped to classes, and identity elements will be mapped to 
integers. To state that integers form an Abelian group over addition, we 
would have: AbelianGroup<int, plus, 0, negate, minus>. There is a mapping 
that allows us to take the domain (int) and the IdentityID (0) and get the 
actual value (0) at run-time when it is needed.

Continuing the Abelian group concept, this definition of the AbelianGroup 
class derives from the appropriate specializations of the Group class and the 
Commutative class because it is a refinement of both concepts.

The "ImplicationsOf" template class allows us to add lemmas that relate 
concepts to other concepts not related through refinement Suppose we choose 
that an Abelian monoid is a refinement of both Commutative and Monoid. Then, 
a Group refined a Monoid. Now, an Abelian group refines a Group and 
Commutative. It would be redundant to then specify that AbelianGroup refines 
AbelianMonoid, so instead we use a lemma: AbelianGroup implies AbelianMonoid. 
ImplicationsOf collects all concepts implied by the concept given to it and 
derives from them. Thus, AbelianGroup directly derives from Group and 
Commutative (the concepts it refines) and through lemmas it will derive from 
AbelianMonoid. This allows concept checking to be done just by checking for a 
base-pointer conversion (we use a small extension to the trick used in 
Boost's is_convertible to do our concept checking).

To state that a given concept models a concept, we specialize an 
"AlgebraTraits" structure. The following specialization registers integers as 
an Abelian Group:

template<>
struct AlgebraTraits<int, 0>
{
  typedef AbelianGroup<int, plus, 0, negate, minus> structure;
};

Overall: We believe that this is a good extensible system for concept 
specification and checking in C++. Tecton provides a solid structure for 
concept specification, and we've been able to leverage that for our concept 
checking library. 

        Doug Gregor
        gregod_at_[hidden]

HOW TO NAVIGATE Algebra.tar.gz...

In Algebra/include/algebra:
axioms.h, structures.h: These headers contain the concepts in the algebra 
hierarchy.
properties.h: This header includes the concept-checking code.
int.h, float.h, complex.h: These headers include the structures detailing the 
concepts modeled by int, float and complex, respectively.

In Algebra/tests:
The source files perform many concept checks. Compilation will fail if a 
concept check fails, and none of the programs produce meaningful output if 
executed.