Open2021/11/22にコメント追加79

OCamlの学習ログ

本当にいろいろな言語がやりたくなってしまう。SATySFiって処理系がOCamlで実装されているらしいのでOCamlを学んでいこうかと思います。

OCamlは関数型言語MLの方言。もともとはObjective Camlの略称で、クラスとかもあるっぽいがあまり使われてないらしい？関数型としての特徴は非純粋関数型で副作用をバシバシ利用できることがある。

環境構築はNixでやる。主要な処理系もOCamlという名前で、Duneというビルドツール、Opamというパッケージマネージャ、utopというおしゃれなREPLがある。NixpkgsにわりとそろっているのでOpamに頼らずともツールがインストールできる。

shell.nix

{ pkgs ? import <nixpkgs> { } }: pkgs.mkShell {
  buildInputs = [
    pkgs.ocaml
    pkgs.dune_2
    pkgs.ocamlPackages.ocaml-lsp
    pkgs.ocamlPackages.utop
    pkgs.ocamlformat
  ];
}

VS CodeではOCaml Platformという公式の拡張機能が2020年ぐらいにリリースされている。

公式サイトのチュートリアルをやっていく。

基本的な型の一覧。

int: 32bit環境では31bit、64bit環境では63bitの整数。1bit少ないのはガベージコレクションのタグ付けに使うためらしいというのをTwitterで見た。
float: IEEE754 64bit浮動小数点数。
bool: true と false。代数的データ型とかで定義されているわけではなさそう？
char: 8bit文字。1文字を8bitで表すというのは少々冗談が過ぎる気がするが1990年代からある言語にあれこれ言っても仕方がないか。
string: 8bit文字の連なりではあるがcharのリストではないらしい。おそらくHaskellを念頭に置いている？

公式ガイドで「Unicode対応ライブラリあるよ」という案内があった。

https://github.com/yoriyuki/Camomile

REPLでは入力の終わりをセミコロン2つ ;; で表す。ほかの言語のノリで改行しても実行されないので慣れていないとちょっと困惑する。ソースファイルではこれは省略できるっぽい？

変数定義は let で行う。F#やRustと同じ。

repl

utop # let x = 29;;
val x : int = 29 

utop # let y = 13;;
val y : int = 13

x + y;;
- : int = 42

それぞれの式にはつねに1つの型が割り当てられる。1 なら int だし 1. なら float、'a'は char、"hello"は string という感じ。

暗黙的な型変換がない。型変換には 変換後_of_変換前 のような関数を使う。

REPL

utop # int_of_char 'a';;
- : int = 97

京都大学のOCaml資料。

http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/pl/03-ocaml.html#ocaml-as-calc-memory

式の計算結果がまずあって，それに名前を付ける—つまり値を格納するメモリ領域に名前を付けているわけではない—ので，int x; のように変数の宣言だけをする，ということはできない．

この部分のとらえ方の違いが面白い。変数を箱と例えるのは適切か否か、という議論にも通じていそう。

変数のシャドーイング (同じ名前の変数を複数回宣言すること) ができる。

let x = 42
let x = 12
let x = x + 1 (* x = 13。前の値を使用できる *)

関数定義にも let を使う。

(* int -> int *)
let square n = n * n

(* int -> int -> int *)
let add a b = a + b

関数呼び出しにはかっこが不要。int -> int -> int のような型がつくことからわかるようにカリー化されていて部分適用が簡単。

(* int *)
let x = add 3 4

(* int -> int *)
let add_3 = add 3

(* int *)
let x = add_3 4

再帰的関数は let rec で定義する。

let rec fact n =
  if n = 0 then 1
  else n * fact (n - 1)

let 定義 in 式 とすることで定義のスコープを 式 の中に限定することができる。

let fact =
  let rec inner acc n = if n = 0 then acc else inner (acc * n) (n - 1) in
  inner 1

与えられた正整数 $n$ に対し $(1^2+2^2+\cdots+n^2)$ を計算する再帰関数 squaresum : int -> int を定義せよ．(引数 $n$ が負である場合の動作はどう定義してもよい．)

\begin{split}\mathrm{squaresum}(n) &= 1^2+2^2+\cdots+n^2 \\ &= 1^2+2^2+\cdots+(n-1)^2+n^2 \\ &= \mathrm{squaresum}(n-1)+n^2 \end{split}

という感じがあり、 $n=0$ の扱いを定義して

\mathrm{squaresum}(n) = \begin{cases} 0 &\text{if } n=0 \\ \mathrm{squaresum}(n-1)+n^2 &\text{otherwise} \end{cases}

というふうにできる。あとは書くだけだが、平方 square を定義しておく。

let rec squaresum n =
  let square n = n * n in
  if n = 0 then 0 else squaresum (n - 1) + square n

与えられた正整数 $n$ に対し， $n$ 番目のフィボナッチ数を計算する再帰関数 fib : int -> int を定義せよ．(引数nが負である場合の動作はどう定義してもよい．)

フィボナッチ数は $0,1,1,2,3,5,\cdots$ と並ぶやつで、 $n>3$ で $\mathrm{fib}(n-2)+\mathrm{fib}(n-1)$ なので、

let rec fib n = match n with 1 -> 0 | 2 -> 1 | _ -> fib (n - 2) + fib (n - 1)

計算量がやばくてfib 40あたりからだいぶ時間がかかってるけどいいか。

ユークリッドの互除法を使ってふたつの正整数 $n, m$ の最大公約数を計算する再帰関数 gcd : int * int -> int を定義せよ．(引数nが負である場合の動作はどう定義してもよい．)

int * int というのはタプル型のこと。別に int -> int -> int でもいいと思うのだが n と m は対等なのでこういう取り方をしてるのだと思う。

パターンマッチは match 値 with から始まり、アームは | パターン -> 式 で書く。

レコード型。型名が小文字で始まるのがちょっと慣れない。

type point = { x : int; y : int }

let origin = { x = 0; y = 0 };;

自動的に origin : point と推論されているけどこれはどうやっているんだろうか？フィールドの名前からこれがどのレコードなのかわかるものなのか？

同じ構造のレコードが複数定義されている場合は最後に定義されているやつに推論されるっぽい。上側の型を使う場合は手動で型注釈する必要がある。

type point = { x : int; y : int }

(* point *)
let origin = { x = 0; y = 0 }

type point' = { x : int; y : int }

(* point' *)
let origin = { x = 0; y = 0 }

(* point *)
let (origin : point) = { x = 0; y = 0 }

フィールドにアクセスする場合はドット . もしくはパターンマッチを使う。レコードのパターンマッチでは使用しないフィールドをアンダースコアで無視する必要があるっぽい。

let x_of p = p.x

let x_of { x; _ } = x
(* {x;} は{x=x;} の略記 *)

バリアントも type。それぞれの Debian などの識別子はコンストラクタと呼ばれ、大文字で始まる。Standard MLでは小文字でもいいらしい。

type kernel = NT | Mach | Linux | Hurd

let ubuntu = Linux

let is_free kernel =
  match kernel with Linux -> true | Hurd -> true | _ -> false

(* ORパターン *)
let is_free kernel = match kernel with Linux | Hurd -> true | _ -> false

型引数の定義は '型引数名型名 というように前置する
型引数を与える際もやはり 型引数型名 というように型引数が前置される
コンストラクタの定義に of を使うがコンストラクタを使うときやパターンで分解するときには使わないのが謎
もちろん再帰的なデータ型が書ける
タプル型は 型1 * 型2 という形。直積であることを隠すつもりがないらしい

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec total t =
  match t with Leaf -> 0 | Node (l, n, r) -> total l + n + total r

let t = Node (Node (Leaf, 2, Leaf), 3, Leaf)

レコードの非破壊更新文法。JSの...objとかRustの..valに相当すると思うが with がどういうwithなのかがよくわからない。

type point = { x : int; y : int }
let origin = { x = 0; y = 0 }
let p = { origin with y = 3 } (* { x = 0; y = 3 } *)

値としてミュータブルなレコードもある。Rustと違って型宣言時にフィールドごとに可変性を指定する。

type point_mut = { mutable x : int; mutable y : int }
let p = { x = 3; y = 3 };; (* ここのダブルセミコロンは省略できないっぽい *)

p.x <- -2 (* レコード更新構文。unit型の値 () を返す *)
p (* { x = -2; y = 3 } *)

unitの話が出てきた。OCamlでは副作用 (side-effect) が普通に扱え、副作用を起こす操作や関数などがよくunit型を返す。レコード更新構文 <- も unit を返すし、標準出力する print_int のような関数は int -> unit のような型を持っている。

ミュータブルなフィールドをもつレコードの実体はヒープ領域に確保されており、プログラムから扱える値はそのIDのようなものを指している (と京都大学の資料に書いてある)。要するに参照なのだろうが、つまり以下のようなことができる。

let p = { x = 3; y = 3 }
let q = p;; (* pとqはヒープ上の同じ物体を参照している *)

p.x <- -2;; (* ヒープ上のレコード実体のフィールドxが-2に書き換えられる *)
p;; (* { x = -2; y = 3 } *)
q   (* { x = -2; y = 3 } *)

ミュータブルなレコードを使って再代入可能な (JSの let に相当する。Rustの let mut も再代入可能だが値そのものの可変性にも影響する) 変数を作れる。これは便利なので ref という名前で最初から使える。

type 'a ref = { mutable contents : 'a }

(* どちらも val x : int ref = {contents = 3} *)
let x = { contents = 3 } (* レコード記法 *)
let x = ref 3 (* ref関数で作る方が手軽。型名と変数名が被る分には全く問題ないっぽい *)

これ「F#を知ってほしい」で見たやつだ！

ref 型はミュータブルなレコードなので x.contents で読み出し x.contents で書き込みできるが、専用の演算子 (!) : 'a ref -> 'a と (:=) : 'a ref -> 'a -> unit が用意されている。

let x = ref 3;;

print_int !x;;
x := 12;;
print_int !x;;

(* 丸かっこで囲むと関数になり部分適用できる *)
let update_x = (:=) x;;
update_x 2;;
print_int !x;;

式をシングルセミコロンで区切って並べると逐次実行になる。

(* y = {contents = 12} *)
let y = x := 33; print_int !x; x := 12; x;;

逐次実行式の値は最後の式 (この例では x) の値になり、それ以外の式の値は捨てられる。JSのコンマ演算子そのものだし、なんとなくRustのブロックにも似ている。最後以外の値は捨てられるので基本的には unit 型の式を置き、2; 3;; のように unit 型以外の式があると Warning 10 [non-unit-statement]: this expression should have type unit. が出る。警告を無視するときには ignore 2; 3;; のようにする。ignore 関数は let ignore _ = () のような、引数を無視して () を返す関数。

if ~ then ~ else ~ 式は then 節がunit型なとき else 節を省略できる。

let is_positive n = if n > 0 then print_endline "positive!"
let is_positive n = if n > 0 then print_endline "positive!" else ()

else が省略可能でかつ;の切断力(?)が強すぎるおかげで、then 節でセミコロンを使うと if がそこで分断されてしまう。

let is_positive n =
  if n > 0 then print_int n;
  print_endline " is positive!" (* ここがifから抜け出てしまう *)

これを回避するために逐次実行を begin と end もしくは丸括弧で囲む。

let is_positive n = 
  if n > 0 then begin
    print_int n;
    print_endline " is positive!"
  end

let is_positive n =
  if n > 0 then (
    print_int n;
    print_endline " is positive!")

これが噂の begin か～と思ってウキウキしてたらフォーマッタが丸括弧に書き直してくる。コミュニティとしてはどっちが主流なんですかね。

リストはセミコロン区切り。

(* int list *)
let l = [1; 2; 3];;

(* int list list *)
[[true; false]; [false; true]];;

リスト 'a list は先頭の要素 'a (head) と残りの配列 'a list (tail) が結合してできている。h :: t でheadとtailを結合して新しいリストを作り、l1 @ l2 でリストどうしを結合して新しいリストを作る。

utop # 12 :: [3; 4; 5];;
- : int list = [12; 3; 4; 5]

utop # [1; 3; 5] @ [2; 4; 6];;
- : int list = [1; 3; 5; 2; 4; 6]

:: はコンストラクタの一種らしい。:: を使って [] 以外のリストに対してマッチできる。

