Tag Archives: метапрограммирование

C++11: SFINAE реализация is_callable

В стандарт C++11 из Boost попал набор шаблонов, позволяющих выполнять некоторые манипуляции с типами или проверять наличие поддержки типами тех или иных операций. Данный набор размещён в стандартном заголовочном файле type_traits. Почему-то в этот набор предопределённых метафункций не попала функция, позволяющая определить, возможно ли вызвать объект некоторого типа (указатель на функцию, ссылку на функцию или функтор) для заданного набора параметров. То есть, проверить поддержку им заданной сигнатуры. Впрочем, такую метафункцию (я назвал её «is_callable») в рамках C++11 реализовать довольно легко.

Основной элемент C++, позволяющий проверять доступность той или иной операции, называется SFINAE — «substitution failure is not an error» — ошибка при подстановке параметров шаблона в шаблоне функции не считается ошибкой компиляции, а просто исключает данный вариант из рассмотрения при вызове перегруженной функции. Классическим примером использования SFINAE является стандартный шаблон enable_if (также взятый из Boost), позволяющий «включать» или «выключать» определения функций в зависимости от выполнения условий времени компиляции.

С появлением ключевого слова decltype, позволяющего «извлечь» тип выражения, появился новый паттерн, задействующий SFINAE в духе enable_if:

template <class T>
decltype((void)(Expr(T)), RetExpr()) foo(T);

Данный вариант функции пропадёт из рассмотрения при вызове, если выражение Expr(T) нельзя скомпилировать для данного типа T. В противном случае, возвращаемый тип функции будет совпадать с типом значения выражения RetExpr(). Приведение к void позволяет гарантировать «нормальное» поведение оператора «запятая» (а то вдруг он перегружен).

Такую конструкцию обычно лучше оформлять с «хвостовым» определением возвращаемого типа. Заодно можно будет воспользоваться именами параметров функции в выражении внутри decltype.

template <class T>
auto foo(T t) ->
    decltype((void)(Expr(t)), RetExpr());

В общем-то, данный приём составляет основу определения метафункции is_callable, для представления которого я написал данный пост. Оно довольно простое.

#include <type_traits>
#include <utility>

template <class F>
struct Try_to_call
{
  template <class... Args>
  static std::false_type can_call(Args&&...);

  template <class... Args>
  static auto can_call(F& f, Args&&... args)
    -> decltype((void)f(std::forward<Args>(args)...),
                std::true_type{});
};

template <class F, class... Args>
using is_callable = decltype
  (
    Try_to_call<F>::can_call(*(F*)nullptr,
          std::forward<Args>(*(Args*)nullptr)...)
  );

Как правило, определяют функцию, дающую вариант «по умолчанию» и для того имеющую максимально обобщённый вид. Здесь это вариант can_call, возвращающий false_type, принимающий любой набор параметров. Вообще любой.

Также можно задействовать примитивные типы с неявным приведением. Например, «вариант по умолчанию» принимает дополнительный параметр типа unsigned, а «желаемый вариант» — параметр типа int. Тогда при передаче, например, числа 1, int — предпочтительнее при выборе перегруженного варианта, однако unsigned тоже сойдёт, так как определено неявное приведение типа int -> unsigned.

Теперь пример использования. При запуске должно вывести 1110. Проверено в MSVC2013 и gcc 4.9.2.

#include <iostream>

int main()
{
  using namespace std;
  auto sqr = [](double x) { return x * x; };
  cout << is_callable<decltype(sqr), int>::value
       << is_callable<int (*)(int), double>::value
       << is_callable<int (*)(int), int>::value
       << is_callable<int (*)(int), double, double>::value
       << endl;
  return 0;
}
Реклама

C++: список типов

Данный пост посвящён созданию списков типов в C++11 и работе с ними.
Список — это линейная рекурсивная структура данных. Условно её можно представить как

type List = Nil | (type, List)

Здесь Nil — вспомогательный тип, означающий пустой список (или конец списка).

// выбор первой части пары
head x = x
head (h, t) = h

// выбор второй части пары
tail x = Nil
tail (h, t) = t

Теперь на C++.

struct Nil {};

template <class H, class T = Nil>
struct Cons {};

template <class L>
struct Head { using type = L; };

template <class H, class T>
struct Head<Cons<H, T>> { using type = H; };

template <class L>
struct Tail { using type = Nil; };

template <class H, class T>
struct Tail<Cons<H, T>> { using type = T; };

Cons (сокращение от construct) позволяет собирать пару типов в новый тип. Фактически, например, список [char, short, int, long] записывается как Cons<char, Cons<short, Cons<int, Cons<long, Nil>>>>. Это не слишком удобно. Добавим вспомогательные определения, позволяющие сократить запись.

// *T -- синоним выборки зависимого имени type
template <class L>
using HeadT = typename Head<L>::type;

template <class L>
using TailT = typename Tail<L>::type;

template <class... Types>
struct List {};

template <>
struct List<> { using type = Nil; };

