(続)OCamlをC言語に変換するプログラムつくりました

OCamlで書いてC言語に変換するプログラム、最低限入れたかった機能を実装して一応形になりました(ソースコードこちら)。プライベートな時間をちまちま使って作ったので思ったより時間がかかってしまいました。最初にブログで紹介してから1年半もたちました。

OCamlをC言語に変換するプログラムをつくりました - masaterukの日記

サポートしている基本型は、Int型とBool型のみ。レコード型とバリアント型も使えます。型変数による多相型も定義できます。リスト型だけ組み込みでサポートしました(ただしライブラリはありません)。

関数を定義するときには、再帰関数でなくてもlet recとするのはMinCamlと同様です。ラムダは書けませんが、クロージャはサポートしてます。matchによるパターンマッチをサポートしているので、だいぶ書けるものが増えました。

たとえば、Haskellの例でよく引き合いに出されるクイックソートなら以下のように書けます。

let rec iter f xs =
  match xs with
  | [] -> ()
  | x :: xs -> f x; iter f xs

let rec append xs ys =
  match xs with
  | [] -> ys
  | x :: xs -> x :: (append xs ys)

let rec filter p xs =
  match xs with
  | [] -> []
  | x :: xs -> if (p x) then x :: (filter p xs) else (filter p xs)

let rec sort xs =
  match xs with
  | [] -> []
  | x :: xs ->
      let rec le y = (y <= x) in
      let rec gt y = (y > x) in
      let left = sort (filter le xs) in
      let right = sort (filter gt xs) in
      append left (x :: right)

let rec is_sorted xs =
  match xs with
  | [] -> true
  | [x] -> true
  | x :: y :: zs -> (x <= y) && (is_sorted (y::zs))

let () =
  let xs = [5; 2; 3] in
  let ys = sort xs in
  assert (is_sorted ys);
  iter print_int ys

通常のOCamlとの違いは、Listのライブラリがないので自前でリスト関数を実装していることと比較関数をラムダではなく名前をつけて関数を定義しているところくらいでしょうか。

破壊的代入をサポートしていないので書けるものがすこし限定されますが、プログラムを副作用が必要な部分とそうでない部分にわければ、副作用がないところは関数型でささっと書いてしまうことができます。テストプログラムとかプロトタイプとか使える用途はそれなりにあるんじゃないと期待してます。

ちなみに上のクイックソートOCamlでは37行ですが、C言語に変換すると361行になります。およそ10倍です。機械生成なので人間が書いたらもう少し短くなるでしょうが、それでもOCamlの方がずっと短く書けるでしょう。C言語の方が行数が多くなるのは、多相型を解決するための型変換とメモリ管理のためにポインタの参照カウンタ操作のコードが増えるからです。OCamlではコンパイラが自動で解決してくれる問題もC言語では自分で解決しなくてはなりません。メモリ管理とか人手でやってやれないことはないですが、ミスなく実装するのは相当難しいとツールで生成されるコードを見ると感じます。

C言語の方が速度が速いでしょうが、もうすべてをC言語で書くのはやめた方がいいでしょう。よくパフォーマンス改善は測定してからと言いますが、それなら最初はOCamlで書いて測定して改善が必要なところだけC言語だけで書き直した方がいいんじゃないでしょうか。