Дженерики в Golang

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

Go был выпущен 10 ноября 2009 года. Менее чем через 24 часа появился первый комментарий о дженериках. (В этом комментарии также упоминаются исключения, которые были добавлены к языку, в форме panic и recover в начале 2010 года.)

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

Почему дженерики?

Но что значит добавить дженерики, и зачем это нужно?

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

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

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

Допустим, это срез int.

func ReverseInts(s []int) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        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, потому что Go имеет статическую типизацию и требует, чтобы вы записали точный тип среза и тип элементов среза.

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

Обобщенное программирование в Go сегодня

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эскизный дизайн дженериков в Go

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

В Gophercon 2019 Robert Griesemer и Ian Lance Taylor опубликовали черновик проекта для добавления дженериков в 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 и стал тем, что называется параметром типа. Вместо того, чтобы быть частью типа параметра slice, теперь это отдельный дополнительный параметр типа.

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

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 является либо string, либо []byte. Можно было бы использовать эту единую универсальную функцию для замены двух функций в пакетах bytes и strings. На практике можно не беспокоиться об этом, но это полезный простой пример.

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

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

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

contract Sequence(T) {
    T string, []byte
}

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

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

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

Вот еще один простой пример функции, которая использует метод 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, который возвращает два Node, которые соединяет Edge.

Реализация здесь пропущена, но она показывает сигнатуру функции New, которая возвращает Graph, и сигнатуру метода ShortestPath в Graph.

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

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

Одна удивительно распространенная жалоба на Go состоит в том, что у него нет функции Min. Или функции Max. Функции Min нет потому, что полезная функция 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 контракт, определенный в пакете contracts.

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
}

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

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 для типа node. Вот как выглядит общая структура данных. Как вы можете видеть, это похоже на написание обычного кода 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)
    }
}

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

---

Читайте также:

• Go FAQ: Почему в Go нет универсальных типов (generics)?
• Go FAQ: Почему в Go нет наследования типов?
• Объектно-ориентированное программирование с наследованием в Golang