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


Не буду сильно вдаватися в теорію. Що таке часткове застосування легко знайти в інтернеті. Зокрема на Вікіпедії.
Якщо коротко, то це механізм, возволяющий зафіксувати
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

На цю тему вже існує маса публікацій, в тому числі і на Хабре:
  1. C++ Variadic templates. Каррирование і часткове застосування
  2. Часткове застосування і каррирование в C++
  3. Каррируем на C++
А гілка "How should I make function curry?" на stackoverflow — просто джерело для тих, хто вперше стикається з цією темою.
На жаль, кількість поки не переросла в якість, і гарного, придатного до використання варіанту я так і не побачив.
При цьому цікаво ось що.
Чудовий факт №1. У згаданих статтях присутні всі техніки, які потрібні для реалізації правильного (на мою думку) часткового застосування.
Треба тільки уважно проаналізувати та скласти кубики в правильному порядку.
Саме цим я і збираюся зайнятися в даній статті.

Зміст
  1. Цілі
  2. Існуючі рішення
  3. Філософствування
  4. Нове рішення
  5. Реалізація
  6. Висновок

Цілі
Отже, які цілі стоять перед нами:
  1. Власне реалізація необхідної функціональності
    тобто реалізація в якомусь вигляді часткового застосування функції.
  2. Максимально можлива ефективність
    не Можна забувати, що ми пишемо на мові C++, одним з основних принципів якого є принцип "Абстракції без накладних витрат" (див. Stroustrup, Foundations of C++).
    зокрема, не повинно відбутися жодного зайвого копіювання і жодного зайвого переносу.
    Прихований текстДодам, що це не тільки одне з найважливіших місць в програмуванні на плюси, але, одночасно, і одне з найбільш цікавих.
  3. Зручність у використанні
    Прикладного програміста повинно бути легко створити частково застосовані функції.
    Також йому повинно бути легко частково застосовані функції спільно з вже існуючими рішеннями. Наприклад, передавати частково застосовану функцію в якийсь стандартний алгоритм.

Існуючі рішення
Автори наявних рішень пропонують два основних варіанти. Назвемо їх застосування по можливості і явне застосування.

Застосування по можливості

Ця техніка полягає в тому, що результат часткового застосування — це функція, яку знову можна частково застосувати. А виклик вихідної функції відбувається тоді, коли одержаних аргументів вже достатньо для того, щоб зробити виклик.
// Нехай дана функція:
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++ не є функціональним мовою. Не можна так просто взяти і перенести конструкції та ідеологію однієї мови на іншу.
Тут як з перекладом поезії з іноземної мови: переклад повинен бути не дослівним, а поетичним, тобто рифмоваться в мові перекладу.

Нове рішення
Виходячи з усього сказаного вище, я прийшов до наступного висновку.
Оскільки програміст завжди знає, де у нього часткове застосування, а де виклик функції, то можна нашу модель одночасно і спростити і зробити більш універсальною.
Складатиметься вона з двох етапів:
  1. Захоплення первинних аргументів.
  2. Безумовний виклик з рештою аргументами.
Проілюструю на прикладі.
// Дана функція підсумовування:
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) є майже все необхідне для реалізації часткового застосування даної моделі.
Нам доведеться тільки довизначити одну операцію, яка, втім, теж виражається через ті ж самі стандартні інструменти.
Отже, нам знадобляться (повний і вичерпний список):
  1. std::forward
  2. std::move
  3. std::forward_as_tuple
  4. std::apply
  5. std::invoke
  6. std::tuple_cat
  7. std::make_tuple
Коли я говорив, що є майже все необхідне, я мав на увазі, що потрібно довизначити одну функцію:
template < typename T>
constexpr decltype(auto) forward_tuple (T && t)
{
return apply(forward_as_tuple, std::forward<T>(t));
}

Дана функція приймає довільний кортеж і повертає новий кортеж, що складається з посилань на елементи вхідного кортежу. Якщо у вхідному кортежі лежали посилання на
lvalue
, то вони такими і залишаються. Ті ж об'єкти, які зберігалися в кортежі, передаються по посиланню
rvalue
.
Тепер можна з упевненістю говорити, що все необхідне у нас вже є. Можна писати код.
  1. Функція
    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
    .
  2. Структура
    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) і т. п.
І все це "з коробки" і без яких-небудь спеціальних рухів з нашого боку.

Висновок
Чому я вважаю своє рішення правильним.
  1. Воно просто і прозоро. Збирається з "елементарних" компонент, які вже є в мові.
  2. Воно ефективно. Абстракція без накладних витрат.
  3. Надійно як молоток. Ніякої "магію".
  4. Добре вбудовується в існуючу парадигму програмування на мові C++.
  5. Сумісно з інструментами, які використовуються в стандартній бібліотеці. Наприклад,
    reference_wrapper
    для сигналізування про передачу параметрів за посиланням (як в
    std::make_tuple
    ,
    std::bind
    ,
    std::thread
    ), а також, що дуже важливо, з алгоритмами.
Повний вихідний код тут: https://github.com/izvolov/burst/blob/master/burst/functional/part.hpp
До змісту
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.