return递归函数的类型推导

Question

最近，我读了 Barry's answer to this question Recursive lambda functions in C++11:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};
// deduction guide
template <class F> y_combinator(F) -> y_combinator<F>;

基本上，y_combinator 允许人们更轻松地编写递归 lambda 表达式（例如，无需 delcare std::function）。在玩y_combinator的时候，我发现了一些奇怪的东西：

int main() {
   // Case #1 compiles fine
   y_combinator{[](auto g, int a, int b) {
      if (a >= b) return 0;
      return 1 + g(a + 1, b);
    }}(1, 2);

    // Case #2 deos not compile
    y_combinator{[](auto g, int a) {
      if (a >= 0) return 0;
      return 1 + g(a + 1);
    }}(1);

    // Case #3 compiles just fine
    y_combinator{[](auto g, int a)->int {
      if (a >= 0) return 0;
      return 1 + g(a + 1);
    }}(1);
}

案例 #1 和案例 #3 编译正常，而案例 #2 无法编译。我在 Clang 10.0 和 GCC 9.3 上得到了相同的结果。对于案例 #2，Clang 说

prog.cc:25:18: error: no matching function for call to object of type 'std::__1::reference_wrapper<const y_combinator<(lambda at prog.cc:23:18)> >'
      return 1 + g(a + 1);
                 ^

Case #1 和 Case #2 的结果有何不同？
为什么尾随 return 类型会导致案例 #2 和案例 #3 有所不同？

你可以在Wandbox上查看。

Answer 1

不同之处在于，在#1 中，对 y_combinator 的初始调用和递归调用具有不同的参数类型，而在#2 中，它们具有相同的参数类型（包括值类别）。

在#1 中，初始参数 (1, 2) 都是 int prvalue，而递归参数 g(a + 1, b) 分别是 int prvalue 和 int lvalue。同时在#2 中初始参数 (1) 和递归参数 g(a + 1) 都是 int prvalue。您可以检查是否对 #1 进行更改，使两个递归参数都是 int prvalue（例如调用 g(a + 1, b + 0)）将 break it, while changing #2 to pass int lvalue as the recursive argument (e.g. g(++a)) will fix 它。

这意味着初始调用的return类型推导是自引用的，因为它完全取决于的类型 对 y_combinator<lambda #2>::operator()<int>(int&&) 的相同调用（而在 #1 中，对 y_combinator<lambda #1>::operator()<int, int>(int&&, int&&) 的初始调用取决于 y_combinator<lambda #1>::operator()<int, int&>(int&&, int&)）。

像#3 那样显式提供 return 类型意味着没有自引用类型推导，一切都很好。

您可能会问，既然递归情况仍然是自引用的（请注意所有 3 个编译器都同意），为什么 #1 可以。这是因为一旦我们可以进入 lambda 自己的类型推导，[dcl.spec.auto]/10 就会启动并且第一个 return 语句为 lambda 提供 return 类型，因此当它递归调用 g, 类型推导已经成功

图表通常有帮助：

y_combinator<lambda #1>::operator()<int, int> -> forwards to [lambda #1]::operator()<y_combinator<lambda #1>> { has return type int by [dcl.spec.auto]/10 calls y_combinator<lambda #1>::operator()<int, int&> (not previously seen) -> forwards to [lambda #1]::operator()<y_combinator<lambda #1>> -> already deduced to return int -> this is OK } y_combinator<lambda #2>::operator()<int> -> forwards to [lambda #2]::operator()<y_combinator<lambda #2>> { has return type int by [dcl.spec.auto]/10 calls y_combinator<lambda #2>::operator()<int> but y_combinator<lambda #2>::operator()<int> has incomplete return type at this point -> error }

A fix（感谢@aschepler）是为了记住已经调用 lambda 的参数列表，并提供一个 "clean" 包装器，其功能调用运算符不是还对每组新的参数类型进行 return 类型推导：

template<class...> struct typelist {}; template<class T, class... Ts> constexpr bool any_same = (std::is_same_v<T, Ts> || ...); template <class F> struct y_combinator { template <class... TLs> struct ref { y_combinator& self; template <class... Args> decltype(auto) operator()(Args&&... args) const { using G = std::conditional_t< any_same<typelist<Args...>, TLs...>, ref<TLs...>, ref<TLs..., typelist<Args...>>>; return self.f(G{self}, std::forward<Args>(args)...); } }; F f; template <class... Args> decltype(auto) operator()(Args&&... args) { return ref<>{*this}(std::forward<Args>(args)...); } }; template <class F> y_combinator(F) -> y_combinator<F>;

Answer 2

使用此代码：

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(*this, std::forward<Args>(args)...);
    }
};

没有 std::ref（我相信这是为了提高效率，因为你不会一遍又一遍地复制对象）错误更改为

prog.cc:23:18: error: function 'operator()<int>' with deduced return type cannot be used before it is defined

所以编译器可能无法识别 return 类型，但我不能告诉你在第一种情况下它是如何推断出来的

return递归函数的类型推导

return type deduction of recursive function

c++

template-argument-deduction

generic-lambda

c++17