Extending the sublibrary

This section considers two ways of extending the sublibrary: by implementing a new magma and by implementing a new operation.

Implementing a new magma

A magma consists of one or more types that together form the magma. (By using multiple types, it is possible to infer things about a value at compile time.) All types of the magma must have the same magma tag. This tag is used to forward to the implementation of the operations. The structs, in namespace operation, related to operations that apply to the new magma must be specialised.

If your magma consists of different types, you want to consider conversion between them. If any value of one type is convertible into another type, that conversion should be implicit. If no value of the type is convertible, the conversion does not have to be possible, but it will often be impossible to disable it at compile time, because the conversion will often happen through another type. If not all values of the type are convertible, the conversion should be explicit, and if the value cannot be converted at run time, math::magma_not_convertible should be thrown.

It is possible to use existing types as magmas. For example, this is done for built-in floating-point types, and log_float.

namespace math

You probably want to specialise math::decayed_magma_tag to declare your type as a magma. Say that you want to implement a magma cost:

struct cost { /* Implementation */ };

struct cost_tag;

template <> struct decayed_magma_tag <cost>
{ typedef cost_tag type; };

The cost_tag type (which can remain undefined) is used to forward operations to the correct specialisation in namespace operation.

template <class Magma, class Enable = void>
struct math::decayed_magma_tag

Specialise this to assign a magma tag to a type. It would be possible to specialise math::magma_tag instead. However, by default that forwards to this, but with qualifiers removed from Magma, so specialising this is easier.

Templates
  • Magma -

    the unqualified type for which the magma tag is required.

template <class Magma>
struct math::magma_tag

Metafunction that assigns magma tags to types. All types that have the same magma tag are in the same magma.

Return
The magma tag.
Templates
  • Magma -

    The type for which the magma tag is required.

struct math::not_a_magma_tag

Incomplete type that indicates that is the magma tag if a type is not in a magma.

namespace operation

Operations on magmas are forwarded to structs in namespace operation using their magma tag. The indirection leads to a slightly convoluted syntax, but it does mean that many queries about operations are automatically supported. Say that you want to implement a magma cost, which is a semiring which times implemented as addition. The specialisation of times in namespace math::operation might look as follows:

template <> struct times <cost_tag>
: approximate
{
    cost operator() (cost const & left, cost const & right) const
    { return cost (left.value() + right.value()); }
};

This is a specialisation for cost_tag, so when math::times is called with arguments of type cost, it knows to forward to this specialisation. It defines an operator() which takes the left and right operand, and returns the result. In general, the specialisation must have an operator() which takes any arguments that the specialisation is for. If a multiple types constitute a magma, then the operation must be implemented for all of the types. If there are three types, for example, the implementation of equal might have nine overloads for operator().

Note that times <cost_tag> derives from math::operation::approximate. This is an empty class that does not do anything, but deriving from it indicates that the operation is approximate. math::is::approximate uses this information. If the operation is not approximate, don’t derive from approximate. Some other properties that can be set by deriving from empty types, such as associative and idempotent.

If an operation is not implemented, i.e. there is no specialisation, for a magma tag, then the default implementation is used. This default implementation often derives from math::operation::unimplemented. math::has uses this to figure out whether an operation is implemented in the same way as math::is::approximate uses the base class. Thus, the example of the specialisation above has a number of ripple effects.

All operations have an Enable template argument, which can be used to implement an operation only if a certain condition is satisfied. For example, division is implemented for floating-point numbers but not for integers. This could be done with a tag arithmetic_magma_tag <Type> which is templated on the actual type, so that the specialisation can be switched on or off depending on it:

template <class Type> struct divide <arithmetic_magma_tag <Type>, either,
    typename std::enable_if <!std::numeric_limits <Type>::is_integer>::type>
: operator_divide <Type>, approximate {};

You will notice that the implementation merely forwards to operator_divide. This is one of the helper classes that forward to operators.

Consider implementing each of the following operations:

template <class MagmaTag, class Enable = void>
struct math::operation::is_member

Return whether a run-time value is actually a member of the magma. Sometimes a C++ type has a specific value that indicates non-membership. For example, not-a-number values. Implemented as returning rime::true_ by default. Specialise this if you implement math::operation::non_member.

template <class MagmaTag, class Enable = void>
struct math::operation::equal

Return whether two elements of the same magma are equal. This must be specialised.

template <class MagmaTag, class Enable = void>
struct math::operation::not_equal

