Каррируем на C++
Привет, хабр.Сидел я как-то вечером, ждал, пока соберется свежая ревизия 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
template
template
Ну, тут на самом деле все довольно тривиально: нужно их просто брать и хранить в CurryImpl. Про эти аргументы мы ничего не знаем, равно как и про их типы, поэтому придётся добавить ещё один аргумент шаблона, да ещё и с вариадик. Непосредственно хранить значения аргументов можно, например, в std: tuple. Сообщать нашему CurryImpl про эти аргументы можно непосредственно в конструкторе. Итого, объявление класса модифицируется как-то так:
template
//, а дальше все как раньше }; Так, хорошо, с хранением разобрались, теперь осталось вызывать функцию. Тут всё становится немного интереснее:, а как, собственно, определить, когда стоит прекратить накапливать аргументы и, собственно, вызвать 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
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
Если же вызвать функцию нельзя, то должна быть другая invoke, которая тоже принимает один аргумент, запоминает его и рекурсивно возвращает новый объект с оператором-круглые-скобки и всем прочим. Как-то так, например:
template
Посмотрим снова на наш оператор-круглые-скобки. Теперь понятно, что мы должны в нём вызвать одну из наших двух перегрузок invoke, по возможности первую, которая вызывает функцию, а то так можно никогда не перестать копить аргументы. Как это сделать? Тут есть куча вариантов, мой любимый в таких случаях — использовать тот факт, что любая перегрузка лучше, чем перегрузка с эллипсисом (aka многоточие, aka вариадики C-стайл). То есть, добавляем ещё один параметр, который даже не будем использовать, например, int в первую функцию и … во вторую, и получаем что-то подобное:
template
Осталось разобраться с вызовом функции из первой перегрузки, и всё будет хорошо.
Что нужно, чтобы вызвать функцию, аргументы которой (с точностью до arg) хранятся в кортеже? Надо как-нибудь распаковать тот кортеж и передать результаты распаковки в функцию как обычные аргументы. Проблема в том, что в точке вызова мы не знаем на этапе написания кода, сколько у нас аргументов, поэтому просто взять и руками подёргать std: get мы не можем. Ну и славно, негоже в 2014 году работу за компилятор делать. Вот был бы у нас какой-нибудь способ сделать вариадик из чисел от 0 до N-1, мы могли бы написать что-то такое:
// в Is лежат числа от 0 до (количество элементов в m_prevArgs)-1
template
return invokeIndexed (arg, std: index_sequence_for
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
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
template
template
template
template
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?
В std: function внутри сидит type erasure, который далеко не всегда девиртуализируется и инлайнится компилятором. Впрочем, это тема для отдельной статьи Скучно. А std: tuple тебе не скучно? Нет, тем более, что собственная реализация была бы точно такая же, от тупла тут никакого оверхеда.Зачем тут C++14, разве C++11 не хватит? Неа, не хватит. C++14 тут полезен, в частности:
чтобы писать auto вместо возвращаемых значений функций, а не выписывать адские рекурсивные decltype или ещё что похуже; чтобы не переизобретать compile-time-последовательность чисел (std: index_sequence_for, это вот всё). Хотя, конечно, без всего этого вполне можно жить, самое главное — вариадики и вывод типов хотя бы в виде decltype.Получается, что с функциями с аргументами по умолчанию передать можно будет только лишь аргументы без значений по умолчанию? Верно.
Зачем везде копировать параметры? Это представляется разумным: получающийся после частичного применения функции функтор может захотеться куда-нибудь передать как коллбек, вернуть из функции, и так далее. Копировать безопаснее, и вообще, вполне себе в функциональном стиле.
Почему оно не production-ready? Потому что коллеги вас растерзают за такой код, а сисадмин и менеджер не захотят переходить на C++14 там наверняка где-то внутри бегает пара проблем, связанных с обработкой ссылок.
