// g++ -std=c++23 Ycomb.cpp -o main && ./main #include #include #include //Y = λf. (λx. f (x x)) (λx. f (x x)) //Y = lambda f. (lambda x. f (x x)) (lambda x. f (x x)) // Alapból a sima C++-ra fordítás esélytelen az auto return type miatt, ami a fontos egymás megjelenés miatt kiértékelhetetlen. template struct SelfApp { std::function(SelfApp)> f; //Nem kell tudni az egész layoutját, mert a std::function type töröl }; // Y :: (Args->T -> Args->T) -> (Args->T) template [[nodiscard]] constexpr decltype(auto) Y(/*std::function(std::function)>*/F f) noexcept { //Template deduction nem megy ha T és Args... van int helyett így kell annak is egy generika //A move miatt nem lesz copy SelfApp g{ [f = std::move(f)](SelfApp x) -> std::function { // majd n parammal kiértékelhető lesz return f(std::function([x](Args... n) { return x.f(x)(std::forward(n)...); })); } }; return g.f(g); //g.f(g) = f( λn. g.f(g)(n) ) //f(g.f(g)) esetén eager evaluation lenne ami azt jelenti, hogy infinite loopba a c++ kiértékelője a g.f(g)-t próbálná kiértékelni. } //Constexpr lehet, hogy nem csinál semmit, mert a std::function-nél itt kell dynamic memória allokáció a type erasure miatt int main() { std::function factorial = Y( [](std::function self) { return std::function([self = std::move(self)](int n) { return n <= 1 ? 1 : n * self(n - 1); }); } ); for (int n = 0; n <= 10; ++n) { std::cout << n << "! = " << factorial(n) << "\n"; } } //Ezzel is próbálkoztam és ez lenne a Y combinator igazi idiomatikus verziója de itt a decltype(f(x(x))) egy végtelenen rekurzív típus kéne, hogy legyen és egy idő után hibára fut, hamarabbi hibára futást a -ftemplate-depth=50 flaggel lehet kikényszeríteni. /* auto Y = [](auto f) { auto g = [=](auto x) -> decltype(f(x(x))) { return f(x(x)); }; return g(g); }; */