Частичное применение и каррирование в C++

Приветствую.

Уж не знаю, как так вышло, но игрался я на досуге с лямбда-выражениями в С++11 (о которых, к слову, я уже писал статью, снискавшую пару лет назад на удивление достаточно неплохую популярность), и под наркотическим воздействием впечатлением от языка Haskell начал разбираться с такими понятиями, как частичное применение и каррирование в контексте языка С++. И для начала, пожалуй, неплохо бы нам определиться с этими терминами.

Собственно, частичное применение функции — это возможность зафиксировать за одним из параметров функции какое-либо определённое значение, то есть из фукнции от N параметров мы получим функцию от N-1 параметров. Если у нас есть бинарная функция, которая суммирует два числа:

int sum(int a, int b) { return a + b; }

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

Строго говоря, частичное применение функций было и в предыдущем стандарте С++. Эту роль выполняли два класса std::binder1st и std::binder2nd, а также всем известные вспомогательные функции std::bind1st и std::bind2nd, которые упрощают создание объектов вышеназванных классов. Правда, есть одна проблема: эти биндеры не умеют работать с обычными указателями на функцию, потому что им необходимо знать тип параметров. Для решения этой и других проблем в STL повсеместно используются функторы. Если честно, я бы предпочёл их называть функциональными объектами, т.к. слово «функтор» со времён знакомста с Haskell у меня ассоциируется с совершенно иной сущностью. Однако, в кругах С++-программистов закрепился данный термин именно для обозначения объектов, которые могут вести себя подобно функциям; кроме того, это быстрее писать :)

Так как же решается эта проблема? Если кто-то не знает, я расскажу в двух словах. Классы std::binder1st и std::binder2nd, которые кстати работают только с бинарными функциями, требуют наличия нескольких typedef в определённом вами функторе: это result_type, first_argument_type и second_argument_type. Для того, чтобы не приходилось каждый раз объявлять эти типы в вашем функторе вручную, можно просто отнаследоваться от std::binary_function<T0,T1,R>, где T0 и T1 — типы аргументов функции, а R — тип возвращаемого значения соответственно.

Пример использования всего этого дела примерно такой:

template <typename T>
struct Sum
	: public std::binary_function<T, T, T>
{
	T operator()(T const & a, T const & b)
	{
		return a + b;
	}
};

// а затем

std::for_each(intArray.begin(), intArray.end(), std::bind1st(Sum<int>(), 42));

Тех, кто давно знаком с STL, такие конструкции уже не пугают (и я, к сожалению, в их числе), но поверьте, нагромождение всех этих спецсимволов и обёрток пугает новичков, пришедших в С++ из других языков. Про читабельность тоже лучше не вспоминать, потому что видывал я комбинации и покруче этой :) Тем более, что позже в библиотеке Boost появилась более мощная замена — Boost.Bind, которая, впрочем, читабельностью отличалась ещё меньше (типичный С++-way). Между прочим следует заметить, что Boost.Bind перекочевал в новый стандарт С++11 на замену старым биндерам, о которых я немного рассказал выше. Однако кто его будет использовать, когда есть… что? Правильно, лямбды! Ну-у-у, с ними совсем другое дело :) Писанины меньше, читабельность лучше (по сравнению с биндерами, конечно же, а не с другими языками ;)).

Итак, у нас есть функтор Sum, который мы определили выше. Я может забыл сказать, но в STL и так уже есть подобный функтор — std::plus<>. Но мы обойдёмся без него, раз уж написали свой аналогичный. В общем, есть у нас бинарный функтор, а нам нужно получить частично применённый унарный. С лямбдами это может выглядеть вот так:

using namespace std; // для for_each, begin и end
// ...
Sum<int> sum;
for_each(begin(intArray)), end(intArray), [sum] (int const & n)
{
	return sum(42, n);
});

Вы можете спросить, зачем мы здесь вызываем sum(42, n), когда можем прямо в теле лямбды написать return 42 + n;. Замечание, конечно, верное, но ведь нас интересует именно частичное применение функции, если вы ещё не забыли. К тому же, функция могла оказаться куда сложнее простого суммирования двух чисел.

А как бы мы это записали на языке Haskell? Пожалуй, получилось бы что-то вроде такого:

