![](https://habrastorage.org/webt/rl/tx/-f/rltx-f5fgboibhjrrvpfkoayvp8.jpeg)
Эта статья о том, что будет означать добавление дженериков в Go, и почему я считаю, что нам это следует сделать. Также я коснусь возможного изменения архитектуры языка ради добавления дженериков.
Go вышел 10 ноября 2009-го. Меньше чем через сутки появился первый комментарий про дженерики. В нём также упомянуты исключения, которые мы добавили в язык в виде паники и восстановления (panic and recover) в начале 2010-го.
За три года наблюдений отсутствие дженериков всегда входило список трёх главных проблем, которые необходимо исправить в языке.
Зачем нужны дженерики?
Что означает добавление дженериков и почему мы этого хотим?
Перефразируя Jazayeri и других: программирование с дженериками позволяет представлять функции и структуры данных в виде дженериков, исключая типы.
Что это означает?
Допустим, нам нужно представить элементы слайса в обратном порядке. Это не слишком распространённая задача, но и не такая уж редкая.
Пусть у нас есть слайс целых чисел.
func ReverseInts(s []int) {
first := 0
last := len(s)
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
Выглядит просто. Но даже для простой функции вроде этой вам может понадобиться написать несколько тестов. И когда я это сделал, то обнаружил баг. Уверен, многие его уже заметили.
func ReverseInts(s []int) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
Мы вычитаем 1, в то время как назначаем переменную
last
. Теперь поменяем порядок в слайсе строковых значений.func ReverseStrings(s []string) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
Если вы сравните
ReverseInts
и ReverseStrings
, то увидите, что функции совершенно одинаковые, за исключением типа параметра. Вряд ли я вас этим удивил.А вот что может удивить новичков в Go, так это отсутствие способа написать простую функцию
Reverse
, работающую со слайсами любых типов.В большинстве других языков вы можете написать такую функцию.
В динамически типизируемых языках вроде Python или JavaScript вы можете просто написать функцию без указания типа элементов. В Go так нельзя, потому что это статически типизируемый язык, он требует прописать конкретный тип слайса и тип его элементов.
Большинство других статически типизируемых языков, вроде С++, Java, Rust или Swift, поддерживают дженерики именно для таких ситуаций.
Современное программирование на Go с дженериками
Так как же люди пишут подобный код на Go?
В этом языке вы можете написать функцию, которая работает с разными типами слайсов с помощью интерфейсного типа (interface type) и определения метода для типов слайсов, которые вы хотите передавать. Так работает функция
sort.Sort
из стандартной библиотеки.Иными словами, интерфейсные типы в Go — это разновидность программирования с дженериками. Они позволяют выявлять общие аспекты разных типов и выражать их в виде методов. Затем можно писать функции, использующие эти интерфейсные типы, и функции будут работать с любыми типами, реализованными в этих методах.
Но этот подход не соответствует нашим желаниям. Нужно самостоятельно писать методы в интерфейсах. Довольно странно определять именованный тип с парой методов чтобы лишь поменять порядок элементов в слайсе. А методы, которые вы пишете, будут совершенно одинаковыми для всех типов слайсов, так что мы не исключили код, а, в каком-то смысле, перенесли и уплотнили. Хотя интерфейсы — это способ представления дженериков, они не дают нам всего, что нам нужно от дженериков.
Другой способ использования интерфейсов для дженериков, при котором не нужно писать методы, заключается в том, чтобы переложить на язык обязанность определять методы для каких-то типов. Сейчас Go этого не поддерживает, но, к примеру, язык может определять, чтобы каждый тип слайса имел метод
Index
, возвращающий элемент. Но чтобы использовать этот метод на практике, потребуется возвращать пустой тип интерфейса, и тогда мы теряем все преимущества статического типизирования. Не будет способа определять дженерик-функцию, которая берёт два разных слайса с элементами одного типа, или которая берёт map'у с элементами одного типа и возвращает слайс с элементами такого же типа. Go статически типизирован потому, что это облегчает написание больших программ. Мы не хотим терять преимущества статического типизирования ради выгод дженериков.Ещё один подход заключается в написании дженерик-функции
Reverse
, использующей пакет reflect, но это было бы слишком странно и работал бы чересчур медленно. Кроме того, потребовалось бы делать явные утверждения типов и отказаться от проверки на статичность типов.Или можно написать генератор кода, который берёт тип и генерирует функцию
Reverse
для слайсов этого типа. Для этого подходят несколько генераторов. Но такое решение прибавляет ещё один этап в каждый пакет, которому понадобится Reverse
, что усложняет сборку из-за необходимости компилирования всех копий, а исправление багов в исходном коде потребует перегенерирования всех экземпляров, некоторые из которых могут уже задействоваться в совершенно других проектах. Все описанные подходы достаточно странные, и я думаю, что большинство программистов, которым нужно менять порядок в слайсах на Go, просто пишут функцию для конкретного типа слайса. Потом им нужно написать тесты для функций, чтобы удостовериться, что они не сделали простых ошибок, вроде той, что я сделал в начале. А потом придётся рутинно прогонять эти тесты.
И когда мы это делаем, это означает, что мы делаем кучу лишней работы просто ради функции, которая выглядит точно так же, за исключением типа элементов. Дело не в том, что это невозможно. Это точно возможно, и программисты на Go так и делают. Просто должен быть способ получше.
Для статически типизированных языков вроде Go этот способ получше называется дженериками. Выше я написал, что программирование с дженериками позволяет представлять функции и структуры данных в виде дженериков исключая типы. Именно это нам и нужно.
Что дженерики могут дать Go
Первое и самое важное, что нам нужно от дженериков в Go, это возможность писать функции вроде
Reverse
и не беспокоиться о типах элементов в слайсах. Мы хотим исключить тип элементов. Также мы хотим писать функцию и тесты однократно, класть их в доступный для Go пакет и вызывать по мере необходимости.А поскольку мы говорим об open source, то будет ещё лучше, если кто-нибудь сможет написать
Reverse
один раз, а мы все будем пользоваться этой реализацией.Здесь мне следует сказать, что термин «дженерики» может обозначать много разного. В этой статье я подразумеваю под «дженериками» то, что описал выше. В частности, я не имею в виду шаблоны, как в С++, которые поддерживают гораздо больше возможностей, чем я перечислил.
Я подробно рассказал о
Reverse
, но есть и много других функций, которые мы могли бы писать как дженерики, например:- Поиск наименьшего или наибольшего элемента в слайсе.
- Поиск среднего или стандартного отклонения в слайсе.
- Вычисление модуля или пересечения в map.
- Поиск кратчайшего пути в графе с узлами или рёбрами.
- Применение к слайсу или map'е функции преобразования, которая возвращает новый слайс или map.
Эти примеры доступны в большинстве других языков. Фактически, я написал этот список, просто посмотрев на шаблоны из стандартной библиотеки С++.
Есть примеры, характерные для Go с его строгой поддержкой параллелизма.
- Чтение из канала без таймаута.
- Комбинирование двух каналов в один.
- Параллельный вызов списка функций, который возвращает слайс результатов.
- Вызов списка функций с использованием
Context
, возвращающий результат первой завершаемой функции, отменяющий и очищающий дополнительные горутины.
Я много раз видел все эти функции, с разными типами. Их не трудно написать на Go. Но лучше было бы хорошо многократно использовать эффективную и отлаженную реализацию, которая работает для всех типов.
Чтобы не было недопонимания, это всего лишь примеры. Есть много других функций общего назначения, которые будет проще и безопаснее писать с использованием дженериков. Кроме того, как написал выше, это не только функции, а ещё и структуры данных.
В Go встроены две дженерик-структуры данных общего назначения: слайсы и map. Они могут содержать значения любых типов, с проверкой на статичность типов значений, которые хранятся и извлекаются. Значения хранятся сами по себе, а не как интерфейсные типы. То есть, когда у меня есть
[]int
, слайс содержит сами числа, а не числа, преобразованные в интерфейсный тип.Слайсы и map'ы — самые полезные дженерик-структуры данных, но они не единственные. Вот другие:
- Наборы.
- Самобалансирующиеся деревья с эффективной вставкой и обходом в порядке сортировки.
- Мальтикарты с многочисленными экземплярами ключа.
- Конкуретные map'ы хэшей, поддерживающие параллельную вставку и поиск безо всяких блокировок.
Если мы можем писать дженерик-типы, мы можем определять новые структуры данных, вроде тех, что имеют те же преимущества проверки типов, как у слайсов и map: компилятор может статически проверить типы значений, которые они содержат, и значения могут храниться сами по себе, а не как интерфейсные типы.
Должна быть возможность взять алгоритмы, вроде упомянутых мной выше, и применить их к дженерик-структурам данных.
Все эти примеры должны быть такими же, как в случае с
Reverse
: дженерик-функции и структуры пишутся один раз, помещаются в пакет, а затем многократно используются там, где нужно. Они должны работать как слайсы и map, в том смысле, что они должны хранить не значения пустых интерфейсных типов, а конкретные типы, которые будут проверяться при компиляции.Вот какую пользу может извлечь Go из дженериков. Дженерики могут стать эффективными кирпичиками, позволяющими делиться кодом и проще создавать программы.
Надеюсь, я смог объяснить, почему имеет смысл их изучить.
Преимущества и цена
Но дженерики не появляются из Big Rock Candy Mountain, края, в котором солнце каждый день сияет над лимонадными источниками. У каждого изменения языка есть своя цена. Несомненно, что добавление дженериков в Go усложнит язык. Как и с любым изменением, нам нужно обсудить максимизацию преимуществ и минимизацию цены.
В Go мы старались уменьшить сложность с помощью независимых, самостоятельных особенностей, которые можно свободно комбинировать друг с другом. Мы снижаем сложность, делая эти особенности простыми, и увеличиваем преимущества этих свойств, обеспечивая свободную комбинируемость. То же самое мы хотим сделать и с дженериками.
Чтобы выражаться конкретнее, приведу несколько рекомендаций, которым мы должны следовать.
Минимизация новых концепций
Нужно добавлять в язык как можно меньше новых концепций. Это означает минимальное количество нового синтаксиса, ключевых слов и других наименований.
Сложность падает на автора дженерик-кода, а не пользователя
Сложность должна максимально перекладываться на программиста, пишущего дженерик-пакет. Мы не хотим, чтобы пользователь пакета волновался по поводу дженериков. Значит, должна быть возможность естественным образом вызывать дженерик-функции, то есть нужно сообщать обо всех ошибках использования дженерик-пакетов так, чтобы их можно было легко понять и исправить. Также должен быть простой способ отладки вызовов в дженерик-коде.
Автор кода и пользователь могут работать независимо
Нужно легко разделять задачи автора дженерик-кода и его пользователей, чтобы они могли развивать код независимо. Один не должен беспокоиться о том, что делает другой, хотя бы не больше, чем беспокоятся автор и пользователь обычной функции из другого пакета. Вроде бы очевидно, но не во всех языках это условие соблюдается в отношении дженериков.
Быстрая сборка и исполнение
Мы хотим как можно больше сократить длительность сборки и исполнения по сравнению с сегодняшней производительностью Go. C дженериками связаны компромиссы между быстрой сборкой и исполнением. Нам нужно как можно больше ускорить оба процесса.
Сохранение ясности и простоты Go
Самое важное заключается в том, что сейчас Go является простым языком. Программы на Go обычно легко понять. В ходе нашего длительного исследования мы большое внимание уделяем поиску возможности добавления дженериков с сохранением ясности и простоты. Нам нужно найти механизмы, которые хорошо укладываются в текущий язык, которые не превратят его во что-то совершенно другое.
Этим рекомендациям нужно следовать при любых реализациях дженериков в Go. Это моё самое важное сообщение сегодня: дженерики могут дать языку значительные преимущества, но их стоит внедрять лишь в том случае, если Go останется самим собой.
Черновик архитектуры
Думаю, это возможно. Чтобы завершить статью, я хочу от обсуждения необходимости внедрения дженериков и требований к ним перейти к обсуждению архитектуры, с помощью которой дженерики можно внедрить в Go.
На Gophercon в этом году Роберт Гриземер (Robert Griesemer) и я опубликовали черновик архитектуры дженериков в Go. По ссылке вы найдёте все подробности, а здесь я коснусь лишь основных моментов.
Так реализована функция
Reverse
.func Reverse (type Element) (s []Element) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
Тело функции совершенно такое же, изменилась только сигнатура.
Тип элементов слайса исключён. Теперь он называется
Element
и превратился в так называемый параметр типа (type parameter). Вместо того, чтобы быть частью параметра типа слайса, он теперь отдельный, дополнительный параметр типа.Обычно для вызова функции с параметром типа нужно передать аргумент типа, который выглядит как и любой другой аргумент, не считая того, что это тип.
func ReverseAndPrint(s []int) {
Reverse(int)(s)
fmt.Println(s)
}
Это
(int)
, представленный в примере после Reverse
.К счастью, в большинстве случаев, включая этот, компилятор может вывести аргумент типа из типов обычных аргументов, и вам вообще не понадобится упоминать аргумент типа.
Вызов дженерик-функции выглядит как вызов любой другой функции.
func ReverseAndPrint(s []int) {
Reverse(s)
fmt.Println(s)
}
Хотя дженерик-функция
Reverse
чуть сложнее функций ReverseInts
и ReverseStrings
, эта сложность возлагается на автора кода, а не на вызывающего.Контракты
Поскольку Go статически типизирован, нужно обсудить тип параметра типа. Этот метатип говорит компилятору, какого рода аргументы типов разрешены при вызове дженерик-функции, а также какого рода операции может выполнить дженерик-функция со значениями параметра типа.
Функция
Reverse
может работать со слайсами любых типов. Она может только присваивать значения типа Element
, который работает с любыми типами в Go. Для этого вида дженерик-функций, который встречается очень часто, нам не нужно говорить ничего особого о параметре типа.Теперь посмотрим на другую функцию.
func IndexByte (type T Sequence) (s T, b byte) int {
for i := 0; i < len(s); i++ {
if s[i] == b {
return i
}
}
return -1
}
Сейчас пакеты bytes и strings из стандартной библиотеки содержат функцию
IndexByte
. Эта функция возвращает индекс b
в последовательности s
, где s
является строкой или []byte
. Мы могли бы одной этой дженерик-функцией заменить две функции в пакетах bytes и strings. На практике можно этого не делать, но это простой и полезный пример.Теперь нам нужно узнать, как действует параметр
T
— как строка или []byte
. Можно применить к нему len
, индексировать и сравнить результат операции индексирования со значением byte.Для выполнения компиляции самому параметру типа
T
тоже нужен тип. Это будет метатип, но поскольку нам иногда нужно описывать различные взаимосвязанные типы, и поскольку метатип описывает связь между реализацией дженерик-функции и вызывающим её, мы называем тип T
контрактом. В данном случае контракт называется Sequence
. Он идёт после списка параметров типа.Вот как контракт
Sequence
определяется в этом примере.contract Sequence(T) {
T string, []byte
}
Всё просто, потому что и пример простой: параметр типа
T
может быть строкой или []byte
. Контракт может быть новым ключевым словом или специальным идентификатором, который распознаётся в области видимости пакета. Подробности вы можете узнать из документации к черновику архитектуры.Те, кто помнят архитектуру, которую мы представили на Gophercon 2018, заметят, что такой способ написания контракта гораздо проще. Мы получили много отзывов о ранней версии, в которой контракты были гораздо сложнее, и постарались учесть пожелания. Новые контракты гораздо проще писать, читать и понимать.
Контракты позволяют задавать тип параметра типа и/или список методов параметра типа. Также контракты позволяют описывать взаимосвязи между разными параметрами типов.
Контракты с методами
Вот ещё один простой пример функции, использующей метод
String
для возвращения []string
строкового представления всех элементов в s
.func ToStrings (type E Stringer) (s []E) []string {
r := make([]string, len(s))
for i, v := range s {
r[i] = v.String()
}
return r
}
Всё просто: проходим по слайсу, вызываем метод
String
применительно к каждому элементу и возвращаем слайс с получившимся строковыми значениями.Этой функции нужно, чтобы тип элемента реализовывал метод
String
. И контракт Stringer
это гарантирует.contract Stringer(T) {
T String() string
}
Контракт утверждает, что
T
должен реализовывать метод String
.Вы могли заметить, что этот контракт выглядит как интерфейс
fmt.Stringer
, так что нужно указать на то, что аргумент функции ToStrings
не является слайсом fmt.Stringer
. Это слайс какого-то типа элементов, и тип элементов реализует fmt.Stringer
. Представления памяти слайса типа элементов и слайса fmt.Stringer
обычно различаются, и Go не поддерживает прямое преобразование между ними. Так что лучше не полениться и написать, даже если fmt.Stringer
существует.Контракты с несколькими типами
Вот пример контракта с несколькими параметрами типов.
type Graph (type Node, Edge G) struct { ... }
contract G(Node, Edge) {
Node Edges() []Edge
Edge Nodes() (from Node, to Node)
}
func New (type Node, Edge G) (nodes []Node) *Graph(Node, Edge) {
...
}
func (g *Graph(Node, Edge)) ShortestPath(from, to Node) []Edge {
...
}
Здесь описан граф, построенный из узлов и рёбер. Мы не требуем для него определённую структуру данных. Вместо этого мы говорим, что тип
Node
должен содержать метод Edges
, который возвращает список рёбер, соединённых с Node
. А тип Edge
должен иметь метод Nodes
, который возвращает два Nodes
, соединённых Edge
.Я опустил реализацию, но здесь показана сигнатура функции
New
, которая возвращает Graph
, и сигнатура метода ShortestPath
в Graph
.Важный вывод заключается в том, что контракт не обязательно относится к какому-то одному типу. Он может описывать взаимосвязи между двумя и больше типами.
Упорядоченные типы (Ordered types)
В Go удивительно часто жалуются на отсутствие функции
Min
. Ну, или Max
. Причина в том, что полезная функция Min
должна работать только с упорядоченными типами, то есть она должна быть дженериком.Поскольку писать
Min
самостоятельно довольно просто, любая полезная реализация дженериков должна позволять нам добавлять эту функцию в стандартную библиотеку. Вот как она выглядит в нашей архитектуре:func Min (type T Ordered) (a, b T) T {
if a < b {
return a
}
return b
}
Контракт
Ordered
говорит о том, что тип T
должен быть упорядоченным, то есть контракт поддерживает операторы вроде «меньше чем», «больше чем», и так далее.contract Ordered(T) {
T int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64,
string
}
Контракт
Ordered
— это просто список всех упорядоченных типов, определённых языком. Контракт принимает любые типы из списка, или любые именованные типы, в основе которых лежит какой-то тип из списка. По сути, любой тип можно использовать с оператором «меньше чем».Гораздо проще перечислить типы, поддерживающие оператор «меньше чем», чем изобрести новую нотацию, работающую со всеми операторами. Наконец, в Go операторы поддерживаются только встроенными типами.
Тот же подход можно использовать применительно к любому оператору, или, в более общем плане, написать контракт для любой дженерик-функции, которая должна работать со встроенными типами. Это позволяет тому, кто пишет дженерик-функцию, явно указать набор типов, с которыми должна использоваться функция. И это позволяет вызывающему дженерик-функцию ясно видеть, применима ли функция к типам, с которыми используется.
На практике этот контракт, вероятно, попадёт в стандартную библиотеку. И поэтому функция
Min
(которая, вероятно, тоже окажется в стандартной библиотеке) будет выглядеть так. Здесь мы просто ссылаемся на контракт Ordered
, определённый в контрактах пакета.func Min (type T contracts.Ordered) (a, b T) T {
if a < b {
return a
}
return b
}
Дженерик-структуры данных
Наконец, давайте посмотрим на простую дженерик-структуру данных, двоичное дерево. В этом примере дерево содержит функцию сравнения, поэтому к типам элементов не предъявляется никаких требований.
type Tree (type E) struct {
root *node(E)
compare func(E, E) int
}
type node (type E) struct {
val E
left, right *node(E)
}
Так создаётся новое двоичное дерево. Функция сравнения передаётся в функцию
New
.func New (type E) (cmp func(E, E) int) *Tree(E) {
return &Tree(E){compare: cmp}
}
Не экспортированные методы возвращают указатель либо на слот, содержащий
v
, либо на место в дереве, в которое она должна отправиться.func (t *Tree(E)) find(v E) **node(E) {
pn := &t.root
for *pn != nil {
switch cmp := t.compare(v, (*pn).val); {
case cmp < 0:
pn = &(*pn).left
case cmp > 0:
pn = &(*pn).right
default:
return pn
}
}
return pn
}
Подробности в данном случае не имеют значения, особенно в свете того, что я не тестировал этот код. Я лишь пытаюсь показать, на что похоже написание простой дженерик-структуры данных.
Этот код тестирует, содержит ли дерево значение.
func (t *Tree(E)) Contains(v E) bool {
return *t.find(e) != nil
}
This is the code for inserting a new value.
func (t *Tree(E)) Insert(v E) bool {
pn := t.find(v)
if *pn != nil {
return false
}
*pn = &node(E){val: v}
return true
}
Обратите внимание на аргумент типа
E
в типе узла. Так выглядит написание дженерик-структуры данных. Пишется так же, как обычный код на Go, за исключением того, что там и сям разбросаны аргументы типов.Пользоваться деревом просто.
var intTree = tree.New(func(a, b int) int { return a - b })
func InsertAndCheck(v int) {
intTree.Insert(v)
if !intTree.Contains(v) {
log.Fatalf("%d not found after insertion", v)
}
}
Так и должно быть. Писать дженерик-структуру данных немного сложнее, потому что зачастую нужно явно прописывать аргументы типов для поддерживаемых типов. Но максимально возможное использование такой структуры ничем не отличается от использования обычной не-дженерик-структуры данных.
Следующие шаги
Мы работаем над фактическими реализациями, которые позволяют нам экспериментировать с этой архитектурой. Важно иметь возможность испытать её на практике, чтобы быть уверенными в том, что мы можем писать такие программы, какие хотим. Работа движется не так быстро, как мы надеялись, но по мере поступления новой информации об этих реализациях мы будем делиться с вами подробностями.
Роберт Гризмер написал подготовительный CL, который модифицирует пакет go/types. Это позволяет протестировать, может ли код, использующий дженерики и контракты, выполнять проверку типов. Работа ещё не закончена, но для одного пакета эта фича по большей части работает, и мы продолжим разработку.
Нам хотелось бы, чтобы с помощью этой и последующими реализациями люди пытались писать и использовать дженерик-код, смотрели, что происходит. Мы хотим быть уверены, что люди могут писать нужный им код, и что они могут использовать его как ожидается. Конечно, сначала не всё будет работать, и по мере работы мы что-то изменим. И нам гораздо интереснее отзывы о семантике, чем о подробностях синтаксиса.
Хочу поблагодарить всех, кто комментировал предыдущую архитектуру, и всех, кто обсуждал возможный облик дженериков в Go. Мы прочитали все комментарии и очень благодарны за ваш труд. Без него мы не пришли бы к тому, к чему пришли.
Наша цель — создать архитектуру, позволяющую писать рассмотренные мной выше разновидности дженерик-кода, не усложняя язык настолько, чтобы он стал слишком сложен в использовании или уже не ощущался бы как Go. Мы надеемся, что эта архитектура — шаг к цели, и будем продолжать улучшать её, опираясь на свой и ваш опыт в том, что работает, а что нет. Если мы достигнем этой цели, то сможем что-то предложить для будущих версий Go.