Go言語のジェネリクス入門(2) インスタンス化と型推論

はじめに

注意: 2023/06/08更新

Go1.21(順調なら2023年8月にリリース予定)において、型推論アルゴリズムの枠組みが新しくなります。

https://github.com/golang/go/issues/58650

この記事の多くの内容は古いものとなります。
更新予定は今のところないので、注意書きを記載しておきます。

↑の変更のポイントだけ筆者なりにまとめておくと、関数引数型推論と制約型推論との間の順序の関係がなくなることと、順序の関係がなくなることによって型推論に使える情報の種類を増やしやすくなることがポイントです。

注意

この記事はGo1.18リリース前に書いたのですが、そのせいでGo1.18以降で動作しなくなっているサンプルコードがあります。
具体的には、Go1.18リリース時点では「パラメータ化された型」にたいする型推論が行われなくなりました。そのため、このような型推論についてのサンプルコードが動作しなくなっています。

型推論アルゴリズム自体は「パラメータ化された型」と「パラメータ化された関数」で大きく変わらないので、記事の内容の大部分は現在でも正しいものです。
ただしサンプルコードは動作しないものがあるので、「型」から「関数」へと書き換える必要があります(プルリク歓迎です)。現在その時間がとれてないので注意書きを最初に書いておきます。

---

この記事はGo言語のジェネリクス入門(1)の続編で、インスタンス化や型推論について解説します。

実用上はコンパイルエラーになったら直せばいいのでここに書かれているようなことを知らなくてもそれほど困らないと思います。しかし、型推論の仕組みについて正確に知ることで初めて思いつくコーディングパターンも時々はあるかもしれません。

Go言語仕様書は非常に読みやすい言語仕様書ですが、それでもジェネリクス関係の仕様を正確に理解するのは骨が折れるはずなので、正確な仕様を理解したくなった方の助けになればと思います。

型セットについての資料

この記事では型セット(Type set)についての理解を前提とします。Type setについては、ひとまず次のポイントを理解してください。

• Go言語のinterface型はすべて、「型の集合（型セット）」を定めるものである。
• 型TがinterfaceIを実装するとは、Iの型セットにTが属するということである。

型セットについては前編では説明していないのですが、現在のところ次のような資料が利用できます。

英語でよければ1番上のGriesemer氏の解説がよく、日本語で読む場合はGo の "Type Sets" proposal を読む - Zennの後半部分が良いかと思います。

リンク	内容紹介
GopherCon 2021: Robert Griesemer & Ian Lance Taylor - Generics!	[英語] Go言語開発者によるジェネリクス解説です。前半のgriesemer氏の発表部分に型セットの説明があります。
Type Parameters Proposal	[英語] ジェネリクスのプロポーザルドキュメントです。型セットについてはここで説明されています。
Go の "Type Sets" proposal を読む - Zenn	Type Setsのプロポーザルが出たときに書いた記事です。前半は経緯の解説なので今は読む必要ありません。Type setの仕様は後半で解説しています。
初めての型セット	Go1.17リリースパーティの発表スライドです。「型セット」と「実装」の概念理解にフォーカスしています。 すこし図があります。
Go言語仕様書(Go1.18ドラフト) - Interface types	言語仕様書の型セット該当部分です。

インスタンス化とは

ジェネリックな関数と型は、使う前に必ずインスタンス化して普通の関数・型にする必要があります。

インスタンス化とは、それぞれの型パラメータに具体的な型引数(type argument)を代入することです。

この記事では、type parameterの訳語として「型パラメータ」、type argumentの訳語として「型引数」を使います。

意味的には疑問もあるところと思いますが、口頭での言いやすさなども加味すると便利なため、個人的に採用しています。

次の例では、Print[T any]関数のTという型パラメータにstringという型引数が代入されることで、Print関数のインスタンス化が行われています。

package main

import (
	"fmt"
)

// This playground uses a development build of Go:
// devel go1.18-c9fe126c8b Mon Feb 21 21:28:40 2022 +0000

func Print[T any](s ...T) {
	for _, v := range s {
		fmt.Print(v)
	}
}

func main() {
	Print("Hello, ", "playground\n")
}

https://gotipplay.golang.org/p/ZRx0SE4Q1Yi

