Goのinterfaceは明示的に実装を宣言せず、実装側がinterfaceのシグネチャを満たしているかによって型が決まるDuck typingを採用していると言われています。私は当初このような説明を聞いたときにピンと来ず、むしろそれはTypeScript等に見られるStructural Typingなのでは？と思いました。
しかし実際にデータ構造を調べて見ると、確かにDuck typingであり、かつStructural Typingでもあるという考えに至りました。
これまでなかなかGoのデータ構造に触れる機会がありませんでしたが、調べてみるとこれまで気づかなかった観点がいくつも出てきたのでぜひ紹介したいと思います。
Duck typingについて
今回の主題となる部分ですので、Duck typing(ダックタイピング)についておさらいします。
Duck typingはアナロジーである「ダックテスト」に端を発しています。(厳密な起源は不明?なようですが、達人プログラマとして知られるDave ThomasによりRubyコミュニティで生まれた概念とされています。)
If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck.
もしもアヒルのように見え、アヒルのように泳ぎ、アヒルのように鳴くのなら、それはアヒルなのだろう
これは例えばJavaであればオブジェクトの型がコンパイル時に検証されるのに対して、Rubyではランタイム時にインターフェースを持っているかが検証されるため、柔軟にポリモーフィズム(多態性)を実現できるというものです。
class Duck
def cry
puts 'duck'
end
end
class Cat
def cry
puts 'cat'
end
end
def cry(obj)
obj.cry
end
cry(Duck.new) # -> cry
cry(Cat.new) # -> cat
上記のRubyのコードはDuckとCatとで共通のスーパークラスを持たないクラスのインスタンスですが、cryメソッド内ではどちらも同じように鳴かせることができました。
これがJavaであれば明示的にimplementsを宣言するか、共通のスーパークラスを持つ必要がありますが、Duck typingにおいては実装側に明示的な宣言がないのが特徴です。どのクラスに属しているかというよりも、オブジェクトが実際にどのような性質を持っているかに注目するという点で、まさに「アヒルのように見えればアヒルである」というアナロジーにマッチしています。
Nominal TypingとStructural Typing
本題に入る前にもう少し型システムについて説明します。型システムにおいてNominal TypingとStructural Typingという分類があります。
Nominal Typingの「Nominal」とは「名目上の」と言う意味で、型の内部構造よりもその型が何であるかによって区別します。対してStructual Typingはその名の通り、型の構造によって区別されるものです。
文字での説明よりも実際にコードを見たほうがわかりやすいので、まずはNominal TypingとしてJavaのコードを以下に示します。
// Javaのサンプルコード
class FirstName {
String value;
FirstName(String value) {
this.value = value;
}
}
class LastName {
String value;
LastName(String value) {
this.value = value;
}
}
class Main {
static void callName(FirstName name) {
System.out.println(name.value);
}
public static void main(String[] argv) {
callName(new FirstName("takeshi")); // OK
callName(new LastName("gouda")); // Error!
}
}
FirstNameとLastNameはどちらのメンバ関数を持たず、valueというプロパティがあり、同一の内部構造を持ったクラスです。しかしFirstNameを引数に取る関数に対しては、FirstNameのインスタンスしか受け付けないという性質を持っています。もしもSecondClassのインスタンスを利用したい場合は、FirstClassのコンストラクタを通してからでないとコンパイルが通りません。
対してStructural Typingの性質を持つTypeScriptでは異なるクラスのオブジェクトでも、内部構造が同じであればエラーが検出されません。(※厳密にはJavaScriptのクラスは糖衣構文ですが、ここではその説明は割愛します)
// TypeScriptのサンプルコード
class FirstName {
value: string;
constructor(value: string) {
this.value = value;
}
}
class LastName {
value: string;
constructor(value: string) {
this.value = value;
}
}
const callName = (name: FirstName) => console.log(name.value);
callName(new FirstName("takeshi")); // OK
callName(new LastName("gouda")); // こっちもOK!
Nominal Typingに慣れている方からすれば不思議に感じるかもしれませんが、 TypeScriptでは型の構造に着目するため、異なるクラスのインスタンスであってもコンパイルが通るのです。
お気づきの方がいるかもしれませんが、Duck typingとStructural Typingはとても似ています。実際にTypeScriptを使ってDuck typingらしいコードを書いてみましょう。
type Duck = {cry: () => void, swimSpeed: number};
type Cat = {cry: () => void};
const cry = (obj: {cry: () => void}) => obj.cry();
const duck: Duck = {cry: () => console.log('Duck'), swimSpeed: 2.0};
const cat: Cat = {cry: () => console.log('Duck')};
cry(duck);
cry(cat);
Duck型とCat型の異なるタイプを持つオブジェクトですが、cryの型構造が同じであるために同一の関数に渡すことができました。
オブジェクトの振る舞いに注目しているという点で実質的にDuck typingに見えますが、Duck typingはランタイム時に動的にアクセスされるのに対して、Structural Typingは静的な型システムである点で異なります。ただしDuck typingとStructural Typingは対立する概念ではないので、明確に区別する必要があるかというと考えものですが。
GoにおけるStructural Typing
冒頭で触れた通り、Goは明示的な宣言を必要とせず、実装側がinterfaceのシグネチャを満たすことでポリモーフィズムを実現するので、Structural Typingの性質を持っています。
type Duck interface {
cry()
}
type Cat struct {
}
func (c Cat) cry() {
fmt.Println("Cat")
}
func cry(obj Duck) {
obj.cry()
}
func main() {
cry(Cat{})
}
InterfaceのDuckはcry()というメンバ関数を持ち、本来Duckとして扱うべきものではなくても、CatはDuckのシグネチャを満たすことでDuckとして扱うことができます。
RubyやPythonといった動的型付け言語と異なりシグネチャのチェックはコンパイル時に行われるので、もしもCatにcryメソッドがなければコンパイルに失敗します。そのため静的な型付けという面でStructural Typingの性質を持つと言えます。
ではなぜGoはDuck typingと言われるのかと疑問に思うかもしれませんが、それは後ほど説明します。
Nominal TypingとStructural Typingの両立
Nominal TypingとStructural Typingを対立構造のように紹介したままでは、誤解を招くかもしれないと思い、少し補足的な説明を加えさせて頂きます。
NominalとStructuralは言語につきどちらか一方しか実現できないわけではなく、Goはいずれの性質を持っており、他にもScalaやTypeScrip等でも実現可能です。
// Goのサンプルコード
type Duck struct {
cry func()
}
type Cat struct {
cry func()
}
func cry(obj Duck) {
obj.cry()
}
func main() {
cry(Duck{}) // OK
cry(Cat{}) // NG!
}
InterfaceではなくStructを利用する場合はNominalに型がチェックされるため、同じ構造でもコンパイル時にエラーが検出されます。むしろポリモーフィズムを意識しない場合、多くはNominalにチェックされるでしょう。
ちなみにTypeScriptはNominal Typingを言語機能としてサポートして欲しいという意見が長らく出ていますが、実装者が少し工夫をすることでNominalを実現することができます。例えばDDDを実践したいといった場合には有用になるでしょう。
なぜGoはDuck typingと言われるのか
ここまでDuck typingはランタイム時、Structural Typingは静的な型システムであると説明しました。そしてGoはコンパイル時にシグネチャがチェックされるためStructural Typingでありながら、なぜDuck typingとも言えるのでしょうか。
それはInterfaceによるポリモーフィズムを実現する際、Goはitable(Interface table)に動的にデータ構造を生成するという特徴を持っているためです。
例えばC++ではVirtual method table(vtable)と呼ばれるlookupのためのデータ構造をコンパイル時に作成するのに対して、Goはシグネチャのみを事前にチェックし、lookupは動的に行われるという点で異なります。これはアプリケーションレベルのコードを書いているときにはあまり意識されないことでピンと来ないかもしれませんので、詳しく追っていきましょう。
Virtual method table(vtable)について
Goのitableに入る前に、まずはvtableについて説明します。
vtableは通常、Subtypingによるポリモーフィズムのため、動的なディスパッチを実現するためのものです。具体的にはあるクラスがスーパークラスを継承している場合、そのクラスのメンバ関数がどちらに属するものなのかを通常コンパイル時に解決します。
// Javaのサンプルコード
class Animal {
void cry() {
System.out.println("cat");
}
void swim() {
System.out.println("swim");
}
}
class Cat extends Animal {
@Override
void cry() {
System.out.println("cat");
}
}
class Main {
public static void main(String[] argv) {
Animal cat = new Cat();
cat.cry(); // -> Catクラスのcryが呼ばれる
cat.swim(); // -> Animalクラスのswimが呼ばれる
}
}
上のサンプルコードでは、CatのインスタンスをAnimalクラスとして宣言しています。これはポリモーフィズムのうちSubtyping(部分型付け)と呼ばれ、派生型も継承元の型として扱うことができる性質によるものです。
Catクラスのインスタンスを通じてcryとswimを呼んでいますが、cryはCatクラスの実装が、swimはAnimalクラスの実装が呼ばれます。これはコンパイル時にvtableと呼ばれるデータ構造を生成し、cryの場合はCat->cryのポインタを、swimの場合はAnimal->swimのポインタを保持することで実現されます。
Goではランタイム時にディスパッチが動的に行われる
Goの場合もvtableによるディスパッチの仕組みは同じです。しかし静的型付け言語では上記のようなディスパッチは通常コンパイル時に解決されるのに対して、Goではランタイム時に行われます。そしてこれがDuck typingと言われる理由だと解釈できます。実際にGoのDeveloperであるIan Lance Taylorの記事を見ても分かります。
This is not pure duck typing, because when possible the Go compiler will statically check whether the type implements the interface. However, Go does have a purely dynamic aspect, in that you can convert from one interface type to another. In the general case, that conversion is checked at runtime.
(訳: これは純粋なダックタイピングではありません。なぜならGoのコンパイラは可能なら型がインターフェースを実装しているかを静的に解釈しようとするからです。一方でGoは純粋に動的な側面もあり、あるインターフェースから別のものに変換する際、ランタイム時に動的に変換が行われます。)
それでは実際にサンプルコードを使ってこの動きを説明していきます。
type Animal interface {
cry()
}
type Cat struct {
}
func (c Cat) cry() {
fmt.Println("cat")
}
func (c Cat) swim() {
fmt.Println("swim")
}
func cry(obj Animal) {
obj.cry()
}
func main() {
cry(&Cat{})
}
CatはAnimal型のシグネチャを満たしており、Animal型を引数に取るcryメソッドに渡すことができ、もしもCatがシグネチャを満たしていなければコンパイルに失敗します。
Goは明示的にimplementsを宣言しないため、全てのStructがどのInterfaceを満たしているかを逐一チェックしているのではないかと思われるかもしれません。M個のInterfaceに対してN個のStructがある場合、M×N回数のチェックが必要になると多くの計算量が求めれますし、ほとんどが使われないので事前にデータ構造を作成するのは効率的ではありません。
Goはこれを動的に解決しているので必要になった時のみ、itableと呼ばれる専用のデータ構造を生成し、lookupを行います。また毎回データ構造を作成するのはコストになるため、一度生成されたものはハッシュテーブルに格納され、次回からは生成済みのものが再利用されるようになっています。
Goの実装について
これらの実装はiface.goに書かれているので、簡単に内容を紹介していきます。
var (
itabLock mutex // lock for accessing itab table
itabTable = &itabTableInit // pointer to current table
itabTableInit = itabTableType{size: itabInitSize} // starter table
)
type itabTableType struct {
size uintptr // length of entries array. Always a power of 2.
count uintptr // current number of filled entries.
entries [itabInitSize]*itab // really [size] large
}
(※コードはバージョン1.13.4時点のものを掲載しています)
itableはinterfaceとそれを実装する変数のペアから生成され、itabTableType型のitableTableに格納されていきます。その中のフィールドであるentriesがハッシュテーブルの役割を果たしており、デフォルトでは512のサイズを保持しています。
まずはinterfaceと変数のペアをもとに、entriesからitableを探索します。探索方法は少し複雑ですが以下のようなステップで行われます。
- interfaceと実装変数、およびitableTableのサイズを使ったビット演算で初期キーを生成する
- entriesのポインタと組み合わせてハッシュのキーを生成する
- そのキーに当たる値がなければitableを新たに生成するフローに入る
- 既に値があり、それが現在探しているinterfaceと変数に合致すれば、キャッシュ済みの値としてそれを返す
- 他の値とキーが衝突している場合は、ループしながらQuadratic probingの手法で空いている番地を探していく→3に戻る
itableの生成処理
では上記の「3」のフローにおいて、itableを生成する際にどのような処理が行われているのでしょうか。
func (m *itab) init() stringという関数がこれにあたり、実際にコードを掲載しながら紹介したいのですが、分量が多いのでこの項では割愛します。興味のある方はこちらのリンクからチェックしてみてださい。
大まかに説明すると、itableはinterfaceと変数の型と、実装メソッドのポインタ配列の先頭を持ちますが、キモとなるのは実装メソッドのポインタ配列を作る部分です。
interfaceと変数が持つメソッドを参照しながら、interfaceの各メソッドにあたる実装のポインタを配列に格納していきます。(メソッドが合致するかどうかはメソッドの名前やパッケージの状態によって判別されます)
ここで保持されるのはinterfaceのメソッド分のみで、例えばinterfaceのメソッドが2つ、変数のメソッドが5つあったとしても、2つのメソッド分のポインタが格納されます。interfaceのメソッドを呼び出すときはこれを使ってディスパッチが行われることになります。
ランタイム時にinterfaceの実装をチェックしながらitableを生成し、これを使うことでlookupが行われるのがDuck typingにおける重要なポイントです。これはGoの特徴的な挙動で、開発者の記事にも「Goが初めてかどうかは分からないが、確かにこれは良くある方式ではない」と書かれています。
意外と実装方法はシンプルで、interfaceのメソッド数と変数のメソッド数の分だけループを回し、それぞれが合致すれば配列に格納します。(ただしパフォーマンス向上のためにメソッドのリストは事前ソートされています)
なおitableは実際に以下のように定義されています。
type itab struct {
inter *interfacetype
_type *_type
hash uint32 // copy of _type.hash. Used for type switches.
_ [4]byte
fun [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
}
この中のfun [1]uintptrは、interfaceの先頭メソッドの実装にあたるポインタ(を保持する値)を格納しており、これが0であればinterfaceが正しく実装されていないことを示します。
そのためitableの生成後はfun[0] != 0のチェックを行い、もしもゼロなら生成できていないとみなすかpanicを発生させます。
itableTableへ値を追加する
一度生成したitableは、次回以降に再利用するためにitableTableのentriesに格納されます。以下のコードがそれに当たりますが、ハッシュテーブルのパフォーマンス向上のために工夫がされています。
func itabAdd(m *itab) {
// <中略>
t := itabTable
if t.count >= 3*(t.size/4) { // 75% load factor
// Grow hash table.
// t2 = new(itabTableType) + some additional entries
// We lie and tell malloc we want pointer-free memory because
// all the pointed-to values are not in the heap.
t2 := (*itabTableType)(mallocgc((2+2*t.size)*sys.PtrSize, nil, true))
t2.size = t.size * 2
// <中略>
t = itabTable
// Note: the old table can be GC'ed here.
}
t.add(m)
}
ハッシュテーブルでは事前にデータセットが分かっている場合は完全ハッシュ関数によって衝突を防げるのですが、値が動的に追加される場合、いかに工夫してもキーの衝突を防ぐことは至難です。(これは「誕生日のパラドックス」としても知られています)
そこでキーが衝突したときの対応としてGoはOpen addressingであるQuadratic probingを採用しています。これは衝突時に同じキーを持つ値を配列で管理せずに、別の番地を探すための手法です。
load factorと呼ばれるハッシュテーブルの占拠率が低いときには高速に処理できるものの、これが高まると飛躍的にパフォーマンスが低下する性質があるため、itabTableのload factorが75%を超えたときにはサイズを増やすことで、load factorを下げてパフォーマンスを改善しています。
(初期は512のサイズが与えられており、itableを追加する前に逐次load factorをチェックして、逼迫していればサイズを増やします)
以上のフローを経てitableがentriesに格納されます。次からはハッシュ関数とOpen addressingによって格納された値を発見できるので、再度の生成&格納をスキップしてitableを返すことになります。
繰り返しになりますが、これらはランタイム時に行われ、コンパイル時はシグネチャのチェックのみを行うので、GoはDuck typingであり、Structural Typingでもあるということになります。
最後に
当初は「なぜGoはDuck typingを採用していると言われるのか」と疑問に思ったことから調べてみましたが、データ構造を調べてみるとGoがユニークな方式を採用していることが分かりました。
私自身、データ構造やアルゴリズムは勉強中の身ですが、言語実装を読んでみると実際に理論がどのように使われているのかを知ることができて殊の外楽しく学習できました。
「Goを勉強するならGo自体のソースを読んだほうが良い」と以前言われたことがあり、興味本位で初めてみましたが凄く良い勉強になったので、もしGoを勉強されている方がいれば興味を持って頂ければ幸いです。