Grand Central Dispatch のブロックでYコンビネータを書いてみた
id:amachang:20080124:1201199469
id:tanakh:20040813
ブロック構文
C にクロージャのようなものを追加する Grand Central Dispatch - blog.8-p.info
ブロックについてはこちらのページが参考になった。
ここが重要なことで、Block_copyを用いると、ブロックをクロージャのように扱えるようだ。
さっそく書いてみる
今回ブロック構文で書くのは次の形のYコンビネータ
y :: ((a -> a) -> (a -> a)) -> a -> a y f x = f (y f) x
#include <Block.h> // Block_copy, Block_releaseに必要 #include <stdio.h> typedef int (^int2int)(int); // Haskell風に書くと、Int -> Int typedef int2int (^Yfunc)(int2int); // (Int -> Int) -> (Int -> Int) int2int YCombinator(Yfunc f) { printf("Y copy\n"); return Block_copy(^(int x) { int2int y = YCombinator(f); int2int g = f(y); int val = g(x); Block_release(y); Block_release(g); printf("Y release\nF release\n"); return val; }); }
Yコンビネータの部分はこうなった。Block_copyでブロックをコピーすれば、どこからでもそのブロックを呼べるようになる。つまり、ブロックの中からブロックを作った関数のローカル変数を読み出せる。
ただ、ブロックが不要になったら手動で解放しないといけないらしい。Block.hに書いてあった。なので、Yコンビネータの中でもその作業をする必要がある。
こいつに渡すブロック、例えば階乗の場合は次のようになる。
Yfunc fact = ^(int2int f) { printf("F copy\n"); return Block_copy(^(int x) { return x < 2 ? 1 : x * f(x - 1); }); };
これはとても素直に書けた。
使ってみる
使う側もいつものYコンビネータのように呼ぶだけ。
int main(void) { int2int f = YCombinator(fact); printf("%d\n", f(3)); Block_release(f); return 0; }
そして出力はこう
Y copy Y copy F copy Y copy F copy Y copy F copy Y release F release Y release F release Y release F release 6
しっかり3! = 6が計算されている。