Tが型推論により自動決定されているので、あたかもPrintというジェネリックな関数をそのまま使っているようにも見えます。
しかし、実際には型推論がされていてもいなくてもインスタンス化は必ず行われています。
つまり、上記のコードは次のように書き換えても同じ意味です。

func main() {
	Print[string]("Hello, ", "playground\n")
}

言語仕様上は次のように明記されています。

https://tip.golang.org/ref/spec#Function_declarations

If the function declaration specifies type parameters, the function name denotes a generic function. Generic functions must be instantiated when they are used.

https://tip.golang.org/ref/spec#Type_declarations

If the type definition specifies type parameters, the type name denotes a generic type. Generic types must be instantiated when they are used.

インスタンス化は2ステップで行われる

インスタンス化は、次の2ステップで行われます。

• 型引数を対応する型パラメータに代入する。
• 代入された型引数が、対応する型パラメータの型制約を実装することを検証する。満たしていなければ、インスタンス化が失敗する。

型セットの復習として、次の2つが全く同じ意味であることを確認しておきます。

• 型引数が型制約を実装する
• 型引数が型制約の型セットに属する(型セットの要素である)

この記事ではこれと同じ意味で「型制約を満たす」という表現を用いることがあります。直感的なためです。

具体例(インスタンス化の失敗)

https://gotipplay.golang.org/p/FUdYlX-a6oH

package main

import "fmt"

type S[T fmt.Stringer] struct{}

type s = S[int]
// ./prog.go:7:12: int does not implement fmt.Stringer (missing String method)

• Step1: 型パラメータTに型引数intを代入する
• Step2: intがTの型制約fmt.Stringerを実装することを検証する

これはintがfmt.Stringerを実装しないため、インスタンス化が失敗します。

型推論はインスタンス化の前に行われる

型引数が欠けているとき、Go言語処理系は型推論により欠けている型引数の決定を試みます。

インスタンス化をするまえに型引数は全て決定している必要があるため、型推論が必要な場合には、型推論はインスタンス化の前に行われます。

型推論が成功してもインスタンス化が失敗することはある

https://gotipplay.golang.org/p/t4n8HllorSt

package main

func main() {
	var ch chan int
	f(ch)
}

func f[T <-chan int](ch T) {}

このコードは次のようにコンパイル失敗します。

./prog.go:5:3: chan int does not implement <-chan int

Tをchan intと推論することには成功しているのですが、その推論結果であるchan intという型引数が型制約<-chan intを実装しないため、インスタンス化のStep 2で失敗しています。

全体像

以上により、ジェネリックな型・関数を使うときには

• 型引数が欠けている場合には型推論を試みる
• インスタンス化を行う
• 関数呼び出しの場合には、引数をインスタンス化後の関数にわたす

というように処理が進みます。このそれぞれの段階でコンパイルエラーが発生し得ます。

これを図にすると次のようになります。型推論についてまだ説明していない詳細が含まれていますが、これは後ほど説明します。

型推論の概要

Goジェネリクスにおける型推論とは、未知の型引数を既知の情報から推論し、決定することです。

既知の情報には2種類あり、それに応じて型推論メカニズムも2種類あります。この両方を決まった順序で行うというのが型推論の概要です。

型推論メカニズム	使う情報
関数引数型推論	関数呼び出しで、引数として渡された値の型
制約型推論	すでに決定できた型引数と、型引数が従う型制約

さらに関数引数型推論が、「型あり引数」をもちいるものと「型なし引数」を用いるものの2種類あります。

これらを合わせて、型推論は次のような4つのステップにより行われます。

1. 型あり引数を用いた関数引数型推論
2. 制約型推論
3. 型なし引数を用いた関数引数型推論
4. 制約型推論

型なし引数とは、型なし定数(untyped constant)の引数のことです。f(1)やfmt.Println("hello world")の引数が該当します。

型あり引数とは、それ以外の全ての引数のことです。

x := 1 // xの型はintになる(※default type)
f(x) // xは型あり引数

型なし定数について詳しくは、つぎのDQNEOさんによる発表とスライドをみるとよくわかります。

• 入門Go言語仕様輪読会 Untyped Constants
• 発表スライド

