Skip to content

Instantly share code, notes, and snippets.

@S-Shimotori

S-Shimotori/15292-generics.md

Created August 4, 2017 11:33
Show Gist options
  • Save S-Shimotori/1439cd7df842f1c453cf97d3278a0cd7 to your computer and use it in GitHub Desktop.
Save S-Shimotori/1439cd7df842f1c453cf97d3278a0cd7 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
15292-generics.md

Proposal: Go should have generics

Author: Ian Lance Taylor

Created: January 2011

Last updated: April 2016

Discussion at https://golang.org/issue/15292

Abstract

Go should support some form of generic programming. Generic programming enables the representation of algorithms and data structures in a generic form, with concrete elements of the code (such as types) factored out. It means the ability to express algorithms with minimal assumptions about data structures, and vice-versa (paraphrasing Jazayeri, et al).

Background

Generic arguments in favor of generics

People can write code once, saving coding time. People can fix a bug in one instance without having to remember to fix it in others. Generics avoid boilerplate: less coding by copying and editing.

Generics save time testing code: they increase the amount of code that can be type checked at compile time rather than at run time.

Every statically typed language in current use has generics in one form or another (even C has generics, where they are called preprocessor macros; example).

Existing support for generic programming in Go

Go already supports a form of generic programming via interfaces. People can write an abstract algorithm that works with any type that implements the interface. However, interfaces are limited because the methods must use specific types. There is no way to write an interface with a method that takes an argument of type T, for any T, and returns a value of the same type. There is no way to write an interface with a method that compares two values of the same type T, for any T. The assumptions that interfaces require about the types that satisfy them are not minimal.

Interfaces are not simply types; they are also values. There is no way to use interface types without using interface values, and interface values aren’t always efficient. There is no way to create a slice of the dynamic type of an interface. That is, there is no way to avoid boxing.

Specific arguments in favor of generics in Go

Generics permit type-safe polymorphic containers. Go currently has a very limited set of such containers: slices, and maps of most but not all types. Not every program can be written using a slice or map.

Look at the functions SortInts, SortFloats, SortStrings in the sort package. Or SearchInts, SearchFloats, SearchStrings. Or the Len, Less, and Swap methods of byName in package io/ioutil. Pure boilerplate copying.

The copy and append functions exist because they make slices much more useful. Generics would mean that these functions are unnecessary. Generics would make it possible to write similar functions for maps and channels, not to mention user created data types. Granted, slices are the most important composite data type, and that’s why these functions were needed, but other data types are still useful.

It would be nice to be able to make a copy of a map. Right now that function can only be written for a specific map type, but, except for types, the same code works for any map type. Similarly, it would be nice to be able to multiplex one channel onto two, without having to rewrite the function for each channel type. One can imagine a range of simple channel manipulators, but they can not be written because the type of the channel must be specified explicitly.

Generics let people express the relationship between function parameters and results. Consider the simple Transform function that calls a function on every element of a slice, returning a new slice. We want to write something like

func Transform(s []T, f func(T) U) []U

but this can not be expressed in current Go.

In many Go programs, people only have to write explicit types in function signatures. Without generics, they also have to write them in another place: in the type assertion needed to convert from an interface type back to the real type. The lack of static type checking provided by generics makes the code heavier.

What we want from generics in Go

Any implementation of generics in Go should support the following.

  • Define generic types based on types that are not known until they are instantiated.
  • Write algorithms to operate on values of these types.
  • Name generic types and name specific instantiations of generic types.
  • Use types derived from generic types, as in making a slice of a generic type, or conversely, given a generic type known to be a slice, defining a variable with the slice’s element type.
  • Restrict the set of types that may be used to instantiate a generic type, to ensure that the generic type is only instantiated with types that support the required operations.
  • Do not require an explicit relationship between the definition of a generic type or function and its use. That is, programs should not have to explicitly say type T implements generic G.
  • Write interfaces that describe explicit relationships between generic types, as in a method that takes two parameters that must both be the same unknown type.
  • Do not require explicit instantiation of generic types or functions; they should be instantiated as needed.

