Hindley Milner型推論に機能を追加していく２ Bool型の追加

前回の記事に続いてHM型推論を少し拡張する。

今回はBool型を追加し、Boolのリテラル式二つとIf式を実装する。

型

Bool型を追加：

type ty =
...
| TBool

式

True、False、If式の追加：

type exp =
...
| ETrue
| EFalse
| EIf of exp * exp * exp

If式は条件式、条件が真の場合の式、条件が偽の場合の式の三つの式を持つ。

typeof

まずTrueとFalse：

let rec typeof env level = function
...
| ETrue | EFalse -> TBool

これらリテラル式に対するtypeofは当然TBoolになる。

If式：

| EIf(cond,e1,e2) ->
  unify (typeof env level cond) TBool;
  let te1 = typeof env level e1 in
  unify te1 (typeof env level e2);
  te1

まず条件式がBool型であること（あるいはBool型に単一化できること）をunifyを使って確認し、その後他の二つの式の型が同一であることも確認してからその型を返す。

今までunifyはmatch_fun_tyからのみ呼ばれていたが、これから式を追加していくにつれてtypeofのいろんな部分で使われることになる。

それ以外

上記以外の関数については前回TUnitを追加したところにTBoolも追加するだけ：

let rec generalize level ty = match ty with
...
| TUnit | TBool -> ty

let instantiate level ty =
  let id_var_hash = Hashtbl.create 10 in
  let rec f ty = match ty with
  ...
  | TUnit | TBool -> ty
  in f ty

let rec match_fun_ty tfunc targ = match tfunc with
...
| TUnit | TBool -> failwith "Non-arrow type found in function position"

let rec occursin id = function
...
| TUnit | TBool -> false

let rec adjustlevel level = function
...
| TUnit | TBool -> ()

まとめ

If式のtypeof以外は特に真新しいところはなし。

次回

次はInt型とAdd、IsZero式を追加する。

今回のコード

gist.github.com