fetburner.core

コアダンプ

手続き型言語OCaml

OCaml

この記事はML Advent Calendar8日目の記事として書かれました。 7日目の記事はでこれきさんのfoldみぎひだりです。

Standard MLやOCamlをはじめとしたML系の言語は関数型言語として有名ですが、参照、配列、例外といった副作用を伴う機能も扱う事ができます。 また、ML系の言語で手続き的に書いたからと言ってその言語の魅力が損なわれるわけではなく、 強い静的型付け、型推論やparametric polymorphismなどの恩恵を受けられるので、むしろ良く設計された手続き型言語のように映る事でしょう。 積極的にMLで手続き的な処理を書いていこうな。

  • 2015年12月8日1:05 Kleene's algorithmの実装を間違えていたので修正
  • 2015年12月8日17:54 プログラムの例をリファクタリングした

手続き的な処理と言えば僕はグラフ関連のアルゴリズムが思い浮かんだのですが皆さんはどうでしょうか。 ヴァリアントを使えば良いのでMLで木構造を扱うのは楽ちんですが、グラフだと一筋縄ではいかないので僕はあまり好きではありません。 Structured Graphと言ってグラフを関数型言語でうまく扱うための研究もあるぐらいです。

赤黒木のように関数型なスタイルで書くと見通しが良くなって幸せ、みたいなプログラムは関数型で書くべきでしょうが、 純粋関数型で書くと状態を引き回す羽目になってつらいみたいなプログラム(e.g. gensym)を関数型で書くべきとは僕は思いません。 やはり手続き型で書くのが楽なアルゴリズムは手続き型で書くべきでしょう。

例えば、グラフの最短経路を求めるワーシャルフロイド法をOCamlで手続き型に書くとこんな感じになります。

let warshall_floyd ( + ) min loop n d =
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      for k = 0 to n - 1 do
        d.(j).(k) <- min d.(j).(k) (d.(j).(i) + loop d.(i).(i) + d.(i).(k))
      done
    done
  done
