Статически типизированные продолжения
Намедни на RSDN был задан такой вопрос: Пусть у нас есть функция, возвращающая полиморфный тип class Base { virtual int foo () const = 0; }; class A: public Base { int foo () const { return 1; } }; class B: public Base { int foo () const { return 2; } }; class C: public Base { int foo () const { return 3; } }; class D: public Base { int foo () const { return 4; } };
Base* getconfig (char cfg) // не будем пока отвлекаться на уборку мусора { switch (cfg) { case 'a': return new A (); case 'b': return new B (); case 'c': return new C (); case 'd': return new D (); default: throw std: invalid_argument («bad type»); } } и функция, принимающая его экземпляры int entry (Base* x, Base* y) { return x→foo ()*10 + y→foo (); } которую используют примерно так void run (char cx, char cy) { std: cout << cx << cy << " : " << entry(getconfig(cx), getconfig(cy)) << std::endl; } Можно ли протащить полиморфизм на стадию компиляции?Можно! Но для этого придётся вывернуть код мехом внутрь, то есть, переписать его в continuation passing style (CPS) — или, по-русски, — на продолжениях.
Сперва напомним, что это такое, в общих чертах. Если у нас есть выражение z = f (g (x)), мы его вычисляем так: y = g (x) z = f (y) Теперь определим функцию высшего порядка (принимающую на вход другую функцию) G (x, k) = k (g (x)). Буквально это значит «вычисли g (x) и передай результат продолжению k» (k — kontinuation, часто пишется через «k», чтобы отличать от «c» — constant).Казалось бы, ничего принципиального не поменялось: z = G (x, f)? На самом деле, поменялось! В C++ вывод типов однонаправленный: по аргументам подбирается наиболее подходящая сигнатура функции, будь то шаблон или семейство перегрузок. Если функция g возвращает полиморфный тип, она сможет передать его в f напрямую, без абстрагирования до базового.
Посмотрим, как трансформируются более сложные выражения. f (g (h (x))) <=> H (x, λ y.G (y, λ z.f (z)))), где λ t.expr (t) — лямбда-выражение (замыкание), да простят мне читатели не-C++-ный, а классический стиль записи; H (x, k) = k (h (x))G (x, h) = k (g (x))
f (g (x), h (y)) <=> G (x, λu.H (y, λv.f (u, v)))
Это ведь то, что нам надо! За одной маленькой деталью: полиморфные лямбды.С ними нашу задачу можно реализовать так:
template
template
template
void run (char cx, char cy) { getconfig (cx, [=](auto x) { getconfig (cy, [=](auto y) { entry (x, y, [=](auto sum) { finish (cx, cy, sum); }) }) }); } Выглядит неплохо, хотя и несколько громоздко…Одна беда: полиморфные лямбды появились только в C++14.
А без них передавать шаблоны функций как аргументы других функций — мучительное дело. Но не безнадёжное!
Прибегнем к нескольким трюкам.
Первый трюк
Тип функции должен быть фиксированным (не шаблонным), но сама функция — полиморфной. Как такое возможно? А вот как:
struct getconfig_t {
template
struct entry_t {
template
struct finish_t { // так мы придали фиксированный тип не только шаблону, но и семейству перегрузок функции // (в обычной жизни это была бы россыпь типов void (int), void (unsigned) и т.д. void operator ()(int sum) { std: cout << "int " << sum << std::endl; } void operator()(unsigned sum) { std::cout << "uint " << sum << std::endl; } void operator()(long sum) { std::cout << "long " << sum << std::endl; } void operator()(unsigned long sum) { std::cout << "ulong " << sum << std::endl; } void operator()(double sum) { std::cout << "double " << sum << std::endl; } } const finish; Теперь мы сможем написать entry(A(), B(), finish);, однако, для всей нашей конструкции придётся громоздить нечто страшное: объекты-замыкания
struct F {
char cx, cy; // связанные переменные контекста
F (char cx, char cy) : cx (cx), cy (cy) {}
template
template
struct G {
char cx, char cy;
G (char cx, char cy) : cx (cx), cy (cy) {}
template
void run (char cx, char cy) { getconfig (cx, G (cx, cy)); } К счастью, в старом добром C++ есть библиотека, строящая действительно полиморфные замыкания, — по сути, синтаксические деревья, которые окончательно собираются в момент применения аргументов. Это std: bind, полученная из boost: bind.Выражение bind (foo, x, _1) возвращает даже не одноместную функцию, а не-менее-чем одноместную, принимающую любые типы, лишь бы результат подстановки был совместим с сигнатурой функции foo: bind (foo, x, _1)(100, 200, «bar»).Такая гибкость для нас избыточна, но лучше больше, чем меньше, не правда ли?
Итак, попробуем…
#include
void run (char cx, char cy)
{
getconfig (cx,
bind (getconfig, cy,
bind (entry, _1, _2,
bind (finish, cx, cy, _1)
)
)
);
}
И, конечно же, это добро не скомпилируется! Дело в том, что bind создаёт дерево выражения, и вложенные bind — не независимые замыкания, а просто части одного большого выражения, — по сути, просто скобки оператора ().Без CPS и полиморфизма мы могли бы написать
bind (finish, _1, _2, bind (entry, bind (getconfig, _1), bind (getconfig, _2))) (cx, cy);
и аргументы полученного замыкания — cx и cy — были бы подставлены во все соответствующие места этой мега-формулы.Второй трюк
Чтобы изолировать вложенные bind’ы, в boost была специальная функция protect, маскирующая тип выражения (bind смотрит на свои аргументы с помощью type traits std: is_placeholder и std: is_bind_expression).Почему-то в C++11 эта функция не вошла в стандартную библиотеку, но её несложно написать по мотивам. Спасибо Stack Overflow, всё уже украдено до нас.
template
// если это не bind — передадим как есть
template
// если это bind — завернём в protect_wrapper
template
template
void run (char cx, char cy) { getconfig (cx, probind (getconfig, cy, probind (entry, _1, _2, // что здесь делать? getconfig хочет функцию-продолжение с единственным аргументом! probind (finish, cx, cy, _1) // здесь всё правильно: отдадим в entry замыкание с одним аргументом ) ) ); } Надо каким-то образом показать, что один аргумент надо подставить прямо сейчас, а другой станет формальным параметром полученного замыкания.Без protect — оба подставятся сразу, с protect — оба станут формальными.Вообще, bind, возвращающий bind — это нетривиальная задача. На том же StackOverflow народ спрашивает частные случаи про «bind return bind», и даёт частные ответы. А у нас полиморфизм времени компиляции…
Третий трюк У нас есть несколько путей.
Во-первых, можем реализовать честный карринг, разобрать список аргументов на цепочку вызовов функций, возвращающих функции, потом в выражении собрать всё обратно… Это будет, мягко сказать, громоздко.
Во-вторых, под конкретный случай написать каррированную версию entry
struct curried_entry_t {
template
void run (char cx, char cy)
{
getconfig (cx,
probind (getconfig, cy,
bind (curried_entry, _1, // getconfig (cx, H) вызовет H (x) = probind (getconfig, cy, bind (curried_entry, x, F))
probind (finish, cx, cy, _1)
)
)
);
}
… или, хотя бы, функцию-комбинатор:
struct curry_binary_t {
template
void run (char cx, char cy) { getconfig (cx, probind (getconfig, cy, bind (curry_binary, probind (entry, _1, _2, probind (finish, cx, cy, _1) ), _1 // getconfig (x, H) вызовет H (x) и подставит x сюда ) ) ); } В-третьих, прибегнем к трюку, похожему на трюк с protect: помешаем bind’у раньше времени выполнять подстановку.
// местоимения второго порядка _dN и функция их трансляции _pass_
struct _d1_t {} const _d1; auto _pass_(_d1_t) → decltype (_1) { return _1; }
struct _d2_t {} const _d2; auto _pass_(_d2_t) → decltype (_2) { return _2; }
struct _d3_t {} const _d3; auto _pass_(_d3_t) → decltype (_3) { return _3; }
// и т.д. до _d9
template
struct partial_t { //TODO: нагенерить сигнатуры на все разумные количества аргументов (или попробовать переписать на вариадиках)
template
template
template
void run (char cx, char cy) { getconfig (cx, probind (getconfig, cy, bind (partial, probind (entry, _1, _2, probind (finish, cx, cy, _1) ), // аргумент F — некая двухместная функция… _1, // первый аргумент которой подставлен вызывающей стороной getconfig (cx, H) --> H (x) _d1, //, а второй будет формальным аргументом результирующей функции, которую вызовет getconfig (cy, E) --> E (y) ) ) ); } Итак, мы добавили к стандартной библиотеке комбинаторов недостающий protect, необходимый нам partial, — и смогли написать продолжения на полиморфных замыканиях!
Ну, а чтобы избавиться от этой страшной лесенки, перепишем в столбик
void run_(char cx, char cy) { // кирпичики: продолжения auto g = probind (getconfig, cx, _1); // void (K) auto h = probind (getconfig, cy, _1); // void (K) auto e = probind (entry, _1, _2, _3); // void (ABCD, ABCD, K) // последний кирпичик — без продолжения auto f = probind (finish, cx, cy, _1);
// комбинации auto fe = probind (e,_1,_2, f); //auto feh = probind (h, bind (curried_entry,_1, f)); //auto feh = probind (h, bind (curry_binary, fe,_1)); auto feh = probind (h, bind (partial, fe, _d1, _1)); auto fegh = probind (g, feh);
// запускаем fegh (); } Ну что, испытаем?
int main ()
{
vector
struct A { int foo () { return 1; } } const a; struct B { unsigned foo () { return 2; } } const b; struct C { long foo () { return 3; } } const c; struct D { double foo () { return 4; } } const d;
// все наши полиморфные функции будут иметь первоклассный фиксированный тип
struct getconfig_t
{
template
struct entry_t // e (X, Y, K), где X и Y = A/B/C/D, а K имеет сигнатуру f (N)
{
template
struct finish_t // void f (N)
{
template
void operator ()(char cx, char cy, int n) const { report (cx, cy, «int », n); } void operator ()(char cx, char cy, unsigned n) const { report (cx, cy, «uint », n); } void operator ()(char cx, char cy, long n) const { report (cx, cy, «long », n); } void operator ()(char cx, char cy, unsigned long n) const { report (cx, cy, «ulong », n); } void operator ()(char cx, char cy, double n) const { report (cx, cy, «double», n); } } const finish;
/////////////////////////// // протектор bind-выражений
template
template
template
template
///////////////////////////// // каррированая функция entry
struct curried_entry_t // E1 e (Y, K), где E1 = void e1(X)
{
template
///////////////////////////////// // комбинатор двухместной функции
struct curry_binary_t
{
template
////////////////////////////////// // комбинатор частичных применений
struct _d1_t {} const _d1; auto _pass_(_d1_t) → decltype (_1) { return _1; }
struct _d2_t {} const _d2; auto _pass_(_d2_t) → decltype (_2) { return _2; }
struct _d3_t {} const _d3; auto _pass_(_d3_t) → decltype (_3) { return _3; }
template
struct partial_t
{
template
template
template
struct binder_t
{
template
/////////////// // комбинируем!
void run_1(char cx, char cy) { // кирпичики: продолжения auto g = probind (getconfig, cx, _1); // void (K) auto h = probind (getconfig, cy, _1); // void (K) auto e = probind (entry, _1, _2, _3); // void (ABCD, ABCD, K) // последний кирпичик — без продолжения auto f = probind (finish, cx, cy, _1);
// комбинации auto fe = probind (e,_1,_2, f); //auto feh = probind (h, bind (curried_entry, _1, f)); //auto feh = probind (h, bind (curry_binary, fe, _1)); auto feh = probind (h, bind (partial, fe, _d1, _1)); auto fegh = probind (g, feh);
// запускаем fegh (); }
void run_2(char cx, char cy) { getconfig (cx, probind (getconfig, cy, bind (partial, probind (entry, _1, _2, probind (finish, cx, cy, _1) ), _1, _d1 ) ) ); }
/////////////////////////// // перебираем всё со всеми!
int main ()
{
vector
возвращать значение через return возвращать значение через присваивание в out-параметр поиграть с большей глубиной частичного применения — это понадобится, если будем писать трёхместную функцию entry (X, Y, Z, Kont) Тем более, мы не стали делать красивости, чтобы можно было создавать конвеер продолжений (в стиле >>= или do-нотации Хаскелла, где продолжения суть монада).И уж тем более, не добрались до такой важной вещи, как произвольное управление ходом программы и созданием сопрограмм, — то, чем как раз CPS славится.Но, поскольку статья о продолжениях, — попробуйте продолжить эту тему.
