Glas List: [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.: [phone]   Fax: [phone]
http://www.osl.iu.edu/~pgottsch