プログラミング言語SML#解説 3.7.1版
9 SML#の拡張機能:その他の型の拡張

9.2 ランク1多相性による値多相性制約の緩和

MLの多相型システムは,第7.13節で学んだ手続き的 機能を導入すると,整合性が崩れることが知られています. 例えば参照型構成子refは,任意に型の参照を作ることができる ので,MLの型システムの原則に従いナイーブに導入すると,以下のような多相 型を持つように思います.

val ref : [’a. ’a -> ’a ref]
val := : [’a. ’a ref * ’a -> unit]

しかし,この型付けのもとでMLの型推論を実行すると,以下のようなコー ドが書けてしまい,型システムが破壊されていまいます.

val idref = ref (fn x => x);
val _ = idref := (fn x => x + 1);
val _ = !idref "wrong"

まず1行目でidrefの型が[’a.?(’a -> ’a) ref]と推理さ れます. この型は(int -> int) refとしても使用できる型です. また,代入演算子:=も多相型を持ちますから (int -> int) ref型とint -> int型を受け取ることができます. 従って2行目の型が正しく受け付けられ実行されます. この時idrefの値はint -> intの値への参照に変更されて いますが,その型は以前のまま[’a. (’a -> ’a) ref]です. 従って3行目の型が正しく,実行されてしまいますが,その結果は,算 術演算が文字列に適用され実行時型エラーとなります.

この問題を避けるために,MLでは,

多相型を持ち得る式は値式に限る

という値多相性制約が導入されています. 値式とは,計算が実行されない式のことであり,定数や変数,関数式 fn x => x,それらの組などです. 関数呼び出しを行う式は値式ではありません. たとえば,ref (fn x => x)はプリミティブrefが呼び 出されますから値式ではありません. この制約によって,関数呼び出しの結果に多相型を与えることが禁止さ れます. これによって,参照を作り内部に参照を含むref (fn x => x)の ような式は多相型を持てなくなり,上記の不整合が避けられます.

SML#もこの制約に従っています. しかし,SML#では,多相型が組の要素や関数の結果などの部分式 にも与えることができるため,この値式制約が限定されたものとなり,ユーザに とって大幅にその制約が緩和される効果があります. 例えば以下の関数定義と関数適用をみてみましょう.

val f = fn x => fn y => (x, ref y)
val g = f 1

Standard MLの型システムでは,関数fには

val f = _ : [’a, ’b. ’a -> ’b -> ’a * ’b ref]

のような多相型があたえられますが,この関数の適用f 1の結果に現れる 型変数を再び束縛することは値多相性制約に反しますので,gには多相型 を与えることができません. これに対してSML#では,ランク1多相性により,この関数に以 下の型が推論されます.

val f = _ : [’a. ’a -> [’b. ’b -> ’a * ’b ref]]

この結果の型に対して推論された多相型は,関数適用の前に推論された ものであり,関数適用の結果に対して推論されたものではありません. 従って,関数適用の結果はその多相型に’aの実際の値が代入され た以下のような多相型となります.

val g = _ : [’a. ’b -> int * ’b ref]