6

最近，我阅读了Barry对这个问题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 表达式（例如，无需删除 a 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);
                 ^
  1. 案例#1 和案例#2 的结果有何不同？
  2. 为什么尾随返回类型会在案例 #2 和案例 #3 之间产生差异？

您可以在Wandbox上查看。

4

2 回答 2

4

不同之处在于，在 #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)）会破坏它，而更改#2 以将int lvalue 作为递归参数（例如g(++a)）将修复它。

这意味着初始调用的返回类型推导是自引用的，因为它取决于完全相同的调用的类型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 那样显式地提供返回类型意味着没有自引用类型推导，一切都很好。

您可能会问，既然递归案例仍然是自引用的（注意所有 3 个编译器都同意），为什么 #1 可以。这是因为一旦我们可以进入 lambda 自己的类型推导，[dcl.spec.auto]/10 就会启动，并且第一条return语句给 lambda 一个返回类型，所以当它递归调用时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
  }

一个修复（感谢@aschepler）是记住已经调用 lambda 的参数列表，并提供一个“干净的”包装器，其功能调用运算符尚未对每组新参数进行返回类型推导类型：

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>;
于 2020-06-02T22:29:17.630 回答
0

使用此代码：

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

所以可能编译器无法确定返回类型，但我不能告诉你在第一种情况下它如何推断它

于 2020-06-02T22:29:33.140 回答