sum a b = a + b

someFunc intList = map (λ n → sum 42 n) intList

Если вы не знакомы с Haskell, не отчаивайтесь. Этот код аналогичен последнему примеру на С++. Сейчас я в двух словах объясню: в первой строчке мы объявили функцию sum, которая принимает a и b, а возвращает их сумму. Далее мы объявили какую-то функцию, которая принимает в качестве параметра какой-то список (вероятно список целых чисел, судя по названию параметра) и что-то с ним делает. Функция map — это аналог std::for_each, т.е. она принимает какую-то функцию и вызывает её для каждого элемента списка. В качестве функции мы передаём лямбду, которая вызывает функцию sum, явно передавая ей в качестве первого параметра фиксированное значение, а в качестве второго параметра естественно выступает аргумент лямбды. Всё это на самом деле не важно… Вернее, могло бы быть не важно, если б тот же самый код на Haskell нельзя было написать вот так:

sum a b = a + b

someFunc intList = map (sum 42) intList

Как мы видим, на сей раз вместо лямбды мы использовали куда более короткую конструкцию, а именно вызов бинарной функции sum с одним параметром. Как же это работает? Да очень просто! :) Вызов (sum 42) вернёт нам новую функцию, которая принимает один параметр, а затем суммирует его с числом 42. По сути это то же частичное применение — мы просто говорим функции sum: «Вот тебе первый параметр, запомни его! Но второго параметра мы ещё не знаем, так что с ним тебе предстоит разбираться позже». Всё это работает за счёт того, что все функции в Haskell каррированные (к слову, был такой математик — Haskell Curry ;)). Поэтому пришло время разобраться, что же это такое.

Во-первых, каррирование — это операция. То есть это не просто какое-то там свойство или магическое существо во вселенной Haskell — это преобразование. Во-вторых, это преобразование, выполняемое над функцией: оно берёт функцию от N параметров и преобразует её в аналогичную функцию от одного параметра, которая возвращает функцию от N-1 параметров. Поясню на примере. Для этого вернёмся к нашей С++-функции sum, но добавим ей ещё один параметр (на всякий случай):

template <typename T1, typename T2, typename T3, typename R>
R sum(T1 a, T2 b, T3 c) { return a + b + c; }

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

sum :: ((T1 × T2 × T3) → R)

Данная запись означает, что функция принимает три аргумента типов T1, T2 и T3 соответственно, а возвращает значение типа R. Собственно, после каррирования по определению выше мы должны получить нечто такое:

sum :: (T1 → ((T2 × T3) → R))

То есть это функция, которая принимает один параметр типа T1, а возвращает другую функцию, которая в свою очередь принимает два аргумента типов T2 и T3 соответственно, а возвращает (как и раньше) значение типа R. По сути мы «откусываем» первый параметр функции и говорим, мол, «мы его запомнили, не переживайте». А затем возвращаем аналогичную функцию, которая принимает на один параметр меньше. Ничего не напоминает? Да ведь на основе этого можно реализовать частичное применение!

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

sum :: (T1 → (T2 → (T3 → R)))

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

Надеюсь, до сих пор всё было более или менее ясно. Но, думаю, многие из вас уже тычат пальцем в монитор с восклицанием: «Ну наконец покажи уже код блжад!» Резонно, не могу возразить. Поэтому с теорией закончили, переходим к практике. На дворе 2012-й год, поэтому мы будем использовать новый стандарт С++11, хотя и постараемся ограничиться лишь тем, что поддерживает Microsoft Visual Studio 2010 — в плане поддержки нового стандарта она, наверное, наиболее отстающая из релизных компиляторов.

Начнём с простого. Есть бинарная функция. В результате каррирования мы должны получить унарную функцию, которая возвращает нам другую унарную функцию. С использованием С++11 это проще пареной репы:

#include <cstddef>
#include <iostream>

using namespace std;

template <typename R, typename T0, typename T1>
function<function<R(T1)>(T0)> curry_(function<R(T0,T1)> f)
{
    return [=] (T0 const & t0) -> function<R(T1)>
    {
        return [=] (T1 const & t1) { return f(t0, t1); };
    };
}

int sum(int a, int b) { return a + b; }

