Arantium Maestum

プログラミング、囲碁、読書の話題

簡単な型システムを実装していく6 STLC+Bool+Nat+Let+Record

前回のLetまで実装した型システムにレコードを追加する。

gist.github.com

レコードというのは{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がエラーを投げる。

次回

次回はバリアント(直和型)を実装する。