2
\$\begingroup\$

Here's some code I wrote to manage the different types of morphism and their compositions in C++17.

Let me know if you had any suggestions for substantial simplifications or improvements, or if I missed something.

There's an example at the end that composes a number of different morphisms together and then confirms that the final result can be used in a constexpr context.

#include <iostream>
#include <vector>
#include <type_traits>

/// Extract the first argument type from a map.
template <typename R, typename A0, typename ... As>
constexpr A0 firstArg (R(*)(A0, As...));

/** Set theoretic morphisms **/

template<typename S, typename T>
struct Homomorphism {
    constexpr static T value(const S);
};

template<typename S, typename T>
struct Monomorphism: Homomorphism<S, T> {
    constexpr static T value(const S);
};

template<typename S, typename T>
struct Epimorphism: Homomorphism<S, T> {
    constexpr static T value(const S);
};

template<typename S>
struct Endomorphism: Homomorphism<S, S> {
    constexpr static S value(const S);
};

template<typename S, typename T>
struct Isomorphism: Monomorphism<S, T>, Epimorphism<S, T> {
    constexpr static T value(const S);
};

template<typename S>
struct Automorphism: Endomorphism<S>, Isomorphism<S, S> {
    constexpr static S value(const S);
};

template<typename H1,
         typename H2,
         typename S  = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T1 = std::decay_t<decltype(H1::value(std::declval<S>()))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename R  = std::decay_t<decltype(H2::value(std::declval<T2>()))>>
struct MonomorphismComposition: Monomorphism<S, R> {
    static_assert(std::is_base_of_v<Monomorphism<S, T1>, H1>);
    static_assert(std::is_base_of_v<Monomorphism<T2, R>, H2>);
    static_assert(std::is_same_v<T1, T2>);
    constexpr static R value(const S &s) {
        return H2::value(H1::value(s));
    }
};

template<typename H1,
         typename H2,
         typename S  = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T1 = std::decay_t<decltype(H1::value(std::declval<S>()))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename R  = std::decay_t<decltype(H2::value(std::declval<T2>()))>>
struct EpimorphismComposition: Epimorphism<S, R> {
    static_assert(std::is_base_of_v<Epimorphism<S, T1>, H1>);
    static_assert(std::is_base_of_v<Epimorphism<T2, R>, H2>);
    static_assert(std::is_same_v<T1, T2>);
    constexpr static R value(const S &s) {
        return H2::value(H1::value(s));
    }
};

template<typename H1,
         typename H2,
         typename S  = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T1 = std::decay_t<decltype(H1::value(std::declval<S>()))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename R  = std::decay_t<decltype(H2::value(std::declval<T2>()))>>
struct IsomorphismComposition: Isomorphism<S, R> {
    static_assert(std::is_base_of_v<Isomorphism<S, T1>, H1>);
    static_assert(std::is_base_of_v<Isomorphism<T2, R>, H2>);
    static_assert(std::is_same_v<T1, T2>);
    constexpr static R value(const S &s) {
        return H2::value(H1::value(s));
    }
};

template<typename H1,
         typename H2,
         typename T1 = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename T  = std::enable_if_t<std::is_same_v<T1, T2>, T1>>
struct EndomorphismComposition: Endomorphism<T> {
    static_assert(std::is_base_of_v<Endomorphism<T>, H1>);
    static_assert(std::is_base_of_v<Endomorphism<T>, H2>);
    constexpr static T value(const T &s) {
        return H2::value(H1::value(s));
    }
};

template<typename H1,
         typename H2,
         typename T1 = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename T  = std::enable_if_t<std::is_same_v<T1, T2>, T1>>
struct AutomorphismComposition: Automorphism<T> {
    static_assert(std::is_base_of_v<Automorphism<T>, H1>);
    static_assert(std::is_base_of_v<Automorphism<T>, H2>);
    constexpr static T value(const T &s) {
        return H2::value(H1::value(s));
    }
};

template<typename H1,
         typename H2,
         typename S  = std::decay_t<decltype(firstArg(&H1::value))>,
         typename T1 = std::decay_t<decltype(H1::value(std::declval<S>()))>,
         typename T2 = std::decay_t<decltype(firstArg(&H2::value))>,
         typename R  = std::decay_t<decltype(H2::value(std::declval<T2>()))>>
struct HomomorphismComposition: Homomorphism<S, R> {
    static_assert(std::is_base_of_v<Homomorphism<S, T1>, H1>);
    static_assert(std::is_base_of_v<Homomorphism<T2, R>, H2>);
    static_assert(std::is_same_v<T1, T2>);
    constexpr static R value(const S &s) {
        return H2::value(H1::value(s));
    }
};

template<typename T>
struct IdentityAutomorphism: Automorphism<T> {
    constexpr static T value(const T &t) {
        return t;
    }
};

/** This is a monomorphism if the type of S is a subset of T, i.e. is convertible to T. **/
template<typename S, typename T>
struct EmbeddingMonomorphism: Monomorphism<S, T> {
    static_assert(std::is_convertible_v<S, T>);
    constexpr static T value(const S &s) {
        return s;
    }
};

/*** EXAMPLE ***/

struct divby2: Automorphism<double> { constexpr static double value(double d) { return d / 2; }};
struct embed_divby2: MonomorphismComposition<EmbeddingMonomorphism<int, double>, divby2> {};

struct squared: Monomorphism<int, int>, Endomorphism<int> { constexpr static int value(int i) { return i * i; } };
struct squared_embed_divby2: MonomorphismComposition<squared, embed_divby2> {};

struct S {
    explicit constexpr S(int val): val{val} {};
    const int val;
};
struct s_to_int: Isomorphism<S, int> { constexpr static int value(const S &s) { return s.val; } };

struct bighom: MonomorphismComposition<s_to_int, squared_embed_divby2> {};
struct biggerhom: MonomorphismComposition<bighom, IdentityAutomorphism<double>> {};

constexpr auto sum() {
    double d = 0;
    for (int i = 0; i < 10; ++i)
        d += biggerhom::value(S{i});
    return d;
}

int main() {
    for (int i = 0; i < 10; ++i)
        std::cout << biggerhom::value(S{i}) << '\n';

    constexpr double d = sum();
    std::cout << "Sum is: " << d << '\n';
}
\$\endgroup\$
3
\$\begingroup\$

I'm under the impression that this code is part of a larger design, whose extent and intentions I can't entirely guess. Sorry if my review seems a bit restrictive or short sighted in that regard.

General design

My understanding is that you want to build a mathematical type system over the fairly permissive C++ set of function and function-like types. That's a noble undertaking but I'm afraid that they are so different realities that it will end in a misunderstanding.

Take your definition of what a c++ application is: R(*)(A0, As...) (in the firstArg signature). This will match a function pointer, but function references, lambdas, member functions, functors, pointer to member functions are as legitimate targets and they won't necessarily match this signature.

Then there is also the problem of function overloading: what if foo has three overloads? Which one will R(*)(A0, As...) match? (the answer is none, it simply won't compile).

Three lines further, in contrast to this vigorous simplification, you begin to build a complex inheritance tree whose semantics are transparent to the compiler, at least beyond the identity between argument and return type: how would the compiler decide if a function really is a monomorphism?

I believe you would be better off with a simpler design uncoupling c++ types and mathematical types, at least to a certain extent.

C++ application composition

That is already a hard problem on its own right, depending on how much you want to constrain the domain. But it's certainly easier if you want to only accept applications exposing S value(T) as an interface. What I'd suggest then is to provide a handier template:

template <typename R, typename A>
struct Application {

    using result_type = R;
    using argument_type = A;

    template <typename F>
    Application(F f) : fn(f) {}

    R value(A) { return fn(a); } // no need to have it static now

    std::function<R(A)> fn;
};

You can then turn any complying function-like object into a compatible Application: auto square = Application<double, double>([](auto n) { return n * n; };. Verifying application composition is now trivial: std::is_same<typename F::argument_type, typename G::result_type (std::is_convertible might be a choice too).

Morphisms classification

I'm a bit skeptical about this all-encompassing inheritance tree. The first thing to note is that simple inheritance won't constrain value in the derived class based on its specification in the base class. Inheriting from endomorphism won't constrain a class to expose a value function whose argument type and return type are the same. Virtual functions would constrain it, but frankly, with multiple inheritance that seems unnecessarily dangerous and complex.

What you could do is keep the kind of morphism as a tag and then constrain the function value with std::enable_if and std::conditional:

template <typename R, typename A, typename Morphism>
struct Application {
    // ...
    using morphism_tag = Morphism;
    using result_type = std::conditional_t<std::is_base_of_v<Endomorphism, morphism_tag>,
                                           std::enable_if_t<std::is_same_v<R, A>, R>,
                                           R
                                          >;
    result_type value(argument_type);
    // ...
};

Your code won't compile if you generate an Application with an Endomorphism tag whose return type doesn't match the argument type.

I'm not sure how extensible it would be though, and which rules we would be able to enforce.

Morphisms composition

With this infrastructure, you would be able to compose morphisms more easily, along those lines:

template <typename R1, typename A1, typename T1,
          typename R2, typename A2, typename T2>
constexpr auto resulting_morphism(Application<R1, A1, T1>, Application<R2, A2, T2>) {
    if constexpr (std::is_base_of_v<Endomorphism, T1> && std::is_base_of_v<Endomorphism, T2>)
        return Monomorphism();
    else if constexpr ( /*...*/ )
    // ...
    else throw std::logical_error(); // throw in constexpr context simply won't compile
)

template <typename R1, typename A1, typename T1,
          typename R2, typename A2, typename T2>
constexpr auto compose(Application<R1, A1, T1> a1, Application<R2, A2, T2> a2) {
    return Application<R1, A2, decltype(resulting_morphism(a1, a2)>([](auto arg) {
        return a1(a2(arg));
        });
}
\$\endgroup\$
  • \$\begingroup\$ This is all excellent. Thank you so much for the feedback! \$\endgroup\$ – Sebastian Nov 30 '18 at 15:52
  • \$\begingroup\$ A question: I suppose this would limit Application to not being constexpr since std::function is not constexpr. (I believe it has a non-trivial destructor?) I am quite inexperienced with tags and have never used std::conditional, so this is teaching me a lot. I'm very thankful for your answer. \$\endgroup\$ – Sebastian Nov 30 '18 at 21:58
  • \$\begingroup\$ Also, the code was just my brain spiralling out again upon realizing - months ago - that there is an epi between mazes with infinitesimally thin walls, and mazes where the walls have the same thickness as the cells themselves. \$\endgroup\$ – Sebastian Dec 1 '18 at 12:38
  • \$\begingroup\$ @Sebastian: I believe you're right about the constexpr thing. The second comment I didn't understand. \$\endgroup\$ – papagaga Dec 2 '18 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.