unification(unify)の直感的説明

型推論の厳密な説明には、unification(unify)の理解が必要です。

しかし、unificationの厳密な説明をすると前置きが長くなってしまうので、ここでは

• unificationとは、型パラメータを含む2つの型をパターンマッチングする仕組みである
• パターンマッチングした結果、substitution map entryが作られる

ことを具体例から感じ取ってください。

型1	型2	つくられるsubstitution map entry
[]map[int]bool	T1	T1 -> []map[int]bool
[]map[int]bool	[]T1	T1 -> map[int]bool
[]map[int]bool	[]map[T1]T2	T1 -> int, T2 -> bool
[]map[int]bool	*T	unification失敗し、entryはつくられない

ここで、substitution mapとは、型推論によって作られるkey->valueストアであって、型パラメータをkeyとし、他の型をvalueとするものです。

型推論の目的は、substitution mapを完成させて、未知の型パラメータを具体的な型引数に対応付けることだと言えます。

ここまでの言葉を使って少しフォーマルに言い直すと、「unificationとは、2つの型を受け取って動作するルーチンであり、その結果としてsubstitution mapに0個以上のエントリを追加するもの」だと言えます。

ですから、今後unificationが出てきたときは、「受け取る2つの型は何なのか？」ということを問いながら読みすすめると理解がしやすいとおもいます。

以下、substitution map entryのことを単に「エントリー」と書きます。

関数引数型推論

関数引数型推論は、「関数に渡された実引数の型」と、「関数の引数の型」をunifyします。ただし、このunificationは、関数の引数の型が型パラメータを含むときにのみ行われます。

例を挙げましょう。

func f[T any](x T) {...}

var x int
f(x)

この関数呼び出しf(x)では型パラメータTが未知なので型推論が起動します。xの型intと, パラメータの型Tがunificationルーチンの「引数」となります。TとintのunificationによりentryT -> intがsubstitution mapに追加され、ここですべての型パラメータが既知となるため型推論が完了します。

制約型推論

制約型推論は、「型パラメータ」と、「その型パラメータに課された型制約のcore type」をunifyします。
ただし、型制約がcore typeを持つ場合にのみ制約型推論が起動されます。

core typeについては前編を参照ください。

型制約はインタフェース型であり、よってもちろんそれ自体が「型」であることを注意しておきます。「unificationは2つの型を受け取るルーチンである」と書いたとおりですね。

次のような「ただひとつのdefined typeを型セットに含む」型制約の場合のみ、「core typeではなくadjusted core typeというものにunifyされる」という例外があります。

ただし実用上の重要性が低いため、この記事では一旦詳細を略します。

type MyInt int

type C interface {
  MyInt
}

仕様書にある例を使って説明します。

https://gotipplay.golang.org/p/G77uiNe_taU

type T[A any, B []C, C *A] struct {
	A A
	B B
	C C
}

func main() {
	var t T[int]
	fmt.Printf("A: %T, B: %T, C:%T\n", t.A, t.B, t.C)
	// A: int, B: []*int, C:*int
}

このジェネリックなT型は3つの型パラメータA, B, Cを持ちますが、変数tの宣言において1つの型引数A = intしか特定していません。しかし、制約型推論によって残り2つの型引数を決定できるため、コンパイルが成功します。

流れとしてはつぎのようになります。

1. var t T[int]は関数呼び出しではないため関数引数型推論は行われず、スキップされます。
2. 未知の型パラメータB, Cがあるため、制約型推論が起動します。
   1. Cはcore type*Aをもつため、Cと*AをunifyしてC -> *Aというエントリーができます。
   2. Bはcore type[]Cをもつため、Bと[]CをunifyしてB -> []Cというエントリーができます。
   3. 明示された型引数intにより、A -> intがすでにあるため、C -> *AにおけるAをintで置き換えます。これでC -> *intというエントリーができます。
   4. さらにB -> []CにおけるCを*intで置き換えることで、B -> []*intというエントリーができます。
   5. これ以上置き換えはできないので、制約型推論が終了します。
3. 未知の型パラメータがなくなったので、型推論を終了します。

最終的なsubstitution mapは次のようになっています:

A -> int
B -> []*int
C -> *int

unification/unify

ここまでの話で、型推論(関数引数型推論と制約型推論)がどのように行われるかを説明してきました。

しかし、その説明のなかで「unifyする」とか「unification」という手続き（ルーチン）がどのようなものなのかは厳密に説明していませんでした。

このセクションでは、いままで直感的にしか説明していなかったunify/unificationを厳密に定義することで、型推論の解説を完成させます。

unificationの厳密な定義

定義

2つの型をunifyするとは、その2つの型を 等価(equivalent) にするようなsubstitution map entryを見つけることである。

つまり、XとYという2つの型をunifyするとは、エントリーP -> Aを適当に追加して、XとYに含まれているPをAに置き換えればXとYが等価になるようにするということです。

仕様書上は次のように書かれています。

https://tip.golang.org/ref/spec#Type_unification

Unification is the process of finding substitution map entries that make the two types equivalent.

この定義を完全なものとするには、「等価(equivalent)」とは何かも定義する必要があります。

「型が等価である」ことの厳密な定義は少しあとに回したいのですが、すこしだけ述べておくと、「型が等価である」というのは「型が同一である」よりも少し広い（ゆるい）条件です。
つまり、2つの型が同一(identical)であればそれらは等価でもあるのですが、2つの型が等価であっても同一ではない場合があります。

まずunificationの具体例をみておきましょう。

例

• [B []C]において、型Bと型[]Cをunifyするとは、エントリーB -> []Cを追加することです。なぜなら、BにはBが「含まれて」おり、BをエントリーB -> []Cに従って置き換えることで[]Cと[]Cが「等価」になるからです。
• []map[int]boolと[]map[T1]T2をunifyするとは、T1 -> int, T2 -> boolという２つのエントリーを追加することです。なぜなら、[]map[T1]T2に含まれるT1とT2をそれぞれエントリーに従って置き換えることで、2つの型はどちらも[]map[int]boolとなり、等価となるからです。

unificationが失敗する例をあげておきます。

[]map[int]boolと*Tのunificationを試みると、どのようなエントリT -> ?を追加してもこの2つの型を等価にすることはできないので、unificationが失敗します。

型推論の中でunificationが失敗すれば、コンパイルエラーとなります。

https://gotipplay.golang.org/p/C1kepqzqWKJ

func f[T any](x *T) {}

func main() {
	f(make([]map[int]bool, 0))
	// type []map[int]bool of make([]map[int]bool, 0) does not match *T (cannot infer T)
}

関数引数型推論により[]map[int]boolと*Tのunificationが試みられますが、この2つを等価にするようなエントリーは存在しないのでunificationが失敗し、型推論の失敗によりコンパイルが失敗します。

unificationの厳密な定義をみたとき、腑に落ちなさを感じる方もいるとおもいます。その腑に落ちなさは、この定義が「エントリーを求める方法」について何も述べていないからではないかと思います。

実際、Go言語仕様書はunificationにおいて「エントリーを求める方法・アルゴリズム」については述べていません。しかし、unificationによって見つけるべきエントリーとはどのようなものなのか、については正確に述べているので、仕様書としては十分なのです。

高校相当の数学に例えると、「unificationの定義」は、「(0個以上の)エントリーxの組が満たすべき方程式」のようなものです。2次方程式x^2 + x - 1 = 0の解とは何か、という「定義」は、その方程式を「解く方法」がわからなくても、それとは無関係に行うことができます。これと同じように、unificationの定義においては、「エントリーが満たすべき性質」を述べているだけで、「そのようなエントリーを求める方法」については述べていませんし、それで十分だということです。

方程式のたとえによるならば、「方程式」を満たすエントリーが存在すればunificationが可能ですし、方程式が「解なし」であればunificationは失敗し、コンパイルエラーになるわけです。

型の同一性(identity)と等価性(equivalence)

「型の同一性」はGo1.17以前から定義されている用語です。

https://go.dev/ref/spec#Type_identity

ここで厳密な定義を解説することはしませんが、type A Bというように型定義したときにAとBとは異なる型であるということだけ注意してください。

定義(型の等価性)

2つの型X, Yが等価であるとは、つぎの3つのいずれかが成り立つことです。

