簡単な型システムを実装していく6 STLC+Bool+Nat+Let+Record
前回のLetまで実装した型システムにレコードを追加する。
レコードというのは{x=1; y=true}
のような値にラベルのついたデータ構造。ちなみにタプルは型システム的にはレコードの亜種と考えていい(ラベルが0~の整数だと見做せる)。どちらも代数的データ型における直積型。
ただし処理系の内部実装的には、レコードがタプルに脱糖されることも多いと思う(OCamlがそう)。型検査の前に脱糖してしまうと{x:bool; y:int}
と{a:bool; b:int}
が同じ型になってしまうので、タプルへの脱糖は型検査の後にならざるを得ない。
型
レコード型を追加:
type ty = ... | TRecord of (string * ty) list
「ラベル(を表す文字列)とその型の対」のリストとして表される。
式
レコードを表す式ERecord
とレコードのフィールドにアクセスするEProj
(Projectionの意):
type exp = ... | ERecord of (string * exp) list | EProj of exp * string
ERecord
はラベルと式の対のリスト(TRecord
がラベルと型の対のリストだったのと対応している)、EProj
はレコードとして評価されるはずの式と、それに対してアクセスされるラベルの文字列で構成されている。
typeof
関数
新しい二つの式のケースをtypeof
のパターンマッチにも追加する。
まずはERecord
:
let rec typeof env = function ... | ERecord les -> TRecord (List.map (fun (l,e)->(l, typeof env e)) les)
ERecord
はラベルと式の対のリストなので、一つ一つのラベルと対になっている式の型を調べて行って、ラベルと型のリストであるTRecord
型を返す。
EProj
:
| EProj(e,l) -> (match typeof env e with | TRecord(lts) -> List.assoc l lts | _ -> failwith "record type expected")
まずアクセスされる式が実際にレコード型かどうかを調べる(レコード型じゃない式に対してのフィールドアクセスはエラー)。レコード型であれば、アクセスされるラベルと対になっている型を返す。もしラベルが存在しない場合はList.assoc
がエラーを投げる。
次回
次回はバリアント(直和型)を実装する。