多相変数の表現

• 型チェックの後に，プログラムは，Poly-Tiger の構造に似た， 陽に型づけされた中間言語に変換することができる．
• Canonicalization(19.7 節で述べられているように，関数的中間言語 に変換される)と最適化(17 〜 19 章)は，型付けされた IR (intermediate representation) で処理されることができる．
• 最後に，命令選択(instruction selection) のための準備をしなければ ならない．
• 多相言語にとって解決しなければならない基本的な問題は， コンパイラが，多相変数にあるデータの型(そのサイズ)を知らないことである．
• append 関数を考えてみよう．

  
  function append<e>(a:list<e>,b:list<e>):list<e>=
    if a=nil
    then b
    else let var x:e:=a.head
             var y:list<e>:=a.tail
         in list<e>{head=x,tail=append<e>(y,b)}
         end
  

• x の型は何でしょう．もし， x がポインタ(レコードや 配列型)であったらガベージコレクションのためのルートを serve すべきであ る．
• もし， x が 整数( int) であったらそうすべきではない．
• もし，倍精度浮動小数点であったら(Poly-Tiger を浮動小数点型を追加 したら)，それを 8 バイトの長さで扱い，ポインタであったら (典型的には) 4 バイトで扱う．
• コンパイラが a.head の値のサイズを知る必要があるのは 明らかである．
• a データをレコードから新しく生成された list レコード にコピーしなければならない．何ビットコピーしなければならないかを知る必 要がある．ガベージコレクションの問題も重要である．
• ガベージコレクションが必要とする 新しい list を生成する「割り当て」(allocation) が呼び出されるとす ると， append の全ての局所変数，コンパイラの一時領域 (temporaries) は，ガベージコレクションのルートである(節 13.7 を参照)．
• a.head が 整数 $i$ であるとすると，ヒープアドレス$i$ から， 到達可能なデータをトレースしようとすると，悲惨なことになる．
• しかし， a.head のコンパイル時の型は，単に e である( append の異なった呼び側で，異なった型に instantiate される 型変数)．
• どのようにして a.head のため異なった型とサイズに，マシンコー ドを関係づけることができるか．
• いくつかの解が存在する．
  1. 展開(Expansion)
     一般的に使われる append<e> 関数のコードを生成しない．その代わり， e がインスタンシエートされた各々の場所で，その型用の append 関数を生成する．
  2. Boxing, tagging:
     すべての値が同じサイズであることを保証し(典型的には 1 ワード)， ガベージコレクションのルートとすることができる．
  3. Coercions:
     異なった型は，異なったサイズであることを許すが，それらを，多相関数へ受 渡す場合は，一定サイズの表現に強制(coerce) する．
  4. Type-passing:
     異なった型は，異なったサイズであることを許す．「多相関数が受渡す型をどう 扱うかを知っている」値と共に，多相関数に型情報を受渡す．
• これら各々で，すべての場合を扱うことができる完全な解である．- あるコンパイラは，展開を使うのみであったり，他のコンパイラでは boxing/tagging を扱ったりする，などである．
• しかし，コンパイラは，ある型に対しては tagging を使い，他の型には coercions を使い，他の場合は type-passing を使い，便利な場合には， 展開を使うといったやり方によりプログラムを最も最適化することができる．
• 以下の節では，これらのテクニックをより詳しく述べる．