• X, Yが同一(identical)であるとき
• X, Yがどちらもchannel型であり、方向を無視すれば同一であるとき
• X, Yのunderlying typeが等価であるとき

等価性の例

• type X = intとtype Y = intは同一なので等価です。
• X = <-chan intとY = chan intは方向を無視すれば同一なので等価です。
• type X <-chan intとtype Y = chan intは、Xのunderlying type<-chan intとYのunderlying typechan intが等価なので、等価です。

等価ではない例も挙げておきます。

type MyInt int

type X chan int

type Y chan MyInt

このように定義したX, Yは等価ではありません。

等価性とunificationの例

等価性があってはじめてunificationが成功する例を挙げましょう。

https://gotipplay.golang.org/p/ckSANEXiR9c

package main

import "fmt"

type A chan int
type X[T ~<-chan U | ~chan U, U any] struct {
	T T
	U U
}

func main() {
	var x X[A]
	fmt.Printf("T: %T, U: %T\n", x.T, x.U)
	// T: main.A, U: int
}

ジェネリックな型Xは型パラメータT, Uを持ちますが、宣言var x X[A]において１つの型引数しか渡されていません。
よって、制約型推論によってUが決定できないとコンパイルエラーになってしまいます。

この型推論は次のように進みます。

• エントリーT -> Aは明示的に与えられます。
• 型パラメータUの制約anyはcore typeが存在しない型なので、Uについての制約型推論は行われません。
• 型パラメータTの制約~<-chan U | ~chan Uはcore type<-chan Uを持ちます。よって制約型推論により、Tと<-chan Uのunificationを行いますが、TはAであることがすでにわかっているので、Aと<-chan Uのunificationを行います。
• つまり、エントリーU -> ?を追加することでtype A chan intと<-chan Uを等価にすることができるかどうかが問題になります。
• 試みとして、U -> intというエントリーを追加すると仮定しましょう。
• type A chan intと<-chan intが等価かどうか？を考えます。
• この2つは同一ではないので、1つ目の条件にはあてはまりません。
• Aはchan intとは異なる型なので、channelの方向を無視しても同一の型にはなりません。よって2つ目の条件にもあてはまりません。
• 最後にunderlying typeを考えると、Aのunderlying typeはchan intであり、これは方向を無視すれば<-chan intと同一の型になります。よって等価性の3番めの条件を満たしています。
• つまり、エントリーU -> intを追加することで、型Aと<-chan intを等価にすることができたので、このエントリーの追加をもってunificationが成功しました。
• これですべての型パラメータが確定したので、型推論が完了します。

このcore typeは難しいパターンなので、前編のcore type部分を見直してください。

上記の例だとあたかもエントリーを「あてずっぽう」に決めているように見えるので違和感をおぼえるかもしれません。

もちろん実際のコンパイラは決まったアルゴリズムでエントリーを発見しているはずですが、前述の通りunificationが可能であることを示すためには実際に等価性を満たすことのできるエントリーが存在することを言えば十分です。

具体例や未解決の問題

いくつか型推論にまつわる面白い話題を挙げてこの記事を終わります。

公式ドキュメントに見る制約型推論の活用例

Type Parameters Proposalに出てくる、Pointer method exampleを解説します。

このセクションはほとんどproposalにかかれている通りのことを書きます。ここで挙げるのは、制約型推論の応用として面白い例だからです。

次のようなジェネリックな関数を考えます。

// Setterはstringの値をSetできるインタフェース
type Setter interface {
	Set(string)
}

// FromStringsは[]stringを受け取ってSetterのスライスを返す
// その際にSetメソッドでsの内容をSetする
func FromStrings[T Setter](s []string) []T {
	result := make([]T, len(s))
	for i, v := range s {
		result[i].Set(v)
	}
	return result
}

これを次のように使いたいのですが、これはコンパイルできません。

type Settable int

func (p *Settable) Set(s string) {
	i, _ := strconv.Atoi(s) // real code should not ignore the error
	*p = Settable(i)
}

func F() {
	nums := FromStrings[Settable]([]string{"1", "2"})
  _ = nums
}

https://gotipplay.golang.org/p/g2GkggqE7e0

