Re: [閒聊] Z-Combinator with C++0x lambda
: => 代換 fixedpoint-of-f 可得到 Y(f) = f(Y(f))
: 3. 若能有辦把上式轉換成「沒有 free variable」的形式 (也就是等號右邊
: 不能有 parameter 以外的 var) 則 Y 可稱為一個 combinator，
: 因為 Y(f) = f(Y(f)) 本身就有遞回效果 (可以一直代入)，
: 若可以轉換成 combinator 的 equivalent，則相當於你可以不在定義中
: 寫出自己的名字 (這是 combinator 的定義，再看一次：等號右邊不能有
: parameter 以外的 var)，也能造成遞迴的效果。
: 4. fixedpoint combinator 的組成法有無限多種，y-combinator 是最有名的一種
: z-combinator 是 y-combinator 的一種簡單的變型
看到 sunneo 兄的推文，重新翻了一下我寫的東西
發覺有些地方不太對，所以做了一點修正，另外也想想 sunneo 所講的
我沒寫過 CUDA，但查了以後大概知道 CUDA 從 C++ 中砍掉的部份是
1. no function pointer
2. no recursion
CUDA 雖然基本上支援 C++ object model，template 那些的，
不過 combinator 最基本的要求 "lambda" 也沒有。所以我本來想應該是沒辦法做
不過回頭想想，如果是要做到 recursive 的話，只要 fixedpoint combinator
中的一個 pattern 應該就可以了，而且既然有 Functor 的存在，
C++ 中的 lambda 和 functor 大致上也是都可以互換的 ...
雖然我不知道 CUDA 中能不能寫 mutual recursion，應該不會不行吧 XD：
int factorialB(int);
int factorialA(int n) {
if( n == 0 ) return 1;
return n*factorialB(n-1);
}
int factorialB(int n) {
if( n == 0 ) return 1;
return n*factorialA(n-1);
}
cout << factorialA (10) << endl; // 3628800
不過為了實驗精神我還是試圖保留部份的 z-combinator pattern，
然後用 Functor 去取代各種 lambda 的使用，為求簡化，把 template
與 <functional> 的使用也都拿掉，經過一段時間的 trial and error，
大概做出下面的片段
struct InnerLayer;
struct ActualFun;
struct Untype;
struct InnerLayer{
Untype* x_;
InnerLayer(Untype* x) : x_(x){}
int operator()(int n);
};
struct Factorial{ //the actual would-be recursive program
InnerLayer in_;
Factorial(InnerLayer in) : in_(in){}
int operator()(int n) {
if( n == 0 ) return 1;
return n*in_(n-1);
}
};
struct Untype{
Factorial operator()(Untype xprime) {
return Factorial(InnerLayer(&xprime));
}
};
int InnerLayer::operator()(int n) {
return (*x_)(*x_)(n);
}
cout << Untype()(Untype())(10) << endl; // 3628800
or..
cout << Factorial(InnerLayer(&Untype()))(10) << endl; // 3628800
這.. 自然是難看很多，而且 type 完全交叉鎖死，基本上我覺得是爛爆了 XD
想要寫另外一個 Fibonacci 要馬就全部 code 再另外貼一份，
要馬就要 template 化，一 template 化，交叉 dependency 就爆了，
雖然我記得有手動 template instantiation (export 都被砍了..)
的寫法，不過一來是我忘了怎麼寫，二來是這樣還是很麻煩 XD
大概在某個 unit 裡要這樣寫:
struct InnerLayer<Factorial>;
int InnerLayer<Factorial>::operator()(int n) {...
struct InnerLayer<Fibonacci>;
....之類的吧？
有錯請指正 <(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.72.57.78
※ 編輯: linjack 來自: 203.72.57.78 (03/25 17:28)
※ 編輯: linjack 來自: 203.72.57.78 (03/25 19:13)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：