Рекурсивные лямбда-колбэки без Y Combinator
Я хочу создать обратный вызов, который рекурсивно возвращает себя в качестве обратного вызова.
Предлагаемый метод для рекурсии состоит в том, чтобы функция имела ссылку на себя:
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 а затем ошибки сегментации.
4 ответа
Как вы правильно заметили, существует неверная ссылка из лямбда-захвата [&],
Ваши возвращаемые значения являются функторами различного рода, поэтому я предполагаю, что точный тип возвращаемого значения не важен, просто то, что он ведет себя как функция, то есть может быть вызвано.
Если recursive_function завернут в struct или же class Вы можете сопоставить оператора вызова с recursive_function член. Проблема возникает с захватом this переменная. Это будет захвачено с this при создании, поэтому, если объект копируется немного, оригинал this может больше не быть действительным. Так что соответствующий this может быть передано в функцию во время выполнения (это this проблема может не быть проблемой, но она сильно зависит от того, когда и как вы вызываете функцию).
#include <functional>
#include <iostream>
volatile bool no_optimize = true;
struct recursive {
std::function<void (recursive*, int)> recursive_function = [] (recursive* me, int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
me->recursive_function(me, recurse - 1);
}
};
void operator()(int n)
{
if (no_optimize) {
recursive_function(this, n);
}
}
};
recursive get_recursive_function() {
return recursive();
}
int main(int, char **) {
get_recursive_function()(10);
}
В качестве альтернативы, если recursive_function может быть static тогда объявление его в оригинальном примере кода также может помочь вам.
Я хотел добавить некоторую общность к ответу выше, то есть сделать его шаблоном;
#include <functional>
#include <iostream>
volatile bool no_optimize = true;
template <typename Signature>
struct recursive;
template <typename R, typename... Args>
struct recursive<R (Args...)> {
std::function<R (recursive const&, Args... args)> recursive_function;
recursive() = default;
recursive(decltype(recursive_function) const& func) : recursive_function(func)
{
}
template <typename... T>
R operator()(T&&... args) const
{
return recursive_function(*this, std::forward<Args>(args)...);
}
};
recursive<void (int)> get_recursive_function()
{
using result_type = recursive<void (int)>;
if (!no_optimize) {
return result_type();
}
result_type result ([](result_type const& me, int a) {
std::cout << a << std::endl;
if (a > 0) {
me(a - 1);
}
});
return result;
}
int main(int, char **) {
get_recursive_function()(10);
}
Как это работает? По сути, он перемещает рекурсию изнутри функции (т.е. вызывает себя) к объекту (то есть оператору функции на самом объекте) для реализации рекурсии. в get_recursive_function тип результата recursive<void (int)> используется в качестве первого аргумента для рекурсивной функции. это const& потому что я реализовал operator() как const в соответствии с большинством стандартных алгоритмов и по умолчанию для лямбда-функции. Это требует некоторого "сотрудничества" с исполнителем функции (то есть использование me параметр; само по себе *this), чтобы рекурсия работала, но за эту цену вы получаете рекурсивную лямбду, которая не зависит от ссылки на стек.
Все проблемы в программировании могут быть решены с помощью другого уровня косвенности, за исключением слишком большого числа уровней косвенности.
Моя цель - создать тип recursive<void(int)> это позволяет вам легко создавать рекурсивную лямбду. Для этого вы переходите в лямбду с подписью void(recursive<void(int)>, int) - первый аргумент - это то, что вы вызываете, чтобы выполнить рекурсивный вызов.
Затем я завязываю его в узлы и делаю его полностью рекурсивной функцией с подписью void(int),
Вот моя реализация recursive<Signature>:
template<class Sig>
struct recursive;
template<class R, class... As>
struct recursive< R(As...) > {
using base_type = std::function<R(recursive, As...)>;
private:
std::shared_ptr< base_type > base;
public:
template<typename...Ts>
auto operator()(Ts&&... ts) const
-> typename std::result_of< base_type( recursive, Ts... ) >::type
{
return (*base)(*this, std::forward<Ts>(ts)...);
}
recursive(recursive const&)=default;
recursive(recursive&&)=default;
recursive& operator=(recursive const&)=default;
recursive& operator=(recursive &&)=default;
recursive() = default;
template<typename L, typename=typename std::result_of< L(recursive, As...) >::type>
explicit recursive( L&& f ):
base( std::make_shared<base_type>(std::forward<L>(f)))
{}
explicit operator bool() const { return base && *base; }
};
Это, правда, довольно сложно. Я сделал несколько вещей, чтобы сделать его более эффективным, такой идеальный пересылка. Это также, в отличие от std::function, дважды проверяет, что тип лямбда, который вы передаете ему, соответствует желаемой подписи.
Я верю, но не подтвердил, что я сделал дружелюбным сделать подпись лямбды void(auto&&,int), Кто-нибудь знает полностью совместимый онлайн-компилятор C++1y?
Выше это просто шаблон. Важно то, как это выглядит в точке использования:
std::function<void (int)> get_recursive_function() {
auto f =
[] (recursive<void(int)> self, int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
self(recurse - 1);
}
};
return recursive< void(int) >( f );
};
Здесь мы делаем популярным auto f = lambda синтаксис. Нет необходимости хранить его в std::function,
Затем мы явно приведем его к recursive<void(int)>, который связывает его в узлы и удаляет recursive<void(int)> аргумент f с фронта и выставляет подпись void(int),
Это требует, чтобы ваш лямбда recursive<void(int)> self в качестве первого параметра, и сделать рекурсию через него, но это не кажется резким. Если бы я написал это правильно, он мог бы работать с auto&& self в качестве первого параметра, но я не уверен.
recursive<?> работает на любую подпись, естественно.
И с отложенными вызовами во внешнем цикле это все еще работает. Обратите внимание, что я избавился от этой глобальной переменной (она будет работать с ней как с глобальной переменной, просто было грязно оставлять ее в).
В C++1y мы можем исключить стирание типа &;; shared_ptr накладные расходы вы видите выше (с recursive объект, держащий shared_ptr<function<?>>). Вы должны предоставить возвращаемое значение, так как я не могу получить result_of распутать мой беспорядок
struct wrap {};
template<class R, class F>
struct recursive {
using base_type = F;
private:
F base;
public:
template<class... Ts>
R operator()(Ts&&... ts) const
{
return (*base)(*this, std::forward<Ts>(ts)...);
}
recursive(recursive const&)=default;
recursive(recursive&&)=default;
recursive& operator=(recursive const&)=default;
recursive& operator=(recursive &&)=default;
recursive() = delete;
template<typename L>
recursive( wrap, L&& f ):
base( std::forward<L>(f) )
{}
};
template<class T>using decay_t = typename std::decay<T>::type;
template<class R, class F>
recursive<R, decay_t<F>> recurse( F&& f ) { return recursive<R, decay_t<F>>(wrap{}, std::forward<F>(f)); }
Тогда немного другая реализация get_recursive_function (где я добавил состояние для развлечения):
std::function<void (int)> get_recursive_function(int amt) {
auto f =
[amt] (auto&& self, int count) {
std::cout << count << std::endl;
if (count > 0) {
self(count - amt);
}
};
return recurse<void>( std::move(f) );
};
int main() {
auto f = get_recursive_function(2);
f(10);
}
использование std::function в возвращаемом значении get_recursive_function необязательно - вы можете использовать auto в С ++ 1г. Все еще есть некоторые издержки по сравнению с идеальной версией (где лямбда может получить доступ к своей собственной operator()), поскольку operator() вероятно, не знает, что он вызывается рекурсивно на том же объекте, когда он вызывает self,
Было бы заманчиво позволить operator()( blah ) в теле лямбды, чтобы позволить рекурсивный вызов лямбды. Это, вероятно, сломало бы очень мало кода.
Мой текущий обходной путь, который, к сожалению, сложен:
#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();
}
}
Поскольку вы уже имеете дело с std::function что добавляет немного накладных расходов повсюду, вы можете добавить постоянство памяти, которое только добавит косвенность на вызывающем сайте с unique_ptr:
std::unique_ptr<std::function<void (int)>> CreateRecursiveFunction() {
auto result = std::make_unique<std::function<void (int)>>();
auto ptr = result.get();
*result = [ptr] (int recurse) { // c++1y can also capture a reference to the std::function directly [&func = *result]
std::cout << recurse << std::endl;
if (recurse > 0) {
(*ptr)(recurse - 1); // with c++1y func( recurse - 1 )
}
};
return result;
}