Хабрахабр

[Перевод] Зачем нужны дженерики в Go?

Эта статья о том, что будет означать добавление дженериков в Go, и почему я считаю, что нам это следует сделать. Также я коснусь возможного изменения архитектуры языка ради добавления дженериков.

Меньше чем через сутки появился первый комментарий про дженерики. Go вышел 10 ноября 2009-го. В нём также упомянуты исключения, которые мы добавили в язык в виде паники и восстановления (panic and recover) в начале 2010-го.

За три года наблюдений отсутствие дженериков всегда входило список трёх главных проблем, которые необходимо исправить в языке.

Что означает добавление дженериков и почему мы этого хотим?

Перефразируя Jazayeri и других: программирование с дженериками позволяет представлять функции и структуры данных в виде дженериков, исключая типы.

Что это означает?

Это не слишком распространённая задача, но и не такая уж редкая. Допустим, нам нужно представить элементы слайса в обратном порядке.

Пусть у нас есть слайс целых чисел.

func ReverseInts(s []int)
}

Выглядит просто. Но даже для простой функции вроде этой вам может понадобиться написать несколько тестов. И когда я это сделал, то обнаружил баг. Уверен, многие его уже заметили.

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, работающую со слайсами любых типов.

В большинстве других языков вы можете написать такую функцию.

В Go так нельзя, потому что это статически типизируемый язык, он требует прописать конкретный тип слайса и тип его элементов. В динамически типизируемых языках вроде Python или JavaScript вы можете просто написать функцию без указания типа элементов.

Большинство других статически типизируемых языков, вроде С++, Java, Rust или Swift, поддерживают дженерики именно для таких ситуаций.

Так как же люди пишут подобный код на Go?

Так работает функция sort. В этом языке вы можете написать функцию, которая работает с разными типами слайсов с помощью интерфейсного типа (interface type) и определения метода для типов слайсов, которые вы хотите передавать. Sort из стандартной библиотеки.

Они позволяют выявлять общие аспекты разных типов и выражать их в виде методов. Иными словами, интерфейсные типы в Go — это разновидность программирования с дженериками. Затем можно писать функции, использующие эти интерфейсные типы, и функции будут работать с любыми типами, реализованными в этих методах.

Нужно самостоятельно писать методы в интерфейсах. Но этот подход не соответствует нашим желаниям. А методы, которые вы пишете, будут совершенно одинаковыми для всех типов слайсов, так что мы не исключили код, а, в каком-то смысле, перенесли и уплотнили. Довольно странно определять именованный тип с парой методов чтобы лишь поменять порядок элементов в слайсе. Хотя интерфейсы — это способ представления дженериков, они не дают нам всего, что нам нужно от дженериков.

Сейчас Go этого не поддерживает, но, к примеру, язык может определять, чтобы каждый тип слайса имел метод Index, возвращающий элемент. Другой способ использования интерфейсов для дженериков, при котором не нужно писать методы, заключается в том, чтобы переложить на язык обязанность определять методы для каких-то типов. Не будет способа определять дженерик-функцию, которая берёт два разных слайса с элементами одного типа, или которая берёт карту с элементами одного типа и возвращает слайс с элементами такого же типа. Но чтобы использовать этот метод на практике, потребуется возвращать пустой тип интерфейса, и тогда мы теряем все преимущества статического типизирования. Мы не хотим терять преимущества статического типизирования ради выгод дженериков. Go статически типизирован потому, что это облегчает написание больших программ.

Кроме того, потребовалось бы делать явные утверждения типов и отказаться от проверки на статичность типов. Ещё один подход заключается в написании дженерик-функции Reverse, использующей пакет reflect, но это было бы слишком странно и работал бы чересчур медленно.

Для этого подходят несколько генераторов. Или можно написать генератор кода, который берёт тип и генерирует функцию Reverse для слайсов этого типа. Но такое решение прибавляет ещё один этап в каждый пакет, которому понадобится Reverse, что усложняет сборку из-за необходимости компилирования всех копий, а исправление багов в исходном коде потребует перегенерирования всех экземпляров, некоторые из которых могут уже задействоваться в совершенно других проектах.