(* int list -> int *)
let rec sum l = match l with [] -> 0 | h :: t -> h + sum t
(* 'a list -> int *)
let rec length l = match l with [] -> 0 | _ :: t -> 1 + length t
(* 'a list -> 'a list -> 'a list *)
let rec append a b = match a with [] -> b | h :: t -> h :: append t b
(* ('a -> 'b) -> 'a list -> 'b list *)
let rec map f l = match l with [] -> [] | h :: t -> f h :: map f t

let two_times = map (( * ) 2)
(* [2; 4; 6; 8; 10] *)
two_times [1; 2; 3; 4; 5]

上で定義した関数の一部は標準ライブラリのListモジュールに入っている。

[ 1; 2; 3; 4 ] |> List.map (( * ) 2) |> List.fold_left ( + ) 0;;
List.length [1;2;3;4;];;

C, Haskellでいう main 関数に相当するような、プログラムのエントリポイントにあたる () という奇妙な名前の関数がある。

let () = print_endline "Konnichiwa~"

OCamlでは別にすべてを関数で書かなきゃいけないわけでもなく、

print_endline "Konnichiwa~"

のようなコードも問題なく動くのだが、これだと

let msg = "koncha~";;
print_endline msg

というように ;; が必要になる場面がある。OCamlではダブルセミコロンはあまり良くないものとしてとらえられているらしく、メインルーチンは let () = に記述することが主流っぽい。

module.ml という名前のソースファイルを作ると、自動的に Module というモジュールが定義される。

amod.ml

let msg = "Hello from OCaml!"

let say_msg () = print_endline msg

bmod.ml

let () = Amod.say_msg ()

open モジュール名 でモジュールの内容物をモジュール名なしで使えるようにする。

open Amod

let () =
  say_msg ()

open するべきか否かというのはモジュールの性質による。List には filter のような被りやすい名前があるのでopenしないし、Printf には printf のように特異的な名前が多いのでopenしがち、というような。

.mli ファイルによってエクスポートするべき物体を選択できる。

たとえば状態 cnt を保持して、increment 関数を使って1足し、print_count 関数で出力するというモジュールを考えてみる。

amod.ml

open Printf

let cnt = ref 0

let increment () = cnt := !cnt + 1

let print_count () = printf "count: %d\n" !cnt

外部から cnt に触れると cnt := 10000 とかやる人間が出てきて困るので、外部モジュールからはこの cnt は隠したい。

そしたら .mli ファイルを書く。

amod.mli

val increment : unit -> unit

val print_count : unit -> unit

外部モジュールからは見えなくなった。

main.ml

open Ocamllearn.Amod

let () =
  print_count ();
  increment ();
  print_count ()

このモジュールを使った状態のカプセル化、クラスのある言語なら

class Amod {
    private var cnt = 0
    fun increment() {
        this.cnt++
    }
    fun printCount() {
        println (this.cnt)
    }
}

のように書くところだ。やっぱりカプセル化はオブジェクト指向とは関係ないんじゃないのか？

モジュールを使って型の詳細を隠蔽することもできる。

amod.ml

open Printf

let cnt = ref 0

(* idは機械的に与えられる *)
type person = { name : string; id : int }

let register_person name =
  let person = { name; id = !cnt } in
  cnt := !cnt + 1;
  person

let print_count () = printf "There are %d registered person.\n" !cnt

let say_name { name; _ } = printf "Hi, I'm %s\n" name

amod.mli

(* 型は存在するが、その内容は隠蔽されている *)
type person

val register_person : string -> person

(* スマートコンストラクタ的な *)
val print_count : unit -> unit

val say_name : person -> unit

main.ml

open Ocamllearn.Amod

let () =
  print_count ();
  let person = register_person "Sakina" in
  print_count ();
  let person2 = register_person "Chiaki" in
  say_name person;
  say_name person2

ファイルに対応したモジュールのほかに、ソースファイル内でサブモジュールを宣言することもできる。struct ってなんだよ。

parent.ml

open Printf

module Counter = struct
  let count = ref 0

  let increment () = count := !count + 1

  let print_count () = printf "count: %d\n" !count
end

main.ml

open Ocamllearn.Parent.Counter

let () =
  print_count ();
  increment ();
  print_count ()

サブモジュールにも .mli ファイルに相当する sig ... end がある。

parent.ml

open Printf

module Counter : sig
  val increment : unit -> unit

  val print_count : unit -> unit
end = struct
  let count = ref 0

  let increment () = count := !count + 1

  let print_count () = printf "count: %d\n" !count
end

モジュールシグネチャは別に宣言してもよい。ここで宣言したシグネチャは別のモジュール宣言に再利用できる。

parent.ml

open Printf

module type Counter = sig
  val increment : unit -> unit

  val print_count : unit -> unit
end

module Counter : Counter = struct
  let count = ref 0

  let increment () = count := !count + 1

  let print_count () = printf "count: %d\n" !count
end

(* Counterと同じインターフェースをもつモジュール *)
module CounterStepby2 : Counter = struct
  let count = ref 0

  let increment () = count := !count + 2

  let print_count () = printf "count: %d\n" !count
end

ファンクタ という機能がある。かなりOCamlの中でも特徴的な機能というイメージを持っている。

ファンクタを一言で表すとモジュールを受け取ってモジュールを返す関数のようなもの。例えば標準ライブラリの Set モジュールには Make というファンクタが定義されている。Set.Make は OrderedType というモジュール型のモジュールを受け取る。OrderedType は以下のようなモジュール型。

OrderedType

module type OrderedType =
  sig
    type t
    val compare: t -> t -> int
  end

Setの要素となる型 t と t に対する比較関数 compare が定義されたモジュールということができる。具体的には以下のようなモジュールが OrderedType に適合する。

parent.ml

module IntSet = Set.Make (struct
  type t = int

  let compare = compare
end)

同じようにして string のSetを定義しよう。string に対する操作は String モジュールに定義されており、t も compare も定義されているのでそのまま与えることができる。

module StringSet = Set.Make (String)

Rustなら Set の型引数には Ord トレイトを実装した型しか入れられないみたいな制約が入っているのだろうが、OCamlはファンクタを使ってアドホック多相なしにこれを実現しているみたいだ。

ところで compare 関数は比較結果に応じて -1 0 1 を返すらしいのだが、あの、Rustみたいにバリアントを使ったりはしないんですか？

StringSetを使ってみる例。パイプライン演算子 |> はF#から逆輸入されたらしい。フォーマット若干変じゃないか？

main.ml

module StringSet = Set.Make (String)

let () =
  StringSet.singleton "Sakina"
  |> StringSet.add "Chiaki" |> StringSet.add "Shiyuki" |> StringSet.add "Kurumi"
  |> StringSet.iter print_endline

ファンクタを定義してみる。

counter.ml

module type Counter_Argument = sig
  val init : int

  val increment : int -> int
end

module type Counter_Type = sig
  val increment : unit -> unit

  val print_count : unit -> unit
end

module Make (X : Counter_Argument) : Counter_Type = struct
  open Printf

  let count = ref X.init

  let increment () = count := X.increment !count

  let print_count () = printf "count: %d\n" !count
end

使ってみる。

main.ml

open Ocamllearn

module Counter1 = Counter.Make (struct
  let init = 0

  let increment = ( + ) 2
end)

module Counter2 = Counter.Make (struct
  let init = 100

  let increment = ( + ) (-1)
end)

let () =
  Counter1.print_count ();
  Counter1.increment ();
  Counter1.print_count ();

  Counter2.print_count ();
  Counter2.increment ();
  Counter2.increment ();
  Counter2.print_count ();

カウンター、よく考えるとこれでよくないか？

type counter = { increment : unit -> unit; print_count : unit -> unit }

let make increment init =
  let count = ref init in
  let increment () = count := increment !count in
  let print_count () = Printf.printf "count: %d\n" !count in
  { increment; print_count }

ファンクタはモジュールを扱えるので、特に型を受け取ったり返したりする場面で使うべきだといえそう。

include を使ってモジュール宣言で既存モジュールの内容を展開できる。同名のモジュールも作れるので、既存のモジュールをシャドーイング的に拡張するのに使える。

main.ml

module List = struct
  include List

  let head l = match l with [] -> None | h :: _ -> Some h
end

module Option = struct
  include Option

  let on_some f opt = match opt with None -> () | Some v -> v |> f |> ignore
end

let () = [ 1; 2; 3 ] |> List.head |> Option.on_some print_int

名前付き引数がある。

普通の関数は以下のような形になる。

let rec range_list first last =
  if first = last then [] else first :: range_list (first + 1) last

let () = range_list 1 4 |> List.iter (printf "%d\n")

名前付き引数には ~ をつける。

let rec range_list ~first ~last =
  if first = last then [] else first :: range_list ~first:(first + 1) ~last

let () = range_list ~first:1 ~last:4 |> List.iter (printf "%d\n")

仮引数部で ~first:value として名前付き引数 ~first の値を value に束縛。実引数部で ~first:value として ~first に value を割り当て。

let rec range_list ~first:a ~last:b =
  if a = b then [] else a :: range_list ~first:(a + 1) ~last:b

名前付き引数は省略可能にすることもできる。~ の代わりに ? をつける。?first:int -> int -> int list というような型がつき range_list 3 のように ~first を飛ばして呼び出すことができる。

let rec range_list ?(first = 0) last =
  if first = last then [] else first :: range_list ~first:(first + 1) last

let () =
  let print_int_endline = printf "%d\n" in
  range_list 4 |> List.iter print_int_endline;
  range_list 4 ~first:(-2) |> List.iter print_int_endline

省略可能引数の使い方がわかってきた気がする。まず、省略可能引数を含む関数は最後に名前なし引数をとる必要がある^[1]。これは、名前なし引数を与えることによって「関数を呼び出す」ことを明示し、部分適用のための省略と省略可能引数の省略を区別するため。

let rec rl ?(first = 0) ~last () =
  if first = last then [] else first :: rl ~first:(first + 1) ~last ()

脚注

省略可能引数1つだけの場合はなくてもよさそう？ ↩︎

仮引数部で ?n としてデフォルト値を与えない場合、関数の実装では option 型が付加される。もちろん省略された場合が None で与えられた場合が Some。

let print_maybe_int ?n () =
  match n with
  | Some n -> printf "The number is %d!\n" n
  | None -> printf "None!\n"

実引数部で ?arg:opt とすると option 型の値を省略可能引数に展開できる。

let print_div x y =
  let result = if y = 0 then None else Some (x / y) in
  print_maybe_int ?n:result

例によって ?arg:arg は ?arg に省略できる。

let print_div x y =
  let n = if y = 0 then None else Some (x / y) in
  print_maybe_int ?n

Rustと異なり、OCamlのバリアントは 型名::コンストラクタ名 ではなくコンストラクタ名をそのまま使える。名前が被っている場合には後に定義されたものが優先される。これは正直微妙な気がする。

type lock = Open | Closed

type door = Open | Closed

(* val d : door *)
let d = Open

多相バリアントについて。一般的に、(列挙型はそういうものなので当たり前なのだが、) lock の Open と door の Open は型から別物である。

しかし、多相バリアントという特殊なバリアントではこれを打ち破れる。なんというか、多相バリアントではそれぞれのコンストラクタが「開かれている」イメージがある。TypeScriptのstring literal型のunionに近いといえばわかるだろうか？

多相バリアントは `Foo という形の式で、本当にそのまま宣言も何もなしに値として使えてしまう。

(* [> `Foo ] *)
let foo = `Foo

ifで分岐すればunionのようになる。

(* bool -> [> `No | `Yes ] *)
let f b = if b then `Yes else `No

(* bool -> [> `Bu | `Shi] *)
let g b = if b then `Shi else `Bu

多相バリアントunionどうしを合体させることもできる。

let h t = match t with true, b -> g b | false, b -> f b

さて、type を使って多相バリアントのユニオンに名前を付けることができる。

type lock = [ `Open | `Closed ]

type door = [ `Open | `Closed ]

これらの型は相互互換性がある。たとえば多相バリアントにパターンマッチする関数には [< `Closed | Open] -> string のような型がつき、[ `Open | `Closed ] と定義されている lock door 両方に適用できる。

let state_of_door d = match d with `Open -> "open" | `Closed -> "closed"

< (より小さい) は「`Closed` `Open 以外がある多相バリアント型を使えない」という意味らしい。

ここで [ `Open | `Closed | `Broken ] をもつ型を定義してみた。

type window = [ `Open | `Closed | `Broken ]

let state_of_window w =
  match w with `Open -> "open" | `Closed -> "closed" | `Broken -> "broken"

state_of_window は [< `Broken | `Closed | `Open ] -> string という型がある。これは `Broken | `Closed | `Open のどれかを受け取る関数である。なので例えば「`Broken | `Closed のどちらか」みたいな値も与えられる。

let (d : door) = `Open

let state = state_of_window d

リリースを見ていこうと思う。

https://ocaml.org/releases/

リリースを見ると先進的な機能がよくわかる気がするので。

OCaml 4.13

Safe points: a multicore prerequisite that ensures that ocamlopt-generated code can always be interrupted.

マルチコア対応らしい。そういえばOCamlはマルチコアに対応してないとかいった話を聞いたことがあるかもしれない。OCaml 5でなんかいい感じになるらしい。

ocamlopt はOCamlコードをネイティブコードにコンパイルするCLI。

https://ocaml.org/releases/4.13.0.html

The best-fit GC allocation policy is the now default policy (and many other GCs improvements.

OCamlはガベージコレクションする。言語処理系実装するならGCにも触れなきゃいけなくなるのだろうか？

Named existential type variables in pattern matching Showable (type a) (x, show : a * (a -> string)) .

言語機能のやつが来た。パターンマッチ中のexistential type variablesがShowableと命名された？existential typeとは？

Let-punning for monadic let: let* x = x in can be shortened to let* x in.

monadic letというものがあるらしい。let* x = x in はHaskellの x <- x に相当するのだろうか？

筑波大学の資料

を読んでいる。初手から処理系を作り始め、

このようにする理由は、時間を節約するためではなく、「処理系を作成することが、そのプログラム言語を本当に理解するための近道である」という考え方による。

という言葉^[1]が飛び出すので面白い。

脚注

引用元: http://logic.cs.tsukuba.ac.jp/jikken/programming.html ↩︎

かんたんな二項演算を評価するやつ。binop で関数を受け取る発想に早々に至ったので関数型プログラミングに~~毒され~~習熟してきたといえるだろうか。

type exp =
  | IntLiteral of int
  | Plus of exp * exp
  | Times of exp * exp
  | Subtract of exp * exp
  | Div of exp * exp
  | BoolLiteral of bool
  | If of exp * exp * exp
  | Eq of exp * exp

type value = IntVal of int | BoolVal of bool

let rec eval2 e =
  let binop f (e1, e2) =
    match (eval2 e1, eval2 e2) with
    | IntVal n1, IntVal n2 -> IntVal (f n1 n2)
    | _ -> failwith "integer expected"
  in
  match e with
  | IntLiteral n -> IntVal n
  | Plus (e1, e2) -> binop ( + ) (e1, e2)
  | Times (e1, e2) -> binop ( * ) (e1, e2)
  | Subtract (e1, e2) -> binop ( - ) (e1, e2)
  | Div (e1, e2) ->
      binop
        (fun n1 n2 -> if n2 = 0 then failwith "division by zero" else n1 / n2)
        (e1, e2)
  | Eq (e1, e2) -> (
      match (eval2 e1, eval2 e2) with
      | IntVal n1, IntVal n2 -> BoolVal (n1 = n2)
      | BoolVal n1, BoolVal n2 -> BoolVal (n1 = n2)
      | _ -> failwith "types unmatch")
  | If (predicate, then_exp, else_exp) -> (
      match eval2 predicate with
      | BoolVal true -> eval2 then_exp
      | BoolVal false -> eval2 else_exp
      | _ -> failwith "predicate is not of type bool")
  | _ -> failwith ""

実行したり表示したりする部分はこんな感じ。

let string_of_value v =
  match v with IntVal n -> string_of_int n | BoolVal b -> string_of_bool b

let () =
  Eq (Plus (IntLiteral 3, IntLiteral 2), IntLiteral 5)
  |> eval2 |> string_of_value |> print_endline

なるほど、環境という名前と値の対応付け一覧を持っておくことで変数が実装できるらしい。

type exp =
  | VarRef of string
  | Let of string * exp * exp
  | IntLiteral of int
  | Plus of exp * exp
  | Times of exp * exp
  | Subtract of exp * exp
  | Div of exp * exp
  | BoolLiteral of bool
  | If of exp * exp * exp
  | Eq of exp * exp

let emptyenv () = []

(* 環境に変数を追加する *)
let ext env x v = (x, v) :: env

(* 環境に変数が含まれているか探す。なかったら例外 *)
let rec lookup x env =
  match env with
  | [] -> failwith "unbound variable"
  | (y, v) :: t -> if x = y then v else lookup x t

めっちゃenvenv書くことになった。

let rec eval3 e env =
  let binop f (e1, e2) env =
    let eval e = eval3 e env in
    match (eval e1, eval e2) with
    | IntVal n1, IntVal n2 -> IntVal (f n1 n2)
    | _ -> failwith "integer expected"
  in
  match e with
  | VarRef x -> lookup x env
  | IntLiteral n -> IntVal n
  | Plus (e1, e2) -> binop ( + ) (e1, e2) env
  | Times (e1, e2) -> binop ( * ) (e1, e2) env
  | Subtract (e1, e2) -> binop ( - ) (e1, e2) env
  | Div (e1, e2) ->
      binop
        (fun n1 n2 -> if n2 = 0 then failwith "division by zero" else n1 / n2)
        (e1, e2) env
  | Eq (e1, e2) -> (
      match (eval3 e1 env, eval3 e2 env) with
      | IntVal n1, IntVal n2 -> BoolVal (n1 = n2)
      | BoolVal n1, BoolVal n2 -> BoolVal (n1 = n2)
      | _ -> failwith "types unmatch")
  | If (predicate, then_exp, else_exp) -> (
      match eval3 predicate env with
      | BoolVal true -> eval3 then_exp env
      | BoolVal false -> eval3 else_exp env
      | _ -> failwith "predicate is not of type bool")
  | Let (varname, varexp, rest) ->
      let env = ext env varname (eval3 varexp env) in
      eval3 rest env
  | _ -> failwith ""

envを試すコードはこんな感じ。

let eval3_with_emptyenv e = eval3 e []

let string_of_value v =
  match v with IntVal n -> string_of_int n | BoolVal b -> string_of_bool b

let () =
  Let ("x", Plus (IntLiteral 4, IntLiteral 3), Plus (VarRef "x", IntLiteral 3))
  |> eval3_with_emptyenv |> string_of_value |> print_endline

Nixで完璧に環境構築できるようになった。

さっき出てきたように無名関数は fun パターン -> 式 という形をとるのだが、function という別タイプもある。

let add = fun x -> x + x
let add = function x -> x + x

function は文法がことなり function パターン1 -> 式1 | 任意の回数繰返し | パターンn -> 式n という形。パターンマッチする関数をちょっと短く書けるし filter などで活躍しそう。

let on_some f opt = match opt with Some v -> f v | None -> None

let on_some f = function Some v -> f v | None -> None

Haskellでいう

onSome f (Some v) = f v
onSome _ None = None

を思い出した。

パターンマッチのとき「v が Some のときその Some なんか をそのまま返す」ようなことがある。OCamlではこれは as を使って達成される。

function
  | None -> parse chars
  | Some _ as r -> r (* ここでrはSome _全体 *)

筑波大学の資料はyacc/lexを使っててなんか面白くないのでパーサコンビネータを実装する。1回F#で実装しているのだけどちょっと違いそう。

長いので折りたたみ

open Containers

let unimplemented name = failwith (name ^ "is not implemented!")

type 'a result = ('a * char list) option

type 'a t = Parser of (char list -> 'a result)

let parse (Parser p) chars = chars |> p

let parse_string (Parser p) s = s |> String.to_list |> p

let get_char = Parser (function [] -> None | c :: cs -> Some (c, cs))

let map f p =
  Parser
    (fun chars ->
      match parse p chars with
      | None -> None
      | Some (v, chars') -> Some (f v, chars'))

let ( <$> ) = map

(** Parser which always succeeds. *)
let pure v = Parser (fun chars -> Some (v, chars))

(** Parser which always fails. *)
let empty = Parser (fun _ -> None)

let apply (p_f : ('a -> 'b) t) p_a =
  Parser
    (fun chars ->
      match parse p_f chars with
      | None -> None
      | Some (f, chars') -> parse (map f p_a) chars')

let ( <*> ) = apply

let ( <* ) xp yp = (fun x _ -> x) <$> xp <*> yp

let ( *> ) xp yp = (fun _ x -> x) <$> xp <*> yp

let product xp yp = (fun x y -> (x, y)) <$> xp <*> yp

let ( let+ ) x f = map f x

let ( and+ ) xa ya = product xa ya

(** If `xp` suceeds returns its result. Otherwise returns `yp`'s one. *)
let either xp yp =
  Parser
    (fun chars ->
      match parse xp chars with None -> parse yp chars | Some _ as r -> r)

(** Binary operator version of `either`. If left parser suceeds returns its result. Otherwise returns right side's one. *)
let ( <|> ) = either

let bind (xp : 'a t) (fp : 'a -> 'b t) =
  Parser
    (fun chars ->
      match parse xp chars with
      | None -> None
      | Some (x, chars') -> parse (fp x) chars')

let ( >>= ) = bind

let ( let* ) x f = bind x f

let satisfy predicate =
  let* x = get_char in
  if predicate x then pure x else empty

let get_two = (fun x y -> [ x; y ]) <$> get_char <*> get_char

let match_char ch = satisfy (Char.equal ch)

let match_lowercase_ascii =
  let p = function 'a' .. 'z' -> true | _ -> false in
  satisfy p

let match_capital_ascii =
  let p = function 'A' .. 'Z' -> true | _ -> false in
  satisfy p

let match_digit =
  let p = function '0' .. '9' -> true | _ -> false in
  satisfy p

let match_latin_ascii = match_lowercase_ascii <|> match_capital_ascii

let match_alphanumetic_ascii = match_latin_ascii <|> match_digit

let match_space =
  let p = function ' ' | '\t' | '\n' | '\r' -> true | _ -> false in
  p

let get_middle = get_char *> get_char <* get_char

let get_string str =
  let rec f = function
    | [] -> pure []
    | ch :: chars ->
        let* _ = match_char ch and+ _ = f chars in
        pure (ch :: chars)
  in
  str |> String.to_list |> f |> map String.of_list

let some (p : 'a t) =
  let* first = p in
  let purep = map Option.pure p <|> pure None in
  let rec inner acc =
    let* ch = purep in
    match ch with None -> pure acc | Some ch -> inner (ch :: acc)
  in
  inner [ first ]

let many p = some p <|> pure []

あれ？Haskellから翻訳してるから先行評価のOCamlだとstack overflowするらしい．は～～～

前にF#で書いたパーサコンビネータではどうやってたか見てみたらrefを使って相互参照していた。

これをOCamlに移植しておおむねOK！！

二項演算子パースしようとするとstack overflowになる～～～

let open Mod in expr で局所的にopenしたり，Mod.f Mod.v を Mod.(f v) と書けたりする機能がある．