再帰的データ型

• Tiger では，バリアント，レコード型は，再帰かもしれ ない．言語はリストや木を構築するために再帰型の形式を持たなければならない．
• 例えば，以下のパラメータ化された型は，等しいかどうか:

  
  type list<a>={head:a, tail:list<a>}
  type sequence<a>={head:a, tail:sequence<a>}
  

• レコード distinction 規則によりこの疑問を横によけた． つまり，異なった位置で宣言されたレコード型は，区別した． 簡単で，手際のよい解である．
• Unique $tycons$ がこの区別のために使われた(この章の最初で 説明した)．

広域レコードフィールド

• Tiger 言語では，異なったレコード型で，同じフィールド名を使うかも しれない． p.x をコンパイルする場合， p のレコード型はフィー ルド x を検索する前に知られていなければならない．
• しかし ImplicitPoly-Tiger では p.x のような式は， p の型を知らない前に，型チェックされなければならない． その場合は p のメタ変数を持つのみである．
• それゆえ ($x$ のような) フィールド名は，広域(global) スコー プをもつことを必要とする．
• レコード宣言，レコード生成式，フィールドセレクションのための型チェッ ク規則は，アルゴリズム 16.11 で示す．
• $ty$ の新しい種類を必要とする．
  
  $$ty\rightarrow\hbox{\bf Field}(ty,ty)$$
  
  
  $\hbox{\bf Field}(t_{id},t)$は，レコード型 $t_{id}$ に対して，型 $t$ のフィールドを意味する．
• フィールド名の広域化は喜ばしいことではない．なぜなら同じフィール ド名を 簡単に 2 つの異なったレコード型で用いることができないためである．
• しかし，これは Tiger の フィールドセレクションにおいて， 自動的に型推論を処理するための交換的な価値である．
• ML 言語では，この問題のために異なった方法で解決している． レコード型における広域フィールド名の代わりに，データ型における広域 データコンストラクタを用いている．
• そのため，ML では，同じデータコンストラクタ名を 2 つの異なった型 で用いることはできない．
• head のような Field は，多相的で，以下のようになる．
  
  $$\hbox{\bf Poly}([\beta],\hbox{\bf Field}(\hbox{\bf App}(\hbox{\tt list},[\beta]),\beta))$$
  
  
  これは，型 list<$\beta$ > のレコードから型 $\beta$ の値を選 択する．
• フィールドが式で使われる場合，多相関数のように， instantiate されるに違いない．