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

From: Hubert.Holin_at_[hidden]
Date: 2001-01-12 19:00:27

Paris (U.E;), le 13/01/2001

        I would absolutely welcome algebraic classes!

        I would just like to say that we should not forget that some very 
exciting possibilities lie with non-abelian (say quaternions ;-)  ), 
and even non-associative (say octonion :-)  ) structures. Actually, an 
alternate implementation of quaternions to that I submited here, and on 
which I will be working next, would fit well in such a framework (seen 
from a number-theoretic angle). The reason this alternate 
implementation is (also) necessary is because I want to tackle some 
cryptography problems.

        On the commutative front, as I said before, we really do need good 
geometry classes, though the need is both for continuous types and 
integer types.

        One should be aware, however, of the deep problems one might face 
if one wants to represent continuous types (reals & all): they can't be 
exact, different reals map to the same representation.

        Thus, perhaps, it would be better to split this hierachy in two: 
one for integer types and one for continuous types. As a mathematician, 
I can only dream of playing with even bigger sets...

        Hubert Holin
        Hubert.Holin_at_[hidden]

--- In boost_at_[hidden], Doug Gregor <gregod_at_r...> wrote:
> 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_c...
> 
> 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.