关于 Go 泛型 (Generics)

未匹配的标注

本文为官方 Go Blog 的中文翻译,详见 翻译说明

Ian Lance Taylor
2019 年 7 月 31 日

介绍

这是我上周在 Gophercon 2019 上的讲话的博文版本。

www.youtube.com/watch?v=WzgLqE-3Ih...

这篇文章的主题是加入泛型对于 Go 到底意味着什么,和我为什么认为应当加入泛型。我也会蜻蜓点水地说一说在更新之中一种给 Go 加入泛型的可能的设计方式。

Go 在 2009 年 11 月 10 日发行。还不到 24 小时,我们就看到了关于泛型的第一个条篇论。(那条评论同样也说到了异常,我们在 2010 年上半年用 panic 和 recover 的形式把这加入到语言成分之中。)

在 Go 语言三年以来的用户问卷调查之中,对泛型的缺乏一直都被列在需要处理的首要问题之中。

为什么是泛型呢?

但是加入泛型到底意味着什么,而且为什么我们需要泛型呢?

Jazayeri 等人 解释道:泛型编程,让我们能够使用一种消除了类型区分的一般形式,来表达函数和数据结构。

这是什么意思?

举一个简单的例子,假设我们要把一个切片整体前后颠倒。这虽然看起来不是多少程序员会去干的事情,但也不是什么离谱的事。

比如说吧,这是一个整数类型的切片。

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

挺简单的,但是即是是这么简单的函数,可能也需要写那么几个测试用例。实际上,我这么做了,还发现了 bug。相信很多读者已经看到那个 bug 了。

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

我们需要在设定 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 之中一样的套路可不行,因为 Go 是静态类型的语言,要求你明确写出切片和切片元素的类型。

大多其他静态类型的语言,比如 C++ 或者 Java、Rust、Swift,都支持使用泛型来面对这种类型处理问题。

Go 范型编程在当下

实际上大家是怎么在 Go 之中写这样的代码的呢?

在 Go 之中你可以使用接口类型来写一个对不同类型的切片都可用的函数,同时对你需要传入的切片类型定义相应的方法。这正是 sort.Sort 标准库所采用的策略。

换句话说,Go 语言之中的接口类型是范型编程的一种形式。接口让我们能够在捕捉不同类型之间的相似性之后,用方法来描述这种相似性。我们可以写对接口类型作用的函数,这些函数将会对实现了指定方法的所有类型生效。

但是这样的手段远远达不到我们想要的程度。用上接口,你还是得自己手动加上各种联系类型的方法。只是为了把一个切片颠倒一下,就定义一种类型感觉上还是有点膈应。而且你给不同类型的切片写的方法还都是一模一样的。所以这样我们不过是把重复的代码整合压缩到了一起,并没将其消除。虽说接口是范型的一种形式,但是它并没有满足范型能给我们的全部。

另一种不同的、绕过自己写方法的需要的用接口实现范型策略,就是让语言本身为某些类型定义方法。在当下这还不是语言本身所支持的,但是,比如说语言本身可以定义任何一个切片都有一个返回一个元素的索引方法。但是为了在实践之中使用这样的方法,这个方法必须返回一个空接口类型,于是就失去了静态类型所带来的好处。更微妙的是,这样是无法定义接受两个元素类型相同的不同切片的函数的,亦或是接受某一种元素类型的 map 然后返回同样元素类型的切片的函数。Go 是静态类型的语言,因为静态类型会让大型程序的工作更加简单。我们是不愿意为了得到范型带来的好处而失去静态类型带来的优点的。

另一个方法就是使用反射包来写范型的  Reverse 函数,但是这写起来恶心,跑起来又慢,基本没有人会这么做。这个方法通常需要显式的类型断言,也是没有静态类型检查的。

或者,你可以写一个接受元素类型,生成相应 Reverse 函数的代码生成器(generator)。现在已经有那么几个代码生成器就是做这个的了。但是这样给所有需要使用 Reverse 的包都带来了一个新的步骤,这使得生成(build)变得更加复杂。因为所有不同的版本都得被编译,而且在主源文件之中修复 bug 需要把所有实例重生成,这些实例可能有些根本就是在另一个项目之中。

所有这些方法都算是有够奇怪的,以至于我认为 Go 语言之中,需要颠倒一个切片的人也就是为自己需要的切片类型写个函数就算了。然后接下来他们就转到写测试用例来确保不会出现我那样的基础错误这种事情上了。然后例行的运行测试。

不论我们用的是什么方法,处理这样的函数都意味着我们要为一组除了类型看起来都一样的函数,做不少额外的工作。这不是说事情做不成了。显然是可以的,Go 程序员也在做着。只是理应有更好的方法。

像是 Go 语言这样的静态类型语言,那一个更好的方法就是范型。我早些就提到,范型让我们能够用一种更加一般的形式,去描述函数去除了类型之后的信息。这正是我们折腾那么多想要做到的。

范型能给 Go 带来什么

首先,最重要的一个,就是能够不用关心切片元素的类型,也能写出像是 Reverse 这样的函数。我们想要去除元素类型的影响。之后,我们只用写一次这样的函数,写一个这样的测试,放到可以 go get 到的包之中,然后一劳永逸地用它。

更好的是,在这样一个开源的世界,别人可以帮你写好 Reverse 然后我们享用劳动果实。

到了这个份上,我应该说「范型」可以表示许多不同的东西。在这篇文章之中,我说的「范型」就是表达我所描述的东西。要指出的是,我说的不是 C++ 之中,比这支持更多东西的模版。

我讲到的只是 Reverse 函数,但是在实际之中,还有许多可以使用范型来完成的函数,比如:

  • 找到切片之中的最大/最小元
  • 计算切片的平均值/标准差
  • 计算集合(map) 的交/并
  • 寻找边/节点图之中的最短路径
  • 对切片/map 使用变换函数,得到新的切片/map

这些例子在大多其他语言之中都是可以实现的。实际上我是扫了一眼 C++ 的标准模版库然后列出了这些。

也有一些 Go 语言之中考虑到高并发支持而特有的例子。

  • 指定了超时时长的,从信道(channel)读取的操作
  • 把两个信道合并成一个信道
  • 并行调用一组函数,使用列表返回他们的结果
  • 调用一组函数,使用上下文,通过返回第一个函数的结果来结束操作。随后结束其他的 Goroutine 并做清理工作。

我已经在实际中见过所有这些函数针对不同类型被写了很多遍。在 Go 里面写这些函数并不是很难。但是如果能重用一个被调试好的、高效、能对所有类型通用的实现会是一个很好的事情。

要澄清一下,这些只是例子。实际上有了泛型,有许多通用意义的函数是可以更加方便和安全地完成的。

同时,如我早些写道的,泛型不仅仅可以用在函数上,还可以用在数据结构上。

Go 有两个植入到语言之中的通用泛型数据结构:切片和 map。切片和 map 可以装填任何一种数据类型,同时支持在储存、提取数据时进行类型检查。被储存的类型就是被当前其原本的样子来看待,而不是一个接口。就是说,在创建  []int 的时候,切片里面就是直接放着整数,而不是整数转换成了接口类型。

切片和 map 可以说是最有用的数据结构,但是最有用的数据结构可不止他们。就比如说:

  • 集合
  • 带有快速插入和按照既排顺序遍历元素的自平衡树
  • Multimap,允许多个同名键同时存在的 map
  • 并发的哈希表,提供对并行插入和无单锁的查找功能的支持

如果我们可以使用泛型来定义像这样的新的数据结构,那么就可以让他们像切片和 map 一样享有类型检查的优点:编译器可以静态地检查他们所储存的值的类型,数据也能在被储存时本色出演,而不是装扮成接口类型。

而且这样以来,大家把像是之前说到的那些算法实现在泛型数据结构上也不是问题了。

这些例子就像是 Reverse:范型函数和数据结构,一次写就,一次入包,终生重用。正是因为他们储存具体的类型而不是空接口,数据之间的交互就可以在编译时进行类型的比对,新的这些数据结构用起来就可以像是 map 和切片一样(类型安全)。

泛型,能够给 Go 带来上面这些;能够给我们分享代码和更好地构建程序提供新的积木。

我希望我已经解释清楚为什么泛型是值得深入的。

收益和成本

但是话说回来,泛型是不会从桃花源(原文用典 Big Rock Candy Mountain)那种一锄头能挖出佳酿泉眼(原文引用典故的歌词 lemonade springs)的地方冒出来的。每一个语言的变化都是伴随着成本的。毫无疑问,给 Go 加上泛型会让语言变得更加复杂。和其他所有对语言的调整一样,我们需要讨论如何最大化收益和最小化成本。

在 Go 之中,我们致力于使用独立、相互正交的,可以被任意组合的特性来降低语言的复杂性。我们通过把每一个特性做的简单来降低复杂度的,通过允许特性间任意组合来最大化收益。我们也想对泛型支持做一样的事情。

为了让讨论更加具体化,我要列出一些这其中应当遵循的准则。

***** 最小化新概念

我们应当尽可能少向语言之中加入新的概念。这点的意思是我们要把新加入的语法、关键字和其他名称最少化。

***** 泛型代码的复杂性是由书写者承担的,不是用户

复杂性要尽可能由泛型包的书写者来承担。我们不希望用户在使用包的时候还要操心泛型。这是说调用泛型函数应该是用一种自然的方式,而且任何来自使用泛型包的错误都应该易于理解和更正。此外,调用泛型的部分应当也要易于调试。

***** 编写者和用户可以相互独立地工作

类似的,为了能让包的编写者和使用者相互独立地工作,我们要让使用者对泛型代码和编写者对泛型代码,两个来自不同层面的关注更容易分离。相比于其他包之中普通函数的编写者和调用者,泛型的编写者和调用者之中任一方,都不应该为对方正在着手的事情承担更多的忧虑。这听起来很显然,但是在其他的各种语言之中,有时这一点是没有做到的。

***** 生成耗时短,运行速度快

自然,我们希望可以尽可能地保持当下 Go 给我们带来的短生成耗时,高运行速度。泛型通常会引入在编译速度和运行速度之间的取舍。但是我们想尽可能多地,全都要。

***** 保留 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,成为了所谓的 类型参数。不是作为切片参数类型的一部分,而是作为一个分离、额外的类型参数。

通常情况下,要调用这么一个带有类型参数的函数,也就是传入一个类型参数而已。就像是其他参数那样,只不过这参数是个类型罢了。

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

在这个例子之中,就是 Reverse 后面的那个 (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
}

当前,标准库之中的 bytes 包和 strings 包都有 IndexByte 函数。这一个函数是返回序列 s 之中,字节 b 对应的索引。其中的序列 s 可以是 string 也可以是 []byte。我们可以用这一个泛型函数替代两个包之中原来的函数。实践之中我们也许不会费力搞这个,但是这确实是一个实际的简单例子。

此处,我们需要明确类型参数 T 功能上和 string 或者 []byte 要相似。我们可以对其调用 len,可以使用索引,可以在一个字节值和索引运算的结果之间进行比较。

为了让代码编译,类型参数 T 本身也需要有一个类型。一个元类型,不过因为我们常常要描述多个相关的类型,而这同时也描述了泛型函数的实现和它的调用者之间的关系, T 的类型实际上被我们叫做契约。本例中,契约的名字是 Sequence,被写在类型参数表的后面。

这个例子之中的 Sequence 契约是这样定义的。

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

很简单,因为例子本身很简单:类型参数 Tstring 或者 []byte 中的一个。这里的 contract 可能会成为一个新的关键字,或者是一个包级的特殊标识符。如果想知道细节,请阅读完整的草案。

如果有人还记得 我们在 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 方法。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 类型要有能够返回所有相连 Edge 的方法。而 Edge 一定要有能够返回被这条边连接的两个 Node 的方法。

虽然没有实际实现,但是例子很好地展示了返回一个 GraphNew 函数的签名,和 GraphShortestPath 方法的签名。

这里的关键点在于契约涉及到了不止一个类型,它也可以用于描述两个或者多个类型之间的关系。

可排序类型

在抱怨 Go 的声音里,居然有很大一批是在抱怨 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 函数(很有可能也是在标准库的某个角落)会像是这样。此处我们直接引用了定义在 contracts 包之中的 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 的节点,或者寻找 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
}

注意,传入到 node 类型的类型参数 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)
    }
}

没错就该这样。泛型写起来会稍微复杂一些,因为被支持类型的类型参数往往是要显式地写出来。但是用起来和普通的非泛型数据结构就没什么区别。

下一步

我们正在着手于可以让我们尝试这种设计的实现。为了确保我们可以写出我们想要的程序,能有耐心来测试这种设计挺重要的。事情推进并没有如我们希望的那么快。但是只要可以有大家能看得到的实现了,我们便会通知大家。

Robert Griesemer 已经写了一些用于修改 go/types 包的 初步从句语言(CL)。这样就可以测试使用泛型和契约的代码能不能进行类型检查了。现在这个语言还不完整,但是基本可以在单个包中正常生效。我们会继续加油的。

我们希望大家可以通过多多观察自己的泛型代码表现如何来帮助当前和将来的实现。我们希望大家可以写出称心的代码,并且让其正确运行。所有的事情当然不会一下子就弄成,在我们探索的同时可能有一些东西会被改动。还有就是要说清楚,我们更关心语义上的反馈,而不是语法细节上的反馈。

我要感谢评论了早期设计的每一个人,还有所有参与讨论泛型在 Go 之中如何表现的人。我们阅读了每一条评论,非常感激大家为此做的付出。没有这些也不会有我们今天的成果。

我们的目标是要实现一种既可以写出如我今天所描述的那样的代码,而又不会把语言变得过于复杂的设计。我们希望这个设计是通往那个目标的一步,我们会在将来的日子里,根据我们新的认知,根据我们和你们大家的经验,根据什么效果好什么效果不好……来不断进行调整。如果我们最终达到了那个目标,我们便有了可以提交给未来版本的 Go 东西。

本文章首发在 LearnKu.com 网站上。

本译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。

原文地址:https://learnku.com/docs/go-blog/why-gen...

译文地址:https://learnku.com/docs/go-blog/why-gen...

上一篇 下一篇
Summer
贡献者:3
讨论数量: 0
发起讨论 只看当前版本


暂无话题~