Grand Central Dispatch のブロックでYコンビネータを書いてみた

id:amachang:20080124:1201199469
id:tanakh:20040813

はてなの先輩方に影響を受けて、Yコンビネータ書いてみた。

ブロック構文

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が計算されている。

まとめてみる

このYコンビネータには大いに無駄がある。ブロックを呼ぶたびに再帰の深さに比例してコピーが呼ばれるからだ。
また、Yコンビネータが自分に渡された引数と同じ引数で、また再帰しているのも無駄かな。

もっと効率のいい書き方はないのだろうか。