int main()
{
	auto curried_sum = curry_<int,int,int>(sum);

	cout << sum(42, 10)         << endl;   // => 52
	cout << curried_sum(42)(10) << endl;   // => 52

	return EXIT_SUCCESS;
}

В общем, тут такие дела: наша функция curry_ зависит от трёх шаблонных параметров (типы аргументов функции и тип возвращаемого значения). Она принимает в качестве аргумента объект типа std::function<>. Если кто не знает, это такой себе универсальный контейнер, который может хранить в себе функторы, лямбды и даже указатели на функции (Yay! больше никакого головняка :)). Нам важно то, что по сути это функциональный объект, то есть у него перегружен operator(). Далее мы просто возвращаем унарную лямбду (по сути анонимный функтор), которая возвращает другую унарную лямбду. Это практически один в один перевод определения термина каррирование с русского языка на C++.

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

std::bind1st(std::function<int(int,int)>(sum), 42)(10);
// или 
curry_<int,int,int>(sum)(42)(10);

Если первый, можете дальше не читать, поверьте. Если же второй, то должен вам признаться… Второй вариант мне и самому пока не совсем нравится, хотя по моему мнению он уже сейчас куда лучше первого.

Так или иначе, меня слегка раздражает необходимость явно указывать типы аргументов и возвращаемого значения. Компилятор не может автоматически вывести все типы самостоятельно, поэтому ему приходится подсказывать. Кроме того, если мы захотим перегрузить функцию curry_ для тернарной функции, нас постигнет неудача, так как компилятор не умеет различать инстансы std::function<>. Как я понял, причина этого состоит в том, у std::function<> определён шаблонный конструктор, который принимает любой тип, но углубляться в это сейчас не будем, ибо я не до конца уверен, что понял проблему правильно. Впрочем, факт остаётся фактом. И с этим нужно что-то делать.

Вопрос с необходимостью указывать типы аргументов и возвращаемого значения попробуем решить следующим образом. Функцию curry_ оставим, как есть, а для неё напишем шаблонную обёртку, которая будем принимать в качестве шаблонного параметра любой тип. Далее напишем что-то вроде function_traits (кстати странно, что такого нет в стандарте, ведь нет же?), в котором будем запоминать типы аргументов и т.п. Подход с написанием так называемых traits-классов повсеместно используется в STL, поэтому почему бы и нам так не сделать.

template <typename Func>
struct function_traits {};

// специализация шаблона для бинарных функций
template <typename R, typename T0, typename T1>
struct function_traits<R(*)(T0,T1)>
{
	typedef R  result_type;
	typedef T0 first_argument_type;
	typedef T1 second_argument_type; 
};

// обёртка для curry_
template <typename Functor>
function<
    function<
        typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            > (f);
}

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

cout << curry(sum)(42)(10) << endl;

По-моему, это успех! :) Осталось, реализовать curry_ для тернарных функций, да ещё и так, чтобы нам не пришлось заводить другое имя функции для этих целей — пусть всё решается посредством перегрузки функций. Пока что чутьё подсказывает мне, что это будет сделать проблематично. Посмотрите хотя бы на функцию-обёртку curry: она принимает всего один параметр (непосредственно функцию, подлежащую каррированию), но возвращать должна всегда объекты разных типов в зависимости от арности функции (т.е. будет возвращать функцию, возвращающую функцию, или функцию, возвращающую функцию, возвращающую функцию, или … ммм, пожалуй, хватит).

Для решения этой проблемы придётся слегка упороться метапрограммированием подумать и найти вдохновение. Итак, для начала нам нужно различать между собой унарные, бинарные, тернарные, … n-арные функции. Думаю, для этого можно добавить в function_traits статическую константу, которая будет инициализироваться разным значением в зависимости от специализации шаблона. Далее мы добавим в нашу функцию-обёртку curry дополнительный фиктивный аргумент, который будет принимать участие только в разрешении перегрузки функций на этапе компиляции.

Получаем следующее:

template <typename Func>
struct function_traits {};

// специализация шаблона для унарных функций
template <typename R, typename T0>
struct function_traits<R(*)(T0)>
{ 
	typedef R  result_type; 
	typedef T0 argument_type; 
	static const int arity = 1; 
};
 
// специализация шаблона для бинарных функций
template <typename R, typename T0, typename T1>
struct function_traits<R(*)(T0,T1)>
{
	typedef R  result_type;
	typedef T0 first_argument_type;
	typedef T1 second_argument_type; 
	static const int arity = 2;
};

// специализация шаблона для тернарных 
template <typename R, typename T0, typename T1, typename T2>
struct function_traits<R(*)(T0,T1,T2)>
{
	typedef R  result_type; 
	typedef T0 first_argument_type; 
	typedef T1 second_argument_type; 
	typedef T2 third_argument_type; 
	static const int arity = 3; 
};

// метафункция для подсчёта аргументов
template<typename Functor, int NArgs>
struct count_args
    : std::enable_if<function_traits<Functor>::arity == NArgs>
{ static_assert(NArgs >= 0, "Negative number? WTF?"); };


// обёрки

// для унарной функции каррирование не имеет смысла, поэтому возвращаем исходную функцию
template <typename Functor>
Functor curry(Functor f, typename count_args<Functor, 1>::type * = 0)
{
    return f;
}

// бинарная функция
template <typename Functor>
std::function<
    std::function<
        typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f, typename count_args<Functor, 2>::type * = 0)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            > (f);
}

// тернарная функция
template <typename Functor>
std::function<
    std::function<
        std::function<
            typename function_traits<Functor>::result_type(typename function_traits<Functor>::third_argument_type)
        >(typename function_traits<Functor>::second_argument_type)
    >(typename function_traits<Functor>::first_argument_type)
>
    curry(Functor f, typename count_args<Functor, 3>::type * = 0)
{
    return curry_
            < typename function_traits<Functor>::result_type
            , typename function_traits<Functor>::first_argument_type
            , typename function_traits<Functor>::second_argument_type
            , typename function_traits<Functor>::third_argument_type
            > (f);
}

В целом здесь всё предельно ясно. Мы реализовали перегрузку функций, добавив второй фиктивный параметр. Этот параметр использует std::enable_if для «выключения» неподходящих вариантов функции curry во время разрешения перегрузки. Также мы добавили реализацию каррирования для унарных функций, которая просто возвращает исходную функцию. Осталось написать реализацию для функции curry_ для тернарных функций. В теоретической части я упоминал, что во время каррирования тернарной функции, результатом будет унарная, которая теоретически могла бы возвращать функцию от двух аргументов, но фактически возвращает её каррированный вариант. С этим знанием реализация для трёх аргументов предельно проста:

<typename R, typename T0, typename T1, typename T2>
function<function<function<R(T2)>(T1)>(T0)> curry_(function<R(T0,T1,T2)> f)
{
    return [=] (T0 const & t0) -> function<function<R(T2)>(T1)>
    {
        return curry_<R,T1,T2>([=] (T1 const & t1, T2 const & t2)
        {
            return f(t0,t1,t2);
        });
    };
}

В общем, я всё это (кроме примеров использования, конечно) обернул в пространство имён mega и добавил специализации function_traits для функторов, запихнул в один заголовочный файл и залил на GitHub. Надо будет добавить README как-нибудь :) Теперь мы можем писать любую чушь с использованием тернарных функций. Да хоть вот так:

string foo(string s, int i, double d)
{
    ostringstream str;
    str << s << ": " << i << " л. = " << d << "$";
    return str.str();
}

int main()
{
    cout << mega::curry(foo)("Кока-кола")(2)(9.95) << endl;  // => Кока-кола: 2 л. = 9.95$

    return EXIT_SUCCESS;
}

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

Честно говоря, я не проверял, реализовано ли уже нечто подобное, так что не исключаю, что я написал очередной велосипед, ибо мне это было интересно с академической точки зрения. Кроме того, с точки зрения оптимальности я пока тоже не сильно вдавался в подробности. Могу сразу сказать, что компилятор С++ подобные вещи оптимизирует плоховато, поэтому в результате мы получаем целую пачку call'ов с тасканиями разной инфы между регистрами. Но за удобство надо платить.

Спасибо за внимание.

May the Force be with you.

P.S. У меня сейчас раннее утро, а онлайн я появлюсь скорее всего ближе к вечеру. Так что сильно не холиварьте без меня :)