言語処理系勉強会に参加してきた

κeenです。言語処理系勉強会 Vol.1 に参加してきました。そこでの@omochimetaruさんのSwiftのGenericsとProtocolの実装の話が面白かったので少し感想を。

Javaのジェネリクスは型消去で実装されており、全てのジェネリクスを1関数でまかなえます。一方で統一的に扱うために参照型しかジェネリクスに使えず、プリミティブの取り回しに苦労します。 C++のテンプレートやRustのジェネリクスは型毎に実装を作るのでどんな型でも扱えますし、高速です。代わりに関数の数が増えてバイナリサイズが大きくなりがちです。 Swiftはその中間ようなアプローチを取っていました。

Swiftのジェネリクスの話を要約すると、

• ジェネリクス関数には値型も全て参照になって渡される。ただし型のメタデータ(Metatype)を渡してゴニョゴニョして失われた型情報(Value Witness Table)を補完している
  • つまり1つ引数が増える
• プロトコル準拠の制約が入ったジェネリクスにはその型のプロトコル実装情報を渡して(Protocol Witness Table)いる
  • つまりもう1つ引数が増える

ここまではSwiftコンパイラの仕事。 そして後段のLLVMが最適化をする。 VWTやPWDはコンパイル時には分かっている静的情報なのでLLVMは部分評価をしてそれぞれの型に合わせたコードを生成する。 なのでSwiftが吐いたLLVM IRでは参照渡しになっていても実際に生成されるコードが生成渡しになるとは限らない。

この話を聞いてものすごく筋のいい実装だなと思いました。 コンパイラは往々にして複雑になりやすいので「機能を効率的に実装」しようとすると泥沼になってしまいます。 故に「機能を実装する」と「それを効率的にする」は分けた方が開発効率の面で有利です。 Swiftの場合はさらに「機能を実装する」の部分をSwift開発者が、「それを効率的にする」の部分をLLVMに投げています。 これが本当に重要で、関心への集中を実現できています。 すなわち、Swiftコンパイラの作者にしかできない「Swiftに機能を追加する」ことだけをやってそれを効率的にする部分はありものを流用しているのです。 本当にお手本のようなエンジニアリングだなと思いました。まる。

ところでC++やRust、Javaの筋が悪いかというとそういうわけでもありません。 C++やRustはシステムプログラミング言語としてゼロオーバーヘッド原理を実現したいので「設計上」そういう選択をしたのだと思います。 また、Javaは登場当初はジェネリクスが入っておらず、後にジェネリクスが入りました。 Javaは後方互換性を大事にしているのでバイトコードへの大幅変更が必要ない今の方式が採用されたのだと聞いています。 それぞれの言語に各々の正しいエンジニアリングが存在するのでしょうが、多くの高級言語にとってはSwiftのようなアプローチがお手本になるのかなと思います。

追記: こういう話が好きな方は是非言語実装 Advent Calendar 2018に記事を書いて下さい。