Hindley Milner型推論に機能を追加していく１３ Listの追加（後編）

前回に続いてList追加の実装を見ていく。今回はtypeofで使われるヘルパ関数について。

match_list_ty

前回見ていったtypeof関数で新しく使われたmatch_list_tyは「tyをとりリスト型と単一化させた上でそのリスト型が保持している型を返す」という関数。EHeadのケースが一番わかりやすい：

typeof env level = function
...
| EHead e -> match_list_ty (typeof env level e)

他のmatch...ty関数と同じく、引数にとったtyに対してパターンマッチしている：

let rec match_list_ty ty = match ty with
| TList ty -> ty
| TVar {contents=Link ty} -> match_list_ty ty
| TVar ({contents=Unbound(_,level)} as tvar) ->
  let ty = new_tvar level in
  tvar := Link(TList ty);
  ty
| TVar {contents=Generic _} -> failwith "Generic type encountered, expecting list or instantiated variable"
| _ -> failwith "Non-list type found in list position"

処理としてもmatch...tyのおなじみ。

まだ単一化されていない型変数だった場合は「中身の型」のための型変数を新しく作成してからそれを持ったTList型を作り、引数のtyをそのTListにリンクさせてから「中身の型」を返している。

is_simple

Value restrictionのため、ある式が汎化してもいい「簡単な値」かを調べるis_simple関数は式に対してのパターンマッチなので、Listのために追加した５つの式に対応させる必要がある。

まずENil：

let rec is_simple = function
... | ENil -> true

当然ENil（OCamlでいうところの空リスト[]）はsimple。

ECons：

...
| ECons(e,elist) -> is_simple e && is_simple elist

二つの式をConsしている場合、両方の式がsimpleならECons式もsimple。

これはOCamlの挙動とも合致する：

utop # let f = let x = 1::[] in fun () -> (x, ref []);;
val f : unit -> int list * 'a list ref = <fun>
utop # let f = let x = (ref 1)::[] in fun () -> (x, ref []);;
val f : unit -> int ref list * '_weak1 list ref = <fun>

（'_weak1のような全称化されていない型変数が出てくるかどうかで(ref 1)::[]の部分がsimpleかどうかが判定できる）

EIsNil、EHead、ETail：

| EIsNil e | EHead e | ETail e -> is_simple e

これらは（リストであるはずの）式を一つ保持する式なので、その「中身の式」がsimpleならsimple。

OCamlではこれらはList.hdなどの関数で表されるが、その場合は引数がなんであれsimpleだとみなされない：

utop # let f = let x = List.tl [1] in fun () -> (x, ref []);;
val f : unit -> int list * '_weak1 list ref = <fun>

しかしパターンマッチでならsimpleになる：

utop # let f = let x = (match [1] with x::_ -> x | [] -> 0) in fun () -> (x, ref []);;
val f : unit -> int * 'a list ref = <fun>
utop # let f = let x = (match [1] with _::x -> x | [] -> []) in fun () -> (x, ref []);;
val f : unit -> int list * 'a list ref = <fun>

この記事の実装では関数でもパターンマッチでもなく言語自体が提供する構文となっているが、その場合はパターンマッチと同じく「中身がsimpleならsimple」でいい。List.hdの場合は「関数の中身まで辿れないので関数適用はすべてnot simple」というロジックに従っているだけで「リストの先頭をとる」という処理自体がnot simpleなわけではない。

その他

その他のヘルパ関数はいつもどおりTListのためのケースを追加していくだけ。

一例としてgeneralize：

let rec generalize level ty = match ty with
...
| TList ty -> TList (generalize level ty)

次回

次回からはListなどをユーザが自分で定義できるような機能を追加していく。まずは再帰型、その次はユーザが定義できる型コンストラクタが必要になる。