読者です 読者をやめる 読者になる 読者になる

claustrophobia

一般λがなんか書くとか

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を評価

という風に評価されるとのこと。

 つまり

 ということとして理解してよさそう。

なんとなく動作はわかったんで遊びます。

# 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の概念がちゃんとわかっている自信はないので、もっとよく調べないとですね。

型に関しては追い追い調べるとして、ひとまず今回はここまで。

*1:Masuko, M., and K. Asai "Caml Light + shift/reset = Caml Shift," Theory and Practice of Delimited Continuations (TPDC 2011), pp. 33-46 (May 2011).

*2:「評価文脈」と理解してもよい?