Settable does not implement Setter (Set method has pointer receiver)

これは、Setメソッドを実装しているのはあくまで*Settable型であり、Settable型ではないので、Settableが型制約Setterを実装しないからです。

では、*Settable型を渡すとどうなるでしょうか。

func F() {
	nums := FromStrings[*Settable]([]string{"1", "2"})
	_ = nums
}

https://gotipplay.golang.org/p/TYI_tmQ06tZ

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x45810e]

今度はコンパイルできるのですがpanicしてしまいます。

func FromStrings[T Setter](s []string) []T {
	result := make([]T, len(s))
	for i, v := range s {
		result[i].Set(v)
	}
	return result
}

をみると、result[i]は*Settableのゼロ値であるnilが入っているので、Set呼び出しのときにnil pointer dereferenceになるからです。かといって、Settableという型をTから取り出すことはできません。

素朴な解決策は、2つの型パラメータを用いることです。

// パラメータ付きの型制約。何かのBに対するポインタ型であり、かつ、Set(string)を実装するという型制約になっている。
type Setter2[B any] interface {
	Set(string)
	*B
}

// 2つの型パラメータを持つようにする
func FromStrings2[T any, PT Setter2[T]](s []string) []T {
	result := make([]T, len(s)) // T型のスライスとして初期化する
	for i, v := range s {
		// PT型へのコンバージョン
		p := PT(&result[i])
		// PTはSetメソッドを持つ
		p.Set(v)
	}
	return result
}

これを利用してFを書き直せます:

func F2() {
	nums := FromStrings2[Settable, *Settable]([]string{"1", "2"})
	fmt.Println(nums) // [1 2]
}

https://gotipplay.golang.org/p/VFxDjHrE7N6

これは意図通りに動作しますが、2つの型引数を渡すところが億劫です。

そこで、制約型推論を活用して次のようにすることができます。

func F3() {
	nums := FromStrings2[Settable]([]string{"1", "2"})
	fmt.Println(nums) // [1, 2]
}

https://gotipplay.golang.org/p/01aOdAHrXut

型引数を2つ渡すのではなく、１つだけ渡しました。これでも結果は同一となります。

起きているのは次のようなことです。

• T -> Settableが確定する
• PTの型制約Setter2[T]のTにSettableを渡してインスタンス化する。
• PTの型制約を擬似コードで書くと次のようになる:

type Setter2Instantiated interface {
	Set(string)
	*Settable
}

• 制約型推論が起動する。Setter2Instantiatedはcore type *Settableを持つので、PTと*Settableをunifyする。
• エントリーPT -> *Settableが作られ、全ての型引数が確定して型推論が終了する。

このように、制約型推論を使うことで、ポインタレシーバメソッドをジェネリックに扱う関数を少し短いコードで呼び出すことができました。

関数引数型推論と引数の順序

https://github.com/golang/go/issues/43056

関数引数型推論において、unifyしうる型のペアが複数あるとき、どの順序でunifyを行うかは未定義です。
ほとんどの場合、順序によって結果が変わることはありませんが、結果が変わる厄介な例が挙げられています。

制約型推論とdefined type、型推論インタリービング

https://github.com/golang/go/issues/51139

制約型推論とdefined type、代入可能性の兼ね合いでコンパイルできないコードが挙げられています。
Go1.18仕様では関数引数型推論と制約型推論を別のステップで行いますが、関数引数型推論の対象となるペアが複数ある場合に間に制約型推論を挟み込むことでコンパイルが可能になるのではないかという提案がなされています。(issueでいうところのinterleaved world)

問題はこれがGo1.18との後方互換性を持つかどうかで、griesemer氏は「おそらく後方互換性があるだろう」と述べています。

おわりに

筆者が特に書きたかったところがunificationの厳密な定義であるため、それ以外の実用上重要な仕様への言及漏れがあるとおもいます。たとえば型引数の部分的省略、ジェネリックな型制約、相互参照する型制約、また型エイリアスなどについて言及できていません。

そうした不足分に限らず、誤りやわかりにくい点、古くなった用語なども含めて出来得る限りメンテナンスしたいと考えています。GitHubのPRやIssueなど歓迎します。（いきなりPR出していただいて大丈夫です）