没有Y Combinator的递归lambda回调

Question

我希望创建一个回调递归返回自身作为回调.

recurse的建议方法是函数具有对自身的引用:

std::function<void (int)> recursive_function = [&] (int recurse) {
    std::cout << recurse << std::endl;

    if (recurse > 0) {
        recursive_function(recurse - 1);
    }
};

一旦从函数返回它,它就会失败:

#include <functional>
#include <iostream>

volatile bool no_optimize = true;

std::function<void (int)> get_recursive_function() {
    std::function<void (int)> recursive_function = [&] (int recurse) {
        std::cout << recurse << std::endl;

        if (recurse > 0) {
            recursive_function(recurse - 1);
        }
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    get_recursive_function()(10);
}

这会在输出后产生分段错误,10因为引用变为无效.

我该怎么做呢？我已经成功地使用了我认为是Y Combinator(我将作为答案发布),但它非常令人困惑.有没有更好的办法？

---

其他尝试

我尝试了将它包装在另一层回调中的无聊方法:

#include <functional>
#include <iostream>
#include <memory>

volatile bool no_optimize = true;

std::function<void (int)> get_recursive_function() {
    // Closure to allow self-reference
    auto recursive_function = [] (int recurse) {
        // Actual function that does the work.
        std::function<void (int)> function = [&] (int recurse) {
            std::cout << recurse << std::endl;

            if (recurse > 0) {
                function(recurse - 1);
            }
        };

        function(recurse);
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    get_recursive_function()(10);
}

但是在实际场景中失败了,其中函数被延迟并被外循环调用:

#include <functional>
#include <iostream>
#include <memory>
#include <queue>

volatile bool no_optimize = true;

std::queue<std::function<void (void)>> callbacks;

std::function<void (int)> get_recursive_function() {
    // Closure to allow self-reference
    auto recursive_function = [] (int recurse) {
        // Actual function that does the work.
        std::function<void (int)> function = [&] (int recurse) {
            std::cout << recurse << std::endl;

            if (recurse > 0) {
                callbacks.push(std::bind(function, recurse - 1));
            }
        };

        function(recurse);
    };

    if (no_optimize) {
        return recursive_function;
    }

    return [] (int) {};
}

int main(int, char **) {
    callbacks.push(std::bind(get_recursive_function(), 10));

    while (!callbacks.empty()) {
        callbacks.front()();
        callbacks.pop();
    }
}

这给10,然后9再段故障.

Answer 1

我目前的解决方法（不幸的是很复杂）是：

#include <functional>
#include <iostream>
#include <queue>

volatile bool no_optimize = true;

std::queue<std::function<void (void)>> callbacks;

（我认为这是一个Y Combinator，但我不确定。）

std::function<void (int)> y_combinator(
        std::function<void (std::function<void (int)>, int)> almost_recursive_function
) {
    auto bound_almost_recursive_function = [almost_recursive_function] (int input) {
        y_combinator(almost_recursive_function)(input);
    };

    return [almost_recursive_function, bound_almost_recursive_function] (int input) {
        almost_recursive_function(bound_almost_recursive_function, input);
    };
}

这是基本函数；它不调用自身，而是调用它传递的参数。这个参数应该是递归函数本身。

std::function<void (std::function<void (int)>, int)> get_almost_recursive_function() {
    auto almost_recursive_function = (
        [] (std::function<void (int)> bound_self, int recurse) {
            std::cout << recurse << std::endl;

            if (recurse > 0) {
                callbacks.push(std::bind(bound_self, recurse - 1));
            }
        }
    );

    if (no_optimize) {
        return almost_recursive_function;
    }

    return [] (std::function<void (int)>, int) {};
}

因此，可以通过将组合器应用于几乎递归函数来生成所需的函数。

std::function<void (int)> get_recursive_function() {
    return y_combinator(get_almost_recursive_function());
}

main运行时，将根据需要输出10, 9, ..., , 。0

int main(int, char **) {
    callbacks.push(std::bind(get_recursive_function(), 10));

    while (!callbacks.empty()) {
        callbacks.front()();
        callbacks.pop();
    }
}