Каррирование и частичное применение на C++14

В этой статье я расскажу об одном из вариантов каррирования и частичного применения функций в любимом мною C++, покажу свою экспериментальную реализацию сего действа и объясню без математики, на пальцах, что такое вообще каррирование и что же под капотом у kari.hpp, с помощью которой мы и будем каррировать функции. Ну и как тут принято: заинтересовавшихся — прошу под кат.

Каррирование

Что же такое каррирование? Кажется мне, что это одно из самых популярных слов, которым любят бросаться программисты на Haskell (после монад, естественно). А суть термина проста как палка и кто в курсе его смысла или писал на языках вроде ML или Haskell — может спокойно пропускать этот раздел.

Каррирование — это операция преобразования функции N аргументов в функцию от одного аргумента, которая возвращает функцию от следующего аргумента и т.д. пока не вернём функцию от последнего аргумента, которая их все и не применит. Погнали с примерами:

int sum2(int lhs, int rhs) {
  return lhs + rhs;
}

Имеем бинарную функцию сложения. Как превратить её в функцию от одного аргумента? Очень просто:

auto curried_sum2(int lhs) {
  return [=](int rhs) {
    return sum2(lhs, rhs);
  };
}

Что мы сделали? Захватили по значению наш единственный аргумент в лямбду, которая принимает второй оставшийся аргумент и выполняет, в конечном итоге, операцию сложения. В результате можем применять нашу каррированную функцию curried_sum2 по очереди к своим аргументам:

// output: 42
std::cout << sum2(40, 2) << std::endl;
std::cout << curried_sum2(40)(2) << std::endl;

Всё, в этом и есть смысл операции каррирования. Всё это, конечно, можно провернуть на функциях любой арности — суть останется одинаковой, нужно будет возвращать каррированную функцию от N-1 аргументов при каждом применении функции на аргумент:

auto sum3(int v1, int v2, int v3) {
  return v1 + v2 + v3;
}

auto curried_sum3(int v1) {
  return [=](int v2){
    return [=](int v3){
      return sum3(v1, v2, v3);
    };
  };
}

// output: 42
std::cout << sum3(38, 3, 1) << std::endl;
std::cout << curried_sum3(38)(3)(1) << std::endl;

Частичное применение

Частичное применение — это возможность вызывать функции N аргументов передавая в них только часть этих аргументов, результатом такого вызова будет другая функция от оставшихся аргументов.

Тут стоит оговориться, что в языках вроде Haskell всё это работает в автоматическом режиме за спиной у программиста. Это мы и попытаемся изобразить, т.е., в идеале, нужна возможность вызвать нашу функцию sum3 вот так: sum3(38,3)(1) или вот так: sum3(38)(3,1). Вдобавок ко всему, если функция возвращает другую каррированную функцию, её таким же образом можно вызывать списком аргументов к первой. Например:

int boo(int v1, int v2) {
  return v1 + v2;
}

auto foo(int v1, int v2) {
  return kari::curry(boo, v1 + v2);
}

// output: 42
std::cout << kari::curry(foo)(38,3,1) << std::endl;
std::cout << kari::curry(foo)(38,3)(1) << std::endl;
std::cout << kari::curry(foo)(38)(3,1) << std::endl;

Пришлось забежать немного вперёд и показать использование kari.hpp и да, она это умеет.

Постановка целей

Чтобы что-то написать — нужно (желательно?) понимать, что же мы хотим получить на выходе. А на выходе мы хотим получить возможность каррировать и частично применять всё, что может вызываться в C++. А именно:

• лямбды (включая обобщённые (generic) лямбды)
• функциональные объекты (функторы)
• функции любой арности (включая шаблонные функции)
• функции с переменным количеством аргументов (variadic)
• методы классов