(*
val warshall_floyd :
  ('a -> 'a -> 'a) ->
  ('a -> 'a -> 'a) -> ('a -> 'a) -> int -> 'a array array -> unit = <fun>
*)

何と簡潔なプログラムでしょうか！ これを関数型に書き直しても得られるものは少なそうです。

試しに使ってみましょう。

let graph = 
  let inf = infinity in
  [| [| 0.;  4.;  inf; inf; 3.  |];
     [| 4.;  0.;  2.;  inf; inf |];
     [| inf; 2.;  0.;  3.;  2.  |];
     [| inf; inf; 3.;  0.;  7.  |];
     [| 3.;  inf; 2.;  7.;  0.  |] |];;
warshall_floyd ( +. ) min (fun x -> 0.) 5 graph;;
graph;;
(*
- : float array array =
[|[|0.; 4.; 5.; 8.; 3.|]; [|4.; 0.; 2.; 5.; 4.|]; [|5.; 2.; 0.; 3.; 2.|];
  [|8.; 5.; 3.; 0.; 5.|]; [|3.; 4.; 2.; 5.; 0.|]|]
*)

ここで、ワーシャルフロイド法を実装する際に高階関数として実装した事に注目して下さい。

特定の関数を直接使わずに呼び出し側で与えるように実装した事で、この関数は様々な用途に使えるようになります。 例えば、重みの和と重みの最小値を工夫してやれば経路を保存するようにできる上、

let graph = 
  let inf = infinity in
  Array.mapi (fun i row ->
    Array.mapi (fun j w -> (w, if i = j then [] else [(i, j)])) row)
  [| [| 0.;  4.;  inf; inf; 3.  |];
     [| 4.;  0.;  2.;  inf; inf |];
     [| inf; 2.;  0.;  3.;  2.  |];
     [| inf; inf; 3.;  0.;  7.  |];
     [| 3.;  inf; 2.;  7.;  0.  |] |];;
warshall_floyd
  (fun (n1, r1) (n2, r2) -> (n1 +. n2, r1 @ r2))
  (fun ((n1, _) as w1) ((n2, _) as w2) ->
    if n1 <= n2 then w1
    else w2)
  (fun x -> (0., [])) 5 graph;;
(*
- : (float * (int * int) list) array array =
[|[|(0., []); (4., [(0, 1)]); (5., [(0, 4); (4, 2)]);
    (8., [(0, 4); (4, 2); (2, 3)]); (3., [(0, 4)])|];
  [|(4., [(1, 0)]); (0., []); (2., [(1, 2)]); (5., [(1, 2); (2, 3)]);
    (4., [(1, 2); (2, 4)])|];
  [|(5., [(2, 4); (4, 0)]); (2., [(2, 1)]); (0., []); (3., [(2, 3)]);
    (2., [(2, 4)])|];
  [|(8., [(3, 2); (2, 4); (4, 0)]); (5., [(3, 2); (2, 1)]); (3., [(3, 2)]);
    (0., []); (5., [(3, 2); (2, 4)])|];
  [|(3., [(4, 0)]); (4., [(4, 2); (2, 1)]); (2., [(4, 2)]);
    (5., [(4, 2); (2, 3)]); (0., [])|]|]
*)

ある有限オートマトンが与えられた時の同じ言語を受理する正規表現だって求められます！

type regexp =
  (* 文字*)
  | Lit of string
  (* ε *)
  | Eps
  (* 何も受理しない *)
  | Delta
  (* 連接 *)
  | Seq of regexp * regexp
  (* | *)
  | Sum of regexp * regexp
  (* * *)
  | Repeat of regexp

(* 見づらいので簡約する *)
let sum s1 s2 =
  match s1, s2 with
  | Delta, _ -> s2
  | _, Delta -> s1
  | _, _ ->
      if s1 = s2 then s1
      else Sum (s1, s2)

let seq s1 s2 =
  match s1, s2 with
  | Delta, _ -> Delta
  | _, Delta -> Delta
  | Eps, _ -> s2
  | _, Eps -> s1
  | _, _ -> Seq (s1, s2)

let repeat = function
  | Eps -> Eps
  | Delta -> Eps
  | (Repeat _) as s -> s
  | s -> Repeat s

let automata =
  [| [| Delta; Lit "wa"; Delta;    Delta;    Delta;   Delta    |];
     [| Delta; Delta;    Lit "ka"; Delta;    Delta;   Delta    |];
     [| Delta; Delta;    Lit "ba"; Lit "ga"; Delta;   Delta    |];
     [| Delta; Delta;    Delta;    Delta;    Lit "-"; Delta    |];
     [| Delta; Delta;    Delta;    Delta;    Delta;   Lit "ru" |];
     [| Delta; Delta;    Delta;    Delta;    Delta;   Delta    |] |];;
warshall_floyd seq sum repeat 6 automata;;

(* わかば*ガール *)
automata.(0).(5);;
(*
- : regexp =
Seq
 (Seq
   (Seq
     (Seq
       (Sum (Seq (Lit "wa", Lit "ka"),
         Seq (Seq (Seq (Lit "wa", Lit "ka"), Repeat (Lit "ba")), Lit "ba")),
       Repeat (Lit "ba")),
     Lit "ga"),
   Lit "-"),
 Lit "ru")
*)

肝心のワーシャルフロイド法の実装を変更する事無くこれだけの事をできるのですから、MLは手続き型言語としても優秀であると言っても差し支えないでしょう。

ここまで読んだ方の中にはそれほげほげでもできるよと言いたい方もあるでしょう。 確かに、void *なりObjectなり、はたまた動的型付き言語を使うなりして型を潰してしまえば同じ事ができるかもしれません。

しかし、そこは静的型付き言語ML。 parametric polymorphismによって種々のプログラムを型検査で通す懐の深さを見せつつ、次のように本当に危険なプログラムは弾いてくれます。

let graph = 
  let inf = infinity in
  [| [| 0.;  4.;  inf; inf; 3.  |];
     [| 4.;  0.;  2.;  inf; inf |];
     [| inf; 2.;  0.;  3.;  2.  |];
     [| inf; inf; 3.;  0.;  7.  |];
     [| 3.;  inf; 2.;  7.;  0.  |] |];;
warshall_floyd
  (fun (n1, r1) (n2, r2) -> (n1 +. n2, r1 @ r2))
  (fun ((n1, _) as w1) ((n2, _) as w2) ->
    if n1 <= n2 then w1
    else w2)
  (fun x -> (0., [])) 5 graph;;
(*
 Error: This expression has type float array array
       but an expression was expected of type (float * 'a list) array array
       Type float is not compatible with type float * 'a list 
*)

いかがでしょうか。 ML、良い手続き型言語でしょう？