Monthly Archives: Апрель 2014

Метафункции 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++ следует подходить прагматически, не бросаясь в абстракции и не пытаясь достичь степени общности более высокой, чем требуется текущей задачей.

Реклама

Интернет 42

Когда-то было модно заявлять «я не смотрю зомбоящик», а все новости узнавать из этих ваших интернетов («the internets» © G.W.Bush). Интернет превратился в площадку информационной войны (что стало очевидно во время событий «арабской весны») и окатывает своим шумом любого, осмелившегося погрузится в клокочущий хаос блогов и комментов. Но способен ли информационный шум реально изменить мнение читателя, «зомбировать», если уж на то пошло? Матожидание равнодействующей силы примерно равно нулю. В этих условиях мой вывод таков: каждый видит, в основном, то, что ожидает увидеть; каждый верит в то, во что хочет верить. Смысл создания шума в таком случае заключается в «укреплении» «своих рядов» и деморализации сомневающихся в «рядах противника» (и те и другие могут не подозревать, что они находятся в каких-то там «рядах»). Таким образом, информационный шум вызывает поляризацию и разделение в обществе, повышает накал. Его появление — недобрый знак, вестник революций и войн.

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

  1. Кто автор? Какова его мотивация? Возможные издержки или приобретения от поддержки той или иной стороны? Какая ожидаемая целевая аудитория (может анализироваться по комментариям)? Как соотносятся старые сообщения (если они есть, если они не исправлены post factum) с реальностью?
  2. Насколько правдоподобны изложенные «факты»? Насколько их реальность легко проверить? Изменится ли их воспринимаемая правдоподобность, если заменить страны, действующие лица, но вообразив примерно схожую ситуацию? Правдоподобность также можно оценивать по разумности описываемых действий с точки зрения лиц, их совершающих, или предполагаемых сил, за ними стоящих.
  3. Cui bono? Кому выгодно, чтобы человек согласился с основным посылом сообщения или возмутился? Какие могут быть возможные (в силу основных приводимых «фактов», очищенных от эмоций и декоративных подробностей, часто являющихся преувеличениями) альтернативные толкования?