Функции с переменным количеством аргументов можно каррировать через конкретное указание количества аргументов, которое мы хотим каррировать. Также желательно нормальное взаимодействие с std::bind и его результатами. И конечно обязательно нужна возможность применять функции на несколько аргументов и иметь возможность вызывать вложенные функции так, чтобы казалось, что мы взаимодействуем с одной каррированной функцией.

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

Автор, ты сейчас пытаешь изобрести std::bind!

И да и нет. std::bind без сомнения мощный и проверенный инструмент, я не собираюсь писать его убийцу или альтернативную реализацию. Да, его можно использовать как инструмент для каррирования и явного частичного применения (с указанием того, что применяем, на какое место и сколько). Но это неудобно для подобных дел и не всегда применимо, т.к нужно знать конкретную арность функции и в зависимости от неё писать конкретные биндинги (связывания?). Пример:

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

// std::bind
auto c0 = std::bind(foo, _1, _2, _3, _4);
auto c1 = std::bind(c0, 15, _1, _2, _3);
auto c2 = std::bind(c1, 20, 2, _1);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

// kari.hpp
auto c0 = kari::curry(foo);
auto c1 = c0(15);
auto c2 = c1(20, 2);
auto rr = c2(5);
std::cout << rr << std::endl; // output: 42

API

namespace kari {
  template < typename F, typename... Args >
  constexpr decltype(auto) curry(F&& f, Args&&... args) const;

  template < typename F, typename... Args >
  constexpr decltype(auto) curryV(F&& f, Args&&... args) const;

  template < std::size_t N, typename F, typename... Args >
  constexpr decltype(auto) curryN(F&& f, Args&&... args) const;

  template < typename F >
  struct is_curried;

  template < typename F >
  constexpr bool is_curried_v = is_curried<F>::value;

  template < std::size_t N, typename F, typename... Args >
  struct curry_t {
    template < typename... As >
    constexpr decltype(auto) operator()(As&&... as) const;
  };
}

---

kari::curry(F&& f, Args&&... args)

Возвращает функциональный объект типа curry_t (каррированную функцию) с применёнными опциональными аргументами args или результат применения аргументов к переданной функции f (если функция нульарная, либо переданных аргументов хватило для её вызова).

При передаче параметром f уже каррированной функции — возвращает её копию с применёнными к ней аргументами args.

---

kari::curryV(F&& f, Args&&... args)

Позволяет каррировать функции с переменным количеством аргументов. Такие функции могут быть вызваны в дальнейшем оператором () без аргументов. Пример:

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);
c2(); // output: 37 + 5 = 42

При передаче параметром f уже каррированной функции — возвращает её копию с изменённым типом применения на переменное количество аргументов с применёнными аргументами args.

---

kari::curryN(F&& f, Args&&... args)

Позволяет каррировать функции с переменным количеством аргументов с указанием конкретного количества аргументов N, которое мы хотим применить (помимо тех, что передали как args). Пример:

char buffer[256] = {''};
auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d");
c(37, 5, 42);
std::cout << buffer << std::endl;  // output: 37 + 5 = 42

При передаче параметром f уже каррированной функции — возвращает её копию с изменённым типом применения на N аргументов с применёнными аргументами args.

---

kari::is_curried<F>, kari::is_curried_v<F>

Вспомогательные структурки для проверки функции на предмет её каррированности. Пример:

const auto l = [](int v1, int v2){
  return v1 + v2;
};
const auto c = curry(l);

// output: is `l` curried? no
std::cout
  << "is `l` curried? "
  << (is_curried<decltype(l)>::value ? "yes" : "no")
  << std::endl;

// output: is `c` curried? yes
std::cout
  << "is `c` curried? "
  << (is_curried_v<decltype(c)> ? "yes" : "no")
  << std::endl;

---

kari::curry_t::operator()(As&&... as)

Оператор частичного или полного применения каррированной функции. Результатом вызова является каррированная функция от оставшихся аргументов исходной функции типа F, либо результат этой функции полученный её применением на накопленные аргументы и переданные в вызове новые аргументы as. Пример:

int foo(int v1, int v2, int v3, int v4) {
  return v1 + v2 + v3 + v4;
}

auto c0 = kari::curry(foo);
auto c1 = c0(15, 20); // partial application
auto rr = c2(2, 5); // function call - foo(15,20,2,5)
std::cout << rr << std::endl; // output: 42

Вызов без аргументов каррированной функции с помощью curryV или curryN приведёт к попытке его вызова, если аргументов на этот вызов хватает. В противном случае вернёт частично применённую функцию. Пример:

auto c0 = kari::curryV(std::printf, "%d + %d = %d");
auto c1 = c0(37, 5);
auto c2 = c1(42);

// force call variadic function std::printf
c2(); // output: 37 + 5 = 42

Детали реализации

Приводя детали реализации я буду использовать C++17, дабы сократить количество текста и избежать лишних объяснений и нагромождений SFINAE, а также реализаций того, что пришлось дописать в рамках стандарта 14-ого года. Все эти подробности можно посмотреть в репозитории проекта и заодно поставить звёздочку :)

---

make_curry(F&& f, std::tuple<Args...>&& args)

Вспомогательная функция, которая создаёт функциональный объект curry_t или применяет переданную функцию f к аргументам args.

template < std::size_t N, typename F, typename... Args >
constexpr auto make_curry(F&& f, std::tuple<Args...>&& args) {
  if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) {
    return std::apply(std::forward<F>(f), std::move(args));
  } else {
    return curry_t<
      N,
      std::decay_t<F>,
      Args...
    >(std::forward<F>(f), std::move(args));
  }
}

template < std::size_t N, typename F >
constexpr decltype(auto) make_curry(F&& f) {
  return make_curry<N>(std::forward<F>(f), std::make_tuple());
}

Два интересных момента в этой функции:

• применяем функцию к аргументам только если она вызываемая на этих аргументах и счётчик применений N в нуле
• если же функция не применяемая, то считаем такой вызов частичным применением и создаём функциональный объект curry_t с функцией и переданными аргументами в качестве его содержимого

---

struct curry_t

Функциональный объект, который будет хранить наши накопленные аргументы и функцию, которую необходимо будет вызвать при конечном применении, именно его мы будем вызывать и частично применять.

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  template < typename U >
  constexpr curry_t(U&& u, std::tuple<Args...>&& args)
  : f_(std::forward<U>(u))
  , args_(std::move(args)) {}
private:
  F f_;
  std::tuple<Args...> args_;
};

Хранить накопленные аргументы args_ в std::tuple хорошая идея по нескольким причинам:

1) автоматическая обработка ситуации с std::ref, дабы хранить ссылки когда это нужно, а по умолчанию по значению
2) удобное применение функции на аргументы в нём (std::apply)
3) оно уже готово и не надо писать руками :)

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

Шаблонный параметр N служит счётчиком применений для функций с переменным количеством параметров.

---

curry_t::operator()(const As&...)

Ну и конечно, вся соль происходящего в вызывающем функциональный объект операторе.

template < std::size_t N, typename F, typename... Args >
struct curry_t {
  // 1
  constexpr decltype(auto) operator()() && {
    return detail::make_curry<0>(
      std::move(f_),
      std::move(args_));
  }

  // 2
  template < typename A >
  constexpr decltype(auto) operator()(A&& a) && {
    return detail::make_curry<(N > 0 ? N - 1 : 0)>(
      std::move(f_),
      std::tuple_cat(
        std::move(args_),
        std::make_tuple(std::forward<A>(a))));
  }

  // 3
  template < typename A, typename... As >
  constexpr decltype(auto) operator()(A&& a, As&&... as) && {
    return std::move(*this)(std::forward<A>(a))(std::forward<As>(as)...);
  }

