如何在 C++ 中制作基于 SFINAE 的 Y 组合器？

Question

我在考虑 C++14 的隐式模板，我正在尝试声明一个函数来匹配特定的参数类型（SFINAE 和 traits still 给我头痛）。我不确定如何解释我想要什么，但我正在尝试制作一个 Y combinator（只是为了看看它是否可能，而不是用于生产）。

我正在尝试声明一个函数：

template<typename T>
my_traits<T>::return_type Y(T t) {
  // ...
};

使得T是一个匹配

的函数（或函子）

std::function<R(F, Args...)>

// where F (and above return_type) will be
std::function<R(Args...)>

它可以接受任意数量的参数，但第一个应该是具有相同 return 类型和相同参数的函数（除了这个函数本身）。仿函数 operator () 的第一个参数是模板。

我想实现的用法：

auto fib = [](auto myself, int x) {
  if(x < 2)
    return 1;
  return myself(x - 1) + myself(x - 2);
};

// The returned type of fib should be assignable to std::function<int(int)>

我无法使用 T 类型的 return 类型（因为 operator () 过载）。我想做的是可能的吗？我怎样才能做到？

编辑：

从不同的角度看，我正在努力使这项工作：

struct my_functor {
  template<typename T>
  char operator () (T t, int x, float y) { /* ... */ };
};

template<typename T>
struct my_traits {
  typedef /* ... */ result_type;

  /* ... */
};

// I want this to be std::function<char(int, float)>, based on my_functor
using my_result =
my_traits<my_functor>::result_type;

Answer 1

这是一个非常 hacky 的方法，并且有严重的局限性，但这里是这样的：

首先，我们需要一个class假装支持所有可能的操作（尽可能），例如fake_anything class。请注意，这并不完美，因为至少 . 和 :: 将不起作用。要伪造一个仿函数，我们给它一个函数调用运算符：

template<class... Ts> fake_anything operator()(Ts&&...) const;

知道 lambda 只有一个 operator()，而 operator() 只有一个模板参数，我们可以用 decltype(&T::operator()<fake_anything>) 提取它的签名。为此，必须明确指定 lambda 的 return 类型；它不能使用推导，否则推导的 return 类型可能会发生冲突。

最后，我们可以使用标准偏特化方法获得 lambda 和 return 类型的其他参数：

template<class T>
struct extract_signature;

template<class T, class R, class FA, class...Args>
struct extract_signature<R (T::*)(FA, Args...)> {
    static_assert(std::is_same<fake_anything, std::decay_t<FA>>::value, "Unexpected signature");
    using type = std::function<R(Args...)>;
};

template<class T, class R, class FA, class...Args>
struct extract_signature<R (T::*)(FA, Args...) const> {
    static_assert(std::is_same<fake_anything, std::decay_t<FA>>::value, "Unexpected signature");
    using type = std::function<R(Args...)>;
};
// other cv- and ref-qualifier versions omitted - not relevant to lambdas
// we can also static_assert that none of Args is fake_anything, or reference to it, etc.

并添加一个别名模板来隐藏黑客的所有丑陋之处：

template<class T>
using signature_t = typename extract_signature<decltype(&T::template operator()<fake_anything>)>::type;

最后我们可以检查一下

static_assert(std::is_same<signature_t<decltype(fib)>,
                           std::function<int(int)>>::value, "Oops");

Demo.

局限性：

必须明确指定 operator() 的 return 类型。您不能使用自动 return 类型推导，除非所有 return 语句 return 都是相同的类型，而不管函子的 return 类型如何。
造假很不完美
这仅适用于特定形式的 operator()：template<class T> R operator()(T, argument-types...) 有或没有 const，其中第一个参数是 T 或对可能的 cv- 的引用合格 T.

Answer 2

在 C++14 return 中不可能按照 OP 的要求从 int(T, int) 中推导出 int(int)。

但是，我们可以使用以下方法屏蔽结果的第一个参数。 struct YCombinator 使用非递归函数对象成员实例化，其第一个参数是其自身没有第一个参数的版本。 YCombinator 提供了一个调用运算符，该运算符接收非递归函数的参数，然后 return 将其自身替换为第一个参数后成为其函数对象成员。这种技术允许程序员避免在递归函数定义中调用 myself(myself, ...) 的混乱。

template<typename Functor>
struct YCombinator
{
    Functor functor;

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

make_YCombinator 实用程序模板可简化使用模式。这会在 GCC 4.9.0.

中编译运行运行s

template<typename Functor>
decltype(auto) make_YCombinator(Functor f) { return YCombinator<Functor> { f }; }

int main()
{
    auto fib = make_YCombinator([](auto self, int n) -> int { return n < 2 ? 1 : self(n - 1) + self(n - 2); });

    for (int i = 0; i < 10 ; ++i)
        cout << "fib(" << i << ") = " << fib(i) << endl;

    return 0;
}

由于在定义递归函数时没有定义非递归函数，因此通常递归函数必须具有明确的return类型。

编辑：

但是，如果程序员在使用非递归函数。虽然上述构造需要显式 return 类型，但在以下 GCC 4.9.0 中推导 return 类型没有问题：

    auto fib = make_YCombinator([](auto self, int n) { if (n < 2) return 1; return self(n - 1) + self(n - 2); });

为了进一步确定这一点，这里引用了 C++14 标准草案中有关 return 类型推导的引述 [7.1.6.4.11]:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed. Once a return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements. [ Example:
auto n = n; // error, n’s type is unknown
auto f();
void g() { &f; } // error, f’s return type is unknown
auto sum(int i) {
if (i == 1)
    return i; // sum’s return type is int
else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}
—end example ]

如何在 C++ 中制作基于 SFINAE 的 Y 组合器？

How to make a SFINAE-based Y combinator in C++?

c++

templates

c++14

sfinae

typetraits