Можно ли создать реальный тип функции в С++, который можно вызывать с собой?

Я пытаюсь написать рекурсию без ссылки на имя функции в С++ с помощью Y-combinator. Однако я не могу определить тип функции в следующей попытке:

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

Вопрос в том, можно ли переписать struct Factorial на обычную функцию?

Ответ 1

Вы делаете это немного неправильно: первый аргумент factorial1 должен быть уже неподвижной точкой factorial1 с типом unsigned long(*)(unsigned long), а не с factorial1, поэтому нет необходимости предоставлять self для него в качестве аргумента:

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

С++ не позволяет пропускать замыкание как указатель на функцию, поэтому мы должны либо:

Передать 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 по-прежнему относится к себе по имени, поэтому любая реализация комбинатора с фиксированной запятой без хакеров системы типов.

Ответ 2

Вы не можете передавать шаблоны напрямую, но вы можете использовать общий лямбда на лету, поэтому в конце он будет выглядеть так, как вы используете шаблон:

#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);
}

Но я бы подумал, что это хак, поскольку lambdas все еще являются объектами функции.

Ответ 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, что противоречит вашему первоначальному утверждению, которое вы хотите вызвать, не зная/ссылаясь на его имя.