実用 Generics: Python の itertools を Go 2 に移植してみた

この記事は Go 4 Advent Calendar 2020 1日目の記事です。

激しい議論を呼んだことで有名な Go 2 の type generics は、Go 2 → Go 1 translator である "go2go" を介して既にお試しできる状態になっている。

この記事は、Go 2 における type generics のありようについて述べたり議論したりするものではない。お試しできるようになった今、それがどのような雰囲気で、どのように実用できそうかといった個人的感想を紹介する。どうぞ気軽に読んでほしい。

tl;dr

• Type generics の使い心地は思ったより良い
• 各種制限も妥当に設定されているように思える
• Go 1 に translate されたソースコードの見た目は素朴で直感的
• 今まで冗長に書かざるを得なかった部分を安全に短くするのに使えそう
• Python の itertools, functools, 組み込み関数 のうち、iterate できるオブジェクト（以下、iterable）関連の処理を、極力実用的になるように Go 2 に移植した
• 開発環境としてはまだこれから

github.com

Python と比べて体感する「Go 流」

とりあえず実際のコードを見たいという方は「Type generics を試してみる」へスキップしてもらって構わない。

「Go に入れば Go に従え」というように、我々 Go 開発者は Go 特有の概念を習得することで type generics なしで生きてきた。一旦それを忘れて、私が Go を習得する前の初心を思い出してみることにしよう。

Go を書き始める前から、私は Python をよく書いていた。Python の標準ライブラリには、itertools というモジュールがある。名前からして iterator + tools = itertools であることは想像に難くないように、iterate できるオブジェクトをいい感じに加工する関数がコレクトされている。代表的な iterable として、list が挙げられる。

例えば itertools.permutations を使うと、iterable の置換（数列からN個の要素を非復元抽出した際にとりうるすべての組み合わせ）を列挙できる。

In [1]: import itertools

In [2]: list(itertools.permutations([1, 2, 3], 3))
Out[2]: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Python においては str も iterable なので、この引数を str にしても、同じように呼ぶことができる。

In [3]: list(itertools.permutations("ABC", 3))
Out[3]:
[('A', 'B', 'C'),
 ('A', 'C', 'B'),
 ('B', 'A', 'C'),
 ('B', 'C', 'A'),
 ('C', 'A', 'B'),
 ('C', 'B', 'A')]

さて、上記と同じ処理を Go で書き、API を生やすにはどうすればよいだろうか。

"golang permutations" でググると出てくる github.com/gitchander/permutation を例にとると、[]int に対する置換は IntSlice、[]string に対して使える置換は StringSlice として宣言されていることがわかる。このように、具体的な型それぞれに対して処理を記述してやるのが Go 流だ*1。

package main

import (
    "fmt"

    prmt "github.com/gitchander/permutation"
)

func main() {
    a := []int{1, 2, 3}
    p := prmt.New(prmt.IntSlice(a))
    for p.Next() {
        fmt.Println(a)
    }
}

出力:

[1 2 3]
[2 1 3]
[3 1 2]
[1 3 2]
[2 3 1]
[3 2 1]

（README より）

Python では、itertools.permutations は任意のオブジェクトが入っている任意の iterable に対して実行できた。それを「そのまま」Go に移植する…つまり、任意の要素が入っている任意の slice []interface{} に対して実装することはできないのだろうか？

結論から言うと、私も含めて Go 開発者のほとんどが、「できなくはないがやめたほうがいい」と答えるだろう。Go においては、コードの再利用性や短さのために interface{} を使った処理を書くことは一般的に悪手とされる*2。実際の型 (underlying type) が int だったり string だったりする interface{} を加工するには、 type assertion なる概念で事前に具体的な型を「主張」することになるのだが、ちょっとミスると即 panic するため極めて危険だ*3。最後の手段として reflection を使ったとしても、同様あるいはそれ以上の地獄が待ち構えていることだろう*4。

では実際の開発においてどのように解決するかというと、結局さきほどの「型ごとに処理を書く」に帰結する。中身が似ていながらシグネチャの異なるコードが繰り返し実装され、Python よりも縦に長くなるだろう。魔法で無理に短くするよりは、多少冗長でも具体的な方が良い…それが Go 流なのだ。

そんなことはついぞ知らなかった初心者の私は、安易に interface{} に手を出して事故り、結局 Go 流に従うことが最も良い術であると後に悟るのであった。

Type generics を試してみる

Python の itertools のような API は、Go で実現するのが一番難しいタイプの API だ。

ところが、これまでに述べてきた世界観は、Go 2 の type generics の導入によって変化する。「型を書き換えればそのまま動くよく似た処理が、interface を介さず共有できる」からだ。それはつまりどういうことか？

百聞は一見にしかずということで、実例を出しながら説明することにしよう。Permutations の実装は少し長いので、より簡単な itertools.chain（任意個の iterable を連結して返す）を type generics なしで実装してみよう。The Go Playground を embed しているので、Run ボタンを押すと実際の動作を見ることができる。

[]int{1, 2} と []int{3, 4} が連結され、[]int{1, 2, 3, 4} となっていることがわかる。この処理の int の部分を string に変えると string に対しても実装できる。

では、お待ちかねの type generics ありで同じものを実装してみよう。Go Playground に Go 2 translator が統合された "The go2go Playground" で書いたものが以下だ。

Chain(iter ...[]int) []int だったシグネチャが Chain[T any](iter ...[]T) []T に変化していて、かつ []int と []string のどちらを与えてもつつがなく動いていることがわかるだろう。この [T any] というのは型パラメータ (type parameters)であり、T はどのような型にもなりえる。any 以外の型制約 (type constraints) を指定すると、型の振れ幅を制限することができる。文法の詳しい説明は参考ページを参照されたい。

まさに、Python でできていたようなことが Go でも実現している。すばらしい。裏では何が起きているのだろうか？

Translate の結果を読む

上記のコードを Go 1 に translate した結果を以下に載せる。出力は Go 1 になっているので、The Go Playground で実行できる。

私が特筆したいのは、translate 結果が極めてシンプルで、目視で読めることだ。Generic な関数として宣言されていた Chain は、引数の型によって推論されて instantiate୦୦Chain୦int や instantiate୦୦Chain୦string のように instantiate されていることがわかる。

私の体感を率直に言うならば、ちょっと乱暴だが「型部分が推論結果に応じていい感じに書き換わる糖衣構文」のように感じられる。これまでやっていたような「型ごとの実装の記述」を、実装者が見える範囲でコンパイラ（translator）に任せているような感覚がある。

Translator は思ったより賢い

Go には演算子オーバーロードの概念はなく、自分で作った型に対して + や - のような演算を実装することはできない。これは generic な関数でも同様だ。

例えば、「与えられたすべての引数を加算して返す関数」を書いた以下のコードはコンパイルできず、invalid operation: operator + not defined for sum（sum には演算子 + が定義されていない） と怒られてしまう。

これはなぜかというと、T がどのような型でもとりうることから、前述の「+ を実装していない型の値」が渡ってくる可能性があるからだ。そのような値は、sum に代入はできても + で演算することができない。

ここに、+ を実装している型だけに制約する型制約 (type constraints) を明記すると、通るようになる。

当たり前といえば当たり前なのだが、この検証がきちんとなされていて「Generic な関数では組み込みの演算子が使えない」のような制限がないこと、また、ドラフトの translator でありながら既にそこまで検証できていることに少し感動する。

制限

現状では、主に以下のような制限がある。

• 関数に型パラメータをつけることはできるが、レシーバにつけることはできない
  • 型定義に型パラメータを付けて generic な struct などを作ることはできるし、それに対してレシーバを生やすこともできるのでそんなに困らない
• Generic な型をさらに generic にするような手続きや宣言（"高カインド型" のように呼ぶらしい）は書けない
  • まず型が first-class object でない Go においては嬉しさが想像できないし妥当だと思う
• 可変長の型パラメータを受け取ることはできない
  • func [T, U any](t T, u ...U) string のように単一の型の可変長引数を受け取ることはできる

仕様自体の制限ではないが、*_test というパッケージ名でテストコードの名前空間を分割する概念が go2go では利用できない（現在は対応予定なし）。正式に Go 2 としてリリースされた暁には実装されると思われる。現状において Go 2 のテストコードを別な名前空間で書くには、パッケージをディレクトリごと分けたり main に置いたりする必要がある。

