nickolaym August 12, 2014 at 20:08

Statically Typed Continuations

Recently on RSDN the following question was asked:
Suppose we have a function that returns a polymorphic type

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");
  }
}

and a function that takes its instances

int entry(Base* x, Base* y) { return x->foo()*10 + y->foo(); }

which use something like this

void run(char cx, char cy) { std::cout << cx << cy << " : " << entry(getconfig(cx), getconfig(cy)) << std::endl; }

Is it possible to drag polymorphism to the compilation stage?

Can! But for this you have to turn the code with the fur inside, that is, rewrite it in the continuation passing style (CPS) - or, in Russian, on the sequels.

First, recall what it is, in general terms.

If we have the expression z = f (g (x)), we calculate it like this:

y = g (x)
z = f (y)

Now we define a higher-order function (taking another function as input) G (x, k) = k (g (x)). Literally, this means “calculate g (x) and pass the result to the continuation k” (k - kontinuation, often written through “k” to distinguish from “c” - constant).
It would seem that nothing fundamentally changed: z = G (x, f)?

In fact, it has changed! In C ++, type inference is one-way: the arguments select the most appropriate function signature, whether it be a template or a family of overloads. If the function g returns a polymorphic type, it can pass it to f directly, without abstracting to the base one.

Let's see how more complex expressions are transformed.

f (g (h (x))) <=> H (x, λ yG (y, λ zf (z)))),
where λ t.expr (t) is the lambda expression (closure), forgive me non-C ++ readers - but a classic writing style;
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)))

This is what we need! Behind one small detail: polymorphic lambdas .
With them, our task can be implemented as follows:


template 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 void entry(X&& x, Y&& y, K&& kont)
{
  kont(x.foo()*10 + y.foo());
}
template // работаем с любыми числовыми типами, - почему бы и нет?
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);
      })
    })
  });
}

It looks good, albeit a little cumbersome ...
One trouble: polymorphic lambdas appeared only in C ++ 14.

And without them, passing function templates as arguments to other functions is a painful affair. But not hopeless!

Let's resort to a few tricks.

First trick

The type of the function must be fixed (not stereotyped), but the function itself must be polymorphic. How is this possible? That's how:

struct getconfig_t {
  template
  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
  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;

Now we can write entry(A(), B(), finish);, however, for our entire construction we have to pile up something terrible: closure objects

struct F {
  char cx, cy; // связанные переменные контекста
  F(char cx, char cy) : cx(cx), cy(cy) {}
  template void operator()(N sum) const { finish(cx,cy,sum); }
};
template struct E {
  char cx, cy;
  X&& x;
  E(char cx, char cy, X&& x) : cx(cx), cy(cy), x(x) {}
  template 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 void operator()(X&& x) const { getconfig(cy, E(cx,cy,x)); }
};
void run(char cx, char cy) { getconfig(cx, G(cx,cy)); }

Fortunately, in the good old C ++, there is a library that builds truly polymorphic closures - in fact, syntax trees that are finally assembled when the arguments are applied. This is std :: bind obtained from boost :: bind.
The expression bind(foo, x, _1)returns even one-place function, not-less-than singles, receiving any type, as long as the result of the substitution is compatible with the signature function foo: bind(foo, x, _1)(100, 200, "bar").
Such flexibility is excessive for us, but better is more than less is not it?

So let's try ...

#include 
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)
      )
    )
  );
}

And, of course, this good will not compile! The fact is that bind creates an expression tree, and nested bind are not independent closures, but simply parts of one large expression, in fact, just operator brackets ().
Without CPS and polymorphism, we could write

bind(finish, _1, _2, bind(entry, bind(getconfig, _1), bind(getconfig, _2))) (cx, cy);

and the arguments of the resulting closure - cx and cy - would be substituted in all the corresponding places of this mega-formula.

Second trick

To isolate nested binds, boost had a special protect function that masked the type of expression (bind looks at its arguments with type traits std :: is_placeholder and std :: is_bind_expression).
For some reason, in C ++ 11, this function was not included in the standard library, but it is not difficult to write for reasons. Thanks Stack Overflow, everything is already stolen before us.

template // где T - некий класс - результат bind-выражения
struct protect_wrapper : T
{
    protect_wrapper(const T& t) : T(t) {}
    protect_wrapper(T&& t) : T(std::move(t)) {}
    // оператор() унаследован
};
// если это не bind - передадим как есть
template
typename std::enable_if< !std::is_bind_expression< typename std::decay::type >::value,
                T&& >::type
protect(T&& t)
{
    return std::forward(t);
}
// если это bind - завернём в protect_wrapper
template
typename std::enable_if< std::is_bind_expression< typename std::decay::type >::value,
                protect_wrapper::type > >::type
protect(T&& t)
{
    return protect_wrapper::type >(std::forward(t));
}

Now it bind(foo, protect(bind(bar, _1)), _1)(x)will mean that the function foo will receive another function bar (_1) as its input, and not the result of evaluating bar (x).

protect (bind (...)) is an idiom, and in order not to write extra brackets, we can write the appropriate combination:

template auto probind(Args... args) -> decltype(protect(bind(args...))) { return protect(bind(args...)); }

In C ++ 03, it would look more verbose - without variadics, without type inference. But, I hope everyone has already updated their compilers? And who did not update, write protect (bind (.....)).

However, probind alone will not save us.

void run(char cx, char cy)
{
  getconfig(cx,
    probind(getconfig, cy,
      probind(entry, _1, _2, // что здесь делать? getconfig хочет функцию-продолжение с единственным аргументом!
        probind(finish, cx, cy, _1) // здесь всё правильно: отдадим в entry замыкание с одним аргументом
      )
    )
  );
}

We need to somehow show that one argument must be substituted right now, and the other will become a formal parameter of the resulting closure.
Without protect - both will be substituted immediately, with protect - both will become formal.

In general, bind returning bind is not a trivial task. On the same StackOverflow, people ask special cases about “bind return bind”, and give private answers. And we have polymorphism of compilation time ...

Third trick

We have several ways.

First, we can implement honest currying, parse the list of arguments into a chain of function calls that return functions, then put everything back in the expression ... This will be, to put it mildly, cumbersome.

Secondly, for a specific case, write a curried version of entry

struct curried_entry_t {
  template
  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)
      )
    )
  );
}

... or, at least, a combinator function:

struct curry_binary_t {
  template
  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 сюда
      )
    )
  );
}

Thirdly, we will resort to a trick similar to the trick with protect: we will prevent bind from doing the substitution ahead of time.

// местоимения второго порядка _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 auto _pass_(T&& t) -> T&& { return t; } // все остальные аргументы подставляются как есть
struct partial_t
{
  //TODO: нагенерить сигнатуры на все разумные количества аргументов (или попробовать переписать на вариадиках)
  template
  auto operator()(F&& f) const -> decltype( probind(f) )
  { return probind(f); }
  template
  auto operator()(F&& f, T1&& t1) const -> decltype( probind(f, _pass_(t1)) )
  { return probind(f, _pass_(t1)); }
  template
  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)
      )
    )
  );
}

So, we added to the standard library of combinators the missing protect that we need partial , and we were able to write extensions on polymorphic closures!

Well, to get rid of this terrible ladder, we rewrite it in a column

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();
}

Well, shall we experience?

int main()
{
  vector abcd = { 'a','b','c','d','e' };
  for(auto x : abcd)
    for(auto y : abcd)
      run_1(x,y);
}

Full text of the program

all in a bunch

#include 
#include 
#include 
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 // где 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
    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 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
struct protect_wrapper : T
{
    protect_wrapper(const T& t) : T(t) {}
    protect_wrapper(T&& t) : T(std::move(t)) {}
};
template
typename std::enable_if< !std::is_bind_expression< typename std::decay::type >::value,
                T&& >::type
protect(T&& t)
{
    return std::forward(t);
}
template
typename std::enable_if< std::is_bind_expression< typename std::decay::type >::value,
                protect_wrapper::type > >::type
protect(T&& t)
{
    return protect_wrapper::type >(std::forward(t));
}
template
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
    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
    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 auto _pass_(T&& t) -> T&& { return t; }
struct partial_t
{
    template
    auto operator()(F&& f) const -> decltype( probind(f) )
    { return probind(f); }
    template
    auto operator()(F&& f, T1&& t1) const -> decltype( probind(f, _pass_(t1)) )
    { return probind(f, _pass_(t1)); }
    template
    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
    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 abcd = { 'a','b','c','d','e' };
    for(auto x : abcd)
        for(auto y : abcd)
            run_1(x,y);
}

Execution result

Hidden text

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 ...

Of course, we have not tried to do a lot here:

return value through return
return value through assignment to out parameter
play with a greater depth of partial application - this will be needed if we write the three-place function entry (X, Y, Z, Kont)

Moreover, we did not make prettiness so that we could create a conveyor of continuations (in the style of >> = or Haskell do-notation, where continuations are the essence of the monad).
And even more so, we didn’t get to such an important thing as arbitrary control of the program’s progress and creation of coroutines — something that CPS is famous for.

But, since the article is about sequels, try to continue this topic.

Tags: