- PVSM.RU - https://www.pvsm.ru -
Намедни на 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)), мы его вычисляем так:
Теперь определим функцию высшего порядка (принимающую на вход другую функцию) 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<class K> void getconfig(char cfg, K& kont)
{
switch(cfg)
{
case 'a': kont(A()); break; // кстати, теперь необязательно выделять объекты на куче
case 'b': kont(B()); break;
case 'c': kont(C()); break;
case 'd': kont(D()); break;
default: std::cerr << "bad type" << std::endl; break; // вместо броска исключения - просто не вызываем продолжение
}
}
template<class X, class Y, class K> void entry(X&& x, Y&& y, K&& kont)
{
kont(x.foo()*10 + y.foo());
}
template<class N> // работаем с любыми числовыми типами, - почему бы и нет?
void finish(char cx, char cy, N sum)
{
std::cout << cx << cy << " : " << sum << std::endl;
}
// и даже так
void finish(char cx, char cy, int sum) { std::cout << cx << cy << " : " << "int " << sum << std::endl; }
void finish(char cx, char cy, unsigned sum) { std::cout << cx << cy << " : " << "uint " << sum << std::endl; }
void finish(char cx, char cy, long sum) { std::cout << cx << cy << " : " << "long " << sum << std::endl; }
void finish(char cx, char cy, unsigned long sum) { std::cout << cx << cy << " : " << "ulong " << sum << std::endl; }
void finish(char cx, char cy, double sum) { std::cout << cx << cy << " : " << "double " << sum << std::endl; }
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<class K>
void operator() (char cfg, K&& kont) const
{
switch(cfg)
{
case 'a': kont(A()); break;
case 'b': kont(B()); break;
case 'c': kont(C()); break;
case 'd': kont(D()); break;
default: std::cerr << "bad type" << std::endl; break;
}
}
} const getconfig; // заодно сразу определим константу этого типа
struct entry_t {
template<class X, class Y, class K>
void operator()(X&& x, Y&& y, K&& kont) const { kont(x.foo()*10 + y.foo()); }
} const entry;
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<class N> void operator()(N sum) const { finish(cx,cy,sum); }
};
template<class X> struct E {
char cx, cy;
X&& x;
E(char cx, char cy, X&& x) : cx(cx), cy(cy), x(x) {}
template<class Y> void operator()(Y&& y) const { entry(x,y, F(cx,cy)); }
};
struct G {
char cx, char cy;
G(char cx, char cy) : cx(cx), cy(cy) {}
template<class X> void operator()(X&& x) const { getconfig(cy, E<X>(cx,cy,x)); }
};
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 <functional>
using namespace std; // bind
using namespace std::placeholders; // _1, _2
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<typename T> // где T - некий класс - результат bind-выражения
struct protect_wrapper : T
{
protect_wrapper(const T& t) : T(t) {}
protect_wrapper(T&& t) : T(std::move(t)) {}
// оператор() унаследован
};
// если это не bind - передадим как есть
template<typename T>
typename std::enable_if< !std::is_bind_expression< typename std::decay<T>::type >::value,
T&& >::type
protect(T&& t)
{
return std::forward<T>(t);
}
// если это bind - завернём в protect_wrapper
template<typename T>
typename std::enable_if< std::is_bind_expression< typename std::decay<T>::type >::value,
protect_wrapper<typename std::decay<T>::type > >::type
protect(T&& t)
{
return protect_wrapper<typename std::decay<T>::type >(std::forward<T>(t));
}
Теперь bind(foo, protect(bind(bar, _1)), _1)(x)
будет значить, что функция foo получит на вход другую функцию bar(_1), а не результат вычисления bar(x).
protect(bind(...)) — это идиома, и чтобы не писать лишних скобок, мы можем написать соответствующую комбинацию:
template<class... Args> auto probind(Args... args) -> decltype(protect(bind(args...))) { return protect(bind(args...)); }
На C++03 она выглядела бы более многословно — без вариадиков, без вывода типов. Но, я надеюсь, все уже обновили свои компиляторы? А кто не обновил, пишите protect(bind(.....)).
Однако, сам по себе probind нас не спасёт.
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<class Y, class K>
auto operator()(Y&& y, K&& k) const -> decltype( probind(entry,_1,y,k) ) { return probind(entry,_1,y,k); }
};
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<class E, class X, class K>
auto operator(E&& e, X&& x) const -> decltype( probind(e,x,_1) ) { return probind(e,x,_1); }
} curry_binary;
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<class T> auto _pass_(T&& t) -> T&// все остальные аргументы подставляются как есть
struct partial_t
{
//TODO: нагенерить сигнатуры на все разумные количества аргументов (или попробовать переписать на вариадиках)
template<class F>
auto operator()(F&& f) const -> decltype( probind(f) )
{ return probind(f); }
template<class F, class T1>
auto operator()(F&& f, T1&& t1) const -> decltype( probind(f, _pass_(t1)) )
{ return probind(f, _pass_(t1)); }
template<class F, class T1, class T2>
auto operator()(F&& f, T1&& t1, T2&& t2) const -> decltype( probind(f, _pass_(t1), _pass_(t2)) )
{ return probind(f, _pass_(t1), _pass_(t2)); }
} const partial;
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<char> abcd = { 'a','b','c','d','e' };
for(auto x : abcd)
for(auto y : abcd)
run_1(x,y);
}
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
using namespace std::placeholders;
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<class K> // где K имеет сигнатуру void f(ABCD)
void operator()(char t, K kont) const
{
cout << "getconfig(" << t << ") ";
switch(t)
{
case 'a': kont(A()); break;
case 'b': kont(B()); break;
case 'c': kont(C()); break;
case 'd': kont(D()); break;
default: cout << "bad type" << endl; break; // исключение состоит в том, чтобы не вызывать продолжение :)
}
}
} const getconfig;
struct entry_t // e(X,Y,K), где X и Y = A/B/C/D, а K имеет сигнатуру f(N)
{
template<class X, class Y, class K>
void operator()(X&& x, Y&& y, K&& kont) const
{
cout << "entry(...) ";
kont(x.foo()*10 + y.foo());
}
} const entry;
struct finish_t // void f(N)
{
template<class N> void report(char cx, char cy, const char* type, N value) const
{
cout << "finish() : ";
cout << cx << "+" << cy << " = " << type << " " << value << endl;
}
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<typename T>
struct protect_wrapper : T
{
protect_wrapper(const T& t) : T(t) {}
protect_wrapper(T&& t) : T(std::move(t)) {}
};
template<typename T>
typename std::enable_if< !std::is_bind_expression< typename std::decay<T>::type >::value,
T&& >::type
protect(T&& t)
{
return std::forward<T>(t);
}
template<typename T>
typename std::enable_if< std::is_bind_expression< typename std::decay<T>::type >::value,
protect_wrapper<typename std::decay<T>::type > >::type
protect(T&& t)
{
return protect_wrapper<typename std::decay<T>::type >(std::forward<T>(t));
}
template<class... Args>
auto probind(Args... args) -> decltype(protect(bind(args...))) { return protect(bind(args...)); }
/////////////////////////////
// каррированая функция entry
struct curried_entry_t // E1 e(Y,K), где E1 = void e1(X)
{
template<class Y, class K>
auto operator()(Y&& y, K&& k) const -> decltype( probind(entry,_1,y,k) ) { return probind(entry,_1,y,k); }
} const curried_entry;
/////////////////////////////////
// комбинатор двухместной функции
struct curry_binary_t
{
template<class F, class X>
auto operator()(F&& f, X&& x) const -> decltype( probind(f,x,_1) ) { return probind(f,x,_1); }
} const curry_binary;
//////////////////////////////////
// комбинатор частичных применений
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<class T> auto _pass_(T&& t) -> T&struct partial_t
{
template<class F>
auto operator()(F&& f) const -> decltype( probind(f) )
{ return probind(f); }
template<class F, class T1>
auto operator()(F&& f, T1&& t1) const -> decltype( probind(f, _pass_(t1)) )
{ return probind(f, _pass_(t1)); }
template<class F, class T1, class T2>
auto operator()(F&& f, T1&& t1, T2&& t2) const -> decltype( probind(f, _pass_(t1), _pass_(t2)) )
{ return probind(f, _pass_(t1), _pass_(t2)); }
} const partial;
struct binder_t
{
template<class F, class... Args>
auto operator()(F&& f, Args... args) const -> decltype(bind(f,args...)) { return bind(f,args...); }
} const binder;
///////////////
// комбинируем!
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<char> abcd = { 'a','b','c','d','e' };
for(auto x : abcd)
for(auto y : abcd)
run_1(x,y);
}
getconfig(a) getconfig(a) entry(...) finish() : a+a = int 11
getconfig(a) getconfig(b) entry(...) finish() : a+b = uint 21
getconfig(a) getconfig(c) entry(...) finish() : a+c = long 31
getconfig(a) getconfig(d) entry(...) finish() : a+d = double 41
getconfig(a) getconfig(e) bad type
getconfig(b) getconfig(a) entry(...) finish() : b+a = uint 12
getconfig(b) getconfig(b) entry(...) finish() : b+b = uint 22
getconfig(b) getconfig(c) entry(...) finish() : b+c = ulong 32
getconfig(b) getconfig(d) entry(...) finish() : b+d = double 42
getconfig(b) getconfig(e) bad type
getconfig(c) getconfig(a) entry(...) finish() : c+a = long 13
getconfig(c) getconfig(b) entry(...) finish() : c+b = ulong 23
getconfig(c) getconfig(c) entry(...) finish() : c+c = long 33
getconfig(c) getconfig(d) entry(...) finish() : c+d = double 43
getconfig(c) getconfig(e) bad type
getconfig(d) getconfig(a) entry(...) finish() : d+a = double 14
getconfig(d) getconfig(b) entry(...) finish() : d+b = double 24
getconfig(d) getconfig(c) entry(...) finish() : d+c = double 34
getconfig(d) getconfig(d) entry(...) finish() : d+d = double 44
getconfig(d) getconfig(e) bad type
getconfig(e) bad type
getconfig(e) bad type
getconfig(e) bad type
getconfig(e) bad type
getconfig(e) bad type
Конечно, мы здесь не попробовали сделать очень многое:
Тем более, мы не стали делать красивости, чтобы можно было создавать конвеер продолжений (в стиле >>= или do-нотации Хаскелла, где продолжения суть монада).
И уж тем более, не добрались до такой важной вещи, как произвольное управление ходом программы и созданием сопрограмм, — то, чем как раз CPS славится.
Но, поскольку статья о продолжениях, — попробуйте продолжить эту тему.
Автор: nickolaym
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-3/67343
Ссылки в тексте:
[1] Источник: http://habrahabr.ru/post/232979/
Нажмите здесь для печати.