Monday, January 13, 2014

Type Functions: loops and lambdas

pfultz2 on reddit suggested type functions may work well with generic lambdas. I thought I'd try it, but my first attempt ran into N3797 5.1.2/2:
...A lambda-expression shall not appear in an unevaluated operand...

I was going to give up on keeping the function calls inside decltype() (one of my replies to his thread), but then I noticed that I placed my lambda directly in the decltype(). It worked once I moved the lambda into a function; this is the result.

Correction to my previous post (thanks to KrzaQ2 on reddit): these examples rely on C++1y; C++11 doesn't have auto return type deduction for functions.

First some boilerplate from my previous post...

#include <assert.h>
#include <iostream>
#include <type_traits>
#include <typeinfo>

using namespace std;

template<class T>
struct Type
{
    using type = T;
};

template<class T>
auto ptr(Type<T>)
{
    return Type<T*>{};
}

template<int i>
using int_ = integral_constant<int, i>;

#define EXTRACT_TYPE(e) decltype(e)::type

#define ASSERT_EXTRACT_TYPE(a, b) \
    assert(typeid(EXTRACT_TYPE(a)) == typeid(b))
loopn composes a functor to itself n times. I test it by passing in a generic lambda.
// Loop 0 times: don't call F
template<class Arg, class F>
auto loopn(int_<0>, Arg arg, F)
{
    return arg;
}

// Loop n times
template<int n, class Arg, class F>
auto loopn(int_<n>, Arg arg, F f)
{
    return loopn(int_<n-1>{}, f(arg), f);
}

// Convenience wrapper
template<int n, class Arg, class F>
auto loopn(Arg arg, F f)
{
    return loopn(int_<n>{}, arg, f);
}

// exampleLoop<n>() produces an int****...
template<int n>
auto exampleLoop()
{
    return loopn<n>(
        Type<int>{},
        [](auto arg){return ptr(arg);});
}

void testLoopn()
{
    // This doesn't work because of N3797 5.1.2/2:
    //      ...A lambda-expression shall not appear 
    //      in an unevaluated operand...
    // ASSERT_EXTRACT_TYPE(
    //     loopn<2>(
    //         Type<int>{},
    //         [](auto arg){return ptr(arg);}),
    //     int**);

    ASSERT_EXTRACT_TYPE(exampleLoop<0>(), int);
    ASSERT_EXTRACT_TYPE(exampleLoop<1>(), int*);
    ASSERT_EXTRACT_TYPE(exampleLoop<2>(), int**);
    ASSERT_EXTRACT_TYPE(exampleLoop<10>(), int**********);

    // Stress test; we're getting close to the default template
    // nesting depth limits in clang and Visual C++ Nov
    // 2013 CTP.
    decltype(exampleLoop<200>())::type p{};
}

int main()
{
    testLoopn();

    cout << "Tests passed" << endl;
}

Sunday, January 12, 2014

Type Functions in C++

C++ metafunctions normally don't look like functions. What if this changed with C++11/C++14? What if metafunctions can be C++ functions? I decided to try it out.

I decided to begin with type functions. We want functions which take types as arguments and return types. Here's a type container for these functions to operate on.

template<class T>
struct Type
{
    using type = T;
};
Let's try something easy. ptr() turns a T into a T*.
template<class T>
auto ptr(Type<T>)
{
    return Type<T*>{};
}
Let's use this to declare an int**.
void testPtr1()
{
    int                                   i{};
    int*                                  p{&i};
    decltype(ptr(ptr(Type<int>{})))::type pp{&p};

    assert(typeid(pp) == typeid(int**));
}
We only "call" ptr() within decltype(); this prevents it from generating any runtime code, even in debug builds. This isn't very readable, so let's simplify the interface a bit.
static const Type<int> IntType;

#define EXTRACT_TYPE(e) decltype(e)::type

void testPtr2()
{
    int                             i{};
    int*                            p{&i};
    EXTRACT_TYPE(ptr(ptr(IntType))) pp{&p};

    assert(typeid(pp) == typeid(int**));
}
We established an approach for defining and using a type function; let's see how well this works with pattern matching.
template<class T>
auto removeCV(Type<T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<const T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<volatile T>)
{
    return Type<T>{};
}

template<class T>
auto removeCV(Type<const volatile T>)
{
    return Type<T>{};
}

void testRemoveCV1()
{
    EXTRACT_TYPE(ptr(removeCV(Type<int>{})))
        p1{};
    EXTRACT_TYPE(ptr(removeCV(Type<const int>{})))
        p2{};
    EXTRACT_TYPE(ptr(removeCV(Type<volatile int>{})))
        p3{};
    EXTRACT_TYPE(ptr(removeCV(Type<const volatile int>{})))
        p4{};
    EXTRACT_TYPE(ptr(Type<const volatile int>{}))
        p5{};

    assert(typeid(p1) == typeid(int*));
    assert(typeid(p2) == typeid(int*));
    assert(typeid(p3) == typeid(int*));
    assert(typeid(p4) == typeid(int*));
    assert(typeid(p5) == typeid(const volatile int*));
}
That works. Let's simplify our test case a bit.
#define ASSERT_EXTRACT_TYPE(a, b) \
    assert(typeid(EXTRACT_TYPE(a)) == typeid(b))

void testRemoveCV2()
{
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<const int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<volatile int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(removeCV(Type<const volatile int>{})),
        int*);
    ASSERT_EXTRACT_TYPE(
        ptr(Type<const volatile int>{}),
        const volatile int*);
}
Let's try recursion. We want a function which retrieves the nth argument type from a function type.
template<int i>
using int_ = integral_constant<int, i>;

