Статически типизированные продолжения

Намедни на 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)), мы его вычисляем так:

1. y = g(x)
2. 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<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&& { return 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&& { return 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

To be continued...

Конечно, мы здесь не попробовали сделать очень многое:

1. возвращать значение через return
2. возвращать значение через присваивание в out-параметр
3. поиграть с большей глубиной частичного применения — это понадобится, если будем писать трёхместную функцию entry(X,Y,Z, Kont)

Тем более, мы не стали делать красивости, чтобы можно было создавать конвеер продолжений (в стиле >>= или do-нотации Хаскелла, где продолжения суть монада).
И уж тем более, не добрались до такой важной вещи, как произвольное управление ходом программы и созданием сопрограмм, — то, чем как раз CPS славится.

Но, поскольку статья о продолжениях, — попробуйте продолжить эту тему.