Требуется простой и прозрачный механизм рекурсивного вызова лямбда-функций

Vyacheslav Meshkov
Vyacheslav Meshkov

В обычной функции можно без лишних усилий написать рекурсивный вызов void f() { f(); }, чего не скажешь о лямбдах, хотя по сути то ничто мешать не должно. В функциональных языка программирования такой проблемы же нет.

[...](...){ how_to_call_self_?(...); }

Как некий компромисный вариант можно предложить auto func = [](){ func(); }. Сейчас так нельзя. Но я уверен, что можно придумать лучше.

9
рейтинг
12 комментариев
languagelawyer

http://wg21.link/p0200

languagelawyer
Vyacheslav Meshkov

Синтаксис ещё страшнее, чем я написал. Хотелось бы как раз простоты и прозрачности, а не ещё одного std::do_pretty_thing

Vyacheslav Meshkov
Antervis

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

[](Integral x) {
    return x > 1
        ? this_lambda(x)  // Ошибка: тип лямбды еще не выведен
        : 1;
}();

Заодно надо покрыть случай когда у лямбды на каждое использование разные сигнатуры (разворачивание variadic pack, например). В общем, эта задача чуть сложнее, чем "просто добавить this для лямбды"

Antervis
Vyacheslav Meshkov

Antervis, Всё понимаю. Но с одной стороны активно форсят функциональщину в плюсы, с другой бегают по граблям, которых в этой самой функциональщине нет.

ИМХО, если что-то в функциональных ЯП пишется красиво и кратко, а в плюсы протолкнули с тоннами оборачивающего кода, я считаю в данном случае цель не достигнута. Ведь ФЯП в частности ценят за их лаконичность в передаче весьма сложных идиом.

Если так всё плохо с возвращаемым типом, можно разрешить рекурсивный вызов при указании этого типа [](...)->result_t{...}. Для обычных же функций такой проблемы нет. ИМХО именно автовыведение типа надо понизить в приоритетах, и делать только тогда, когда это возможно. А если оно мешает, то запрещать автовыведение типа в пользу более приоритетного функционала.

Vyacheslav Meshkov
Обновлено 
Antervis

Vyacheslav Meshkov,
Для обычных же функций такой проблемы нет.

у обычных функций тип полностью известен.

> ИМХО именно автовыведение типа надо понизить в приоритетах, и делать только тогда, когда это возможно

выводить тип необходимо в любом случае, с++ всё-таки язык со статической типизацией

Antervis
Комментарий удален
Vyacheslav Meshkov

languagelawyer, Вам сколько лет? И какой у вас опыт в плюсах? Зачем вы постите сюда детские сайты?

Vyacheslav Meshkov
Обновлено 
al-mission-2016

Синтаксически, изящно было бы так:
    [](..)
    или
    operator()(..) // т.к. лямбда - это объект сгенерерованного класса у которого определён operator()

Например
    cout <<
        []( int n ) -> int {
            return ( n < 2 )
                ?   1
                :   []( n - 1 ) * n  // <- NB [](...). Пока невозможно :(
                ;
        } (5)
        << endl;

Вопрос обсуждался здесь (эта ссылка уже была выше)
proposal 2016-p0200
и здесь
stackoverflow.com - "can lambda-functions be recursive"

Jason Turner в недавнем C++ Weekly - Ep 162 - Recursive Lambdas
тоже про рекурсивные лямбды через введение именованной лямбды (и возможно внешней обёртки) в таком ключе:

constexpr auto fib = []( const int n ) {
    constexpr auto f_ = []( const auto f_, const int n ) -> int {
        return
            (n > 1)
            ? f_(f_, n - 1) + f_(f_, n - 2)
            : 1;
    };
    return f_(f_, n);
};

auto main() -> int
{
    std::cout << "Hello, C++" << (__cplusplus / 100) << '\n'; // Expected C++17+

    const int n = 4;
    const auto f = fib(n);

    std::cout << "fib(" << n << ") = " << f << '\n';

    return f;
}

К сожалению C++ и вправду пока не имеет средств, позволяющих использовать
безымянные рекурсивные лямбды. Например в качестве функторов.

al-mission-2016
al-mission-2016

Уточнение.
Безымянные рекурсивные лямбды всё же возможны - технология
"лямбда в лямбде" :) Правда вряд ли она простая и прозрачная :).
Идея в том, чтобы внутри внешней безымянной лямбды (напр. функтора) создать
внутреннюю "именованную" лямбду, коротая уже может ссылаться на себя при рекурсии.
При этом имя внутренней лямбды наружу естественно не вытекает.

// g++-8 -std=c++17 ./lambda_in_lambda.cpp
static_assert(__cplusplus > 201700, "C++17 required!");

#include <numeric>
#include <iostream>

auto main() -> int {
    using std::cout, std::endl, std::accumulate, std::begin, std::end;

    // Calculate sum of factorials of numbers in arr.
    constexpr int arr[] { 1, 2, 3, 4 }; // 1! + 2! + 3! + 4! == 33
    const auto sum =
        accumulate( begin(arr), end(arr), 0,
            [](auto init, auto n) {
                auto fac_ = [] ( auto fac_, auto x ) -> int {
                    return (x > 1) ? x * fac_(fac_, x - 1) : 1;
                };
                return init + fac_(fac_, n);
            } );

    cout << sum << endl;

    return sum;
}

al-mission-2016
Vyacheslav Meshkov

Если уж говорить о чистой красоте и изящности, то взять по аналогии с функциями чтобы работало:

auto fact = [](std::size_t const val)->int {
    return val ? val*fact(val-1) : 1;
}{3};

Vyacheslav Meshkov
Обновлено 
languagelawyer

В C++17 с можно покрасивее оформить http://wg21.link/p0200:

#include <functional>
#include <utility>

template<class F>
struct letrec : F {
	letrec(const F& f) : F(f) {}
	letrec(F&& f) : F(std::move(f)) {}

	template<class... Args>
	decltype(auto) operator()(Args&&... args) {
		return F::operator()(std::ref(*this), std::forward<Args>(args)...);
	}
};

letrec fact = [](auto self, int i) -> int {
	return i <= 0 ? 1 : i * self(i - 1);
};
languagelawyer
Обновлено 
Vyacheslav Meshkov

languagelawyer, Финал выглядит вполне себе прилично. Но поправьте меня, если я понимаю неправильно: эта красота достаётся ценой +1 параметра в стек на каждый вызов рекурсивной функции.

Vyacheslav Meshkov
Обновлено 
languagelawyer

Зависит от ABI. Кроме 32-битных интелов немного где все аргументы передаются через стек. 2-4 первых аргумента в регистрах передаются.

Но да, способ не без оверхеда.

languagelawyer
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения