データフロー変数 - みずぴー日記

30分プログラム、その227。Mozartのデータフロー変数をOCamlで作ってみる。
最近読んでいるガウディ本(asin:4798113468)で使われているMozart/Ozにはデータフロー変数というおもしろい変数がある。
これは未束縛の変数を使おうとしたらそのスレッドは停止して、他のスレッドによってその変数が束縛されるのを待つという機能。なので、これを使うと並列フィボナッチ関数は次のように書ける。

fun {Fib X}
 if X<=2 then 1
 else Y in
   thread Y={Fib X-1} end
   Y+{Fib X-2}
 end
end

あるいはシンタックスシュガーを用いると

fun {Fib X}
 if X<=2 then 1
 else thread {Fib X-1} end +{Fib X-2} end
end

のように非常に簡単に書ける。

デザインパターンのFutureパターンに似ている印象を受ける。

で、これがおもしろかったのでOCamlで実現してみる。それだけだとおもしろくないので、camlp4を使って簡潔に書けるようにしてみた。

使い方

let rec fib n = 
  if n <= 2 then
    1
  else
    let x = flow fib (n-1) in
      (wait x)+(fib (n-2))

並列フィボナッチ。flow ...と書くと、それがデータフロー変数になる。必要な部分でwait xとすると、そこで値が得られる。

ソースコード

camlp4部分。

open Pcaml

EXTEND
expr: LEVEL "expr1"
[
  [ "flow" ; e = expr -> <:expr<dataflow (fun ()-> $e$) >> ]];
END;;

本体部分。

let (@@) f g = f g

let dataflow f = 
  let c = Event.new_channel () in
  let proc () = Event.sync @@ Event.send c @@ f () in
  let _ = Thread.create proc () in
    fun () -> Event.sync @@ Event.receive c

let wait f = f ()

let rec fib n = 
  if n <= 2 then
    1
  else
    let x = flow fib (n-1) in
      (wait x)+(fib (n-2))

let _ = 
  Printf.printf "%d\n" (fib 10)

コンパイルは次のようにする。

$ ocamlc -pp "camlp4o pa_extend.cmo q_MLast.cmo" -I +camlp4 -c dataflow.ml
$ ocamlc -thread -pp "camlp4o ./dataflow.cmo" unix.cma threads.cma fib.ml

参考

過去の30分プログラム