[717] Re:イテレータ(とCPS)
投稿者：(ぱ)
2007/02/20 02:13:25
土曜はとあるイベントにて大阪で飲んだくれておりまして、ずいぶん返事が遅くなりまして
すみません。
それプラス、私自身、クロージャに慣れておらず継続もわかっておらず、今回のNykRさんの
サンプルはずいぶん荷が重いものでした。とはいえ放り出していては勉強にならんので、
私なりに解釈してみました。間違い等ありましたらご指摘ください。
さて、単に木をイテレートするだけなら、
tree.each(closure(item) {
# このitemについてなんかする
});
という形のeachメソッドをツリーに装備するのは簡単で、ツリーの中で再帰して、
要素ごとに、渡されたクロージャを呼び出せばよいのですが、こういう形式(内部イテレータ)
だと、あるツリーについて、「ここまで走査した」という状態を保存しておけないのが
問題になるわけですよね。その点、NykRさんの提示されたイテレータでは、こういう
書き方も許される。
# ふたつのイテレータでツリーを並列に走査する。
for (ite1 = iterator_GoF(foreachTree_CPS(tr)),
ite2 = iterator_GoF(foreachTree_CPS(tr));
!ite1.isDone() && !ite2.isDone();
ite1.next(), ite2.next()) {
print(" " + ite1.currentItem());
print(" " + ite2.currentItem());
}
これができるのが外部イテレータの強みです。
Cなどで、再帰を使ってツリーを辿る場合、「ここまで走査した」という情報がスタック上に
ありますから、スタックが1本しかない以上、ふたつのイテレータを並行して使うことは
できないわけです(片方が片方の繰り返しに完全に含まれるなら可能)。
tr = {13,{5,{3,{},{}},{13,{12,{},{}},{}}},{16,{16,{15,{},{}},{}},{17,{},{}}}};
この例では、nodeの[0]にそのノードの値が、[1]に左の子が、[2]に右の子が
入っていますから、再帰で間順で走査するなら以下のようになります。
function internalIterate(node) {
if (node.size() == 0) {
} else {
internalIterate(node[1]); # ...(a)
print(" " + node[0]); # とりあえず表示しておく
internalIterate(node[2]);
}
}
(a)の箇所で左の子について再帰呼び出しを行い、それが戻ってきてから続きの処理を
やっています。「戻ってきてから続きの処理をやる」ことができるのが再帰の嬉しい
ところですが、それを期待していては、外部イテレータは作れない。
そこで、「戻ってきてから続きの処理をする」のではなく、「戻ってきてから
やってほしい続きの処理をクロージャとして渡す」とすれば、関数から戻ってこなくても
よくなる。その変換をしたのがこれ。
function internalIterate(node, cont) {
if (node.size() == 0) {
cont();
} else {
internalIterate(node[1],
closure () { # 続きをクロージャで渡す。
print(" " + node[0]);
internalIterate(node[2], cont);
});
}
}
# 第2引数には「処理の続きを渡す」のだから、最後に「おしまい」と表示される。
internalIterate(tr, closure() {print("おしまい");});
さて、この状態では、要素ごとに行う処理がprint()に固定されていますから
汎用性がありません。では引数でなにか関数を渡せば、とこうしても、
internalIterate(node[1],
closure () { # 続きをクロージャで渡す。
proc(node[0]); # 処理を引数procで渡す
internalIterate(node[2], cont);
});
これでは内部イテレータと同じですから意味がありません。
そこで、このproc()にも、続きの処理をクロージャで渡してやることにします。
function foreachTree_CPS(proc) {
return closure internalIterate(node, cont) {
if (node.size() == 0) {
cont();
} else {
internalIterate(node[1],
closure () {
proc(node[0],
closure() {
internalIterate(node[2], cont);
});
});
}
};
}
外部イテレータの場合、このprocの第2引数をnext()の際に呼び出せばよいわけですね。
なぜならそれが「処理の続き」だから。
イテレータはこうなります。
function iterator_GoF(foreach_CPS, collection) {
this = new_object();
this.first = closure () {
this.isDone = closure () { return false; };
foreach_CPS(closure (item, cont) {
this.currentItem = closure () { return item; };
this.next = closure () { cont(); };
})(collection, closure(){ # ..(b)
this.isDone = closure () { return true; };
});
};
this.first();
return this;
}
イテレータのfirst()が呼び出されたときに、foreach_CPS()を呼び出して、
internalIetrate()を取得し、それに対しcollectionとクロージャを渡しています(b)。
これがつまり元のソースの
internalIterate(tr, closure() {print("おしまい");});
に相当するわけですが、「おしまい」と表示する代わりに、isDoneについて、
trueを返すよう関数を差し替えています。
んで、internalIterate()に渡しているproc()では、
this.currentItem = closure () { return item; };
this.next = closure () { cont(); };
currentItemを設定後、nextに対し、contすなわち「処理の続き」をセットしています。
これで、次に利用者がnext()を呼び出したとき、internalIteratorの続きが実行される、と。
NykRさんのソースとは微妙に変わっていますが、こんな解釈でよいでしょうか?
# いやあ、実に勉強になりました。