递归函数的返回类型推导 [英] return type deduction of recursive function

问题描述

最近，我阅读了 Barry对这个问题的回答 基本上，y_combinator允许人们更轻松地编写递归lambda表达式(例如，无需delcare std::function).当我玩y_combinator时，发现了一些奇怪的东西:

Basically, y_combinator allows one to write a recursive lambda expression more easily (e.g. without having to delcare a std::function). When I played with y_combinator, I found something strange:

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说

Case #1 and Case #3 compile fine while Case #2 does not compile. I got the same result with Clang 10.0 and GCC 9.3. For Case #2, Clang says

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. 为什么尾随返回类型在Case#2和Case#3之间有区别?

您可以在 Wandbox 上进行检查.

推荐答案

区别在于，在#1中，对y_combinator的初始和递归调用具有不同的参数类型，而在#2中，它们具有相同的参数类型(包括值类别).

The difference is that in #1 the initial and recursive calls to y_combinator have different argument types, whereas in #2 they have the same argument types (including value category).

在#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左值作为递归参数(例如g(++a))将修复它.

In #1, the initial arguments (1, 2) are both int prvalue, whereas the recursive arguments g(a + 1, b) are respectively int prvalue and int lvalue. Meanwhile in #2 the initial argument (1) and recursive argument g(a + 1) are both int prvalue. You can check that making a change to #1 such that both recursive arguments are int prvalue (e.g. calling g(a + 1, b + 0)) will break it, while changing #2 to pass int lvalue as the recursive argument (e.g. g(++a)) will fix it.

这意味着首次调用的返回类型推导 是自引用的，因为它取决于精确地的类型，与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&)).

This means that the return type deduction for the initial call is self-referential, in that it depends on the type of precisely the same call to y_combinator<lambda #2>::operator()<int>(int&&) (whereas in #1 the initial call to y_combinator<lambda #1>::operator()<int, int>(int&&, int&&) depends on y_combinator<lambda #1>::operator()<int, int&>(int&&, int&)).

像#3一样显式地提供返回类型意味着没有自引用类型推导，一切都很好.

Supplying the return type explicitly as in #3 means there is no self-referential type deduction, and everything is fine.

您可能会问，鉴于 recursive 情况仍然是自引用的(请注意所有3个编译器都同意)，为什么#1可以通过.这是因为一旦我们能够进入lambda自己的类型推导， [dcl.spec.auto]/10 启动，第一个return语句为lambda提供返回类型，因此当它递归调用g时，该类型推导已经成功.

You might ask, why is #1 OK given that the recursive case is still self-referential (noting that all 3 compilers agree). This is because once we can get into the lambda's own type deduction, [dcl.spec.auto]/10 kicks in and the first return statement gives a return type to the lambda, so when it recursively calls g, that type deduction has already succeeded.

图表通常可以帮助:

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已经被已经调用过，并提供一个干净的"包装器，该包装器的函数调用运算符尚未针对每个新的参数类型集进行返回类型推导:

A fix (thanks to @aschepler) is to remember the argument lists that the lambda has been called with already, and provide a "clean" wrapper whose functional call operator(s) are not yet undergoing return type deduction for each new set of argument types:

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>;

这篇关于递归函数的返回类型推导的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！