Next: Up: Previous:

可能な work around

このタイプの並列性を欠いている言語においては, insert はメソッドの内部で再帰呼び出しの 結果を待つことができない. 再帰呼び出しの結果を 得るために, ルートノードのもともとのcallerは 結果の値が格納される「ボックス」オブジェクトを確保し, 中間のノードは再帰呼び出しを非同期にし, 再帰呼び出しの 鎖にそってオブジェクトを渡す. オブジェクトを単純なセルにすることはできない. それは リーフノードともともとの caller との生産者-消費者 同期を実現しなければならない.

もし再帰呼び出しが末尾呼びだしでないならば, これは より複雑になるだろう. このケースでは, 各ノードは再帰呼びだしにおいて「ボックス」オブジェクト の代わりに, 「継続」オブジェクトを生成して渡す. その継続オブジェクトは再帰呼びだしの計算された結果を 受けとり, 残りの計算を行ない, 親の継続に結果を送る. この継続オブジェクトもcallerとcallee間の同期を 実現しなければならない. この同期がどのように 達成されるかは言語に依存する. ある言語は channel や gate [26] といった組み込みのデータ 構造を提供している. また, ある言語は条件つきメッセージ受信 [3], [4], [23], [30] を提供している.



Mitsubishi Research Institute,Inc.
Mon Feb 24 19:24:01 JST 1997