Czy jest możliwe utworzenie prawdziwego typu funkcji w C++, który można samodzielnie wywołać?

Question

Próbuję napisać rekursję bez odwoływania się do nazwy funkcji w C++ za pomocą Y-combinator. Jednak nie mogę dowiedzieć się, rodzaj funkcji w następującej próbie:

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

Kompilator nie może wywnioskować co jest Function, nie może mnie. Potem próbowałem następujące:

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

ten, w porównaniu do powyższego przykładu, różnica jest taka, że ​​zmienił funkcję pracy w na żądanie obiektu, który Function jest wyprowadzona łatwo jak Factorial, co prowadzi do następnego pełnego wdrożenia syntezatora:

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

chodzi o to, że jest to możliwe do przerobienia struct Factorial do zwykłej funkcji?

Answer 1

Opisywany przypadek wygląda na typ nieskończony lub rekursywny. Możesz zobaczyć, że jest nieskończony, jeśli spróbujesz samodzielnie wydedukować typ, który prawdopodobnie sam odkryłeś. Aby pokazać, że chcę, aby uprościć funkcję factorial1 do:

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

a następnie spróbuj napisać tę funkcję z funkcją wskaźnika zamiast szablonów, aby ręcznie wydedukować jego typ.

Najpierw chcemy, aby foobar przyjęło wskaźnik funkcji jako argument.

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

Ale nadal nie jest to dokładnie to, czego chcemy, ten wskaźnik funkcji powinien przyjąć jako argument wskaźnik do samego siebie.

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

Ale znowu nie są zakończone, ponieważ musimy dodać wskaźnik do siebie jako argument ponownie

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

widać wzór, jak to idzie dalej.

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

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

przykłady dałeś, gdzie udało się to zrobić ze struktury, to po prostu coś, co naśladuje go przez operator(). Jeśli zmienić nazwę tej funkcji do foobar wygląda na to, że:

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

Więc w zasadzie nazwać foobar rekurencyjnie w foobar, co jest sprzeczne początkowej oświadczenie, że chcesz wywołać funkcję bez znajomości/przedstawieniu jej nazwę .

Answer 2

Nie można bezpośrednio przejść szablony, ale można użyć rodzajowego lambda na bieżąco, więc w końcu to będzie wyglądać użyć szablonu:

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

Ale uważam to hack od lambdas są nadal obiektami funkcyjnymi.

Answer 3

robisz to nieco źle: pierwszy argument factorial1 powinna być już stałym punktem factorial1 z typem unsigned long(*)(unsigned long), a nie sam factorial1, więc nie ma potrzeby, aby zapewnić self do niej jako argument:

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

C++ nie pozwala przejść zamknięcie jako wskaźnik do funkcji, więc musi:

• Przełęcz std::function lub jakiś inny wrapper jako self. Nie interesujące IMO.

• Użyj szablonu magii do wygenerowania funkcji punktu stałego w czasie kompilacji.

Druga opcja może być łatwo zrobić:

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

Teraz Fix<unsigned long, factorial1>::Function jest a fixed point of factorial1:

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

Zauważ, że ta implementacja Fix nadal odnosi się do siebie po imieniu, więc każdą realizację Kombinator stałopunktowy bez hacków typu systemowego.