在C++中，是否可能创建一个真正的函数类型，并且该类型可以使用它本身进行调用？

Question

我正在尝试通过Y组合子在C++中编写递归而不引用函数名称。然而，我无法弄清楚以下尝试中函数的类型：

#include <iostream>

using std::cin;
using std::cout;

template<class Function> unsigned long factorial1(Function self, unsigned long n) {
    return n ? n * self(self, n - 1) : 1;
}

unsigned long factorial(unsigned long n) {
    return factorial1(factorial1, n);
}

int main() {
    unsigned long n;
    cin >> n;
    cout << factorial(n) << '\n';
    return 0;
}

编译器无法推断出什么是Function，我也不知道。然后我尝试了以下方法：

#include <iostream>

using std::cin;
using std::cout;

struct Factorial {
    template<class Function> unsigned long operator()(Function self, unsigned long n) const {
        return n ? n * self(self, n - 1) : 1;
    }
};

unsigned long factorial(unsigned long n) {
    return Factorial()(Factorial(), n);
}

int main() {
    unsigned long n;
    cin >> n;
    cout << factorial(n) << '\n';
    return 0;
}

相比上面的例子，不同之处在于我将工作函数更改为可调用对象，其中Function很容易被推导为Factorial，从而导致组合体的完整实现如下：

#include <iostream>

using std::cin;
using std::cout;

struct Factorial {
    template<class Function> unsigned long operator()(Function self, unsigned long n) const {
        return n ? n * self(self, n - 1) : 1;
    }
};

template<class Function> auto y(Function f) {
    return [f](auto n) {
        return f(f, n);
    };
}

int main() {
    unsigned long n;
    cin >> n;
    cout << y(Factorial())(n) << '\n';
    return 0;
}

问题是，是否可能将结构体Factorial重写为普通函数？

- Michael Tsang

---

看看你的第一个例子：为什么不想引用函数名？为什么factorial1是一个模板？如果不是factorial1，self可能是什么呢？ - Christian Hackl

Y组合子需要更强的类型系统（正如您自己发现的那样，模板提供了这种类型系统，也在这里见于Rosetta Code）_或者_它需要一个不存在的类型系统，就像（无类型的）lambda演算一样。因此，请尝试使用std :: uintptr_t，并在必要时进行转换...（顺便说一句：对此评论不做任何保证。） - davidbak

有人回答了我的与 Y Combinator 无关的问题：https://dev59.com/iVgQ5IYBdhLWcg3wazQi - NoSenseEtAl

Answer 1

您的操作略有不当：传递给factorial1函数的第一个参数应该是unsigned long(*)(unsigned long)类型的factorial1的固定点，而不是factorial1本身，因此不需要将self作为参数传递给它。请注意保留HTML标签。

unsigned long factorial1(unsigned long(*self)(unsigned long), unsigned long n) {
    return n ? n * self(n - 1) : 1;
}

C++不允许将闭包作为函数指针传递，所以我们必须采取以下措施之一：

• 将std::function或其他包装器作为self传递。在我看来不是很有趣。

• 使用模板魔法在编译时生成固定点函数。

第二个选项可以很容易地完成：

template<class X, X(*Fn)(X(*)(X), X)>
struct Fix {
    static X Function(X x) {
        return Fn(Fix<X, Fn>::Function, x);
    }
};

现在，Fix<unsigned long, factorial1>::Function是factorial1的不动点：

unsigned long factorial(unsigned long n) {
    return Fix<unsigned long, factorial1>::Function(n);
};

请注意，这个Fix实现仍然通过名称引用自身，因此任何没有类型系统黑客的固定点组合器的实现也会这样。

- user2512323

---

你可以移除 struct Fix，只留下 Function<X, Fn>：https://ideone.com/8DNbVm - Yankes

Answer 2

你不能直接传递模板，但是你可以使用泛型lambda表达式，这样最终看起来就像你使用了模板：

#define PASS_FUNC(name) [dummy=nullptr](auto&&... args){return name(decltype(args)(args)...);}

template<class Function> unsigned long factorial1(Function self, unsigned long n) {
    return n ? n * self(self, n - 1) : 1;
}

unsigned long factorial(unsigned long n) {
    return factorial1(PASS_FUNC(factorial1), n);
}

但我认为这是一种hack，因为lambda仍然是函数对象。

- xinaiz

Answer 3

你所描述的情况看起来像是无限类型或递归类型。如果你尝试手动推导类型，你会发现它是无限的，这可能也是你自己发现的。为了证明这一点，我想将你的factorial1函数简化为：

template <class T> void foobar(T self) {
    self(self);
}

然后尝试使用函数指针而不是模板来编写此函数，以手动推断其类型。

首先，我们希望foobar将函数指针作为参数。

void foobar(void (*self)());
            ^^^^^^^^^^^^^^

但这仍然不是我们想要的，这个函数指针应该以指向自身的指针作为参数。

void foobar(void (*self)(void (*)()));
                         ^^^^^^^^^^

但是我们还没有完成，因为我们需要再次将指向自身的指针作为参数添加进去。

void foobar(void (*self)(void (*)(void (*)())));
                                  ^^^^^^^^^^

你可以看到它如何不断地进行下去。

void foobar(void (*self)(void (*)(void (*)(void (*)()))));
                                           ^^^^^^^^^^

void foobar(void (*self)(void (*)(void (*)(void (*)(void (*)())))));
                                                    ^^^^^^^^^^

你提供的例子，通过结构体实现的方式只是通过operator()模拟而已。如果你将该函数的名称更改为foobar，它看起来像这样：

struct Factorial {
    template<class Function> unsigned long foobar(Function self, unsigned long n) const {
        return n ? n * self.foobar(self, n - 1) : 1;
    }
};

unsigned long factorial(unsigned long n) {
    return Factorial().foobar(Factorial(), n);
}

所以你基本上在foobar中递归调用foobar，这与你最初的说法相矛盾，即你想在不知道/引用其名称的情况下调用该函数。

- Alexander Stante

---

所以你基本上在foobar中递归调用foobar，这与您最初的声明相矛盾，即您想在不知道/引用其名称的情况下调用该函数。这正是固定点组合子（Y组合子）的全部内容，也是OP想要的。我知道这不是很直观。 - davidbak

我只是在说严格来说第二个例子并不是一个 Y 组合子，而只是一个被 operator() 重载所伪装的一般递归。 - Alexander Stante