C++ metaprogramming Knuth's arrows

cpp_metaprogramming_knuth_arrows.md

#Knuth arrows in C++ metaprogramming.

Two implementations of Knuth's arrows using constexpr and template metaprogramming.

• Constexpr Knuth arrows
  • Constexpr service functions
  • Constexpr variant 1
  • Constexpr variant 2
  • Constexpr arrows evaluation
• Template Knuth arrows
  • Template service functions
  • Template arrows
  • Template arrows evaluation

---

Constexpr Knuth arrows

Constexpr service functions

#include <stdint.h>
#include <stdexcept>

constexpr uint64_t pow(uint64_t a, uint64_t n)
{
    return 
        n == 0
            ? 1
            : a * pow(a, n - 1);
}

constexpr uint64_t tower(uint64_t a, uint64_t b)
{
    return
        b == 0
            ? throw std::invalid_argument("b == 0")
            : b == 1
                ? a
                : pow(a, tower(a, b - 1));
}

Constexpr variant 1

constexpr uint64_t arr(uint64_t a, uint64_t b, uint64_t s);

constexpr uint64_t arr2(uint64_t cnt, uint64_t a, uint64_t sp, uint64_t b)
{
    return cnt == 0
        ? arr(a, sp, b)
        : arr(a, arr2(cnt - 1, a, sp, b), sp);
}

constexpr uint64_t arr(uint64_t a, uint64_t s, uint64_t b)
{
    return s == 1
            ? pow(a, b)
            : s == 2
                ? tower(a, b)
                : arr2(b - 1, a, s - 1, a);
}

Constexpr variant 2

constexpr uint64_t arr_impl(bool arr_iter, uint64_t cnt, uint64_t a, uint64_t s, uint64_t b)
{
    return arr_iter
        ? (cnt == 0
                ? arr_impl(false, 0, a, s, b)
                : arr_impl(false, 0, a, arr_impl(true, cnt - 1, a, s, b), s))
        : (s == 1
                ? pow(a, b)
                : s == 2
                    ? tower(a, b)
                    : arr_impl(true, b - 1, a, s - 1, a));
}

constexpr uint64_t arr(uint64_t a, uint64_t s, uint64_t b)
{
    return arr_impl(false, 0, a, s, b);
}

Constexpr arrows evaluation

uint64_t x = arr(3, 2, 3);  // 3 ↑↑ 3 = 7625597484987
uint64_t x = arr(2, 2, 3);  // 2 ↑↑ 3 = 16

Template Knuth arrows

(Resembles the variant #2 of constexpr Knuth arrows)

Template service functions

#include <stdint.h>

/// Pow

template <uint64_t A, uint64_t N>
struct Pow {
    static constexpr uint64_t value = A * Pow<A, N - 1>::value;
};

template <uint64_t A>
struct Pow<A, 0> {
    static constexpr uint64_t value = 1;
};

// Tower

template <uint64_t A, uint64_t B>
struct Tower {
    static constexpr uint64_t value = Pow<A, 
            Tower<A, B - 1>::value
            >::value;
};

template <uint64_t A>
struct Tower<A, 1> {
    static constexpr uint64_t value = A;
};

Template arrows

// ArrImpl

template <bool arr_iter, uint64_t C, uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl {
    static constexpr uint64_t value = 1;
};

template <uint64_t C, uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl<true, C, A, S, B> {
    static constexpr uint64_t value 
        = ArrImpl<false, 0, A,
            ArrImpl<true, C - 1, A, S, B>::value,
            S>::value;
};

template <uint64_t A, uint64_t S, uint64_t B>
struct ArrImpl<true, 0, A, S, B> {
    static constexpr uint64_t value 
        = ArrImpl<false, 0, A, S, B>::value;
};

template <uint64_t C, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, 1, B> {
    static constexpr uint64_t value 
        = Pow<A, B>::value;
};

template <uint64_t C, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, 2, B> {
    static constexpr uint64_t value 
        = Tower<A, B>::value;
};

template <uint64_t C, uint64_t S, uint64_t A, uint64_t B>
struct ArrImpl<false, C, A, S, B> {
    static constexpr uint64_t value 
        = ArrImpl<true, B - 1, A, S - 1, A>::value;
};

// Arr

template <uint64_t A, uint64_t S, uint64_t B>
struct Arr {
    static constexpr uint64_t value
        = ArrImpl<false, 0, A, S, B>::value;
};

Template arrows evaluation

auto T1 = Pow<2, 5>::value;   // 32

auto T2 = Tower<2, 3>::value; // 16

auto T3 = Arr<3, 2, 3>::value;  // 3 ↑↑ 3 = 7625597484987