D言語くんからの問題解説

問題

D言語くんからの問題 pic.twitter.com/mh8p6Jjeqf

— 井山・禿・梃子歴史館 (@__pandaman64__) 2016年6月6日

答え

何も出力されない．
https://dpaste.dzfl.pl/8feee9d7d046

なぜなのか

Range

D言語は複数の要素を持つオブジェクトをレンジ(Range)という共通のインターフェイスで扱えるように設計されています．配列やスライスといったコンテナをRangeとして扱うこともできますし，上のiota(10)も1から10までの整数を表すRangeの一つです．

さらにD言語では，Rangeを加工して新たなRangeを作る，ということが簡単にできます．例えば，map!fun¹はRangeを受け取って各要素にfunを適用した結果からなるRangeを返す関数ですし，filter!predは引数のRangeの要素をそれぞれpredに渡して，trueが返ってくるような要素だけを集めたRangeを返す関数です．標準ライブラリにはこのようなアルゴリズム関数が数多く存在し，これらを入力のRangeに次々と適用して必要な情報を取得するのがD言語における標準的なコーディングスタイルです²．

遅延評価

この問題で重要なのは，Rangeは遅延評価されるということです．つまり，mapやfilterを呼び出した段階では処理は行われず，map等の戻り値のRangeを評価した時点で初めて元のRangeに対しての処理を実行するということです．それでは，Rangeを評価するにはどうすればよいのでしょうか？一番典型的な方法は，foreach文を用いることです．

void main(){
  auto range = iota(10).filter!"a % 2 == 0".map!"a + 1"; //この段階では処理は実行されない

  foreach(const v;range){ //ここで初めて処理を実行する
    wrieln(v); //出力 `1 3 5 7 9 11`
  }
}

foreach文はセミコロンの右側のRangeを初めから走査します．具体的には，vにrange.front³を代入してブロックを実行した後，range.popFront()の呼び出しによってRangeを次の要素に進めます．これをrange.empty³がtrueとなるまで繰り返します．

それではアルゴリズム関数の実装はどう なっているのでしょう．アルゴリズム関数の結果のRangeは，元のRangeを保持しています．それをinnerと書くことにしましょう．filter!predの結果のRangeはpopFront()が呼び出されたときにinnerを空になるかpred(inner.front) == trueとなるまで進めます（inner.popFront()）．またmap!funではfrontの呼び出し⁴に対してfun(inner.front)を返します．ここでは，アルゴリズム関数の結果のRangeに対してfrontやpopFront()を呼び出して初めて元のRangeに対しての処理が行われています．これがRangeの遅延評価です．

問題に立ち返ってみましょう．iota(10).filter!"a % 2 == 0".map!printとRangeを生成したはいいものの，このRangeは評価されていません．ですから，遅延評価によりfilterやmapの処理は行われず，結局何も出力されずにプログラムは終了してしまうのです．

おまけ

この問題は友人が用意してくれた枠を使って10分で作りました．置いておくのでご自由にお使いください．

1. funは関数だと考えてください．問題ではfilterに文字列を渡していますが，このときfilter内部ではこの文字列をaを第一引数とする関数としてコンパイル時に解釈しています．このように柔軟なプログラムが書けるのもD言語の強力なコンパイル時処理の恩恵です． ↩

2. D言語にはUFCS(Universal Function Call Syntax)という機能があり，a.func(b)という式はfunc(a,b)とも解釈されます．問題で言えば，本来はmap!print(filter!"a % 2 == 0"(iota(10)))と書く必要があるのに対し，UFCSによってiota(10).filter!"a % 2 == 0".map!printというメソッドチェーン形式の記述が可能になります． ↩

3. range.frontはRangeの先頭要素，range.emptyはRangeが終端に達したかを表す ↩ ↩²

4. UFCSにより，プロパティの参照a.propは0引数メンバ関数の呼び出しa.prop()または1引数関数の呼び出しprop(a)とも解釈されます． ↩