
Boost : 
From: Doug Gregor (gregod_at_[hidden])
Date: 20010112 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 conceptbased 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 conceptchecking).
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 runtime 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
basepointer 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 conceptchecking 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk