Is it possible to write continuations in C++?

Question

I discovered about continuations while reading The Little Schemer by Friedman and Felleisen, and to practice a little with this concept I wrote a simple code that given a list of integers removes the evens and returns the sum of the odds.

This is my scheme code:

(define nil '())

; s is a list of integers, op is an operator.
(define (rem_add s op)
  (cond ((null? s) (op nil 0))
        ((even? (car s))
            (rem_add (cdr s)
                (lambda (l n) (op l n))))
        (else
            (rem_add (cdr s)
                (lambda (l n) (op (cons (car s) l) (+ n 1)))))))

(define (count s n)
  (cond ((null? s) 0)
        (else (+ (car s) (count (cdr s) n)))))

(define s (list 1 2 3 4 5))
(display (rem_add s count))

I compiled it with chicken scheme and works as expected, producing the output 9.

Then I tried to rewrite the same code in C++, as follows.

#include<functional>
#include<iostream>
#include<set>


int rem_add(const std::set<int>& s, auto op) {
    if (s.empty()) {
        return op(s, 0);
    }
    std::set<int> s2(++s.cbegin(), s.cend());
    if (*s.cbegin() % 2 == 0) {
        return rem_add(s2,
            [op](const std::set<int>& l, int n){
                    return op(l, n);
                });
    } else {
        return rem_add(s2,
            [&s, op](const std::set<int>& l, int n){
                   std::set<int> q(l);
                   q.insert(*s.cbegin());
                   return op(q, n + 1);
            });
    }
}


// Remove the even elements from s, and return the sum of the odd elements.
int main() {
    std::set<int> s {1, 2, 3, 4, 5};

    std::function<int(const std::set<int>&, int)>
      count = [count](const std::set<int>& s, int n)
        {   if (s.empty()) { return 0; }
            std::set<int> s2(++s.cbegin(), s.cend());
            return *s.cbegin() + count(s2, n);
        };
    auto sum_odds = rem_add(s, count);
    std::cout << sum_odds << std::endl;
}

Trying to compile this code with g++ 9.2.1 takes very long. After a few minutes it used up all the memory of my laptop and I had to abort the compilation. The only compiler warning I get is related, I think, just to the use of a very recent keyword:

warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
    7 | int rem_add(const std::set<int>& s, auto op) {
      |                                     ^~~~

I would like to know what is happening under the hood: why does the compiler take so much time and memory for what looks like a very simple piece of code?

Answer 1

Yes, in C++ it is possible to write continuations. See for example this webpage for examples.

The below code uses continuation passing style (CPS) for the example you proposed:

#include<functional>
#include<iostream>
#include<vector>

int main() {

    auto calc = [](auto&& k1, auto&& k2, auto V){ return k1(k2(V,0));};

    std::function<std::vector<int>(std::vector<int>, int)> get_odd;
    get_odd = [&get_odd](auto V, int pos)
    {
        if(pos == V.size()) return V;
        if(V[pos] % 2 == 0)
        {
            V.erase(V.begin()+pos);
            return get_odd(V,pos);
        }
        else
            return get_odd(V,++pos);
    };

    std::function<int(const std::vector<int>&)> sum;
    sum = [&sum](const std::vector<int>& V)
    {
        if (V.empty()) return 0;
        std::vector<int> W(++V.begin(), V.end());
        return V[0] + sum(W);
    };

    std::vector<int> v1{1,2,3,4,5};   
    std::cout << calc(sum, get_odd, v1) << std::endl;

    return 0;
}

The output reads

9

You can run the code online.

Answer 2

Enjoy the power of C++. Some macro magic and it is almost same as original version.

#include <functional>
#include <iostream>
#include <vector>

using Set = std::vector<int>;
using Op = std::function<int(const Set &, int n)>;
int car(const Set &s) { return *s.cbegin(); }
Set cdr(const Set &s) { return Set(++s.cbegin(), s.cend()); }
bool even(int x) { return (x % 2) == 0; }
bool null(const Set &s) { return s.empty(); }
Set cons(int x, const Set &s) { Set r = s; r.push_back(x); return r; }

#define DEFINE_OP(name, s, op) int name(const Set &s, Op op) {
#define DEFINE_N(name, s, n) int name(const Set &s, int n) {
#define DEFINE_S(name, ...) auto name = Set{__VA_ARGS__};
#define COND_START if (false) {}
#define COND(expr, result) else if (expr) { return result; }
#define ELSE(result) else { return result; } }
#define LAMBDA(l, n, body) [s, op](const Set &l, int n) { return body; }
#define DISPLAY(func, s, count) int main() { std::cout << func(s, count) << std::endl; return 0; }

// here is the implementation

DEFINE_S(nil)

DEFINE_OP (rem_add, s, op)
  COND_START
    COND (( null ( s ) ), ( op (nil, 0) ))
    COND (( even ( car(s) )),
            ( rem_add (cdr (s),
                 LAMBDA (l, n, ( op (l, n) ) ))))
    ELSE (
            ( rem_add (cdr (s),
                 LAMBDA (l, n, ( op ( cons ( car (s), l), n + 1) )))))

DEFINE_N (count, s, n)
  COND_START
    COND ( (null (s)), (0))
    ELSE ( (car (s) + count (cdr (s), n - 1 ) ))

DEFINE_S(s, 1, 2, 3, 4, 5);
DISPLAY(rem_add, s, count)