template <class H, class... T>
struct List<H, T...> 
{ using type = Cons<H, typename List<T...>::type>; };

template <class... Types>
using ListT = typename List<Types...>::type;

Теперь тот же список типов, что был приведён выше, можно записать как ListT<char, short, int, long>.
Обработка списка распадается на обращение к голове и рекурсивную обработку хвоста. Напишем функцию, выводящую в консоль названия типов, зафиксированных в списке (я воспользуюсь частичной специализацией шаблонов функций, появившейся в C++11).

template <class List>
void print_typelist()
{
  std::cout << typeid(HeadT<List>).name() << ' ';
  print_typelist<TailT<List>>();
}

template <>
void print_typelist<Nil>() {}

Предположим, что есть метафункция f : type -> type и требуется получить список результатов применения данной функции к исходному списку (операция map). Как это реализовать?

map f Nil = Nil
map f (h, t) = (f h, map f t)

Чтобы оформить это на C++, необходимо решить, на какой вариант представления метафункций при этом ориентироваться. В данном случае, я выбрал вариант 2 как основной, применяемый Стандартной библиотекой.

template <template <class A> class F, class L>
struct Map
{ using type = typename F<L>::type; };

template <template <class A> class F, class H, class T>
struct Map<F, Cons<H, T>>
{
  using type = Cons<typename F<H>::type,
                    typename Map<F, T>::type>;
};

template <template <class A> class F>
struct Map<F, Nil> { using type = Nil; };

Предположим, есть метафункция b(x, y), принимающая два параметра. Тогда можно поставить задачу о свёртке списка, т.е. вычисления выражения вида b(start, b(item1, b(item2, …, b(itemN-1, itemN)…))). В функциональных языках функцию, позволяющую выполнить такую свёртку списка для произвольных функции b и начального значения start, обычно называют foldr (правоассоциативная свёртка). Я буду использовать следующее определение на C++.

template <
  template <class A, class B> class F,
  class S, class L>
struct Fold
{
  using type = S;
  static const auto value = type::value;
};

template <
  template <class A, class B> class F,
  class S, class H, class T>
struct Fold<F, S, Cons<H, T>>
{
  using type = typename
    F<S, typename Fold<F, H, T>::type>::type;
  static const auto value = type::value;
};

Воспользуемся Fold для определения операций проверки выполнения некоторого предиката на каком-либо или на всех элементах списка.

template <bool B>
using Bool = std::integral_constant<bool, B>;

using False = Bool<false>;
using True = Bool<true>;

template <class A, class B>
struct Or: Bool<A::value || B::value> {};

template <class A, class B>
struct And: Bool<A::value && B::value> {};

template <class L>
using ExistsTrue = typename Fold<Or, False, L>::type;

template <class L>
using AllTrue = typename Fold<And, True, L>::type;

Например, мы хотим проверить, принадлежит ли некоторый тип заданному списку. Определим для этого метафункцию Belongs тип список:

template <
  template <class A, class B> class F,
  class A>  // карринг
struct Bind
{
  template <class B>
  using apply = typename F<A, B>::type;
};

template <class T, class L>
struct Belongs
  : ExistsTrue<typename 
      Map<Bind<std::is_same, T>::template apply, L>::type> {};

На данной основе не сложно определить и другие операции, обычно определяемые для списков (например, вычисление длины).

Исходный код

Метафункции C++

Общее определение: функции, вычисляемые во время компиляции, в том числе, позволяющие вычислять типы.

Механизм шаблонов C++ является чистым функциональным языком (с громоздким синтаксисом), выражения на котором вычисляются во время компиляции, поэтому основной метод реализации метафункций опирается на механизм шаблонов и (частичной) специализации. В C++2011 появился второй метод: на основе constexpr, здесь он не рассматривается.

Я буду выписывать «определения» в псевдокоде, напоминающем Haskell, а затем приводить аналог на C++.

Связывание имени с константой

let x = y
// x -- новое имя для значения y
// применительно к типам в C++
// C++1998
typedef y x;

// C++2011
using x = y;
Вариант 1

Пусть f принимает тип и возвращает тип.

Определение

f :: type -> type
f x = ...
template <class x> class f { ... };

Применение

f x  // или
f(x) // или
(f x)
f<x> // C++

Функции высших порядков

f :: (type -> type) -> type
f x = ...
template <template <class> x> class f { ... };

Достоинство: краткость синтаксиса применения.

Недостатки:

  • нельзя сопоставить уже существующие типы (например, нельзя выразить определение f int = float);
  • неудобно использовать функции высших порядков.
Вариант 2

Прообраз введён стандартной библиотекой C++, использующей зависимые имена в шаблонах (например, в std::unary_function, классах характеристик std::char_traits, std::iterator_traits, контейнерах).
Популяризован библиотеками Boost.MPL, Boost.TypeTraits (последняя вошла в стандарт C++2011).

Определение

f :: type -> type
f x = expr
template <class x> struct f
{
  typedef expr type;
};

Применение

f x // f(x)
typename f<x>::type // C++

Достоинства:

  • можно привязать любой тип;
  • можно задать мультифункцию (несколько зависимых имён);
  • можно вычислять не только типы, но и значения (традиционно используется вложенное имя value):
factorial :: unsigned -> unsigned
factorial n = n * factorial (n - 1)
factorial 0 = 1
template <unsigned n> struct factorial
{
  enum { value = n * factorial<n - 1>::value };
};

template <> struct factorial<0> { enum { value = 1u }; };

Другой классический пример такого рода: числа Фибоначчи.

  • можно задавать через наследование (используется std::conditional из type_traits):
uint :: unsigned -> type
uint bits = if bits < 9  then uint8_t  else
            if bits < 17 then uint16_t else
            if bits < 33 then uint32_t else
            uint64_t ;
template <unsigned bits> struct uint
  : conditional<(bits < 9),  uint8_t,  typename
    conditional<(bits < 17), uint16_t, typename
    conditional<(bits < 33), uint32_t,
    uint64_t >::type>::type> {};

Недостатки:

  • длинный синтаксис применения (причём typename требуется в контексте определения шаблона при использовании имён, зависящих от параметров шаблона, но запрещено в противном случае);
  • неудобно передавать в функции высшего порядка.

Замечание
С++2011 позволяет сократить синтаксис применения с помощью template-using объявления:

template <unsigned bits> using uint_t = typename uint<bits>::type;
uint_t<19> counter; // OK

Данный подход применяется в type_traits C++2014.

Замыкания и карринг

mul a b = a * b
mul5 = mul 5
thirty = mul5 6

Карринг в C++ напрямую не поддерживается. Его можно имитировать, разделив параметры шаблона.

template <int a>
struct mul
{
  template <int b>
  struct curried { enum { value = a * b }; };
};

using mul5 = mul<5>;
const auto thirty = mul5::curried<6>::value;

Обработка списков (C++2011 variadic templates)

len :: [type] -> int
len x:xs = 1 + len xs
len [] = 0
template <class ...xs>
struct len {};

template <class x, class ...xs>
struct len<x, xs...> { enum { value = 1 + len<xs...>::value }; };

template <>
struct len<> { enum { value = 0 }; };

Использование одновременно значений и типов в качестве параметров может быть затруднено отсутствием перегрузки метафункций. Поэтому для целочисленных типов в type_traits введена обёртка integral_constant (увы, писать выражения с помощью обычных арифметических и логических операций становится невозможно). Определим factorial на её основе (вариант с «хвостовой» рекурсией).

factorial n f = factorial (n - 1) (n * f)
factorial 0 f = f
template <uint64_t n>
using Uint = integral_constant<uint64_t, n>;

using Zero = Uint<0>;
using One = Uint<1>;

template <class N, class M>
struct Sub
  : Uint<N::value - M::value> {};

template <class N, class M>
struct Mul
  : Uint<N::value * M::value> {};

template <class N, class F = One>
struct factorial
  : factorial<Sub<N, One>, Mul<F, N>> {};

template <class F>
struct factorial<Zero, F>
  : F {};

Увы, приведённый код не компилируется. Дело в том, что подстановка шаблонов выполняется немедленно, ленивые вычисления для типов не используются, поэтому компилятор не способен «дойти» до template < class F > struct factorial. Следующий вариант также не будет компилироваться:

template <class N, class F = One>
struct factorial
{
  using base = factorial<Sub<N, One>, Mul<F, N>>;
  using type = typename base::type;
  enum { value = base::value };
};

Впрочем, обойти эту проблему можно, сразу включив условие в определение:

template <class N, class F = One>
struct factorial
  : conditional<N::value != 0,
      factorial<Sub<N, One>, Mul<N, F>>,
      F>::type {};
Вариант 3

Отделение имени от параметров шаблона с помощью вложенных определений. Первый известный мне подобный пример — стандартные аллокаторы C++1998 (rebind). Также применяется в Boost.MPL.

Определение

f x = expr
struct f
{
  template <class T> struct apply { typedef expr type };
};

Применение

f x
typename f::template apply<x>::type

Достоинства:

  • все из варианта 2;
  • удобно передавать в функции высшего порядка (универсальность: достаточно оперировать именами метафункций, являющимися обычными типами, а не шаблонами), в частности, такую метафункцию можно передать саму себе в качестве параметра;

Недостаток: ещё более длинный синтаксис применения (для прямого применения возможно сокращение с помощью template-using, что, впрочем, не спасает при описании выражений внутри метафункций).

Перечисленные варианты могут быть скомбинированы ради удобства, однако очень легко (особенно, учитывая тяжёлый синтаксис) залезть в такие дебри, что и компилятор может зависнуть или завершиться с ошибкой при попытке это разобрать, поэтому к использованию метафункций C++ следует подходить прагматически, не бросаясь в абстракции и не пытаясь достичь степени общности более высокой, чем требуется текущей задачей.