是否可以用 C++ 编写延续？

Question

我在阅读 Friedman 和 Felleisen 的 The Little Schemer 时发现了延续，为了练习这个概念，我写了一个简单的代码，给定一个整数列表删除偶数和 returns 赔率之和。

这是我的方案代码：

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

我用 chicken 方案编译它并按预期工作，产生输出 9。

然后我尝试用C++重写了同样的代码，如下。

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

尝试使用 g++ 9.2.1 编译此代码需要很长时间。几分钟后，它耗尽了我笔记本电脑的所有内存，我不得不中止编译。我得到的唯一编译器警告是相关的，我认为，只是使用了一个最近的关键字：

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

我想知道幕后发生了什么：为什么编译器会为一段看起来非常简单的代码占用这么多时间和内存？

Answer 1

是的，在 C++ 中可以编写延续。例如，参见此 webpage。

对于您提出的示例，以下代码使用连续传递样式 (CPS)：

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

输出为

You can run the code online.

Answer 2

享受C++的力量。一些宏魔术，它几乎与原始版本相同。

#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)

是否可以用 C++ 编写延续？

Is it possible to write continuations in C++?

c++

recursion

scheme

continuations

language-lawyer