izvolov Oct 24 2016 at 12:31

Элементы функционального программирования в C++: частичное применение

8 min

15K

C++*Programming*Designing and refactoring*Functional Programming*

Не буду сильно углубляться в теорию. Что такое частичное применение легко найти в интернете. В том числе на Википедии.

Если кратко, то это механизм, позволяющий зафиксировать 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?" на stackoverflow — просто кладезь для тех, кто впервые сталкивается с этой темой.

К сожалению, количество пока не переросло в качество, и хорошего, пригодного к использованию варианта я так и не увидел. При этом любопытно вот что.

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

Надо только всё внимательно проанализировать и сложить кубики в правильном порядке. Именно этим я и собираюсь заняться в данной статье.

Цели

Итак, какие цели стоят перед нами:

Собственно реализация требуемой функциональности

То есть реализация в каком-то виде частичного применения функции.
Максимально возможная эффективность

Нельзя забывать, что мы пишем на языке C++, одним из основных принципов которого является принцип "Абстракции без накладных расходов" (см. Stroustrup, Foundations of C++).

В частности, не должно произойти ни одного лишнего копирования и ни одного лишнего переноса.

Скрытый текст
Добавлю, что это не только одно из самых важных мест в программировании на плюсах, но, одновременно, и одно из самых интересных.
Удобство в использовании

Прикладному программисту должно быть легко создавать частично применённые функции.

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

Существующие решения

Авторы имеющихся решений предлагают два основных варианта. Назовём их применение по возможности и явное применение.

Применение по возможности

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

// Пусть дана функция:
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;
};
```
1. Хранит частично применённые объекты: функцию и первые её k аргументов.
2. Имеет оператор "скобочки", который принимает произвольное количество аргументов
  1. При вызове формируется кортеж ссылок на входные аргументы при помощи функции forward_as_tuple.
  2. Кортеж с сохранёнными ранее объектами также преобразуется в кортеж ссылок при помощи определённой нами функции forward_tuple.
  3. Оба кортежа ссылок склеиваются в один при помощи функции tuple_cat. Получается один большой кортеж ссылок.
  4. Склеенный кортеж разворачивается и передаётся в функцию invoke при помощи функции apply.
  5. Вызов функции 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) и т.п.

И всё это "из коробки" и без каких-либо специальных телодвижений с нашей стороны.

Заключение

Почему я считаю своё решение правильным.

Оно просто и прозрачно. Собирается из "элементарных" компонент, которые уже есть в языке.
Оно эффективно. Абстракция без накладных расходов.
Надёжно как молоток. Никакой "магии".
Хорошо встраивается в существующую парадигму программирования на языке C++.
Совместимо с инструментами, которые используются в стандартной библиотеке. Например, с reference_wrapper для сигнализирования о передаче параметров по ссылке (как в std::make_tuple, std::bind, std::thread), а также, что очень важно, с алгоритмами.

» Полный исходный код здесь.

К содержанию

Tags:

Hubs: