Boost logo

Glas :

[glas] Concept definitions for scalar-like types

From: Peter Gottschling (pgottsch_at_[hidden])
Date: 2005-07-21 00:13:08


Some weeks ago I submitted a pdf file proposing some fundamental
concepts. Toon and Karl proposed several modifications. As we had the
feeling that this are mostly subtle details we were changing
incrementally we discussed the topics offline. Now we have presented
our work on the web page and wish to discuss these concepts -- Magma to
Field -- with the whole mailing list.

Important issues are:

1. Pure algebraic concepts, like Group, are defined in a way that
modeling types can be implemented in terms of functors. Therefor, these
concepts are multi-type concepts consisting of a primary type
representing a set (like int) and a functor type realizing a binary
operation.

2. As a consequence, algorithms for pure algebraic concepts can be used
for different operations, e.g., square-and-multiply can be used with an
additive functor to implement a multiplication, with a multiplication
to implement an exponentiation, or even with a string concatenation to
reduce the number of concatenations (the implementation was trivial,
only the empty string had to be defined as identity).

3. Obviously, every type can have an arbitrary number of operations
(even if we most likely focus on addition and multiplication).

4. Identity and inverse are defined as type traits templated by the
primary type and the operation, e.g. the identity for integer
multiplication is glas::identity<int, glas::add<int> >()(). Identities
and inverses of standard addition and multiplication functors are
predefined. Other functors' identities and inverses has to be provided
by users. This definition might look a little bit complicated on the
first glance but is required to be generic. For instance, somebody can
provide its own additive identity like template<> struct
identity<mytype, glas::add<mytype> > { ....

5. On other hand, it is much easier to implement algorithms with the
operators +, -, *, / instead of functors. Additive and multiplicative
concepts are thus defined in terms of operators.

6. One crucial property of these concepts is that additive and
multiplicative concepts are true refinements of their pure algebraic
counterparts even if the latter are 2-type concepts and the other
1-type concepts.

7. This relationship is established by two default functors that base
on operators, e.g., if T models AdditiveSemiGroup then the tuple {T,
glas::add<T>} models SemiGroup. (Except for operators like += the
opposite implication is also true.)

8. Long discussions caused the question whether a Field is
MultiplicativeGroup because the 0 is not invertible. Excluding the 0
from the set F\{0} results in a MultiplicateGroup. But is the complete
Field a MultiplicativeGroup despite the 0?

9. To deal with this, we introduced another concept --
PartiallyInvertibleRing where not all elements have to be invertible
w.r.t. multiplication and a Field is clearly a refinement of this
concept with the requirement that only one element is not invertible.
Other examples for PartiallyInvertibleRings are vectors (or matrices)
with element-wise addition and multiplication. In this case, all
vectors containing 0s are not invertible and the concept Field is
definitively not modeled.

10. The large number of concepts allows a precise definition of
algorithms requirements. In the pdf file were many example programs
that showed that the complexity of the concept hierarchy does not
complicate the programming with these concepts. When it is updated to
the modified concept definitions it can be posted again.

More thoughts and some open questions will come in further mails (very
likely also from Toon and Karl).

Best,
Peter
------------
Peter Gottschling
Research Associate
Open Systems Laboratory
Indiana University
301i Lindley Hall
Bloomington, IN 47405
Tel.: +1 812 855-8898 Fax: +1 812 856 0853
http://www.osl.iu.edu/~pgottsch