Return whether two elements of the same magma are not equal. Implemented by default as !(equal (left, right)). Specialise this only if the default implementation does not suffice.

template <class MagmaTag, class Enable = void>
struct math::operation::approximately_equal

Return whether two elements of the same magma are approximately equal. Implemented by forwarding to equal by default. Specialise only if it is necessary for this magma to distinguish between exact and approximate equality.

template <class MagmaTag, class Enable = void>
struct math::operation::compare

Specialise to compare two elements of a magma.

This must returns false for both orders of arguments iff equal returns true for these arguments.

Preferably, return true if the first value is better, in some sense, than the second value.

template <class MagmaTag, class Operation, class Enable = void>
struct math::operation::order

Specialise to indicate that operation Operation returns the extreme element using some order. This predicate then must implement a strict weak ordering. Return true iff the left-hand argument is preferable on this ordering than the right-hand argument. If one of the arguments to Operation is preferable other than the other one, it should return that argument unchanged. If order <MagmaTag, callable::times> is implemented, then math::operation::times is implemented automatically; similarly for plus.

template <class MagmaTag, class Enable = void>
struct math::operation::non_member

Specialise to return a non-member value. It is best to return an object of the most specific type, and allow conversion to a more general type where possible.

template <class MagmaTag, class Operation, class Enable = void>
struct math::operation::identity

Specialise to produce the identity with respect to Operation.

template <class MagmaTag, class Operation, class Enable = void>
struct math::operation::annihilator

Specialise to produce the annihilator with respect to Operation.

template <class MagmaTag, class Enable = void>
struct math::operation::pick

Return magma1 iff condition is true, and magma2 otherwise.

It is not normally necessary to specialise this. The default implementation uses operation::unify_types to unify the return type if necessary.

template <class MagmaTag, class Enable = void>
struct math::operation::choose

Implement choosing the most preferable of two values. If order <MagmaTag, callable::choose> is implemented, this automatically returns the best element according to this order. It is therefore normally not necessary to explicitly specialise this.

It is useful to implement this if at all possible, even if there is no meaningful ordering. Some composite semirings, like the lexicographical semiring, require that all elements define “choose”.

template <class MagmaTag, class Enable = void>
struct math::operation::times

Implement multiplication of two values. Specialise this if the multiplication operation exists for the magma. If order <MagmaTag, callable::times> is implemented, this automatically returns the best element according to this order, and it is not necessary to specialise this.

template <class MagmaTag, class Enable = void>
struct math::operation::plus

Implement addition of two values. Specialise this if the addition operation exists for the magma. If order <MagmaTag, callable::plus> is implemented, this automatically returns the best element according to this order, and it is not necessary to specialise this.

template <class MagmaTag, class Direction, class Enable = void>
struct math::operation::divide

Implement division of two values. Note that the numerator is always the first argument and the denominator always the second, no matter what the direction is. The default behaviour for left and right division is to forward to general division. If left and right division are the same, therefore, this class has to be specialised once, with “either” as direction. If left and right division behave differently, only specialise this for the appropriate direction(s).

template <class MagmaTag, class Direction, class Enable = void>
struct math::operation::minus

Implement subtraction of two values. Note that the minuend is always the first argument and the subtrahend always the second, no matter what the direction is. The default behaviour for left and right subtraction is to forward to general subtraction. If left and right subtraction are the same, therefore, this class has to be specialised once, with “either” as direction. If left and right subtraction behave differently, only specialise this for the appropriate direction(s).

template <class MagmaTag, class Direction, class Operation, class Enable = void>
struct math::operation::invert

Implement to return the inverse of a value with respect to an operation. That is, operation (invert (a), a) == identity<T> (operation).

template <class MagmaTag, class Operation, class Enable = void>
struct math::operation::reverse

