[閒聊] Z-Combinator with C++0x lambda
http://herbsutter.wordpress.com/2010/03/13/
trip-report-march-2010-iso-c-standards-meeting/
前兩天看到草藥先生的 trip report，
慶祝一下 C++0x FCD 終於通過了，C++11 指日可待，
我把之前胡亂測試 C++0x lambda 的小程式貼出來給大家娛樂娛樂
那個時候正好看到 y-combinator 這東西，想試試 C++0x 的 lambda
可不可以寫類似的東西，所以就開始亂搞。
關於 y-combinator 可以搭配 wikipedia 上的文章看這篇非常詳細的教學:
http://mvanier.livejournal.com/2897.html
懶得看的人我盡量講簡短一點，希望不要有太大的錯誤 XDD
1. f(x) = x 的情況下我們稱 x 為 f 的 fixed-point
此時 f(f(f(f(f...(x)...))))) 也會等於 x (apply 無限次都不會變)
2. 若 Y(f) 可產生一個 f 的 fixed-point，我們稱 Y 為 fixed-point function
=> Y(f) = fixedpoint-of-f = f ( fixedpoint-of-f )
=> 代換 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 的一種簡單的變型
不過學理完全不懂的狀況下
搞了好久才知道 y-combinator 不用 lazy 的方法真的實作不出來，
所以去瞭解了一下 z-combinator 怎麼寫，大概就是 y-combinator
裡面再抽一層 lambda 吧，確實這樣用 eager/strict 的語言都可以實作了
#include <iostream>
#include <functional>
#define F std::function
template <typename R, typename... Args>
struct Untyped {
Untyped( F< F<R(Args...)>(Untyped<R, Args...>) > lamb )
:lamb_(lamb){}
F<R(Args...)> operator()(Untyped<R, Args...> xprime) const {
return lamb_(xprime);
}
F< F<R(Args...)>(Untyped<R, Args...>) > lamb_;
};
template <typename R, typename... Args>
F<R(Args...)> Z (F< F<R(Args...)> (F<R(Args...)>) > f) {
Untyped<R, Args...> temp(
[f](Untyped<R, Args...> x) -> F<R(Args...)> {
return f(
[x](Args... args) -> R {
return x(x)(args...);
}
);
});
return temp(temp);
}
使用到的 C++0x feature 主要是 variadic template 與，當然，lambda.
compiler 是用 g++ 4.5 (experimental)。
variadic template 的部份完全只是為了把 function signature 泛化，
最基本的 signature 寫 function<int(int)> 就夠了 ...
其中要做出 untyped 的主因是要處理掉 x(x)(args...) 那一段，
因為我想不到別的比較好看的方法可以避掉 compile-time recursive signature
e.g: x(x(x(x....(x))) .. 這樣最裡面的那個 (x)
與外面的其他所有 x 的 signature 一定會不一樣
補充：這邊好像講得不太清楚。compile-time recursive signature 的問題
只要把 Z 定義裡面我現在用到 Untype<R, Args...> 的地方
全部換成「理論上應該要可以用」的 std::function< R (Args...) >
就知道為什麼 x(x)(args...) 那邊一定寫不出來囉 ...
使用實例如：
int main()
{
F< F<int(int)>(F<int(int)>) > almost_factorial =
[](F<int(int)> f) -> F<int(int)> {
return [f](int n) -> int {
if( n == 0 ) return 1;
return n*f(n-1);
};
};
std::cout << Z(almost_factorial)(10) << std::endl;
F< F<int(int)> (F<int(int)>) > almost_fibonacci =
[](F<int(int)> f) -> F<int(int)> {
return [f](int n) -> int {
if( n == 0 ) return 0;
else if( n == 1 ) return 1;
else return f(n-1) + f(n-2);
};
};
std::cout << Z(almost_fibonacci)(10) << std::endl;
F< F<int(int, int)> (F<int(int, int)>) > almost_ackermann =
[](F<int(int, int)> f) -> F<int(int, int)> {
return [f](int m, int n) -> int {
if( m == 0 ) return n+1;
else if( m > 0 && n == 0 ) return f(m-1, 1);
else if( m > 0 && n > 0 ) return f(m-1, f(m, n-1));
};
};
//beware of the growth rate of ackermann function for m >= 4 !
std::cout << Z(almost_ackermann)(3, 3) << std::endl;
return 0;
}
照常去定義你平常會寫成 recursive 的 function，
但是裡面用一個 lambda 把它的 name 代換掉，
這樣定義裡面就沒有「明顯遞迴」存在
再補：
我寫出 almost_factorial，而 Z 吃了它之後，可產生 factorial，
所以 factorial 是 almost_factorial 的 fixed-point
其實我這樣是把推導順序倒過來講了，前面貼的那個 link 中，
一開始就在解釋為何把 almost_factorial 定義成 factorial 裡抽出一個 lambda
然後剛好 factorial 就會是這個 almost_factorial 的 fixed-point
有一串簡單的實例驗證
實用性？賣悶 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.72.57.78
※ 編輯: linjack 來自: 203.72.57.78 (03/19 12:30)
推
03/19 12:32, , 1F
03/19 12:32, 1F
※ 編輯: linjack 來自: 203.72.57.78 (03/19 12:55)
推
03/19 12:58, , 2F
03/19 12:58, 2F
→
03/19 13:00, , 3F
03/19 13:00, 3F
※ 編輯: linjack 來自: 203.72.57.78 (03/19 13:37)
※ 編輯: linjack 來自: 203.72.57.78 (03/19 14:01)
※ 編輯: linjack 來自: 203.72.57.78 (03/19 14:01)
※ 編輯: linjack 來自: 203.72.57.78 (03/19 14:02)
推
03/19 18:33, , 4F
03/19 18:33, 4F
推
03/22 20:58, , 5F
03/22 20:58, 5F
※ 編輯: linjack 來自: 203.72.57.78 (03/25 11:05)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：