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

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