Каррируем на C++

в 19:17, , рубрики: c++, haskell, ненормальное программирование

Привет.

Сидел я как-то вечером, ждал, пока соберется свежая ревизия clang, и смотрел на код одного своего проекта, в котором встречались не очень красивые вещи вроде

std::transform (someContainer.begin (), someContainer.end (), std::back_inserter (otherContainer),
    [this] (const SomeUglyAndLongType& item) { return HandleItem (item); });

Зачем создавать целую лямбду, чтобы у функции двух аргументов (если, как пишут классики, this считать неявным нулевым аргументом) зафиксировать один из них? На каком-нибудь псевдохаскеле можно было бы просто написать что-то вроде

map (handleItem this) someContainer

Мапы, функторы и прочие монады сделаем как-нибудь в следующий раз, а вот вещи, напоминающие (handleItem this) можно попробовать научиться писать.

Итак, что хочется сделать? Хочется научиться каррировать произвольные функции, то есть, вызывать их по «кусочкам» — передали первый аргумент, получили какую-то новую функцию одного аргумента, передали второй, получили новую функцию, и так далее, пока все аргументы для нашей исходной функции не будут переданы. Когда аргументы кончились, переходим на личности и вызываем нашу исходную функцию со всеми указанными аргументами.

Или, если вдруг кому так понятнее будет, нужно из функции N аргументов T1 × T2 ×… × TN → R сделать последовательность функций T1 → (T2 → (… → (TN → R))). Хотя, кому так понятнее, тот и наверняка и без меня знает, что такое каррирование.

Сразу предупреждаю, что решение получится не production-quality по ряду причин, которые мы обсудим чуть позже.

Что нам для этого понадобится? Понадобится свежий компилятор с поддержкой C++14, например, clang 3.4 и новее. Нужна и стандартная библиотека из C++14, на некоторых линуксах с этим могут быть проблемы, так что с кодом можно играться и на онлайн-сервисах вроде этого.

Как должен выглядеть результат наших попыток сделать из C++ хаскель на, собственно, плюсах? Ну, например, как-нибудь так:

auto test (int t1, int t2, double t3, const std::string& str)
{
    return t1 * t2 * t3 * str.size ();
}
// ...
std::cout << curry (test) (1) (2) (3.0) ("four") << std::endl;

Естественно, свободными функциями curry ограничиваться не должно.

Что нам нужно сделать? Да всего-ничего, написать функцию curry. Ну так давайте и напишем!

Пусть curry (f) возвращает какой-нибудь объект (назовём его CurryImpl), которому, очевидно, нужна будет функция f, которую мы передали в curry, а ещё у него должен быть перегружен operator(), и по условию задачи он должен принимать один аргумент непонятно какого типа, и непонятно что возвращать. Естественно, CurryImpl шаблонный, чтобы уметь запоминать любые функции:

template<typename F>
class CurryImpl
{
    const F m_f;            // наша функция, переданная в curry
public:
    CurryImpl (F f)
    : m_f { f }
    {
    }

    template<typename T>
    auto operator() (const T& arg) const
    {
        // осталось тут что-то написать
    }
};

template<typename F>
auto curry (F f)
{
    return CurryImpl<F> { f };
}

Давайте теперь посмотрим на оператор-круглые-скобки. Итак, этот оператор принимает один аргумент arg и либо вызывает искомую функцию m_f, если это последний аргумент в цепочке вызовов, либо возвращает другой объект, который запомнил этот arg.

Сначала разберёмся с тем, как запоминать аргументы.

Ну, тут на самом деле все довольно тривиально: нужно их просто брать и хранить в CurryImpl. Про эти аргументы мы ничего не знаем, равно как и про их типы, поэтому придётся добавить ещё один аргумент шаблона, да ещё и с вариадик. Непосредственно хранить значения аргументов можно, например, в std::tuple. Сообщать нашему CurryImpl про эти аргументы можно непосредственно в конструкторе. Итого, объявление класса модифицируется как-то так:

template<typename F, typename... PrevArgs>
class CurryImpl
{
    const F m_f;
  
    const std::tuple<PrevArgs...> m_prevArgs;
public:
    CurryImpl (F f, const std::tuple<PrevArgs...>& prev)
    : m_f { f }
    , m_prevArgs { prev }
    {
    }

    // а дальше все как раньше
};

Так, хорошо, с хранением разобрались, теперь осталось вызывать функцию. Тут всё становится немного интереснее: а как, собственно, определить, когда стоит прекратить накапливать аргументы и, собственно, вызвать m_f? А просто взять и вызвать, если получится — всё отлично!

А поможет нам в этом одно замечательное правило C++ — SFINAE, или Substitution Failure Is Not An Error. Если вкратце, [в данном контексте] суть в том, что, если компилятор при выборе кандидатов на вызов функции среди ряда перегруженных функций видит некое некорректное выражение в объявлении функции, то он её отбрасывает и смотрит дальше вместо error в консоли и слишком рано завершённой компиляции. Собственно, все эти std::enable_if и компания основаны именно на SFINAE.

Итак, SFINAE. Напишем функцию, которая будет вызывать нашу исходную m_f только тогда, когда такой вызов будет well-formed. В этом нам поможет замечательная шаблонная функция std::result_of. std::result_of<F (T1, T2, ...)> определяет вложенный тип type, равный типу, возвращаемому объектом F, если он вызван с аргументами типа T1, T2,… Подробнее она описана, например, здесь. Собственно, ключевые слова по ссылке, для C++14:

Only defined if F can be called with the arguments ArgTypes… in unevaluated context.

Для C++11 формулировка слегка другая, но это несущественно.

Кстати, в C++14 можно пользоваться удобным синонимом std::result_of_t<...> вместо typename std::result_of<...>::type.

Итак, пишем нашу функцию:

    template<typename T>
    std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg) const        // PrevArgs — аргумент CurryImpl, как мы помним
    {
        // тут как-то вызываем нашу m_f и возвращаем её результат
    }

Как это работает? Если m_f, которая типа F, можно вызвать со всеми предыдущими аргументами и текущим, то всё хорошо, функция «существует», если нельзя — компилятор её и не рассматривает.

Если же вызвать функцию нельзя, то должна быть другая invoke, которая тоже принимает один аргумент, запоминает его и рекурсивно возвращает новый объект с оператором-круглые-скобки и всем прочим. Как-то так, например:

    template<typename T>
    auto invoke (const T& arg) const
    {
        return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
    }

Что мы тут сделали? Вернули новый CurryImpl, который сохраняет все предыдущие аргументы плюс один новый. На уровне типов это отражается в записи PrevArgs..., T, если хотите, добавляющей T в variadic-список типов, а на уровне значений — просто соединяем два кортежа, старый m_prevArgs и новый одноэлементный кортеж.

Посмотрим снова на наш оператор-круглые-скобки. Теперь понятно, что мы должны в нём вызвать одну из наших двух перегрузок invoke, по возможности первую, которая вызывает функцию, а то так можно никогда не перестать копить аргументы. Как это сделать? Тут есть куча вариантов, мой любимый в таких случаях — использовать тот факт, что любая перегрузка лучше, чем перегрузка с эллипсисом (aka многоточие, aka вариадики C-стайл). То есть, добавляем ещё один параметр, который даже не будем использовать, например, int в первую функцию и ... во вторую, и получаем что-то подобное:

    template<typename T>
    auto operator() (const T& arg) const
    {    
        return invoke (arg, 0);
    }
private:
    template<typename T>
    std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg, int) const
    {
        // тут как-то вызываем нашу m_f и возвращаем её результат
    }
  
    template<typename T>
    auto invoke (const T& arg, ...) const
    {
        return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
    }

То есть, если первая перегрузка доступна, всегда будет выбираться она: int компилятору нравится куда больше, чем ...

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

Что нужно, чтобы вызвать функцию, аргументы которой (с точностью до arg) хранятся в кортеже? Надо как-нибудь распаковать тот кортеж и передать результаты распаковки в функцию как обычные аргументы. Проблема в том, что в точке вызова мы не знаем на этапе написания кода, сколько у нас аргументов, поэтому просто взять и руками подёргать std::get мы не можем. Ну и славно, негоже в 2014 году работу за компилятор делать. Вот был бы у нас какой-нибудь способ сделать вариадик из чисел от 0 до N-1, мы могли бы написать что-то такое:

    // в Is лежат числа от 0 до (количество элементов в m_prevArgs)-1
    template<typename T, std::size_t... Is>
    auto invokeIndexed (const T& arg /*, тут ещё что-то, чтобы Is вывелся компилятором сам*/) const
    {
        return m_f (std::get<Is> (m_prevArgs)..., arg);
    }

Здесь по правилам разворачивания variadic-параметров выражение std::get<Is> (m_prevArgs)... развернётся компилятором в std::get<I1> (m_prevArgs), std::get<I2> (m_prevArgs), и так далее для всех индексов Is.

А, стоп, так в точности такой вариант можно сделать на тех же вариадиках в C++11, а в C++14 его даже добавили в STL! Замечательно, всё встаёт на свои места. Идём по ссылке, видим замечательный метод std::index_sequence_for, который нам как раз нужен (у нас ведь на руках есть PrevArgs...), и пишем в теле нашей первой invoke вызов invokeIndexed:

return invokeIndexed (arg, std::index_sequence_for<PrevArgs...> {});

А invokeIndexed тогда вторым параметром должна принимать std::index_sequence, которая как раз и отвечает за хранение списка чисел:

    template<typename T, std::size_t... Is>
    auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
    {
        return m_f (std::get<Is> (m_prevArgs)..., arg);
    }

Отлично! Всё работает! На радостях пишем то, с чего начинался пост, вроде такого:

struct Foo
{
    auto doFoo (int baz, int qux)
    {
        return (m_bar + baz) / qux;
    }
};
// ...
Foo someFoo;
const auto fooRes = Curry (&Foo::doFoo) (&someFoo) (2) (4);

И сразу же компилятор возвращает нас в жестокую реальность: выражение m_f (arguments) не является well-formed, если m_f — указатель на функцию-член класса.

Впрочем, как учили нас классики, любая проблема решается добавлением ещё одного уровня абстракции, поэтому добавим ещё один уровень, который будет ответственен непосредственно за вызов функции с аргументами. Уровень будет представляться в виде шаблонной структуры, параметризуемой типом нашей m_f, и будет иметь шаблонный оператор-круглые-скобки. Опишем сначала общий случай, когда мы просто берём и вызываем нашу функцию:

    template<typename IF>
    struct Invoke
    {
        template<typename... IArgs>
        auto operator() (IF fr, IArgs... args)   
        {
            return fr (args...);
        }
    };

Перепишем invokeIndexed:

    template<typename T, std::size_t... Is>
    auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
    {
        return Invoke<F> {} (m_f, std::get<Is> (m_prevArgs)..., arg);
    }

К счастью, для частных случаев указателей на функции-члены никаких SFINAE не нужно, можно просто специализировать наш Invoke, да и выбирать из списка аргументов Args... первый — по соглашению он и будет нашим объектом, на котором нужно вызвать функцию. При этом ещё не забудем, что первый аргумент может быть как указателем на класс, так и ссылкой, и хочется поддерживать оба варианта вызова:

    template<typename R, typename C, typename... Args>
    struct Invoke<R (C::*) (Args...)>
    {
        auto operator() (R (C::*ptr) (Args...), C c, Args... rest)
        {
            return (c.*ptr) (rest...);
        }
      
        auto operator() (R (C::*ptr) (Args...), C *c, Args... rest)
        {
            return (c->*ptr) (rest...);
        }
    };

Кстати, между ними есть принципиальная разница, очевидная, конечно, но проговорить стоит: в первом случае изменения затронут локальную копию c, а во втором они будут видны и извне, на объекте, который в один из операторов-круглые-скобочки мы передали. То есть:

struct Foo
{
    int m_state = 42;

    auto doFoo (int bar)
    {
        m_state += bar;
        return m_state;
    }
};

Foo foo;
curry (&Foo::doFoo) (foo) (1);        // foo.m_state всё ещё 42
curry (&Foo::doFoo) (&foo) (1);       // foo.m_state теперь 43