// Found it
template<class R, class A0, class... A>
auto argn(int_<0>, Type<R(A0, A...)>)
{
    return Type<A0>{};
}

// Continue search
template<int n, class R, class A0, class... A>
auto argn(int_<n>, Type<R(A0, A...)>)
{
    return argn(int_<n - 1>{}, Type<R(A...)>{});
}

void testArgn1()
{
    ASSERT_EXTRACT_TYPE(
        argn(int_<0>{}, Type<void(int, double, float)>{}),
        int);
    ASSERT_EXTRACT_TYPE(
        argn(int_<1>{}, Type<void(int, double, float)>{}),
        double);
    ASSERT_EXTRACT_TYPE(
        argn(int_<2>{}, Type<void(int, double, float)>{}),
        float);
}
argn(int_<n>{}, ...) seems a little silly; let's give it a nicer interface.
template<int n, class T>
auto argn(Type<T> t)
{
    return argn(int_<n>{}, t);
}

void testArgn2()
{
    ASSERT_EXTRACT_TYPE(
        argn<0>(Type<double(int, double, float)>{}), 
        int);
    ASSERT_EXTRACT_TYPE(
        argn<1>(Type<double(int, double, float)>{}), 
        double);
    ASSERT_EXTRACT_TYPE(
        argn<2>(Type<double(int, double, float)>{}), 
        float);
}
Let's try conditionals.
template<class T, class F>
auto if_(true_type, T t, F)
{
    return t;
}

template<class T, class F>
auto if_(false_type, T, F f)
{
    return f;
}

// demoIf's return type depends on Cond
template<class Cond>
auto demoIf(Cond c)
{
    return if_(c, Type<int>{}, Type<double**>{});
}

// Let's give the compiler more work to do
template<class Cond1, class Cond2>
auto demoNestedIf(Cond1 c1, Cond2 c2)
{
    return if_(c1,
        if_(c2,
            Type<char>{},
            Type<short>{}),
        if_(c2,
            Type<int>{},
            Type<long>{}));
}

void testIf()
{
    ASSERT_EXTRACT_TYPE(demoIf(true_type{}),  int);
    ASSERT_EXTRACT_TYPE(demoIf(false_type{}), double**);

    ASSERT_EXTRACT_TYPE(
        demoNestedIf(true_type{},  true_type{}),
        char);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(true_type{},  false_type{}),
        short);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(false_type{}, true_type{}),
        int);
    ASSERT_EXTRACT_TYPE(
        demoNestedIf(false_type{}, false_type{}),
        long);
}
We could try a type list at this point, but I'm feeling a bit ambitious. Let's try a type map.
// Each KV must be a pair. first_type and second_type must be
// default-constructable and copyable. Type<...> works well as a
// key or a value.
template<class... KV>
struct Map
{
};

// Match found
template<class K0, class V0, class... KV>
auto at(Map<pair<K0, V0>, KV...>, K0)
{
    return V0{};
}

// Continue search. Generates a compiler error if K is not
// found.
template<class KV0, class... KV, class K>
auto at(Map<KV0, KV...>, K k)
{
    return at(Map<KV...>{}, k);
}

void testMapAt()
{
    using M = Map<
        pair<int_<4>,    Type<double>>,
        pair<Type<int*>, Type<int>>,
        pair<Type<int>,  Type<int*>>>;

    ASSERT_EXTRACT_TYPE(at(M{}, int_<4>{}),    double);
    ASSERT_EXTRACT_TYPE(at(M{}, Type<int*>{}), int);
    ASSERT_EXTRACT_TYPE(at(M{}, Type<int>{}),  int*);
}
erase() takes a bit more work.
template<class KV0, class... KV1>
auto prepend(KV0, Map<KV1...>)
{
    return Map<KV0, KV1...>{};
}

// Key found
template<class K0, class V0, class... KV>
auto erase(Map<pair<K0, V0>, KV...>, K0)
{
    return Map<KV...>{};
}

// Continue search
template<class KV0, class... KV, class K>
auto erase(Map<KV0, KV...>, K k)
{
    return prepend(KV0{}, erase(Map<KV...>{}, k));
}

// End of map
template<class K>
auto erase(Map<>, K)
{
    return Map<>{};
}

void testMapErase()
{
    using M = Map<
        pair<int_<4>, Type<double>>,
        pair<Type<int*>, Type<int>>,
        pair<Type<int>, Type<int*>>>;

    // key not found
    assert(
        typeid(erase(M{}, int_<2>{})) ==
        typeid(M));

    // remove row 0, 1
    assert(
        typeid(erase(erase(M{}, int_<4>{}), Type<int*>{})) ==
        typeid(Map<pair<Type<int>, Type<int*>>>));

    // remove row 0, 2
    assert(
        typeid(erase(erase(M{}, int_<4>{}), Type<int>{})) ==
        typeid(Map<pair<Type<int*>, Type<int>>>));

    // remove row 2, 1
    assert(
        typeid(erase(erase(M{}, Type<int>{}), Type<int*>{})) ==
        typeid(Map<pair<int_<4>, Type<double>>>));
}
I'll leave insert() as an exercise.

I like how these type functions turned out; they seem a little less messy than the template struct approach. There's a lot more to template metaprogramming than just manipulating types; I plan to keep exploring.

#include <assert.h>
#include <iostream>
#include <type_traits>
#include <typeinfo>
#include <utility>

using namespace std;

... code snippets from above ...

int main()
{
    testPtr1();
    testPtr2();
    testRemoveCV1();
    testRemoveCV2();
    testArgn1();
    testArgn2();
    testIf();
    testMapAt();
    testMapErase();

    cout << "Tests passed" << endl;
}
Full source at ideone