陽に型付けされた多相言語

• Poly-Tiger は，付録で示した Tiger 言語と異なり，文法 16.2 に示すように，宣言，型，新しい種類の式を持つ．
• Fun-Tiger のように Poly-Tiger は，関数型 $ty\rightarrow ty$ (文法 16.2 では，関数型，複数引数関数型，引数なし関数型)を持つ．
• 関数呼び出しは $exp_f(exp_1,exp_2,\cdots,exp_n)$ で示す ($exp_f$ は，式で識別子のみではない)．
• Poly-Tiger のために，型 $ty$ に，新しく型を示す． poly<a>$T$ は，すべての型 a に対しての型 $T$ を示す．
• 例えば poly<a>a->a は，すべての型 a に対して 型 a をパラメータにとり，返答の型 a となる．
• type $id\:\:tyvars\:\:=\:\:ty$ は，パラメータ型 $id$ を宣言している．右側の $ty$ に出現する型変数は， 陽にパラメータ $tyvars$ を指定しなければならない．
• 例えば，以下の例を示そう．

  
  type list <e>={head:e,tail:list<e>}
  

  list は型ではなく，プログラマによって宣言された 型コンストラクタ(短くは $tycon$)である．しかし，すべての型 $T$ に対し て list<$T$> は型である．
• 多相レコードコンストラクタからレコードを構成するための， 型 instantiation によるレコード生成規則は，レコードフィールドを初期 化する前に，型引数を必要とする．
• 例えば list<int> というレコード型を生成するには，

  
  list<int>{head=4,tail=nil}
  

  と示す．
• instantiation を伴った関数呼び出しにより，多相関数を呼び出す．多 相 append 関数は，以下のように定義することができる．

  
  type list<e> = {head:e,tail:list<e>}
  function append<e>(a:list<a>,b:list<e>):list<e>=
    if a=nil
    then b
    else list<e>{head=a.head,
                 tail=append<e>(a.tail,b)}
  

• append の型は，
  poly<e>(list<e>,list<e>)->list<e> である．
• 2 つの 4 を示すリストを構築してみよう．

  
  var one4:list<int>:=list<int>{head=4,tail=nil}
  var two4s:list<int>:=append<int>(one4,one4)
  

• 整数リストのリストを構築することさえできる．

  
  list<list<int>>{head=two4s,tail=nil}