Вот, в общем-то, и всё.

Всё вместе

#include <tuple>
#include <type_traits>
#include <utility>
#include <iostream>
#include <string>

template<typename F, typename... PrevArgs>
class CurryImpl
{
    const F m_f;
  
    const std::tuple<PrevArgs...> m_prevArgs;
public:
    CurryImpl (F f, const std::tuple<PrevArgs...>& prev)
    : m_f { f }
    , m_prevArgs { prev }
    {
    }
  
    template<typename T>
    auto operator() (const T& arg) const
    {    
        return invoke (arg, 0);
    }
private:
    template<typename T>
    std::result_of_t<F (PrevArgs..., T)> invoke (const T& arg, int) const
    {
        return invokeIndexed (arg, std::index_sequence_for<PrevArgs...> {});
    }
    
    template<typename IF>
    struct Invoke
    {
        template<typename... IArgs>
        auto operator() (IF fr, IArgs... args)   
        {
            return fr (args...);
        }
    };

    template<typename R, typename C, typename... Args>
    struct Invoke<R (C::*) (Args...)>
    {
        auto operator() (R (C::*ptr) (Args...), C c, Args... rest)
        {
            return (c.*ptr) (rest...);
        }
      
        auto operator() (R (C::*ptr) (Args...), C *c, Args... rest)
        {
            return (c->*ptr) (rest...);
        }
    };

    template<typename T, std::size_t... Is>
    auto invokeIndexed (const T& arg, std::index_sequence<Is...>) const
    {
        return Invoke<F> {} (m_f, std::get<Is> (m_prevArgs)..., arg);
    }
  
    template<typename T>
    auto invoke (const T& arg, ...) const
    {
        return CurryImpl<F, PrevArgs..., T> { m_f, std::tuple_cat (m_prevArgs, std::tuple<T> { arg }) };
    }
};

template<typename F>
auto curry (F f)
{
    return CurryImpl<F> { f, {} };
}

auto test (int t1, int t2, double t3, const std::string& str)
{
    return t1 * t2 * t3 * str.size ();
}

struct Foo
{
    int m_bar;

    auto doFoo (int baz, int qux)
    {
        auto result = (m_bar + baz) / qux;
        ++m_bar;
        return result;
    }
};

int main ()
{
    const auto res = curry (test) (1) (2) (3.0) ("four");
    std::cout << res << std::endl;

    Foo someFoo { 42 };
    const auto fooRes = curry (&Foo::doFoo) (&someFoo) (2) (4);
    std::cout << fooRes << " " << someFoo.m_bar << std::endl;
    
    someFoo.m_bar = 42;
    auto lambda = [someFoo] (int bar, int baz) mutable { return someFoo.doFoo (bar, baz); };
    const auto lambdaRes = curry (lambda) (4) (2);
    std::cout << lambdaRes << std::endl;
}

Ещё всё вместе есть онлайн.

Теперь ответы на некоторые предполагаемые вопросы:

Зачем параметризовать CurryImpl типом функции, почему бы просто не использовать std::function?

  1. В std::function внутри сидит type erasure, который далеко не всегда девиртуализируется и инлайнится компилятором. Впрочем, это тема для отдельной статьи
  2. Скучно.

А std::tuple тебе не скучно?
Нет, тем более, что собственная реализация была бы точно такая же, от тупла тут никакого оверхеда.

Зачем тут C++14, разве C++11 не хватит?
Неа, не хватит. C++14 тут полезен, в частности:

  1. чтобы писать auto вместо возвращаемых значений функций, а не выписывать адские рекурсивные decltype или ещё что похуже;
  2. чтобы не переизобретать compile-time-последовательность чисел (std::index_sequence_for, это вот всё).

Хотя, конечно, без всего этого вполне можно жить, самое главное — вариадики и вывод типов хотя бы в виде decltype.

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

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

Почему оно не production-ready?
Потому что коллеги вас растерзают за такой код, а сисадмин и менеджер не захотят переходить на C++14 там наверняка где-то внутри бегает пара проблем, связанных с обработкой ссылок.

Автор: 0xd34df00d

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js