Specialise to return the reverse of a value with respect to an operation. That is, reverse (operation (reverse (a), reverse (b)) == operation (a, b). If the operation is either times or plus and it is commutative, then this is implemented automatically by returning the argument exactly.

template <class MagmaTag, class Enable = void>
struct math::operation::print

Specialise to output a human-readable description of the value of the magma to a stream. This is not required, but useful for debugging. This will normally produce the same output as operator<<. Indeed, if this operator is defined, derive from operator_shift_left_stream to forward to it.

Helpers for implementing operations

template <class Order>
struct math::operation::choose_by_order

Take two arguments and select the left one if order (left, right) returns true, and the right one otherwise.

Helper for implementing operations.

template <class Order>
struct math::operation::reverse_order

Take a predicate implementing a strict weak ordering, and reverse the order. (This involves swapping the order of the arguments. Not very complicated.)

This is a helper for implementing comparisons. It is used, for example, by max_semiring, to prefer the largest value instead of the smallest.

If the type already exists and has operators defined, then predefined structs in namespace math::operation can be used straightforwardly. For example, arithmetic_magma.hpp could define equal and times as follows:

// Forward to operator==.
template <class Type> struct equal <arithmetic_magma_tag <Type>>
: operator_equal <bool> {};

// Use multiple inheritance.
template <class Type> struct times <arithmetic_magma_tag <Type>>
// Forward to operator*.
: operator_times <Type>,
// Mark as approximate if the type is floating-point.
    approximate_if <boost::mpl::bool_ <
        !std::numeric_limits <Type>::is_exact>> {};

In the opposite case, where you have defined operations in namespace math::operation, and would like to automatically generate operators, you can use MATH_MAGMA_GENERATE_OPERATORS:

MATH_MAGMA_GENERATE_OPERATORS(tag_predicate)

Generate operator*, operator+, operator-, operator/, operator==, operator!=, operator<, and operator<< as far as the operations are defined (in math::operation). The tag_predicate is a predicate that gets applied to the tag to determine whether to switch on the operators. Put this in the namespace where the class is, so that argument-dependent lookup works properly.

If math::operation::generate_operators <MagmaTag> evaluate to true, and the operation is defined in math::callable::, then switch on the operator and forward to the operation.

Boolean properties

The properties of a magma are set in namespace math::operation. This should be straightforward; namespace math::is tries to conclude things from this.

Setting properties while specialising operations

The easiest way of setting these properties is often to derive an operation from an empty base class, or multiple base classes, that are automatically detected.

struct math::operation::approximate

Inherit from this class to indicate that an operation is approximate. This can be used in testing to require that results are not exact, but close. For example, for floating point values, plus and times are associative only approximately, because intermediate values may be rounded.

struct math::operation::associative

Inherit from this class to indicate that an operation is associative.

struct math::operation::commutative

Inherit from this class to indicate that an operation is commutative.

struct math::operation::idempotent

Inherit from this class to indicate that an operation is idempotent. If an operation is marked as aa path operation, it is automatically also marked as idempotent.

struct math::operation::path_operation

Inherit from this class to indicate that an operation is path_operation. If an operation is marked as aa path operation, it is automatically also marked as idempotent.

struct math::operation::throw_if_undefined

Inherit an inverse operation from this class to indicate that it throws operation_undefined iff it is called with arguments that it is not defined for. In particular, if an attempt is made to take the inverse of an annihilator, inverse_of_annihilator (a subclass of operation_undefined) should be thrown.

For example, an inverse operation (like “divide”) or “invert” could derive from this.

In some cases, you may want to derive from these conditionally. This can be done by deriving from the following.

template <class Condition>
struct math::operation::approximate_if

Inherit from this class to indicate that an operation is approximate if the compile-time constant Condition is true, and not approximate otherwise.

Templates
  • Condition -

    The condition under which the operation is approximate.

template <class Condition>
struct math::operation::associative_if

Inherit from this class to indicate that an operation is associative if the compile-time constant Condition is true, and not associative otherwise.

Templates
  • Condition -

    The condition under which the operation is associative.

template <class Condition>
struct math::operation::commutative_if

Inherit from this class to indicate that an operation is commutative if the compile-time constant Condition is true, and not commutative otherwise.

Templates
  • Condition -

    The condition under which the operation is commutative.

template <class Condition>
struct math::operation::idempotent_if

Inherit from this class to indicate that an operation is idempotent if the compile-time constant Condition is true, and not idempotent otherwise.

Templates
  • Condition -

    The condition under which the operation is idempotent.

template <class Condition>
struct math::operation::path_operation_if

Inherit from this class to indicate that an operation is a path operation if the compile-time constant Condition is true, and not a path operation otherwise.

Templates
  • Condition -

    The condition under which the operation is a path operation.

If an operation is not approximate/associative/and so on, the above will derive from

struct math::operation::ignorable_base_class

Meaningless and empty class to derive from to indicate nothing. This can be useful in a compile-time expression. For example, approximate_if uses it.

Setting properties explicitly

It is also possible to set properties explicitly, by specialising a class with a name starting with is_. For example, if the math::operation::is_distributive <either, ...> is true, then math::is::distributive <left, ...> will be true. Specialising a property usually means deriving it from boost::mpl::true_. Sometimes a more complicated expression is necessary. Properties are mostly false by default (if an operation is not derived from one of the classes above), so they do not have to be specialised if a magma does not have a certain property.

Two properties that concern multiple operations are whether an operation distributes over another, and whether a magma is a semiring (with two operations). That must be indicated by explicitly setting one of these:

template <class MagmaTag, class Direction, class OuterOperation, class InnerOperation, class Enable = void>
struct math::operation::is_distributive

Specialise this to indicate that an operation is distributive. If “is_semiring” is true, this will automatically be true too.

For OuterOperation=times, InnerOperation=plus: Left: a*(b+c) == a*b + a*c. Right: (a+b)*c == a*c + b*c. By setting this to true_ for direction “either”, left and right get set to true_ automatically.

template <class MagmaTag, class Direction, class OuterOperation, class InnerOperation, class Enable = void>
struct math::operation::is_semiring

Define this for semirings, indicating left, right, or either for Direction. By setting this to true_ for direction “either”, left and right get set to true_ automatically.

The following properties can be specialised explicitly, but their default implementations will detect automatically when operations derive from the base classes above.

template <class Operation, class Enable = void>
struct math::operation::is_approximate

Metafunction that indicates whether an operation is approximate.

Return
true iff Operation is derived from math::operation::approximate.

template <class Operation, class Enable = void>
struct math::operation::is_associative

Metafunction that indicates whether an operation is associative.

Return
true iff Operation is derived from math::operation::associative.

template <class Operation, class Enable = void>
struct math::operation::is_commutative

Metafunction that indicates whether an operation is commutative.

Return
true iff Operation is derived from math::operation::commutative.

template <class Operation, class Enable = void>
struct math::operation::is_idempotent

Metafunction that indicates whether an operation is idempotent.

Return
true iff Operation is derived from math::operation::idempotent.

template <class Operation, class Enable = void>
struct math::operation::is_path_operation

Metafunction that indicates whether an operation is a path operation.

Return
true iff Operation is derived from math::operation::path_operation.

Type property

template <class MagmaTag, class Magma1, class Magma2, class Enable = void>
struct math::operation::unify_type

Evaluate to a type that both Magma1 and Magma2 can be converted to and which has the same magma tag as Magma1 and Magma2.

Specialise this only for magmas with different types, if the order operation is defined. This is used in operations that implement an order. This is implemented for the case where Magma1 and Magma2 are the same: it then evaluates to Magma1.

Magma1 and Magma2 are decayed types.

Checking

Magmas (and semirings) can be tested. The properties must be set up (and checked) in advance, examples must be produced, and then the following functions can be used:

template <class Examples>
void check_equal_on(Examples const & examples)

Check that equal returns false for any two elements in example, except when they occupy the same memory address, in which case it must return true.

All examples must be members that compare unequal.

template <class Magma, class Operation, class Examples>
void check_magma(Operation operation, Examples const & examples)

Test the implementation of a magma for internal consistency. Identity and not-a-member are acquired by this function where available.

This function uses properties to determine what to test for. Before calling this, check whether the following are defined correctly:

  • equal. Unequal elements must compare unequal (e.g. use check_equal_on()). Equal elements must compare equal. However, equality is checked for transitivity, so not every pair of elements needs to be checked manually.
  • has <callable::non_member (Magma)>.
  • has <callable::is_member (Magma)>.
  • has <callable::times/plus/... ( <Magma, Magma)>.
  • has <callable::order (Operation, Magma)>.
  • is::approximate <times/plus/... (Magma, Magma)>.
  • has <callable::identity (Magma, Operation)>.
  • has <callable::annihilator (Magma, Operation)>.
  • has <math::callable::invert <left/right/either, Operation> (Magma)>.
  • has <math::callable::reverse <Operation> (Magma)>.
  • is::commutative <Magma, Operation>.
  • is::associative <Magma, Operation>
  • is::idempotent <Magma, Operation>.
  • is::path_operation <Magma, Operation>.

Templates
  • Magma -

    One of the magma types to be tested.

Parameters
  • operation -

    The operation of the magma, e.g. math::times or math::plus.

  • examples -

    The examples, as a range.

template <class Magma, class Operation1, class Operation2, class Examples>
void check_magma(Operation1 operation1, Operation2 operation2, Examples const & examples)

Check that a type is a magma with respect to two operations. This calls check_magma with the two operations.

Before calling this, check that the properties for the single-operation check_magma, and the following property are defined correctly:

Templates
  • Magma -

    One of the magma types to be tested.

Parameters
  • operation1 -

    One operation of the magma, e.g. math::times.

  • operation2 -

    The other operation of the magma,e e.g. math::plus or math::choose.

  • examples -

    The examples, as a range. They can have different types.

template <class Magma, class Direction, class Multiplication, class Addition, class Examples>
void check_semiring(Multiplication multiplication, Addition addition, Examples const & examples)

Check that a type is a semiring. This explicitly checks is::semiring in the correct direction. It also calls check_magma with the two operations.

Templates
  • Magma -

    One of the magma types to be tested.

  • Direction -

    The direction of the semiring. For a normal semiring, this should be set to math::either. A left semiring is indicated with math::left; a right semiring with math::right.

Parameters
  • multiplication -

    The multiplication operation, e.g. math::times.

  • addition -

    The addition operation, e.g. math::plus.

  • examples -

    The examples, as a range.

Useful classes

template <class Type>
struct math::is_direction

Metafunction.

Return
Whether Type is a direction. This can be useful for SFINAE.

struct math::operation::unimplemented

Inherit from this class to indicate that the operation is not implemented (for specific arguments).

template <class Operation>
struct math::operation::is_implemented

Metafunction that indicates whether an operation is implemented.

Return
true iff Operation is not derived from unimplemented.

Implementing a new operation

An operation has a function or callable static object, and a type with an operator() in namespace math::callable. For interaction with magmas, the type must completely define the operation. This way, for example, saying identity <double, callable::plus>() is possible: callable::plus completely defines the operation.

The implementation of operations comes in a number of parts, which are in different namespaces. The namespace math::operation has been discussed above. Structs in this namespace are inherited by types in namespace math::apply, which are instantiated by types in math::callable, which are used in namespace math. The following details these.

namespace apply

Each Type in namespace math::apply deals with compile-time and run-time arguments and forwards them to the struct with the same name in namespace operation. The run-time arguments will often, but not always, be passed through std::decay. structs in operation are normally parameterised by the magma tag. For example, the standard operation identity could have a definition in namespace apply like:

template <class ...> struct identity;

// The actual implementation specialises the variadic declaration.
template <class Magma, class Operation> struct identity <Magma, Operation>
: operation::identity <
    typename magma_tag <Magma>::type,
    typename std::decay <Operation>::type> {};

For some compilers (GCC 4.6) it makes integration into callables easier to have variadic type arguments, but this is by no means mandated. If there are multiple parameters that must be of the same magma, math::apply::detail::magma_tag_all <Magma1, Magma2> can be instead of magma_tag <Magma>.

To allow the nested call protocol to work, the class must derive from operation::unimplemented if unimplemented. (It can additionally derive from operation::approximate if approximate, from operation::associative if associative, et cetera.) This is often easy to do by always deriving from the appropriate type in namespace operation.

It is possible to forward calls to different operations in this namespace, as long as their operator() takes the same arguments. For example, the definition of one could be:

template <class Magma> struct one <Magma>
: identity <Magma, callable::times> {};

namespace callable

The namespace callable contains callable types. Types in this namespace can have template arguments. For example:

template <class Magma> struct one;

non_member must then have an operator(), which in this case takes zero arguments. In general, it constructs an object of the appropriate type from namespace apply and then forwards the arguments to it. Additionally, to adhere to the nested callable protocol, information must be provided at compile time. Any callable must have a class or struct apply <RunTimeArguments ...> deriving from apply::function. This allows such functionality as math::has and math::is::approximate to work. This is easy with

struct times : generic <apply::times> {};

or, if the function has one or more template arguments:

template <class Magma> struct one : generic <apply::one, Magma> {};
template <template< class...> class Apply, class... CompileTimeArguments>
struct math::callable::generic

Generic callable that forwards to Apply, with the compile-time arguments and the function call arguments as template arguments. It provides an operator() and a template struct apply which derives from Apply with the compile-time and run-time arguments.

Templates
  • Apply -

    a variadic template class. When the object is called, Apply <CompileTimeArguments ..., Arguments...> will be instantiated with the exact argument types. It is then default-constructed and called.

  • CompileTimeArguments -

    The compile-time arguments.

namespace math

Finally, the namespace ::math itself contains things that can be called. These can be either a function, or a function object. For example:

static const auto is_member = callable::is_member();

If the callable type is templated, the thing in namespace ::math cannot be a function object, so:

template <class Magma> inline auto non_member()
    RETURNS (callable::non_member <Magma>()());

Now, your new operation can be tested!