2009-07-07 [長年日記]
λ. “Types are calling convensions” by Max Bolingbroke and Simon Peyton Jones
Types are Calling Conventions | Lambda the Ultimate より。 積読中だったんだけど、Chatonの haskell-ja > Archives > 2009/07/06 で出てきたので読んでみた。
Haskell の関数はカリー化されているとはいえ、実際に実行時に一引数渡して関数を返してまた一引数渡して……なんてやっていたら遅くて仕方がないので、実際には引数を出来るだけまとめて渡している。 一方で、複数の値を返すときにはタプルで返すように書くけれど、実際にタプルをヒープ上に確保してなんてやっていたら遅くて仕方がないので、これも出来る限り複数の値を直接返すようにしている*1。 それに出来るだけ非ボックス化して渡したり、他にも色々あるのだけど、こうした呼び出し規約の最適化をGHCは非常にアドホックな形で行っている。
これはあまりよろしくないので、これらの呼び出し規約の違いを型で自然に表現出来るような中間言語 Strict Core を導入し、そうした最適化を安全かつシステマティックに出来るようにしようという話。
Strict Core は名前が示すように正格な言語で、また関数が多引数・多出力になっている。 Strict Core では、評価済みのIntとBoolを一度に受け取って、評価済みのIntを二つ返すような関数の型は 〈Int, Bool〉→〈Int, Int〉 になるし、引数を一つずつ受けとるような関数の場合には 〈Int〉→〈〈Bool〉 → 〈Int, Int〉〉 といった感じの型になる。また、サンクは{Int, Bool}のような型になる*2。 以下では表記をわかりやすくするため、引数・返り値が一つの場合には山括弧は省略することにする。
そうすると、例えば以下のように呼び出し規約を型で書き分けることが出来る。 ただし、丸括弧で囲まれているのはヒープ上に確保されたタプルを表す単一の値の型。
- f1 : Int → Bool → (Int, Bool)
- f2 : 〈Int, Bool〉 → (Int, Bool)
- f3 : 〈(Int, Bool)〉 → 〈Int, Bool〉
- f4 : 〈{Int}, Bool〉 → (Int, Bool)
それで、Haskell(のサブセット言語)を Strict Core に変換して、その上で各種の最適化を行うのだけど、型として違いがわかると確かにわかりやすい。
示されている最適化は基本的に現在のGHCでも(アドホックながら)実装されているものなのだけど、6.2の Use-site arity raising だけは現在のGHCでは行っていない。 これは例えば zipWith : 〈{a} → {b} → c, List a, List b〉 → List c という関数の worker-wrapper 変換で、〈〈{a}, {b}〉→c, List a, List b〉 → List c という型の worker と、関数引数のarityの変換するようなwrapperへと変換するもの。 これは従来の動的なarityの検査*3の代替になりうる。
