MagmaΒΆ

A magma is a set that has a binary operation that returns a value in the set and possibly has an annihilator (see Wikipedia). To a programmer, it looks like a class definition with some abstract methods, but then defined by mathematicians. A semiring can be a useful concept, for example in finite-state automata. A semiring is a magma with a plus operation and a times operation that adheres to certain requirements.

This library uses a few concepts. They are explained below using double as an example, but the point is of course that this can be extended to user-defined types.

First, a binary operation must be defined by a type. This type must be default-constructible. Examples are math::callable::times and math::callable::plus. For convenience, static variables of these classes are math::times and math::plus. After #include "math/arithmetic_magma.hpp", this should compile:

assert (math::times (3., 5.) == 15.);
assert (math::plus (3., 5.) == 8.);

You may think that this does not give much of an advantage over using operators that are built-in or overloaded. However, read on.

An operation can have an identity element. This is an element that when the operation is applied to it and another element, the result is equal to the other element. For example, multiplying any number by 1 yields the original number. Similarly, 0 is the identity element for addition. This should compile:

assert ((math::identity <double, math::callable::plus>()) == 0.);
assert (math::zero <double>() == 0.);

math::zero and math::one are shorthands for the identity of plus and times.

An operation can have an inverse operation. This inverse of an operation is the binary operation that undoes it. For example, since 2. * 3. equals 6.:

assert (math::inverse_operation (math::times) (6., 3.) == 2.);

math::inverse_operation (math::times) simply returns an object of type math::callable::divide. Note that this is possible for real numbers. However, for some operations on some classes, the order of the operands makes a difference. That is, the operation is not commutative. An example is the sequence semiring, which is the set of sequences that are concatenated by operator*. Division removes elements from either the front or the back, which is left division or right division. It is possible to differentiate between left and right division with the tag classes math::left and math::right. For example,

assert (math::divide <math::right> (6., 3.) == 2.);
assert (math::divide <math::left> (6., 3.) == 2.);
assert (math::divide <math::either> (6., 3.) == 2.);

For real numbers, left and right division perform the same operation, but for sequence semirings they are different. :cpp:struct:`math::either`, the default argument for direction, indicates that they are the same.

Another use of function classes is to query properties. Thus,

static_assert (math::has <
    math::callable::identity <double, math::callable::times>()>::value,
    "'identity' should be defined for double and operation 'times'.");
static_assert (math::has <
    math::callable::times (math::callable::plus (double, double const), double)
    >::value,
    "All operations in the sequence of operations should be defined.");
static_assert (math::is::associative <
    math::callable::times (double, double &)>::value,
    "'times' is associative.");
static_assert (math::is::commutative <
    math::callable::plus (double , double)>::value,
    "'plus' is commutative.");
static_assert (math::is::distributive <
    math::callable::times (math::callable::plus (double, double const), double)
    >::value, "'times' distributes over 'plus'.");

Notice that a cute syntax is used where classes in namespace math::callable are used to indicate function calls. This goes for math::has and math::result_of as well. Internally, this uses the nested callable protocol for function objects.

All these properties must be implemented explicitly. To help with this, such functions as math::check_semiring() exist (after saying #include "math/check/check_magma.hpp"). This checks, on a list of examples, that float is indeed a semiring:

std::vector <float> examples;
examples.push_back (-.3f);
examples.push_back (0.f);
examples.push_back (4.f);
math::check_semiring <float, math::either> (math::times, math::plus, examples);

Functions in namespace math work only on one magma. E.g. math::times (3., 8.f), which tries to multiple a double with a float, does not work. This does not mean that arguments must be of the same type. For example, the sequence semiring can distinguish at compile time between sequences with zero, one, or a variable number of elements. Any of the types that are in one magma can be used with a binary operation.

Different magma types can often be converted into each other. If this conversion always succeeds, it is implicit. If its success depends on the run-time value, then the conversion is explicit, and will throw math::magma_not_convertible if it is not. (For most types of magma, it is impossible to disable at compile time even transparently impossible conversions, since the compiler will go through an implicit conversion to access the explicit constructor.)

Previous topic

Log-float

Next topic

Operations

This Page