やねうらおプログラミング道場
http://d.hatena.ne.jp/yaneurao/20041103#p1
のループの話がおもしろかったのでちょっと考えてみた。
結局、前判定にするか後判定にするかというのは、ループ中のカーソル移動時に、
- 今指しているところを信用する
- 次の要素へのアクセスを信用する
のどちらの立場に立つか、ということな気がする。
前判定*1では、「今指しているところ」を信用して処理を行ない、今指しているところが、最後の要素かそうでないかの判定でループを終了させる。
後判定*2では「次の要素へのアクセス」を信用して次の要素を取得し、条件判断を行なった後、判定済みの内容で処理を行なう。
従って、それぞれ要求される条件はこうなる。都合上、後判定から説明する。
- 後判定
- 常に「次の要素へのアクセス」を信用するので、最後の要素の次の要素にもアクセスでき、かつ要素が存在する必要がある。つまり、定義域のひとつ外側の値にアクセス可能であり、それが定義域の外側であると判定できる必要がある*3。従って、静的型付き言語では条件判定のために要素を格納する変数は、定義域外の値をとれる型である必要がある。さらに、ある要素は定義域外であるという判定も可能でないといけない。
- 前判定
- 「今指しているところ」を信用できない空集合には適応できない。さらに「今指しているところ」が定義域の最後であるかどうかを判定する必要がある。しかしながら、全ては定義域の「内側」に対する処理だけでループをまわすことができる。
ちなみにこのトレードオフは外部カーソルを利用したループ特有の問題で、rubyのeach等にみられる内部カーソルでは発生しない。何故なら、内部カーソルのループでは、「今指しているところ」の存在が常に保証される上、ループ終了の条件判断もユーザーが記述するコード外で自動的に行われるからである。
この観点で内部カーソルを捉えると、内部カーソルは外部カーソルでの「初期値の保証 + 最終値の判定による前判定」を抽象化したものだといえる。
したがって、内部カーソル
A.each {|A item| do_something(item);}
は
if (A.begin != A.illegal){ // ここは初期値の保証(空でないことを保証する判定式)がはいる。
// 配列だったらサイズが1以上であることを確認するとか？
A item = A.begin
while(true) {
do_something(item)
if (item == A.end) break;// 定義域の最後であることの判定
++item;
}
}
に自動的に書きかえられるはず*4。
A.illegalなんてのを使ってしまったので、Aの型は定義域+illegal(デリミタ)をとれる型でないといけなくなったが、例えばA.size > 0なんて条件を代わりに使えば,Aは定義域だけをカバーする型でよい。後判定だと必ずデリミタを導入しないといけないので、Aの型は定義域+デリミタをとれる型である必要がある。
なんか変かな。
ああ、そうだ。後判定のほうのデリミタってのは要は番兵ですね。
Cで後判定がよく使われるのは、「要素の最後」を判定するよりコストより、定義域になりえない要素を決めうちで番兵とし、その番兵との比較で判定するコストのほうが低い(場合が多い)からでしょうか。