Потом им нужно написать тесты для функций, чтобы удостовериться, что они не сделали простых ошибок, вроде той, что я сделал в начале. Все описанные подходы достаточно странные, и я думаю, что большинство программистов, которым нужно менять порядок в слайсах на Go, просто пишут функцию для конкретного типа слайса. А потом придётся рутинно прогонять эти тесты.

Дело не в том, что это невозможно. И когда мы это делаем, это означает, что мы делаем кучу лишней работы просто ради функции, которая выглядит точно так же, за исключением типа элементов. Просто должен быть способ получше. Это точно возможно, и программисты на Go так и делают.

Выше я написал, что программирование с дженериками позволяет представлять функции и структуры данных в виде дженериков исключая типы. Для статически типизированных языков вроде Go этот способ получше называется дженериками. Именно это нам и нужно.

Первое и самое важное, что нам нужно от дженериков в Go, это возможность писать функции вроде Reverse и не беспокоиться о типах элементов в слайсах. Мы хотим исключить тип элементов. Также мы хотим писать функцию и тесты однократно, класть их в доступный для Go пакет и вызывать по мере необходимости.

А поскольку мы говорим об open source, то будет ещё лучше, если кто-нибудь сможет написать Reverse один раз, а мы все будем пользоваться этой реализацией.

В этой статье я подразумеваю под «дженериками» то, что описал выше. Здесь мне следует сказать, что термин «дженерики» может обозначать много разного. В частности, я не имею в виду шаблоны, как в С++, которые поддерживают гораздо больше возможностей, чем я перечислил.
Я подробно рассказал о Reverse, но есть и много других функций, которые мы могли бы писать как дженерики, например:

  • Поиск наименьшего или наибольшего элемента в слайсе.
  • Поиск среднего или стандартного отклонения в слайсе.
  • Вычисление модуля или пересечения в карте.
  • Поиск кратчайшего пути в графе с узлами или рёбрами.
  • Применение к слайсу или карте функции преобразования, которая возвращает новый слайс или карту.

Эти примеры доступны в большинстве других языков. Фактически, я написал этот список, просто посмотрев на шаблоны из стандартной библиотеки С++.

Есть примеры, характерные для Go с его строгой поддержкой параллелизма.

  • Чтение из канала без таймаута.
  • Комбинирование двух каналов в один.
  • Параллельный вызов списка функций, который возвращает слайс результатов.
  • Вызов списка функций с использованием Context, возвращающий результат первой завершаемой функции, отменяющий и очищающий дополнительные горутины.

Я много раз видел все эти функции, с разными типами. Их не трудно написать на Go. Но лучше было бы хорошо многократно использовать эффективную и отлаженную реализацию, которая работает для всех типов.

Есть много других функций общего назначения, которые будет проще и безопаснее писать с использованием дженериков. Чтобы не было недопонимания, это всего лишь примеры. Кроме того, как написал выше, это не только функции, а ещё и структуры данных.

Они могут содержать значения любых типов, с проверкой на статичность типов значений, которые хранятся и извлекаются. В Go встроены две дженерик-структуры данных общего назначения: слайсы и карты. То есть, когда у меня есть []int, слайс содержит сами числа, а не числа, преобразованные в интерфейсный тип. Значения хранятся сами по себе, а не как интерфейсные типы.

Вот другие: Слайсы и карты — самые полезные дженерик-структуры данных, но они не единственные.

  • Наборы.
  • Самобалансирующиеся деревья с эффективной вставкой и обходом в порядке сортировки.
  • Мальтикарты с многочисленными экземплярами ключа.
  • Конкуретные карты хэшей, поддерживающие параллельную вставку и поиск безо всяких блокировок.

Если мы можем писать дженерик-типы, мы можем определять новые структуры данных, вроде тех, что имеют те же преимущества проверки типов, как у слайсов и карт: компилятор может статически проверить типы значений, которые они содержат, и значения могут храниться сами по себе, а не как интерфейсные типы.

Должна быть возможность взять алгоритмы, вроде упомянутых мной выше, и применить их к дженерик-структурам данных.