  // 4
  template < typename... As >
  constexpr decltype(auto) operator()(As&&... as) const & {
    auto self_copy = *this;
    return std::move(self_copy)(std::forward<As>(as)...);
  }
}

Мы имеем четыре перегруженных функции оператора вызова.

1. Функция без параметров служит способом начать попробовать применять функцию с переменным количеством аргументов (созданную с помощью curryV или curryN). В ней мы понижаем счетчик применений до нуля показывая тем самым, что функцию пора применять и передаём всё нужное для этого функции make_curry.

2. Функция от одного аргумента понижает счетчик применений на единицу (если есть куда понижать) и складывает наш новый аргумент a в кортеж с уже накопленными аргументами args_ и передаёт это в make_curry.

3. Функция от переменного количества аргументов служит уловкой для частичного применения нескольких аргументов. Она рекурсивно применяет их по одному. Применить их все разом не получится по двум причинам:

   • счётчик применений может достигнуть нуля раньше, чем кончатся аргументы
   • функция f_ может вызваться раньше и вернуть другую каррированную функцию и следующие аргументы предназначаются ей

4. Последняя функция служит мостом для вызова curry_t по lvalue и функциями вызова по rvalue.

Магии происходящему добавляют пометки ref-qualified функций. Если коротко, то с их помощью мы узнаём, что объект вызвали по rvalue ссылке и можно спокойно перемещать аргументы вместо копирования в конечную вызывающую функцию make_curry. В противном же случае мы обязаны копировать аргументы, чтобы сохранить возможность вызывать эту функцию ещё раз зная, что её аргументы на месте.

Бонусы

Перед заключением хотелось бы привести пару примеров синтаксического сахара построенного в kari.hpp и идущего в комплекте с ней бонусом.

Сечения операторов

Программисты знакомые с языком Haskell хорошо знакомы с сечениями операторов, которые позволяют коротко описать частичное применение операторов в нём. Конструкция (*2), например, порождает функцию от одного аргумента, результатом которой будет умножение на 2 переданного аргумента. Хотелось изобразить что-то подобное на C++. Сказано — сделано!

using namespace kari::underscore;
std::vector<int> v{1,2,3,4,5};
std::accumulate(v.begin(), v.end(), 0, _+_);        // result: 15
std::transform(v.begin(), v.end(), v.begin(), _*2); // v = 2, 3, 6, 8, 10
std::transform(v.begin(), v.end(), v.begin(), -_);  // v = -2,-3,-6,-8,-10

Композиции функций

Ну и диагноз был бы неокончательным, если бы не пришла идея изобразить композицию функций. Для оператора композиции был выбран operator * как наиболее внешне похожий из доступных на символ композиции в математике. Им же можно применять получившуюся функцию на аргумент. Результат:

using namespace kari::underscore;

// 1
std::cout << (_*2) * (_+2) * 4 << std::endl; // output: 12

// 2
std::cout << 4 * (_*2) * (_+2) << std::endl; // output: 10

1. композиция функций (*2) и (+2) применяется на 4. (4 + 2) * 2 = 12
2. функция (*2) применяется к 4 и к результату применяется (+2). (4 * 2 + 2) = 10

При этом можно составлять достаточно сложные композиции в бесточечной нотации, но понятны они будут только программистам на Haskell :)

// (. (+2)) (*2) $ 10 == 24 // haskell аналог
std::cout << (_*(_+2))(_*2) * 10 << std::endl; // output: 24

// ((+2) .) (*2) $ 10 == 24 // haskell аналог
std::cout << ((_+2)*_)(_*2) * 10 << std::endl; // output: 22

Заключение

И без меня понятно, что применять такое в реальных проектах не стоит, но я обязан был это сказать. Цель была скорее проверить себя и новый C++. А смогу ли я? А сможет ли C++? Ну что ж, как видим, кое-как, но смогли оба. Отдельное спасибо тем, кто дочитал до конца.

Автор: Матвей Черевко

Источник