Можно ли писать продолжения на C ++? - PullRequest
Новая
       23

Можно ли писать продолжения на C ++?

0 голосов
/ 07 марта 2020

Я узнал о продолжениях, читая Маленький Схемер Фридмана и Феллайзена, и, чтобы немного попрактиковаться с этой концепцией, я написал простой код, который, учитывая список целых чисел, удаляет четные числа и возвращает сумму шансы.

Это код моей схемы: 

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

Я скомпилировал его по схеме курицы и работает, как и ожидалось, выдав результат 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) {
      |                                     ^~~~

Я хотел бы знать, что происходит под капотом: почему компилятор берет так много время и память для того, что выглядит как очень простой кусок кода?

Ответы [ 2 ]

1 голос
/ 07 марта 2020

Да, в C ++ можно писать продолжения. См., Например, эту веб-страницу для примеров.

В приведенном ниже коде используется стиль передачи продолжения (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;
}

Выходные данные читаются 

9

Вы можете запустить код онлайн.

0 голосов
/ 07 марта 2020

Наслаждайтесь силой C++. Немного макро-магии c, и это почти то же самое, что и оригинальная версия.

...