実用例として itertools 他を移植してみた

以上に示したように、以前は Go にそのまま持ってこれなかったような API 設計が、type generics によって実現しそうなことがわかった。それの概念実証として、Python の itertools + α を Go 2 に移植したので公開する。

github.com

現状で実装できているのは以下の通り。ただし、iterable 系を中心に Go でも応用が可能なものだけ実装している。詳しい一覧は README を参照されたい。

• itertools
  • count
  • cycle
  • repeat
  • accumulate
  • chain
  • chain.from_iterable
  • compress
  • dropwhile
  • takewhile
  • filterfalse
  • groupby
  • islice
  • tee
  • zip_longest
• functools
  • lru_cache
  • reduce
• builtins
  • all
  • any
  • enumerate
  • filter
  • map
  • min
  • max
  • range
  • reversed
  • sorted
  • sum
  • zip

簡単なサンプルは以下の通り。

• （わざとらしい）FizzBuzz のサンプル
• FizzBuzz を translate したもの

ちゃんとしたサンプルがまだないのはお詫びしたい。一応すべての関数に対してテストを記述しているので、それで雰囲気はつかめる………はず。

以下のように Go らしいバリエーションも実装している（実用性は不明）。

• Generator による遅延評価を Go でも実現するため slice 版と channel 版の2バージョンを各々用意*5
• 一部の関数で、Go 特有の制限に対応する形で型限定版と interface 版を用意

なお、似たコンセプトのパッケージはこれまで存在していた。言うまでもないが、それらとの差別ポイントとしては interface{} を全く使っていないことが挙げられる。危険な type assertion や面倒な自力ラップをやらずとも、任意の slice を渡すだけで結果が得られるようになっている。

まとめ + 考察

これまで何度か述べたように、Go 開発者は type generics のない Go に慣れ親しみ、Go ならではの書き方を実践してきた。そこに登場してきた type generics は結局の所どういうときに「嬉しい」といえるだろうか。go2-itertools を書いている間に個人的に感じたこととしては、type generics は「何かを抽象化するためにある」というよりは、「今まで冗長になっていた部分を、コンパイラの力を借りて安全に短くできる道具」に思える。「本当に必要になった時だけ interface 化する」という Go 開発者の教訓と同様にして、「本当に必要になった時だけ type generics を使う」という程度がいいだろう。こういうアプローチが欲しかった瞬間は今まであったし、これから先同様な状況に当たることは有り得るはずなので、その時に改めて検討したいと思う。いずれにしても、Go 2 の stable release が出るまではいずれにしても本番環境ではお預けだが。

まだまだ Go 2 に関するノウハウも開発環境も育ち始めたばかりだが、少なくとも go2-itertools については極力今後の参考になり続けられるように、自分で実際に使っていきながら育てていこうと思っている*6。Go 2 に興味のあるみなさんの参考になれば幸いだ。

参考ページ

• Why Generics? - The Go Blog
• The Next Step for Generics - The Go Blog
• 連結リストの実装でGo言語のジェネリクスのドラフトを触ってみる. Go言語で連結リストを実装しながらジェネリクスのドラフト仕様を見てgo2goとい… | by James Kirk | Eureka Engineering | Medium
• Type Parameters - Draft Design

*1:permutations は要素を比較したり加工したりすることもなくただ取り出すだけなので interface{} の slice に対する処理として記述することもできるが、返り値の型も interface{} の slice になってしまうので非常に勝手が悪い

*2:もちろん、外部と可変なデータを受け渡すときのように、真に必要なときはたま〜〜〜〜にある！滅多に無いけど！

*3:もちろん、扱う型を限定して入出力する interface を作って assertion を避ける選択も大いに取り得るが、itertools のようなユニバーサルに使い回せる API 設計にはできない

*4:このへんの interface や reflect の是非についてと、generics がどう役に立つかについては公式の "Why Generics?" に一通りまとまっていいて、質もいいので一読することをおすすめする

*5:channel の取り扱いに goroutine を利用していることから context が渡せないと困るシチュエーションが想定されるが、実用性がよくわからないので未実装

*6:more-itertools というデカい目標が実はある