プログラミング言語SML#解説

Chapter 15. 型の集合

ML系言語であるSML#は,静的な型推論を装備している. コンパイラは,プログラムの最も一般的な型を推論し,プログラムに含 まれる型を決定した後,プログラムを実行コードにコンパイルする. コンパイルされたコードを実行すると,各変数には,型に対応した値が ロードされる. 本節では,SML#が扱う型の集合を定義する.

型は,単相型と多相型に分類される. 単相型の集合は,以下の文法であたえあれる.

ty ::= tyvar 型変数
 | {(tyrow)?} レコード型
 | tySeq longtycon パラメタ付きデータ型
 | ty1 *  * tyn 組型(n2)
 | ty -> ty 関数型
 | (ty)
tyraw ::= lab:ty (, tyraw)? レコードフィールドの型

tyvarは,型の集合を動く変数である. 第13節で定義した通り'a'fooのように表記 される. longtyconは,datatype宣言で定義される型構成子の 名前であり,宣言されたstructureのパス名で修飾される. 第LABEL:sec:typesAndValues節で説明した基底型は,引数を持たない 型構成子である. ラムダ計算の伝統に従い,関数型構成子->は右結合する. したがって,int -> int -> intと記述すると,int -> (int -> int)と解釈される.

多相型の集合は以下の文法で与えられる.

polyTy ::= ty
 | [tyvarSeq.ty]
 | ty -> polyTy
 | polyTy *  * polyTy
 | { (polyTyrow)? }
polyTyraw ::= lab:polyTy (, polyTyraw)?

この集合は,Standard MLの多相型をランク1多相に拡張したものである. 例えば,以下のような多相型が定義できる.

# fn x => (fn y => (x,y), nil);
val it = fn : ['a. 'a -> ['b. 'b -> 'a * 'b] * ['b. 'b list]]