Blocksで不動点関数(Re: リークしない再帰blocksの書き方)
お題:
Sometimes, you want a block to be able to call itself. That means it needs a reference to itself. And that means you have a wonderful opportunity to create a strong reference cycle that will endure till the end of time, or at least till your app exits.
Leak-Free Recursive Blocks - Jeremy W. Sherman
(via: 「リークしない再帰blocksの書き方 | Cocoaの日々情報局」)
Blocksを再帰的に呼び出す際に変数を経由すると、参照サイクルが出来てメモリリークの元になるらしい。経由する変数を弱参照(__weak __block)にすることでリークを避けるというのが一般的なテクニックのようだ。
変数を参照するから参照カウントが問題になるんなら、変数に代入しないで再帰呼び出しすれば良いと思ったのでやってみた。今回の解決策はあんまり実用的じゃないかもしれないけど、こんな方法もあるよということで。
あ、環境がいまだに Lion(10.7.5) + Xcode Version 4.3.3なのでバージョンとかによってはうまくいかないかも。
例題: 階乗計算
普通の関数で再帰を使って階乗計算するプログラムを書くと次のようになる。
long factorial(long n) { if (n == 0) return 1; return n * factorial(n - 1); }
10! = 10 * 9! = 10 * (9 * 8!) = ...という計算を、factorialの中からfactorialを再帰的に呼び出すことで実現している。
これをBlocksで書きたい場合……
long (^factorial)(long) = ^long(long n) { if (n == 0) return 1; return n * factorial(n - 1); // ここではまだfactorialは初期化されていない };
これを"factorial"という関数名を参照することなく書くにはどうしたら良いだろう。
不動点関数を使う
「メモ化(memoization), 再帰関数定義関数, 最小不動点」を参考に、不動点関数fixを真似して書いてみる。fix自体は普通の関数で書くよ。
// 引数がlong一つで戻り値もlongのBlocks typedef long (^simple_block)(long); // simple_blockを受け取りsimple_blockを返すBlocks typedef simple_block (^simple_block_maker)(simple_block); // 不動点関数: simple_block_makerを受け取りsimple_blockを返す simple_block fix(simple_block_maker maker) { return maker(^(long n) { return fix(maker)(n); }); }
分かりやすいようにtypedefしたけど、無くても書けなくもない。
で、使う側はこうなる。
simple_block factorial = fix(^simple_block(simple_block next) { return ^long(long n) { if (n == 0) return 1; return n * next(n - 1); }; }); NSLog(@"10! = %ld", factorial(10));
fixに対して、「Blocksを渡されるとBlocksを生成して返すBlocks」を渡してやる。fix内では、この「Blocks生成器」を引き回しながら、必要な分だけ順次Blocksを生成して呼び出すことで、再帰的な呼び出しを実現している。参照という意味ではサイクルじゃなくて線形になっているので参照サイクルがおこらない(たぶん。) これでメモリリークしないはず(たぶん。)
不動点関数もBlocksで書く
fixは普通の関数だから自分自身を参照しても問題ない、というのはなんかちょっとずるい(反則？)感じもするので、fixもBlocksで書いてみる。
前にJavaで書いたときに型を調べたので、それにあわせてtypedefするよ。(Javaのに合わせてちょっと名前変えた。)
// 引数がlong一つで戻り値もlongのBlocks typedef long (^func)(long); // funcを受け取りfuncを返すBlocks typedef func (^func_factory)(func); // func_makerを受け取りfuncを返すBlocks // typedef func (^func_maker)(func_maker); // こう書きたいけど…… typedef func (^func_maker)(id); // idでごまかす
typedefで自分自身を引数に取る関数は普通には定義出来ない*1ので、一旦idで置いて使う時にキャストするようにする。
これを使ってfixを書き直すと、次のようになる。
func (^fix)(func_factory) = ^func(func_factory factory) {
return ^func(id maker) {
return factory(^long(long n){
return ((func_maker) maker)(maker)(n);
});
}(^func(id maker) {
return factory(^long(long n){
return ((func_maker) maker)(maker)(n);
});
});
};
いわゆるYコンビネータってヤツですナ。Yコンビネータについては「Y コンビネータって何？ - IT戦記」とかを参照すると良いかも。
id型で受け取ったmakerは呼び出しの際にfunc_makerにキャストしてる。まあちょっと苦しいけど……。
呼び出す側は、型の名前を変えた以外は同じ。
func factorial = fix(^func(func next) { return ^long(long n) { if (n == 0) return 1; return n * next(n - 1); }; }); NSLog(@"%ld", factorial(10));
一回しか使わないなら、Blocksを変数に入れる必要も無い。
long ret = ^func(func_factory factory) { return ^func(id maker) { return factory(^long(long n){ return ((func_maker) maker)(maker)(n); }); }(^func(id maker) { return factory(^long(long n){ return ((func_maker) maker)(maker)(n); }); }); }(^(long (^next)(long)) { return ^long(long n) { if (n == 0) return 1; return n * next(n - 1); }; })(10); NSLog(@"%ld", ret);
他の型のBlocksにも使えるようにする
longを受け取ってlongを返すもの専用だと汎用性が低いので、long以外を受け取ったり、複数の引数を使ったり出来るようにしたい。
とりあえず、typedefしてる部分を展開してみる。
long (^(^fix)(long (^(^)(long (^)(long)))(long)))(long) = ^(long(^(^f)(long(^)(long)))(long)) { return ^(id g) { return f(^(long m){ return ((long(^(^)(id))(long)) g)(g)(m); }); }(^(id g) { return f(^(long m){ return ((long(^(^)(id))(long)) g)(g)(m); }); }); };
比較しやすいように参考サイトの表記に合わせて、func_factoryだったところを「f」に、func_makerだったところを「g」にしたよ。若干楽しそう(^(^)
コード内に、戻り値の型、引数の型、仮引数の宣言、呼び出し時の引数が含まれているので、その辺を取り替えられるようにしたい。思い切ってマクロにしてみる。えい！
#define FIX(RET_TYPE, PARAM_TYPES, FORMAL_PARAMS, CALL_PARAMS) \ (^(RET_TYPE(^(^f)(RET_TYPE(^)PARAM_TYPES))PARAM_TYPES) { \ return ^(id g) { \ return f(^FORMAL_PARAMS{ \ return ((RET_TYPE(^(^)(id))PARAM_TYPES) g)(g)CALL_PARAMS; \ }); \ }(^(id g) { \ return f(^FORMAL_PARAMS{ \ return ((RET_TYPE(^(^)(id))PARAM_TYPES) g)(g)CALL_PARAMS; \ }); \ }); \ }) // 階乗 long (^factorial)(long) = FIX(long, (long), (long m), (m)) (^(long (^next)(long)) { return ^long(long n) { if (n == 0) return 1; return n * next(n - 1); }; }); NSLog(@"10! = %ld", factorial(10)); // 3628800 // 互除法 int (^gcd)(int,int) = FIX(int, (int, int), (int m, int n), (m, n)) (^(int (^next)(int, int)) { return ^int(int m, int n) { if (n == 0) return m; return next(n, m % n); }; }); NSLog(@"gcd(246, 654) = %d", gcd(246, 654)); // 6
*1:structを経由するテクニックがあるっぽいけど、Blocksだとちょっと面倒くさい
