Go: Зачем приносить дженерики

Go
Go: Зачем приносить дженерики

Go: Зачем приносить дженерики

  • Китайская версия
  • English version

вводить

Это речевая версия, опубликованная на Gophercon 2019. Видео ссылки доступны. ]

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

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

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

Этот проект принесет больше документации, кода и обсуждений дженериков Go.

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

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

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

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

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

Допустим, это int slice.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Найти минимальный/максимальный элемент в срезе

  • Найдите среднее/стандартное отклонение среза

  • Вычислить карты объединения/пересечения

  • Найти кратчайший путь в узле/ребре

  • Применить функцию преобразования к срезу/карте, возвращая новый срез/карту

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

Есть также несколько специфичных для Go примеров, которые сильно поддерживают параллелизм.

  • читать с канала с тайм-аутом

  • Объединить два канала в один канал

  • Параллельно вызывать список функций, возвращая часть результатов

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

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

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

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

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

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

  • Sets

  • Самобалансирующееся дерево, вставка по порядку и обход по строкам

  • Multimaps с несколькими экземплярами ключа

  • Параллельные хэш-карты, которые поддерживают параллельные вставки и поиски без единой блокировки.

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

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

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

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

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

выгоды и затраты

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

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

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

* Минимизируйте новые концепции

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

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

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

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

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

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

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

* Держите Go для ясности и простоты

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

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

эскизный проект

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

В этом году на Gophercon мы с Робертом Гриземером представили проект добавления дженериков в Go. Подробности смотрите в черновике. Здесь я буду обсуждать некоторые моменты.

Это общая обратная функция в этом плане.

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 и ReverseString, эта сложность ложится на функцию, а не на запись и вызов.

договор

Так как 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 имеют функцию indexbyte. Эта функция возвращает последовательность индекса B, в которой S строку или [] байт. Мы можем использовать эту функцию для замены единых общих строк пакетных байтов и две функции. На практике мы не можем делать, но это простой пример полезного.

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

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

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

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

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

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

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

договор с методом

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

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. Строковые контракты гарантируют это.

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 и Edge. Нам не нужна определенная структура данных для Graph. Вместо этого мы говорим, что тип Node должен иметь метод Edges, возвращающий список Edges, подключенных к Node. И тип Edge должен иметь метод Nodes, возвращающий два узла, к которым подключен Edge.

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

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

упорядоченный тип

Удивительно распространенная жалоба на 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
}

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

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

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

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

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

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

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

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

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

Автор: Ян Лэнс Тейлор.

Оригинал: https://blog.golang.org/why-generics

Перевод: https://github.com/llgoer/go-generics

Категории