多相関数の展開(expansion)

• 多相性への簡単なアプローチは，すべての多相関数を，単相になるまで， インライン展開することである．
• これは Ada の generics と，C++ テンプレートで処理される方式であ る．
• このアプローチの利点は，簡単でかつ効率的なコンパイルモデルである ことである．欠点は，関数が複製され，コードが膨大になることが挙げられる．
• 節 15.4 では，関数のインライン展開を述べた．関数の本体がコピーさ れる．そこでは，定義の仮パラメータが呼び側の実パラメータに置換される．
• このテクニックは，パラメータが値の代わりに，型であるとして機能する ことができる．
• 以下の関数定義を考えてみよう．
  
  $$\hbox{\tt function}\ f<z_1,\cdots,z_k>(x_1:t_1,\cdots,x_n:t_n):t_r=e$$
  
  
  また，関数呼び出し $f<u_1,\cdots,u_k>(a_1,\cdots,a_n)$ を考える．
  
  $$\hbox{\tt let\ function}\ f(x_1:t'_1,\cdots,x_n:t'_n):t'_r = e'\ \hbox{\tt in}$$
  
  
  
  
  $$f(a_1,\cdots,a_n)\ \hbox{\tt end}$$
  
  
  におき換えることができる． ここで， $t'_i=subst(t_i,[z_1\mapsto u_1,\cdots,z_k\mapsto u_k])$ かつ，$e'$ は，$e$ にあるすべての $z_i$ の出現を $u_i$ に置換することに より得られる．
• これは，非再帰関数に対しては，直接的に機能する; ボトムアップに 処理する．しかし，$e$ が $f$ へ の再帰呼び出しを含んでいる場合は，考えるべき 2 つの場合がある．
  1. $f<z_1,\cdots,z_k>$ の形の $e$ にある $f$ の呼び出しは，呼び側の 実型パラメータが $f$ の定義の仮パラメータにマッチする． この場合は，上での let により導入された単相関数 $f$($e$ を書き直 す) を使うようにパラメータを削除することができる．これは， アルゴリズム 16.10 により導入された， 全ての再帰関数呼び出しはこのパターンに従う．
  2. $f$ への再帰呼び出しは，異なる実型パラメータとする．
• 後者の場合は，多相再帰(polymorphic recursion) といい，以下のプロ グラムで説明することができる．

  
  let function blowup<e>(i:int, x:e):e =
    if i=0 then x
    else blowup<list<e>>(i-1,list<e>
      {head=x,tail=nil}).head
  in blowup<int>(N,0)
  end
  

• blowup 関数は，$N$ 個の異なった型: int， list<int>， list<list<int>> など で呼び出されるだろう． blowup の有限のインライン展開では $N$ 個の可能な値をカパーする ことはできない．

• ImplicitPoly-Tiger(ML や Haskell のような) は，多相再帰を許さな い． blowup のような関数は出現しないので単相コードへの完全な展開 は可能である．しかし total なインライン展開は，Poly-Tiger では機能し ない．
• また展開が機能するような言語においても，分割コンパイルをした場合は， 難しい．しばしば，宣言された関数をコンパイルしようとするが， 呼び出し側では，再コンパイルできない．