Partial application in C++
Aug. 25th, 2012 07:31 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
madfЗацікавитись проблемою partial application у C++ мене заставила оказія на роботі і оця стаття на хабрі: "Частичное применение и каррирование в C++". Ну про статтю говорити багато не буду — візьміть та прочитайте. Скажу тільки що автор використовує новий стандарт лише частково, у рамках підтримки його Microsoft Visual Studio 2010. Не використовує навіть variadic templates. На робочій оказії ж зупинюсь детальніше.
В рамках впровадження на роботі Boost.Signal2 замість дерев’яного велосипеду на паровій тязі я стикнувся з проблемою втикання методів класів у слот. Проблема стара як світ і полягає у наявності неявномого параметра this який треба передати явно. Всі, мабуть, знають що методи класів у плюсах це, насправді, звичайнісінькі функції яким неявно першим параметром передається вказівник на об’єкт якому вони належать. Невільні функції, страждають на панщині, що тут поробиш. Якщо мислити на рівні старого-доброго C чи мови ассемблера (від якої він не далеко відкотився) — все в порядку. Втикаємо вказівник на об’єкт (чи, пардон, на структуру) у перший параметр (чи кладемо його у стек, чи записуємо у регістр) і ніяких проблем. Та у плюсах все не так. Не проста у нас функція.
Ну, якщо бути зовсім чесним, то з this усе не так погано. Ми можемо взяти реліктовий std::mem_fun і перетворити наш метод у функціональний об’єкт (у мене язик не повертається назвати його функтором) який веде себе ну прямо як звичайнісінька функція. Тільки має семантику значення на додачу. Проблеми? Є проблеми. Одна із найголовніших проблем — метод має бути нуль-арним чи унарним. Довільну арність mem_fun не вміє. Variadic templates за її часів ще не було, а робити overloading для десятка варіантів, як це любить робити Boost, ніхто не захотів.
Намучившись з std::mem_fun комітет у новий стандарт включив std::mem_fn (зворотня сумісність не дозволила їм просто проапгрейдити стару функцію). Вона робить все те саме, тільки вміє n-арні методи перетворювати на (n + 1)-арні функції.
Здавалося б, усе кльово, проблема зникла. Щастя для всіх, даром і все таке. Але у сигналу із Boost.Signal2 (а значить і у слота) сигнатура трошки інша. Нічого він про ваші this не знає. А значить треба нашій новонародженій функції покласти у дорогу не тільки шмат сала, цибулі й хліба, а ще й не забути вказівник на об’єкт прив’язати. Щоб не загубила, значить. Прив’язати. При-bind-ити. Потрібен пасок. І їх є у мене! Вибирайте: старий конопляний, шкіряний чи новомодний — полікарбонатний! Себто, std::bind1st/std::bind2nd, Boost.Bind і, нарешті, std::bind. Перші два дістались нам у спадок від сивих пращурів. Я за тих часів ще пішки під стілу школу ходив і не те що плюсів — навіть C не знав. Тільки чув про нього. А точніше читав коротеньку замітку у журналі "Наука и Жизнь". А може у журналі "Квант", не пам’ятаю точно. Але суть не в тому. Багато вони не вміли, тільки перетворювати бінарні функції на унарні функціональні об’єкти шляхом "прив’язування" першого чи другого аргументу до цього самого об’єкту. Скажу чесно, я ними користувався всього один раз у житті — у одному місці у проекті Stargazer. В іншому місці у цьому ж проекті їх використав Борис ще до мене. Я не здивуюсь якщо вони там досі живуть (політика у нас така — ніякого Boost і щоб компілювалось на gcc-2.95 і FreeBSD4). Пекельно незручні штуки. Не дивно що у Boost з’явилась більш "продвинута" реалізація яка вміла аж 9 аргументів, але тільки по ссилкам. При чому по константним — тільки для арностей від 1 до 3. Але прогрес не зупинити — на заміну їй прийшла сучасна реалізація яка вміла аж 29 параметрів, move-семантику і вміла копіювати аргументи якщо вони були не r-value.
Ну що, все класно? Ні, не все. Тільки подивіться на це:
#include <functional> #include <iostream> double sum3(double a, double b, double c) { return a + b + c; } int main() { auto sum2 = std::bind(sum3, 10, std::placeholders::_1, std::placeholders::_2); auto sum1 = std::bind(sum3, 10, 20, std::placeholders::_1); auto sum0 = std::bind(sum3, 10, 20, 30); std::cout << sum2(1, 2) << "\n"; std::cout << sum1(1) << "\n"; std::cout << sum0() << "\n"; return 0; } |
| _Winnie C++ Colorizer |
Уявіть що у нас не 3 аргументи а більше. Ну, скажімо, 8. Так, я знаю про псевдоніми namespace'ів і про using. Та все одно задовбишся і не влізеш навіть у наші ліберальні стандарти на роботі — 180 символів на рядок. Куди це годиться, тупо перелічувати всі незайняті параметри?
Моя справа маленька — зробити так щоб мені було зручно працювати з сигналами і слотами. На стільки зручно що мої колеги, які будуть проводити рев’ю мого коду (як мінімум 2 рази перед інтеграцією, а зазвичай навіть більше — такі у нас стандарти), сказали: "Круто!" — і підтримали мене на цьому нелегкому шляху "причинення добра і нанесення справедливості" (c) nightfly. std::bind, звісно, крута штука, багато чого вміє, але він заставляє мене ридати кривавими сльозами. А значить для нашої місії не підходить.
Щоб бути чесним, скажу: на роботі я цю ситуацію розрулив дуже просто. Мені всього-то треба було this причепити куди треба. Я не ставив собі за мету спасти світ. Тому швиденько нашкарябав маленьку variadic function яка повертала лямбду, у якій... Ну ви і самі знаєте що у лямбдах буває. Аргументи захоплені, от що. Дешево і сердито, а головне — працює. І немає більше сотень плейсхолдерів.
Ну а щоб бути чесним до кінця, скажу що цей мій код поки пройшов лише одне рев’ю, бо всі наші й не наші розбіглись по відпусткам і відпочивають. І у цього відпочинку є один побічний ефект. Оскільки серед відпочиваючих виявились мій тімлід і проджект менеджер у мене іноді з’явяється вдосталь часу на всяку маячню. І тому я вирішив замутити свій bind, з... е-е-е... інтелектуальними іграми і красивими дівчатами. :)
І що ж нам потрібно для нашого лунапарку? Пардон, bind'у. Нам потрібні типи даних. Спочатку простенькі, такі які можуть тримати у собі argument pack і integer list. Наприклад, такі:
template <typename ...> struct Sequence; template <int ...> struct IntSequence; |
| _Winnie C++ Colorizer |
Для чого потрібен Sequence, я думаю, більш-менш зрозуміло. А для чого потрібен IntSequence — буде зрозуміло пізніше. Скажу по секрету — проблема у багах компілятора gcc гілки 4.6 на яку я орієнтуюсь.
Який тип має наша функція? Думаю, приблизно такий: ((a0, a1, ..., an) -> r) -> (a0, a1, ..., ak) -> ((ak+1, ak+2, ..., an) -> r). Звісно, для k, n Є N і k < n. Тобто точні типи нам заздалегідь не відомі і ми маємо їх обчислити в момент застосування. А це значить що? Правильно, метапрограмування. Хоча, я думаю, це було очевидно з самого початку.
Що ж, нам потрібна метафункція яка "відкусить" від одного argument pack (a0, a1, ..., an) інший argument pack (a0, a1, ..., ak) і поверне те що залишилось: (ak+1, ak+2, ..., an). З неї і почнемо, благо нічого складного:
template <typename TSeq, typename USeq> struct RemoveFromFront; template <typename ... Ts> struct RemoveFromFront<Sequence<Ts ...>, Sequence<>> { typedef Sequence<Ts ...> type; }; template <typename T, typename ... Ts, typename ... Us> struct RemoveFromFront<Sequence<T, Ts ...>, Sequence<T, Us ...>> { typedef typename RemoveFromFront<Sequence<Ts ...>, Sequence<Us ...>>::type type; }; |
| _Winnie C++ Colorizer |
Рішення стандартне: задаємо базу рекурсії (вироджений випадок коли "кусати" вже нема чого, і так усі яблука понакусювані) і неспішно, по одному, прибираємо аргументи із початкового argument pack. Прибрали, чудово. Тепер ми можемо обчислювати сигнатуру функції. Приступимо до реалізації:
template <typename R, typename TSeq, typename USeq> struct MakeBind; template <typename R, typename ... Ts, typename ... Us> struct MakeBind<R, Sequence<Ts ...>, Sequence<Us ...>> { static std::function<R (Us ...)> make(R (*f) (Ts ..., Us ...), Ts ... args1) { return [=](Us ... args2) { return f(args1 ..., args2 ...); }; } }; |
| _Winnie C++ Colorizer |
Тут уже все виглядає складніше, купа синтаксису і майже нуль семантики. Та насправді, все просто: беремо функцію, беремо argument pack для "відкусюваних" параметрів, зв’язуємо усе по значенню у лямбда-функцію яка приймає на вхід аргументи що залишились не зв’язані, розгортаємо всередині послідовно зв’язані аргументи і аргументи самої лямбди — профіт! Та от проблема, gcc-4.6 не вміє зв’язувать argument pack. Тільки звичайні змінні. Чесно кажучи, ця проблема завдала мені чимало клопоту і рішення підказав StackOverflow. Передати argument pack у вигляді tuple! Ура, ура, ура! Кодуємо:
template <typename R, typename TSeq, typename USeq> struct MakeBind; template <typename R, typename ... Ts, typename ... Us> struct MakeBind<R, Sequence<Ts ...>, Sequence<Us ...>> { static std::function<R (Us ...)> make(R (*f) (Ts ..., Us ...), Ts ... vs) { std::tuple<Ts ...> args1; return [=](Us ... args2) { return f(?, args2 ...); }; } }; |
| _Winnie C++ Colorizer |
Oops, як каже іноді ядро Linux. А як же нам тупль "розкрити"? Задачка... І знову відповідь нам підказує StackOverflow! Argument packs можуть розкриватись по різному. На них можна "замапити" яку-небуть функцію при розкритті. Наприклад... get! Приготуйтесь до магії!
template <int N, int ... ints> struct GenIntSequence { typedef typename GenIntSequence<N - 1, N - 1, ints ...>::sequence sequence; }; template <int ... ints> struct GenIntSequence<0, ints ...> { typedef IntSequence<ints ...> sequence; }; template <typename R, typename USeq, typename ISeq, typename TSeq> struct ApplyArgs; template <typename R, typename ... Us, int ... ints, typename ... Ts> struct ApplyArgs<R, Sequence<Us ...>, IntSequence<ints ...>, Sequence<Ts ...>> { static R apply(R (*f) (Us ..., Ts ...), std::tuple<Us ...> args1, Ts ... args2) { return f(std::get<ints>(args1) ..., args2 ...); } }; |
| _Winnie C++ Colorizer |
Синтаксису стало ще більше, а сенсу не додалося. Тому пояснюю. GenIntSequence це метафункція яка по заданому N віддає нам IntSequence з послідовністю цілих чисел від 0 до N. ApplyArgs надає нам не дуже generic, а скоріше навіть ad-hoc функцію apply яка вміє apply'їти до звичайної функції тупль і, додатково, argument pack. Маючи на озброєнні ці два потужних інструмента, збираємо все до купи:
template <typename R, typename ... Ts, typename ... Us> struct MakeBind<R, Sequence<Ts ...>, Sequence<Us ...>> { static std::function<R (Us ...)> make(R (*f) (Ts ..., Us ...), Ts ... vs) { std::tuple<Ts ...> args1(vs ...); return [=](Us ... args2) { return ApplyArgs<R, Sequence<Ts ...>, typename GenIntSequence<sizeof...(Ts)>::sequence, Sequence<Us ...>>::apply(f, args1, args2 ...); }; } }; |
| _Winnie C++ Colorizer |
Спочатку перетворюємо argument pack на тупль і захоплюємо його по значенню. Потім, разом із залишком аргументів (вони уже йдуть як звичайні аргументи лямбда-функції, хоча і argument pack) передаємо його у ApplyArgs::apply разом із послідовністю чисел від одного до... Так-так, вірно, до арності тупля. Щоб потім цю послідовність розкрити передавши у шаблонний параметр get кожний її елемент, а у звичайний параметр — сам тупль.
Так, я знаю, спочатку все це здається повною маячнею. Потім здається що все елементарно просто. Але повірте, оце розкриття тупля завдало мені клопоту! Що ж, якщо ви дожили до цього моменту — настав час десерту! Давайте подивимось як же ця пташка літає...
int main() { auto sum2 = MakeBind<double, Sequence<double>, Sequence<double, double>>(sum3, 10); } |
| _Winnie C++ Colorizer |
Стоп-стоп! Це ще що за маячня?! Я що, маю вручну прописувати всі ці Sequences? Це навіть гірше за стандартні плейсхолдери зі стандартного bind! Нікуди не годиться! У компілятора є вся інформація щоб самому обчислити всі ці типи. Значить робимо красиву обгортку:
template <typename F, typename ... Ts> auto bind(F & f, Ts ... vs) -> ? { return MakeBind<typename std::result_of<F>::type, Sequence<Ts ...>, typename RemoveFromFront<?, Sequence<Ts ...>>::type>::make(f, vs ...); } |
| _Winnie C++ Colorizer |
Все добре, та скажіть мені, панове, який же тип повертає ця функція-обгортка, га? От тільки не треба тут про std::function, це я і сам знаю. Поганий тип вона повертає. Не можна таких слів записувати, це навіть гірше ніж "Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn!". Жаль що gcc не вміє автоматом виводити тип із виразу для return і треба призивати Алєксанрескуdecltype (це такий новий keyword із нового стандарту, не функція ні в якому разі, хоча і схожий). Доведеться дублювати код, нічого не вдієш:
template <typename F, typename ... Ts> auto bind(F & f, Ts ... vs) -> decltype( MakeBind<typename ResultOf<F>::type, Sequence<Ts ...>, typename RemoveFromFront<typename ArgsOf<F>::type, Sequence<Ts ...>>::type>::make(f, vs ...)) { return MakeBind<typename ResultOf<F>::type, Sequence<Ts ...>, typename RemoveFromFront<typename ArgsOf<F>::type, Sequence<Ts ...>>::type>::make(f, vs ...); } |
| _Winnie C++ Colorizer |
Виглядає страшнувато, але це все-таки "нутрощі" інструмента, а не сам інструмент. Так, а що це за ArgsOf і ResultOf? Вони ще звідки взялись? А взялись вони із моєї голови. Нам же треба по функції отримати список типів її аргументів і тип результату - от вони і взялись. В принципі, замість ResultOf можна було б використати std::result_of, та тільки... Він не вміє працювати з не-вказівниками і не-функторами. Та і прості вони зовсім, за п’ять хвилин пишуться:
template <typename F> struct ArgsOf; template <typename R, typename ... Ts> struct ArgsOf<R (Ts ...)> { typedef Sequence<Ts ...> type; }; template <typename F> struct ResultOf; template <typename R, typename ... Ts> struct ResultOf<R (Ts ...)> { typedef R type; }; |
| _Winnie C++ Colorizer |
Ну і, нарешті, десерт:
double sum3(double a, double b, double c) { return a + b + c; } int main() { auto sum2 = bind(sum3, 10.0); auto sum1 = bind(sum3, 10.0, 20.0); auto sum0 = bind(sum3, 10.0, 20.0, 30.0); std::cout << sum2(1, 2) << "\n"; std::cout << sum1(1) << "\n"; std::cout << sum0() << "\n"; return 0; } |
| _Winnie C++ Colorizer |
$ g++ -W -Wall -Wextra -pedantic -std=c++0x bind.cpp -o bind $ ./bind 13 31 60
У debug-версії, без inlining вся ця машинерія робить аж три проміжних виклики поки добереться до sum3:
$ gdb ./bind
GNU gdb (Gentoo 7.5 p1) 7.5
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
For bug reporting instructions, please see:
<http://bugs.gentoo.org/>...
Reading symbols from /home/faust/temp/bind/bind...done.
(gdb) break sum3
Breakpoint 1 at 0x400a57: file bind.cpp, line 97.
(gdb) r
Starting program: /home/faust/temp/bind/bind
warning: Could not load shared library symbols for linux-vdso.so.1.
Do you need "set solib-search-path" or "set sysroot"?
Breakpoint 1, sum3 (a=10, b=1, c=2) at bind.cpp:97
97 return a + b + c;
(gdb) bt
#0 sum3 (a=10, b=1, c=2) at bind.cpp:97
#1 0x00000000004015be in ApplyArgs<double, Sequence<double>, IntSequence<0>, Sequence<double, double> >::apply (f=0x400a44 <sum3(double, double, double)>, args1=..., args2#0=1, args2#1=2) at bind.cpp:46
#2 0x0000000000401198 in operator() (this=0x606010, args2#0=1, args2#1=2) at bind.cpp:62
#3 0x000000000040168b in std::_Function_handler<double (double, double), MakeBind<double, Sequence<double>, Sequence<double, double> >::make(double (*)(double, double, double), double)::{lambda(double, double)#1}>::_M_invoke(std::_Any_data const&, double, double) (__functor=..., __args#0=1, __args#1=2) at /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/functional:1764
#4 0x0000000000400e61 in std::function<double (double, double)>::operator()(double, double) const (this=0x7fffffffde30, __args#0=1, __args#1=2) at /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/functional:2161
#5 0x0000000000400af4 in main () at bind.cpp:106
(gdb)
Дивно (хоча і не дуже), але -finline-functions і -O1 не допомагають. Але уже з -O2 маємо лише один проміжний виклик:
$ gdb ./bind GNU gdb (Gentoo 7.5 p1) 7.5 Copyright (C) 2012 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "x86_64-pc-linux-gnu". For bug reporting instructions, please see: <http://bugs.gentoo.org/>... Reading symbols from /home/faust/temp/bind/bind...done. (gdb) break sum3 Breakpoint 1 at 0x400d10: file bind.cpp, line 97. (gdb) r Starting program: /home/faust/temp/bind/bind warning: Could not load shared library symbols for linux-vdso.so.1. Do you need "set solib-search-path" or "set sysroot"? Breakpoint 1, sum3 (a=10, b=1, c=2) at bind.cpp:97 97 return a + b + c; (gdb) bt #0 sum3 (a=10, b=1, c=2) at bind.cpp:97 #1 0x0000000000400a53 in operator() (__args#1=2, __args#0=1, this=0x7fffffffde40) at /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/functional:2161 #2 main () at bind.cpp:106 (gdb)
Я вважаю, не так і погано. А тепер про погане. Ця реалізація вміє працювати тільки зі справжніми функціями :). Вона не вміє функціональних об’єктів (в т.ч. і std::function) і не вміє методів. Ще вона вміє прив’язувати аргументи тільки по значенню, а функцію бере не по константному посиланню (це взагалі тупо моя тупка). Так, я знаю, можна зробити overload для них і все стане на свої місця, але... Але мені це вже не цікаво. Як буде така задача — зроблю. А поки вважайте це proof-of-concept.
PS: Я там обіцяв розповісти навіщо потрібні лінійні ієрархії і всяке пекельне метапрограмування, але все ніяк руки не дійдуть. Код уже давно працює, а описати — то наснаги немає, то часу.
