是否有可能在C++中使用可自行調用的實際函數類型？

Question

我想通過Y-combinator在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改寫到一個普通的功能？

Answer 1

你所描述的情況在我看來就像無限類型或遞歸類型。你可以看到，如果你嘗試自己手動推導出這種類型，那麼你自己也可能發現它是無限的。要說明的是，我希望簡化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遞歸，這與你最初的說法，要調用的函數不知道/引用它的名字。

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

但我會認爲這是因爲lambda表達式黑客攻擊仍然是函數對象。

Answer 3

你這樣做是不太正確：第一個參數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; 
} 

C++不允許傳遞閉包作爲一個函數指針，所以我們必須：

• 通行證std::function或某些其它包裝如self。 IMO並不感興趣。

• 使用模板魔法在編譯時生成定點函數。

第二個選項很容易做到：現在

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是a fixed point of factorial1：

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

注意，這Fix實施仍然指向自己的名字，於是將任何實現沒有類型系統攻擊的定點組合器。