- PVSM.RU - https://www.pvsm.ru -
Не буду сильно углубляться в теорию. Что такое частичное применение легко найти в интернете. В том числе на Википедии [1].
Если кратко, то это механизм, возволяющий зафиксировать k
аргументов функции от n
аргументов, сделав из неё функцию от (n - k)
аргументов.
// Пусть имеется функция f от четырёх аргументов:
int f (int a, int b, int c, int d)
{
return a + b + c + d;
}
// Фиксируем первые два аргумента:
auto g = part(f, 1, 2); // 1 + 2 + ...
// Добрасываем оставшиеся два:
assert(g(3, 4) == 10); // ... + 3 + 4 = 10
На эту тему уже существует масса публикаций, в том числе и на Хабре:
А ветка "How should I make function curry? [5]" на stackoverflow — просто кладезь для тех, кто впервые сталкивается с этой темой.
К сожалению, количество пока не переросло в качество, и хорошего, пригодного к использованию варианта я так и не увидел.
При этом любопытно вот что.
Замечательный факт №1. В упомянутых статьях присутствуют все техники, которые нужны для реализации правильного (по моему мнению) частичного применения.
Надо только всё внимательно проанализировать и сложить кубики в правильном порядке.
Именно этим я и собираюсь заняться в данной статье.
Итак, какие цели стоят перед нами:
Собственно реализация требуемой функциональности
То есть реализация в каком-то виде частичного применения функции.
Максимально возможная эффективность
Нельзя забывать, что мы пишем на языке C++, одним из основных принципов которого является принцип "Абстракции без накладных расходов" (см. Stroustrup, Foundations of C++ [13]).
В частности, не должно произойти ни одного лишнего копирования и ни одного лишнего переноса.
Удобство в использовании
Прикладному программисту должно быть легко создавать частично применённые функции.
Также ему должно быть легко использовать частично применённые функции совместно с уже существующими решениями. Например, передавать частично применённую функцию в какой-то стандартный алгоритм.
Авторы имеющихся решений предлагают два основных варианта. Назовём их применение по возможности и явное применение.
Эта техника заключается в том, что результат частичного применения — это функция, которую снова можно частично применить. А вызов исходной функции происходит тогда, когда полученных аргументов уже достаточно для того, чтобы произвести вызов.
// Пусть дана функция:
int f (int a, int b, int c, int d);
// Частичное применение функции:
auto g = part(f);
// Фиксируем первый элемент:
auto h = g(1);
// Одного аргумента недостаточно для вызова функции `f`, поэтому функция пока не вызывается.
// Забрасываем ещё два аргумента:
auto i = h(2, 3);
// Трёх аргументов по-прежнему недостаточно для вызова функции `f`.
// Забросили последний аргумент, функция может быть вызвана, следовательно,
// этот вызов и происходит.
assert(i(4) == 10);
Достаточно остроумная идея.
Но, к сожалению, на практике не работает.
Почему?
Допустим, мы хотим частично применить функцию, вычисляющую сумму произвольного количества переменных:
auto sum (auto ... xs);
В таком случае, мы не знаем, когда нужно остановиться в процессе частичного применения.
Эта сумма вычисляется и от одного, и от двух, и от трёх, да и вообще от любого количества переменных.
Следовательно, предыдущий пример ломается на втором шаге, если вместо f
подставить sum
:
auto g = part(sum);
auto ??? = g(1); // Уже вычислять, или пока нет?
То же самое произойдёт, если у функции есть несколько перегрузок с разным количеством аргументов. Будет непонятно, какую из них нужно вызвать.
Есть и другая проблема, когда можно "проскочить" правильное количество аргументов.
В нашем примере можно изобразить так:
auto g = part(f, 1, 2, 3);
auto h = g(4, 5, 6); // Ой...
Тогда функция будет частично применяться до бесконечности, и никогда не будет вызвана.
Итак, — говорят авторы, — раз мы не знаем, когда нужно остановить частичное применение, давайте сделаем это явно.
А именно, создадим перегрузку оператора "скобочки" без аргументов, вызов которого будет означать, что нужно вызвать внутреннюю функцию с теми параметрами, которые уже были частично применены:
auto g = part(sum);
auto h = g(1); // Уже вычислять, или пока нет? Пока нет!
auto i = h(2, 3, 4, 5, 6); // Записываем новые аргументы и снова ждём.
assert(i() == 21); // А вот теперь вычисляем.
Старая проблема решена. Но возникла новая.
Теперь каждое использование частично применённой функции подразумевает знание о том, что это именно частично применённая функция. Это значит, что её не получится использовать в стандартных алгоритмах. Они просто не знают о том, что после забрасывания аргументов нужно ещё позвать пустые "скобочки".
Чтобы продвинуться дальше, немного пофилософствуем и выскажем пару важных мыслей.
Частичное применение является отложенным вызовом.
Иначе говоря, частичное применение не производит никаких "частичных вычислений". Оно просто запоминает несколько аргументов и ждёт, пока придут остальные.
Если для суммы, произведения и других ассоциативных функций ещё можно придумать костыль, который будет уметь и возвращать частично вычисленный результат (сумму или произведение полученных ранее чисел), и продолжать частичное применение, то для произвольной функции такое решение не подойдёт.
В языке C++ нет встроенного механизма частичного применения.
Это значит, что программист, вообще говоря, не ожидает, что может какой-то произвольной функции передать только часть аргументов, а остальные "добросить" когда-нибудь потом.
Следовательно, работая с частичным применением, программист заведомо знает, что он его использует.
Значит, частичное применение в языке C++ всегда будет явным.
Выходит, перечисленные варианты не годятся.
Из-за, казалось бы, маленьких недочётов эти "прикольные" решения приходится признавать крайне непрактичными, и потому непригодными к повседневному использованию.
Всё же не стоит забывать, что C++ не является функциональным языком. Нельзя так просто взять и перенести конструкции и идеологию одного языка на другой.
Тут как с переводом поэзии с иностранного языка: перевод должен быть не дословным, а поэтическим, то есть рифмоваться в языке перевода.
Исходя из всего сказанного выше, я пришёл к следующему выводу.
Поскольку программист всегда знает, где у него частичное применение, а где вызов функции, то можно нашу модель одновременно и упростить, и сделать более универсальной.
Состоять она будет из двух этапов:
Проиллюстрирую на примере.
// Дана функция суммирования:
auto sum (auto ... xs);
// Частичное применение суммирования к трём аргументам.
auto f = part(sum, 1, 2, 3);
// Результат сохранён в функциональном объекте `f`.
// Вызов функции суммирования:
assert(f(4) == 10);
assert(f(4, 5) == 15);
assert(f(4, 5, 6) == 21);
Если нужно частично применить ещё несколько аргументов, то они "добрасываются" при помощи того же явного вызова функции частичного применения:
auto g = part(f, 4, 5); // Эквивалентно part(sum, 1, 2, 3, 4, 5).
std::bind
!Похоже, но нет.
С одной стороны, std::bind
позволяет обходиться с аргументами более гибко. Ставить их в произвольные места, перемешивать и т.п.
С другой стороны, std::bind
требует явного расставления заполнителей и не работает с произвольным числом аргументов. То есть пользователь обязан заранее указать, сколько аргументов будет "доброшено" в будущем, и на каких конкретно местах в вызове они будут стоять.
Поэтому я считаю, что получившееся решение достаточно самостоятельно и не является частным случаем каких-либо других имеющихся механизмов.
Возможно, самая интересная часть. Код.
В начале статьи я уже упоминал один замечательный факт. Так вот, есть ещё один.
Замечательный факт №2. В стандартной библиотеке (C++17) есть почти всё необходимое для реализации частичного применения по данной модели.
Нам придётся только доопределить одну операцию, которая, впрочем, тоже выражается через те же самые стандартные инструменты.
Итак, нам понадобятся (полный и исчерпывающий список):
Когда я говорил, что имеется почти всё необходимое, я имел в виду, что нужно доопределить одну функцию:
template <typename T>
constexpr decltype(auto) forward_tuple (T && t)
{
return apply(forward_as_tuple, std::forward<T>(t));
}
Данная функция принимает произвольный кортеж и возвращает новый кортеж, состоящий из ссылок на элементы входного кортежа. Если во входном кортеже лежали ссылки на lvalue
, то они такими и остаются. Те же объекты, которые хранились в кортеже, передаются по ссылке на rvalue
.
Теперь можно с уверенностью говорить, что всё необходимое у нас уже имеется. Можно писать код.
Функция part
template <typename ... As>
constexpr auto part (As && ... as)
-> part_fn<decltype(std::make_tuple(std::forward<As>(as)...))>
{
return {std::make_tuple(std::forward<As>(as)...)};
}
Принимает произвольное количество аргументов, первым из которых является некоторая функция или функциональный объект. Сохраняет их все в один кортеж при помощи функции make_tuple
и возвращает этот кортеж, завёрнутый в структуру part_fn
.
Структура part_fn
template <typename Tuple>
struct part_fn
{
template <typename ... As>
constexpr decltype(auto) operator () (As && ... as) const &
{
return apply(invoke,
std::tuple_cat(forward_tuple(t), std::forward_as_tuple(std::forward<As>(as)...)));
}
template <typename ... As>
constexpr decltype(auto) operator () (As && ... as) &
{
return apply(invoke,
std::tuple_cat(forward_tuple(t), std::forward_as_tuple(std::forward<As>(as)...)));
}
template <typename ... As>
constexpr decltype(auto) operator () (As && ... as) &&
{
return apply(invoke,
std::tuple_cat(forward_tuple(std::move(t)), std::forward_as_tuple(std::forward<As>(as)...)));
}
Tuple t;
};
Хранит частично применённые объекты: функцию и первые её k
аргументов.
Имеет оператор "скобочки", который принимает произвольное количество аргументов
forward_as_tuple
.forward_tuple
.tuple_cat
. Получается один большой кортеж ссылок.invoke
при помощи функции apply
.invoke
от полученных аргументов.
Всё.
В этом месте любители хитровывернутого шаблонного кода (как я, например), должны испытать лёгкое разочарование.
С другой стороны, простота, элегантность решения и то, что оно собрано всего из нескольких стандартных "кубиков", косвенно свидетельствует о том, что оно вполне жизнеспособно и может быть легко интегрировано в прикладной код.
int modulo_less (int modulo, int a, int b)
{
return (a % modulo) < (b % modulo);
}
auto v = std::vector<int>{...};
std::sort(v.begin(), v.end(), part(modulo_less, 7));
Благодаря вызову make_tuple
поддерживаются std::ref/cref
:
int append (std::string & s, int x)
{
return s += std::to_string(x);
}
auto s = std::string("qwerty");
auto g = part(append, std::ref(s));
g(5);
g(6);
assert(s == "qwerty56");
А благодаря использованию функции invoke
будут поддерживаться различные сложные случаи, такие как вызов метода класса (см. std::invoke [18]) и т.п.
И всё это "из коробки" и без каких-либо специальных телодвижений с нашей стороны.
Почему я считаю своё решение правильным.
reference_wrapper
для сигнализирования о передаче параметров по ссылке (как в std::make_tuple
, std::bind
, std::thread
), а также, что очень важно, с алгоритмами.Полный исходный код здесь: https://github.com/izvolov/burst/blob/master/burst/functional/part.hpp [21]
К содержанию [12]
Автор: izvolov
Источник [22]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/202350
Ссылки в тексте:
[1] на Википедии: https://ru.wikipedia.org/wiki/Частичное_применение
[2] C++ Variadic templates. Каррирование и частичное применение: https://habrahabr.ru/post/133084
[3] Частичное применение и каррирование в C++: https://habrahabr.ru/post/149056
[4] Каррируем на C++: https://habrahabr.ru/post/238879
[5] How should I make function curry?: http://stackoverflow.com/questions/26655685/how-should-i-make-function-curry
[6] Цели: #goals
[7] Существующие решения: #bad-solutions
[8] Философствования: #philosophy
[9] Новое решение: #good-solution
[10] Реализация: #implementation
[11] Заключение: #conclusion
[12] Цели: #contents
[13] Stroustrup, Foundations of C++: http://www.stroustrup.com/ETAPS-corrected-draft.pdf
[14] std::forward: http://en.cppreference.com/w/cpp/utility/forward
[15] std::move: http://en.cppreference.com/w/cpp/utility/move
[16] std::forward_as_tuple: http://en.cppreference.com/w/cpp/utility/tuple/forward_as_tuple
[17] std::apply: http://en.cppreference.com/w/cpp/utility/apply
[18] std::invoke: http://en.cppreference.com/w/cpp/utility/functional/invoke
[19] std::tuple_cat: http://en.cppreference.com/w/cpp/utility/tuple/tuple_cat
[20] std::make_tuple: http://en.cppreference.com/w/cpp/utility/tuple/make_tuple
[21] https://github.com/izvolov/burst/blob/master/burst/functional/part.hpp: https://github.com/izvolov/burst/blob/master/burst/functional/part.hpp
[22] Источник: https://habrahabr.ru/post/313370/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.