Is it possible to make a real function type in C++ which is callable with itself?

Question

I am trying to write recursion without referencing the function name in C++ by means of Y-combinator. However, I can't figure out the type of the Function in the following attempt:

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

The compiler cannot deduce what is Function, neither can me. Then I tried the following:

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

This, when compared to the above example, the difference is I changed the work function to a callable object, which Function is deduced easily as Factorial, leading to the following complete implementation of the combinator:

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

The question is that, is it possible to rewrite the struct Factorial to a plain function?

Answer 1

You are doing it slightly wrong: first argument to factorial1 should be already fixed point of the factorial1 with the type unsigned long(*)(unsigned long), not the factorial1 itself, so no need to provide self to it as an argument:

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

C++ doesn't allow to pass a closure as a function pointer, so we must either:

• Pass std::function or some other wrapper as self. Not interesting IMO.

• Use template magic to generate fixed point function at compile time.

Second option can be done easily:

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

Now, Fix<unsigned long, factorial1>::Function is a fixed point of factorial1:

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

Note that this Fix implementation still refers to itself by name, so will any implementation of fixed point combinator without type system hacks.

Answer 2

You can't pass templates directly, but you could use generic lambda on fly, so in the end it would look like you use the template:

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

But I would consider this a hack since lambdas are still function objects.

Answer 3

The case you are describing looks to me as something like an infinite type or recursive type. You can see that it is infinite if you try to deduce the type manually by yourself, which you probably discovered by yourself as well. To show that, I want to simplify your factorial1 function into:

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

and then try to write this function with function pointer instead of templates, to manually deduce its type.

First, we want that foobar takes a function pointer as argument.

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

But that's still not exactly what we want, this function pointer should take as an argument a pointer to itself.

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

But again we are not finished, because we have to add a pointer to itself as an argument again

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

You can see the pattern how it goes on and on.

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

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

The examples you gave, where you managed to do that with a struct, is just something that mimics it through operator(). If you change the name of that function to foobar it looks like that:

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

So you basically call foobar recursively in foobar, which contradicts your initial statement, that you want to call the function without knowing / referencing its name.