OchaCamlに触ってみた。
PPL2014（ http://www.fos.kuis.kyoto-u.ac.jp/ppl2014/ ）に参加して来ました。
去年に引続きの参加（但し去年は発表なしで見に行っただけ）だったのですが、去年も今年も（主にお茶女勢による）限定継続の発表を聞いては「限定継続ってなんだっけ」と思ってはググったり、教えてもらったりしていましたので、いい加減ちょっとは学んでおこうと思い、OchaCamlを入れて遊んでみました。
公式ページ通りにインストールしてみます(OSはUbuntu)。tarを落として
cd ~/Project/OchaCaml tar xpfvz cl75unix.tar.gz tar xpfvz OchaCaml.tar.gz patch -p0 < OchaCaml/OchaCaml.diff cd cl75/src make configure
と、ここでエラー。
gcc: エラー: 認識できないコマンドラインオプション ‘-no-cpp-precomp’ です
これは公式に対応が載ってた。makefileのOPTSから消せばそれでいいらしい。
試してみたらconfigure完了。
make configure make world
でビルドも成功。インタプリタを起動させてみる。
~/Project/OchaCaml/OchaCaml/ochacaml
またエラー。「(Home)/cl75/src/camlrun がないです」とのこと。よく見ると公式ページに"Adjust the third line of OchaCaml/ochacaml to your environment. "とある。のでochacamlの3行目をcamlrunの場所に書きかえる。
~/Project/OchaCaml/OchaCaml/ochacaml > Caml Light version 0.75 + shift/reset #
できた。
とりあえず行編集能力がないことを確認したので、
PATH=$PATH:~/Project/OchaCaml/OchaCaml alias ochacaml='ledit ochacaml'
と.bashrcに追加して環境の準備を終えた。
さて、何はともあれshift/resetですね。まずは型を見ましょう。
# shift;;
- : (('a -> 'b) / 'c -> 'c / 'd) / 'b -> 'a / 'd = <fun>
# reset;;
- : (unit / 'a -> 'a / 'b) -> 'b = <fun>
闇っぽいですね。S/A->T/BというのはS->T型なのだけれど、実行（評価？）するとanswer typeをAからBに変更する型、らしいです。answer type？
よくわかんないので論文*1を見てみると、answer typeとは直感的にはresetが返す型のことを言うらしいです。なんだかわかったようなわからないような……
つまり、resetは「unit -> 'a型で、かつanswer typeを'aから'bに変える関数を受け取って'bを返す」関数ということになります。
一方のshiftは、
- ('a -> 'b) -> 'c型で、かつanswer typeを'cから'dに変える関数を受け取って
- 'a型を返し、
- shift関数自身はその実行によってanswer typeを'bから'dに変える。
ということになるのでしょうか。
このへんでわけわからん感じになったので、shift/reset プログラミング入門を読みつつまずは挙動から理解していくことにしました。
shift/resetは
reset (fun () -> C[shift (fun k -> M)])
が(Cは継続*2)
- kにfun x -> C[x]を束縛
- Mを評価
という風に評価されるとのこと。
つまり
評価文脈として E := ... | reset (fun () -> E) | ... みたいになってるっぽい？
— xenophobia (@xenophobia__) 2014, 3月 9
継続を追加するってのはつまり、reset (λ_ . E[shift(fun k -> M)]) → M[k := λx.E[x]]（xはfresh） みたいなreduction relationとさっきの評価文脈を加えること、という理解でいいのかな？
— xenophobia (@xenophobia__) 2014, 3月 9
ということとして理解してよさそう。
なんとなく動作はわかったんで遊びます。
# reset (fun () -> 3 + shift (fun k -> 4 + k 3) * 5);; - : int = 22 # reset (fun () -> shift (fun k -> k) * 2) 123;; - : int = 246
楽しいですね。計算を保留してresetのとこまで一気に戻れるというのはなかなか豪快です。使い道はまだ見えてきませんが。
ちまい例ではまだよくわからんのでもっと複雑な計算をshiftでぶった切ってみましょう。複雑な計算といえば再帰ですね。shift/resetプログラミング入門2.7章を参考に、フィボナッチ関数を再帰の末端に辿りつく度止めるような関数を書いてみます。
let rec path_str_rev = function | -> raise (Invalid_argument "empty path") | x:: -> string_of_int x | x::xs -> path_str_rev xs ^ " -> " ^ string_of_int x;; type 'a result = Cont of (int list * (unit / 'a -> 'a result / 'a)) | Ans of int;; let rec fib_path path n = if n<2 then (shift (fun k -> Cont(path, k));1) else fib_path (n-1 :: path) (n-1) + fib_path (n-2 :: path) (n-2);; let fib_path_start n = reset (fun () -> Ans (fib_path [n] n));; let rec loop = function | Ans n -> print_endline ("Answer = " ^ string_of_int n) | Cont (path, k) -> begin print_endline (path_str_rev path); loop (k ()) end;; let _ = loop (fib_path_start 5);;
実行すると
# load "TestCode/test.ml";; path_str_rev : int list -> string =Type result defined. fib_path : int list => int => int = fib_path_start : int -> 'a result = loop : 'a result => unit = 5 -> 3 -> 1 5 -> 3 -> 2 -> 0 5 -> 3 -> 2 -> 1 5 -> 4 -> 2 -> 0 5 -> 4 -> 2 -> 1 5 -> 4 -> 3 -> 1 5 -> 4 -> 3 -> 2 -> 0 5 -> 4 -> 3 -> 2 -> 1 Answer = 8 - : unit = ()
となります。
なんとなく、どういう型合わせが必要かは掴みかけてきましたが、answer typeの概念がちゃんとわかっている自信はないので、もっとよく調べないとですね。
型に関しては追い追い調べるとして、ひとまず今回はここまで。
