<code>func ReverseInts(s []int) {
  first := 0
  last := len(s)
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}
</code>

<code>func ReverseInts(s []int) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}
</code>

<code>func ReverseStrings(s []string) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}
</code>

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

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

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

Дженерик программирование в Go сегодня

Итак, как люди пишут такой код в Go?

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

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

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

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

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

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

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

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

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

Что дженерики могут принести в Go

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

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

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

Я подробно рассмотрел Reverse, но существует множество других функций, которые можно написать с использованием дженериков, например:

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

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

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

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

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

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

Также, как я писал ранее, это не только функции. Это также структуры данных.

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

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

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

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

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

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

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

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

Преимущества и затраты

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

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

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

Минимизировать новые концепции

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

Сложность лежит на авторе дженерикового кода, а не на пользователе

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

Автор и пользователь могут работать независимо

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

Краткое время сборки, быстрое время выполнения

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

Сохранить ясность и простоту Go

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

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

Черновой дизайн

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

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

На Gophercon этого года Роберт Гриземер и я опубликовали черновой дизайн для добавления дженериков в Go. См. черновой дизайн для полной информации. Я кратко расскажу о некоторых основных моментах здесь.

Вот дженериковая функция Reverse в данном дизайне.

<code>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--
  }
}
</code>

Вы заметите, что тело функции абсолютно такое же. Изменилась только сигнатура.

Тип элемента среза был выделен. Теперь он назван Element и стал тем, что мы называем параметром типа. Вместо того чтобы быть частью типа параметра среза, он теперь является отдельным, дополнительным, параметром типа.

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

<code>func ReverseAndPrint(s []int) {
  Reverse(int)(s)
  fmt.Println(s)
}
</code>

Это (int), видимый после Reverse в данном примере.

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

Вызов дженериковой функции выглядит так же, как вызов любой другой функции.

<code>func ReverseAndPrint(s []int) {
  Reverse(s)
  fmt.Println(s)
}
</code>

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

Контракты

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

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

Рассмотрим краткий пример другой функции.

<code>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
}
</code>

В настоящее время и пакет bytes, и пакет strings в стандартной библиотеке имеют функцию IndexByte. Эта функция возвращает индекс b в последовательности s, где s — это либо string, либо []byte. Мы могли бы использовать эту единственную дженериковую функцию, чтобы заменить две функции в пакетах bytes и strings. На практике мы можем не тратить времени на это, но это полезный простой пример.

Здесь нам нужно знать, что параметр типа T ведёт себя как string или []byte. Мы можем вызвать len на нём, можем индексировать по нему, и можем сравнить результат операции индексирования со значением типа byte.

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

Вот как определяется контракт Sequence для этого примера.

<code>contract Sequence(T) {
  T string, []byte
}
</code>

Он довольно прост, поскольку это простой пример: параметр типа T может быть либо string, либо []byte. Здесь contract может быть новым ключевым словом или специальным идентификатором, распознаваемым в области видимости пакета; подробности смотрите в проекте дизайна.

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

Они позволяют указать базовый тип параметра типа и/или перечислить методы параметра типа. Также они позволяют описать взаимосвязь между различными параметрами типа.

Контракты с методами

Вот ещё один простой пример — функция, которая использует метод String для возврата []string строкового представления всех элементов в s.

<code>func ToStrings (type E Stringer) (s []E) []string {
  r := make([]string, len(s))
  for i, v := range s {
    r[i] = v.String()
  }
  return r
}
</code>

Всё довольно просто: пройдите по срезу, вызовите метод String для каждого элемента и верните срез полученных строк.

Эта функция требует, чтобы тип элемента реализовывал метод String. Контракт Stringer обеспечивает это.

<code>contract Stringer(T) {
  T String() string
}
</code>

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

Можно заметить, что этот контракт выглядит как интерфейс fmt.Stringer, поэтому стоит отметить, что аргумент функции ToStrings не является срезом fmt.Stringer. Это срез какого-то типа элемента, где тип элемента реализует fmt.Stringer. Память, занимаемая срезом типа элемента и срезом fmt.Stringer, обычно различна, и Go не поддерживает прямые преобразования между ними. Таким образом, стоит написать это, даже если fmt.Stringer уже существует.

Контракты с несколькими типами

Вот пример контракта с несколькими параметрами типа.

<code>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 {
  ...
}
</code>

Здесь мы описываем граф, построенный из узлов и рёбер. Мы не требуем конкретной структуры данных для графа. Вместо этого мы говорим, что тип Node должен иметь метод Edges, который возвращает список рёбер, подключённых к данному Node. А тип Edge должен иметь метод Nodes, который возвращает два Node, между которыми проходит Edge.

Я пропустил реализацию, но это демонстрирует сигнатуру функции New, возвращающей Graph, и сигнатуру метода ShortestPath у Graph.

Важно понимать, что контракт не ограничивается одним типом. Он может описывать отношения между двумя или более типами.

Упорядоченные типы

Одна удивительно распространённая жалоба на Go — это отсутствие функции Min. Или, скажем, функции Max. Это происходит потому, что полезная функция Min должна работать с любым упорядоченным типом, а значит, она должна быть дженериком.

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

<code>func Min (type T Ordered) (a, b T) T {
  if a < b {
    return a
  }
  return b
}
</code>

Контракт Ordered говорит, что тип T должен быть упорядоченным типом, то есть он должен поддерживать операторы, такие как меньше, больше и так далее.

<code>contract Ordered(T) {
  T int, int8, int16, int32, int64,
  uint, uint8, uint16, uint32, uint64, uintptr,
  float32, float64,
  string
}
</code>

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

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

Тот же подход можно использовать для любого оператора или, более общим образом, для написания контракта для любой дженерической функции, предназначенной для работы с встроенными типами. Это позволяет автору дженерической функции чётко указать набор типов, с которыми предполагается использование функции. А также позволяет вызывающей стороне чётко видеть, применима ли функция к используемым типам.

На практике этот контракт, вероятно, будет находиться в стандартной библиотеке, и поэтому действительно функция Min (которая, вероятно, также будет находиться в стандартной библиотеке где-то) будет выглядеть следующим образом. Здесь мы просто обращаемся к контракту Ordered, определённому в пакете contracts.

<code>func Min (type T contracts.Ordered) (a, b T) T {
  if a < b {
    return a
  }
  return b
}
</code>

Дженериковые структуры данных

Наконец, рассмотрим простую дженериковую структуру данных — бинарное дерево. В этом примере дерево имеет функцию сравнения, поэтому не существует никаких требований к типу элементов.

<code>type Tree (type E) struct {
  root    *node(E)
  compare func(E, E) int
}
type node (type E) struct {
  val         E
  left, right *node(E)
}
</code>

Вот как создать новое бинарное дерево. Функция сравнения передаётся в функцию New.

<code>func New (type E) (cmp func(E, E) int) *Tree(E) {
  return &Tree(E){compare: cmp}
}
</code>

Неэкспортируемый метод возвращает указатель либо на ячейку, содержащую v, либо на место в дереве, куда она должна быть помещена.

<code>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
      }
      </code>

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

Это код для проверки, содержится ли значение в дереве.

<code>func (t *Tree(E)) Contains(v E) bool {
  return *t.find(e) != nil
}
</code>

Это код для вставки нового значения.

<code>func (t *Tree(E)) Insert(v E) bool {
  pn := t.find(v)
  if *pn != nil {
    return false
  }
  *pn = &node(E){val: v}
  return true
}
</code>

Обратите внимание, что тип node имеет аргумент типа E. Вот так выглядит написание дженериковой структуры данных. Как видно, это выглядит как обычный код на Go, за исключением того, что некоторые аргументы типа разбросаны по нему.

Использовать дерево довольно просто.

<code>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)
  }
}
</code>

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

Следующие шаги

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

Роберт Гриземер написал предварительный CL который изменяет пакет go/types. Это позволяет протестировать, может ли код, использующий дженерики и контракты, пройти проверку типов. В настоящее время реализация неполная, но она в основном работает для одного пакета, и мы продолжим работать над ней.

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

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

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