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

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

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

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

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

Что же такое «добавление дженериков» и зачем это вообще нужно?

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

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

Предположим, что это целочисленный массив.

			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.

Теперь создадим функцию для осуществления такой же операции с массивом строк.

			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 такой способ не сработает, поскольку это язык со статической типизацией и требует точного указания типа среза и типа его элементов. Большая часть других языков со статической типизацией, таких как C++, Java, Rust или Swift, поддерживает дженерики, чтобы устранить это затруднение.

Как Go обходится без дженериков сейчас

Интерфейсы

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

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

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

Методы по умолчанию

Ещё один способ, при котором нам не придётся самостоятельно писать методы — определение в самом языке методов по умолчанию для некоторых типов. В настоящее время такой подход не поддерживается в Go, но, к примеру, в языке можно было бы определить для каждого массива метод Index, возвращающий элемент. Однако, чтобы использовать этот способ на практике, метод должен возвращать пустой интерфейсный тип, а в таком случае мы потеряем все преимущества статического типирования. Более того, мы не смогли бы создать функцию, которая принимает два среза с элементами одного типа или map с элементами определённого типа и возвращает срез. Статическая типизация облегчает Go создание больших программ. И не хотелось бы терять это преимущество ради плюсов, которые дают дженерики.

Пакет reflect

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

Генераторы кода

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

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

Не слишком ли много лишней работы ради функций, которые отличаются только типом элемента? Должен быть способ намного лучше!

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

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

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

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

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

Мы сосредоточились на функции Reverse, однако с помощью дженериков можно сделать гораздо больше:

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

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

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

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

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

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

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

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

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

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

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

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

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

Чем придётся пожертвовать

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

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

Ниже приведён список правил, которых стоит придерживаться при модификации языка:

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

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

Наброски изменений

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

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

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

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

			func ReverseAndPrint(s []int) {
    Reverse(int)(s)
    fmt.Println(s)
}
		

В данном примере это (int).

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

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

			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
}
		

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

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

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

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

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

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

Если вы вспомните, о чём говорилось на Gophercon’е 2018, то увидите, что способ определения контрактов сильно упростился. Разработчики учли отзывы участников конвента, которым контракты образца 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, создание функции ToStrings имеет смысл.

Контракты с множественными типами

Вот пример контракта со множеством параметров типа:

			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.

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

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

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

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

Контракт 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
}
		

А этот код добавляет новое значение:

			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. С ней можно потестировать проверку типов в коде с использованием дженериков и контрактов. Версия неполная и постоянно дорабатывается, но с одним пакетом работает неплохо.

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

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