Они должны работать как слайсы и карты, в том смысле, что они должны хранить не значения пустых интерфейсных типов, а конкретные типы, которые будут проверяться при компиляции. Все эти примеры должны быть такими же, как в случае с Reverse: дженерик-функции и структуры пишутся один раз, помещаются в пакет, а затем многократно используются там, где нужно.

Дженерики могут стать эффективными кирпичиками, позволяющими делиться кодом и проще создавать программы. Вот какую пользу может извлечь Go из дженериков.

Надеюсь, я смог объяснить, почему имеет смысл их изучить.

Но дженерики не появляются из Big Rock Candy Mountain, края, в котором солнце каждый день сияет над лимонадными источниками. У каждого изменения языка есть своя цена. Несомненно, что добавление дженериков в Go усложнит язык. Как и с любым изменением, нам нужно обсудить максимизацию преимуществ и минимизацию цены.

Мы снижаем сложность, делая эти особенности простыми, и увеличиваем преимущества этих свойств, обеспечивая свободную комбинируемость. В Go мы старались уменьшить сложность с помощью независимых, самостоятельных особенностей, которые можно свободно комбинировать друг с другом. То же самое мы хотим сделать и с дженериками.

Чтобы выражаться конкретнее, приведу несколько рекомендаций, которым мы должны следовать.

Это означает минимальное количество нового синтаксиса, ключевых слов и других наименований. Минимизация новых концепций
Нужно добавлять в язык как можно меньше новых концепций.

Мы не хотим, чтобы пользователь пакета волновался по поводу дженериков. Сложность падает на автора дженерик-кода, а не пользователя
Сложность должна максимально перекладываться на программиста, пишущего дженерик-пакет. Также должен быть простой способ отладки вызовов в дженерик-коде. Значит, должна быть возможность естественным образом вызывать дженерик-функции, то есть нужно сообщать обо всех ошибках использования дженерик-пакетов так, чтобы их можно было легко понять и исправить.

Один не должен беспокоиться о том, что делает другой, хотя бы не больше, чем беспокоятся автор и пользователь обычной функции из другого пакета. Автор кода и пользователь могут работать независимо
Нужно легко разделять задачи автора дженерик-кода и его пользователей, чтобы они могли развивать код независимо. Вроде бы очевидно, но не во всех языках это условие соблюдается в отношении дженериков.

C дженериками связаны компромиссы между быстрой сборкой и исполнением. Быстрая сборка и исполнение
Мы хотим как можно больше сократить длительность сборки и исполнения по сравнению с сегодняшней производительностью Go. Нам нужно как можно больше ускорить оба процесса.

Программы на 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 статически типизирован, нужно обсудить тип параметра типа. Этот метатип говорит компилятору, какого рода аргументы типов разрешены при вызове дженерик-функции, а также какого рода операции может выполнить дженерик-функция со значениями параметра типа.

Она может только присваивать значения типа Element, который работает с любыми типами в Go. Функция Reverse может работать со слайсами любых типов. Для этого вида дженерик-функций, который встречается очень часто, нам не нужно говорить ничего особого о параметре типа.

Теперь посмотрим на другую функцию.

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. На практике можно этого не делать, но это простой и полезный пример.

Можно применить к нему len, индексировать и сравнить результат операции индексирования со значением byte. Теперь нам нужно узнать, как действует параметр T — как строка или []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 применительно к каждому элементу и возвращаем слайс с получившимся строковыми значениями.

И контракт Stringer это гарантирует. Этой функции нужно, чтобы тип элемента реализовывал метод String.

contract Stringer(T) { T String() string
}

Контракт утверждает, что T должен реализовывать метод String.

Stringer, так что нужно указать на то, что аргумент функции ToStrings не является слайсом fmt. Вы могли заметить, что этот контракт выглядит как интерфейс fmt. Это слайс какого-то типа элементов, и тип элементов реализует fmt. Stringer. Представления памяти слайса типа элементов и слайса fmt. Stringer. Так что лучше не полениться и написать, даже если fmt. Stringer обычно различаются, и Go не поддерживает прямое преобразование между ними. 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.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть