Dictionary Passing Style

Haskell

desumasuさんがid:desumasu:20070913で触れられてるDictionary Passing Styleについて書いてみようと思います。

参考:栄光のグラスゴーHaskellコンパイルシステム利用の手引

以下のようなテスト用モジュールを実験の為に使用します。

module Test (show2 , show3) where

show2 :: (Show a, Show b) => a -> b -> String
show2 a b = show a ++ ", " ++ show b

show3 :: (Show a) => a -> String
show3 a = show2 a "hoge"

Dictionary Passing Style

Haskellでは多くの場合、多相型の具体的な型への解決は実行時に行われます。(もちろん静的に行われる場合もあります)
例えば、

> show3 True
"True, \"hoge\""

のような呼び出しがどのように行われるかというと、

  1. show3 Trueの呼び出しから、show3の型変数aがBool型であると分かる。
  2. よってshow2の呼び出し時に型変数a, bがBool, String型であると分かる。これにTrueと"hoge"を渡す。
  3. show2内のshowの実行によりBoolに対して定義されたshow,Stringに対して定義されたshowが実行される。

という流れになります。各関数を呼び出す際に、多相型が具体的にどの型になるのかが順次解決されていく様子が分かるかと思います。

こういった実行時のディスパッチは、型づけされていな言語では値そのものに型情報を持たせて行う事がおおいです。
一方、Haskellの場合は静的に型が決定されるので値自身にわざわざ型の情報を持たせる必要がありません。多相型で指定された型についてだけの情報を伝達すればいいので、値そのものに余分なフィールドを用意するなどといった無駄がないわけです。

これを実現する方法がDictionary Passing Styleです。Dictionary Passing StyleについてはHaskellの中間コードを見るとよく分かります。

これから見る中間コードは

  1. パース
  2. 型検査
  3. リネーム
  4. 脱糖

までを行った直後のものです。脱糖というのは糖衣構文を除去した直後の状態で、ここで中間コードを見ると最適化などのかかっていないもとのコードに近い物が見られます。コンパイル時のフラグは-ddump-dsです。

==================== Desugar ====================
Rec {
$dShow_aj0 :: {GHC.Show.Show GHC.Base.Char}
[]
$dShow_aj0 = GHC.Show.$f18
$dShow_aiV :: {GHC.Show.Show [GHC.Base.Char]}
[]
$dShow_aiV = GHC.Show.$f21 @ GHC.Base.Char $dShow_aj0
Test.show3 :: forall a_ada. (GHC.Show.Show a_ada) => a_ada -> GHC.Base.String
[Exported]
[]
Test.show3 =
  \ (@ a_aiJ) ($dShow_aiP :: {GHC.Show.Show a_aiJ}) ->
    __letrec {
      show3_aiK :: a_aiJ -> GHC.Base.String
      []
      show3_aiK =
        \ (a_adi :: a_aiJ) -> show2_aiN a_adi (GHC.Base.unpackCString# "hoge");
      $dShow_aiU :: {GHC.Show.Show a_aiJ}
      []
      $dShow_aiU = $dShow_aiP;
      show2_aiN :: a_aiJ -> [GHC.Base.Char] -> GHC.Base.String
      []
      show2_aiN = Test.show2 @ a_aiJ @ [GHC.Base.Char] $dShow_aiU $dShow_aiV;
    } in  show3_aiK
Test.show2 :: forall a_adc b_add.
              (GHC.Show.Show a_adc, GHC.Show.Show b_add) =>
              a_adc -> b_add -> GHC.Base.String
[Exported]
[]
Test.show2 =
  \ (@ a_aij)
    (@ b_aik)
    ($dShow_aiw :: {GHC.Show.Show a_aij})
    ($dShow_aix :: {GHC.Show.Show b_aik}) ->
    __letrec {
      show2_ail :: a_aij -> b_aik -> GHC.Base.String
      []   
      show2_ail =
        \ (a_adf :: a_aij) (b_adg :: b_aik) ->
          GHC.Base.++
            @ GHC.Base.Char
            (show_aio a_adf)
            (GHC.Base.++ @ GHC.Base.Char (GHC.Base.unpackCString# ", ") (show_aiq b_adg));
      $dShow_aiH :: {GHC.Show.Show a_aij}
      []   
      $dShow_aiH = $dShow_aiw;
      show_aio :: a_aij -> GHC.Base.String
      []   
      show_aio = GHC.Show.show @ a_aij $dShow_aiH;
      $dShow_aiE :: {GHC.Show.Show b_aik}
      []   
      $dShow_aiE = $dShow_aix;
      show_aiq :: b_aik -> GHC.Base.String
      []   
      show_aiq = GHC.Show.show @ b_aik $dShow_aiE;
    } in  show2_ail
end Rec }

まずshow2の引数の部分ですが、

Test.show2 =
  \ (@ a_aij)
    (@ b_aik)
    ($dShow_aiw :: {GHC.Show.Show a_aij})
    ($dShow_aix :: {GHC.Show.Show b_aik}) ->
    __letrec {
      show2_ail :: a_aij -> b_aik -> GHC.Base.String
      []
      show2_ail =
           ... show2の実装

show2の引数が一つ増えている事が分かります。(@ a_aij) .... b_aik})までの部分です。これが辞書です。
つまりDictionary Passing Styleの"Pass"の部分を、"関数の引数として辞書を受け渡す"という方法で行っているわけです。

これはshow2を呼び出しているshow3の実装部分を見るとよく分かります。

      show3_aiK =
	\ (a_adi :: a_aiJ) -> show2_aiN a_adi (GHC.Base.unpackCString# "hoge");
      $dShow_aiU :: {GHC.Show.Show a_aiJ}
      []
      $dShow_aiU = $dShow_aiP;
      show2_aiN :: a_aiJ -> [GHC.Base.Char] -> GHC.Base.String
      []
      show2_aiN = Test.show2 @ a_aiJ @ [GHC.Base.Char] $dShow_aiU $dShow_aiV;

の部分の

show2_aiN = Test.show2 @ a_aiJ @ [GHC.Base.Char] $dShow_aiU $dShow_aiV

の部分でTest.show2に辞書を渡しています。第1要素は多相型a_aiJをそのまま渡し、第２要素は[Char]だと分かっているのでそれを渡しています。そして、show3の実装部分では、このshow2_aiNに実際の引数を渡しています。
(これは関数の第1引数だけ先に渡す、関数の部分適用というやつですね。)
つまり、Haskellの場合は値より先に型が関数に渡されるわけです。値が渡って来てから型が分かる言語と決定的に違うところです。

受け渡される辞書は

@型変数1 @型変数2 @.... $辞書1 $辞書2 ...

という形をしています。辞書の部分にディスパッチすべき関数などが格納されて上位の関数から渡ってきます。

型変数の方はいいとして辞書の方を少し追ってみようと思います。show3内の"hoge"をshowする部分を追ってみます。

$dShow_aj0 :: {GHC.Show.Show GHC.Base.Char}
$dShow_aj0 = GHC.Show.$f18

$dShow_aj0を、GHC.Showの18という番号(18番目という意味ではないらしい)の辞書(ここではChar用の辞書)に束縛。

$dShow_aiV :: {GHC.Show.Show [GHC.Base.Char]}
$dShow_aiV = GHC.Show.$f21 @ GHC.Base.Char $dShow_aj0

GHC.Show.$f21はリスト用のShowの辞書。これにChar用のShowの辞書を渡して、String(==[Char])用のShowの辞書を得ている。

( show3の実装内 )
      show2_aiN = Test.show2 @ a_aiJ @ [GHC.Base.Char] $dShow_aiU $dShow_aiV;

Test2.show2の第2引数は[Char]型で、[Char]用の辞書は$dShow_aiVですよということ。

Test.show2 =
  \ (@ a_aij)
    (@ b_aik)
    ($dShow_aiw :: {GHC.Show.Show a_aij})
    ($dShow_aix :: {GHC.Show.Show b_aik}) ->

$dShow_aixの部分に、[Char]用の辞書が渡ってくる。そして、この辞書から関数showの定義を引っ張ってきて実行すれば[Char]用に定義されたshowが呼び出される。

以上がDictionary Passing Styleの大体の説明です。*1


関数の引数として辞書を渡すという非常にわかりやすい表現になっているうえに、これはとても効率的な方法です。
例えば以下の例だと、Double用のshowの実装を使えばいいとコンパイル時に分かるので一切辞書を受け渡す必要は無く、直接Double用のshowの呼び出しを展開してしまうことができます。実際、GHCはそういった最適化を行ってくれます。

main = putStrLn $ show 1.5

一方値に型を持たせる言語の場合は、実行して値を得るまでは基本的に型が分かりませんから、どうしてもディスパッチ時のオーバーヘッドが出てきてしまいます。

*1:途中で、辞書に辞書を渡すということをしています。実は型クラスもその実態はただの関数だったりするのですが詳しくは省略します。