The downsides of generics

総称型は言語全体に影響する。総称型と共にどう動くかを見るために、全ての単一言語の構造を評価する必要がある。

総称型は標準ライブラリ全体に影響する。

標準ライブラリが総称型を有効に使用することが望ましい。総称型から利益を得られるかどうかの確認をするために既存の各パッケージは再検討する必要がある。

C++の std::basic_string<char, std::char_traits<char>, std::allocator<char> > のように総称型を標準ライブラリの低いレイヤーに組み込むのは魅力的である。これにはメリットがある—一方で誰もそうしないが—理解できないC++のエラーメッセージのように、これは幅広く時には驚くべき効果がある。

research!rsc: The Generic Dilemmaによれば、総称型はプログラマーの時間、コンパイル時間、実行時間との間にトレードオフがあるという。

現在Goはプログラマーの時間を犠牲にしてコンパイル時間と実行時間を最適化している。コンパイル時間はGoの大きな利点である。多くの実行時間を犠牲にせずにコンパイル時間の利点を保つことはできるか？

実行時間の最適化を選ばない限り、総称型の値を使用すると安価な処理によりコストがかかる可能性がある。このことはプログラマーにとって少し混乱することかもしれない。

Goのいくつかの処理は配列の境界チェックなどの隠れたコストを持っているため、他の言語と比べてGoにはあまり重要ではない。それでも、総称型の値を使用することの余分なコストが厳しく制限されていることを確認することが不可欠である。

Goは軽量の型システムを用いている。総称型を追加すると必然的に型システムが複雑になる。その結果軽量であることが不可欠である。

欠点の逆は、Goが比較的小さい言語で、総称型を追加する際に言語のあらゆる面を考慮することが可能である。 仕様のうち次のセクションを拡張する必要がある: 型、型の識別、割り当て、型アサーション、呼び出し、型スイッチ、範囲節を持つステートメント。

総称型を再考慮しなければいけないパッケージは比較的少ない: container/*、sort、flag、おそらくbyte。現在interfaceに関して動作するパッケージについては一般的にそうすることができる。

Conclusion

Generics will make the language safer, more efficient to use, and more powerful. These advantages are harder to quantify than the disadvantages, but they are real.

Examples of potential uses of generics in Go

  • Containers
    • slice keyを文字列に変換してmapを使うよりもコンパイル時に型安全であるようなユーザ実装のハッシュテーブル
    • ソートされたmap(赤黒木か似たようなもの)
    • 両端キュー、循環バッファ
    • より単純なヒープ
    • Keys(map[K]V) []K, Values(map[K]V) []V
    • キャッシュ
    • コンパイル時に型安全な sync.Pool
  • 型安全な方法でこれらcontainerと共に動作する総称型アルゴリズム
    • 和集合/積集合
    • ソート、安定ソート、探索
    • コピー(総称型container、あるいはmap)
    • 関数を適用することによるcontainerの変換--LISPの mapcar やその仲間
  • mathとmath/cmplx
  • testing/quick.{Check,CheckEqual}
  • ミックスイン
    • ioutil.NopCloser のようなもの、ただし渡されたinterfaceを制限するのではなく他のメソッドを保持する( bytes.Buffer の ReadFoo variantを見よ)
  • protobuf proto.Clone
  • ソート関数呼び出し時の定型文の削除
  • 総称型の差分: func [T] Diff(x, y []T) []range
  • Cannel処理
    • N個のチャンネルを1つにマージ
    • チャンネルをN個に多重化
    • worker-pool pattern
  • immediate dominator computationのようなグラフアルゴリズム
  • 長さの異なる多次元配列(sliceではない)
  • go.textのパッケージの多くが string と []byte variantsに関してAPIや実装の重複を避けられる; しかし利益を得られる多くのポイントは高いパフォーマンスを必要とし、総称型はその利益を提供すべき

Proposal

I won’t discuss a specific implementation proposal here: my hope is that this document helps show people that generics are worth having provided the downsides can be kept under control.

The following documents are my previous generics proposals, presented for historic reference. All are flawed in various ways.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment