2009年11月4日水曜日

遅延ストリームによってシミュレーションと出力処理を分離


このエントリで紹介したHaskellのコードでは、遅延ストリームという手法を使っています。

このエントリでは、遅延ストリームとそれを使うメリットについて書きます。

遅延ストリームとは?


遅延ストリームとは、遅延評価される無限リストです。

使っているのは、
output $ take (read (n!!0)) $ simulation ps0
の部分です。

simulation関数の型は
[Particles]->[[Particles]]
となっていて、粒子の初期状態を引数にとり、各ステップでの粒子の状態をリストで返します。

そのリストから、コマンドライン引数で与えたステップ数だけtake関数でとりだし、output関数(アクション)でファイルに出力しています。

このように書くと、取り出すステップ数だけ先に計算して、すべて計算し終わってからまとめて出力されることになりそうですが、Haskellの場合は遅延評価されるので、1ステップずつ評価されてファイルに出力されるのです。

遅延ストリームを使うメリットは?


このように遅延ストリームを使うメリットは、関数のモジュール性を高めて、シミュレーションと出力を完全に分離できることです。

simulation関数とoutput関数はまったく独立していて、たとえば、output関数のみをdisplay関数に差し替えて画面に出力する、ということができます。
display $ simulation ps0

逆に、この処理を遅延評価でない言語、たとえばC++で書くと、
for ( int i = 0 ; i < n; i++ )
  {
    output_particles( p_ps, i );
    simulation( p_ps );
  }
のように、forループの中にシミュレーションと出力を書くことになり、お互いが強く結びついてしまいます。遅延ストリームをなら、このように強く結びつくことを避けられます。

以上のように、遅延ストリームを使うと、関数のモジュール性を高めることができるのです。

OCamlで遅延ストリームは使える?


OCamlも言語に遅延評価の仕組みが含まれているので、同様に遅延ストリームを使うことができます。

OCamlでの遅延ストリームは、このエントリにあるコードから抜粋すると、
open Lazy;;

type 'a stream = Nils
               | Cons of 'a * 'a stream lazy_t;;

let rec stream_take (n : int) (s : 'a stream) : 'a stream =
  match (n,s) with
  | (_,Nils)       -> Nils
  | (0,Cons(x,_ )) -> Nils
  | (n,Cons(x,xs)) -> Cons(x, lazy(stream_take (n-1) (force xs)));;

let rec simulation ps = 
  let ps'  = calc_amount ps (mk_neighbor_map ps) in
  let ps'' = advance ps' (mk_neighbor_map ps')
  in Cons(ps, lazy(simulation ps''));;

let main =
  let n = int_of_string (Sys.argv.(1))
  in print_number_of ps0;
     stream_output (stream_take n (simulation ps0));;
のように書くことができます。

'a stream型のcarを'a型、cdrを'a stream lazy_t型とし、cdrを順番にforceしていくことで遅延ストリームを実現しています。

Haskell版と同様に、粒子の状態を1ステップずつ評価してファイルに出力します。

C++では?


C++では言語に遅延評価の仕組みがありません。なので、遅延ストリームをそのまま使うことはできません。

ただ、シミュレーションと出力の分離という意味では、関数オブジェクトを使うことで、同等のことは一応可能です。
-

0 件のコメント: