K.Maebashi's BBS 投稿フォーム

ハンドル名
件名
Link

>土曜はとあるイベントにて大阪で飲んだくれておりまして、ずいぶん返事が遅くなりまして
>すみません。
>それプラス、私自身、クロージャに慣れておらず継続もわかっておらず、今回の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さんのソースとは微妙に変わっていますが、こんな解釈でよいでしょうか?
>
># いやあ、実に勉強になりました。
>

spamよけのため、ここに「ほげぴよ」と入力してください。

削除パスワード : クリック！