【在主画面加入捷径】
       
【选择语系】
繁中 简中

[Golang] 程序设计教学:泛型 (Generics) 相关的议题

【赞助商连结】

    泛型 (generics) 是一种多态的模式,透过泛型程序,可将同一套程序代码用到不同类型的数据上。基本上,Go 不支援泛型,这在社群中已经有许多人提过,笔者先前也于自己的部落格撰文讨论过;Go 官方网站的 FAQ 也已经明确说明此事。本文的目的是探讨可能的替代方案,让读者从中选择适合自己的方案。

    少数的泛型支援

    直接说 Go 不支援泛型是过于简化的说法;其实,Go 在内建容器中,包括数组、切片、map 等,是支援泛型的。读者可以观察一下这些内建容器的范例程序代码,就可以发现 Go 程序对这些内建容器可以直接套用在不同类型上。然而,Go 对泛型的支援也仅止于此,其他的部分就无法使用泛型。为了兼容性,要加入泛型且不破坏先前的程序代码,可能会让 Go 核心团队伤脑筋一番。

    替代策略

    观察一些社群的部落格、讨论区文章或套件,可以发现,基本上,目前社群的替代策略有以下数种:

    • 接口
    • 空接口
    • 程序代码生成
    • 发展新语言

    使用接口取代泛型

    依照 Go 标准函式库来观察,Go 官方团队的思维是用接口取代泛型。例如以下采自 Go by Example 的排序程序;

    package main
     
    import "sort"
    import "fmt"
     
    type ByLength []string
     
    func (s ByLength) Len() int {
        return len(s)
    }
    func (s ByLength) Swap(i, j int) {
        s[i], s[j] = s[j], s[i]
    }
    func (s ByLength) Less(i, j int) bool {
        return len(s[i]) < len(s[j])
    }
     
    func main() {
        fruits := []string{"peach", "banana", "kiwi"}
        sort.Sort(ByLength(fruits))
        fmt.Println(fruits)
    }
    

    只要该类型满足 LenSwapLess 三个公开方法,就可以对该类型排序。除了要手刻三个方法比较繁琐外,这样的程序已经颇有泛型的味道在里面。

    使用空接口则有一些 dirty hack 的味道,因为空接口可塞入任意类型,我们只要在需要处理特定类型时,再加入额外的程序代码即可。笔者本身最喜欢这个方法,因为不需要使用额外的工具来生成程序代码;但这个方法没有成为主流。在后文中,笔者会以实际的例子来说明如何利用空类型来仿真泛型,以及讨论为什么这个方法未成主流。

    使用程序代码生成器产生程序代码,其实就是把原来编译器的工作转移到程序设计者身上。许多社群方案都是使用程序代码生成器的方式来仿真泛型。笔者不太喜欢这种方案,这种方案只对程序设计者本身有帮助,对于套件使用者来说,其实没有泛型程序的特性。这些方案并没有达成社群共识,大抵上每个方案只有少数开发者在维护。笔者会以 genny 为例,说明如何使用程序代码生成器仿真泛型。

    有少数的激进派会开发新的语言,再将该语言的程序代码转为 Go 程序代码。ply 就是一个尝试性的方案,由于 ply 除了增加一些容器相关的函式外,大抵上还是 Go 程序;而且,使用者也无法自行增加其他的泛型函式。由于使用新语言会使得项目变较复杂,笔者对这种方案通常都相对审慎。

    使用空接口

    在本节中,笔者以实际的例子来展示如何用空接口仿真泛型程序。我们现在要建立一个具有泛型特性的键结串行 (linked list),先看内部的属性:

    // Excerpt
    // List holds the internal structure of a doubly-linked list
    type List struct {
        head *node
        tail *node
    }
     
    // Internal struct as a node
    type node struct {
        data interface{}
        next *node
        prev *node
    }
    

    在我们的串行中,数据存放于 data 属性中,由于 data 为空接口,我们可以放入任意的数据类型。

    对于和数据本身无关的操作,不需要处理类型议题。例如,以下的 Push 方法在串行尾端加入一个元素:

    // Excerpt
    // Push data into the tail of the list
    func (list *List) Push(data interface{}) {
        node := node{data: data, next: nil, prev: nil}
        if list.head == nil {
            list.head = &node
            list.tail = &node
        } else {
            list.tail.next = &node
            node.prev = list.tail
            list.tail = &node
        }
    }
    

    但是,某些操作和数据相关,这时,我们用函数式程序设计的方法,将数据相关的运算委任 (delegating) 给套件使用者;因为我们无法预先知道数据的类型。在以下实例中,Select 方法过滤掉不符合条件的元素:

    // Excerpt
    // Select items from the list when item fulfill the predicate.
    // Implement grep function object to use this method.
    func (list *List) Select(grep func(interface{}) (bool, error)) (*List, error) {
        newList := New()
     
        current := list.head
        for current != nil {
            b, err := grep(current.data)
            if err != nil {
                return newList, err
            }
     
            if b == true {
                newList.Push(current.data)
            }
     
            current = current.next
        }
     
        return newList, nil
    }
    

    本段程序代码的前提是数据是可拷贝的 (clonable),因 Go 不支援重载函式,若明确调用 Clone 方法会使得大部分的内建类型无法使用,这是设计上的考量。对于没有内建拷贝机制的类型,要由使用者在将数据传入串行前即拷贝一份。

    使用范例如下:

    package main
     
    import (
        "errors"
        "github.com/cwchentw/algo-golang/list"
        "log"
    )
     
    func main() {
        l := list.New()
     
        for i := 1; i <= 10; i++ {
            l.Push(i)
        }
     
        evens, _ := l.Select(isEven)
        for e := range evens.Iter() {
            n, _ := e.(int)
            if n % 2 != 0 {
                log.Fatalln("Error Select result")
            }
        }
    }
     
    func isEven(a interface{}) (bool, error) {
        n, ok := a.(int)
        if ok != true {
            return false, errors.New("Failed type assertion on a")
        }
     
        return n % 2 == 0, nil
    }
    

    其实,使用接口和空接口是类似的,使用者皆需要撰写一些样板程序代码,只是前者是面向对象的风格,后者则使用函数式程序来撰码。Go 核心团队并没有采用这种方式来撰写容器,可能是函数式程序在某种程度比面向对象程序难以理解;大部分 Go 的教材也较少强调以 Go 撰写函数式程序。Go 标准函式库内虽然有一个以空接口实现的串行,但使用上不若切片来得广泛,则是因为该串行的接口不易使用的缘故。

    如果读者对这个项目有项目有兴趣,可以到 GitHub 上观看此项目的源代码。

    使用程序代码生成器

    Go 社群有数个以程序代码生成器的概念去实现的泛型替代方案,笔者这里以 genny 为例,说明如何使用这类方案仿真泛型。

    以下范例摘自 genny 项目。我们撰写一个有泛型特性的队列 (queue) 如下:

    package example
     
    import "github.com/cheekybits/genny/generic"
     
    type Generic generic.Type
     
    // GenericQueue represents a queue of Generic types.
    type GenericQueue struct {
        items []Generic
    }
     
    // NewGenericQueue makes a new empty Generic queue.
    func NewGenericQueue() *GenericQueue {
        return &GenericQueue{items: make([]Generic, 0)}
    }
     
    // Enq adds an item to the queue.
    func (q *GenericQueue) Enq(obj Generic) *GenericQueue {
        q.items = append(q.items, obj)
        return q
    }
     
    // Deq removes and returns the next item in the queue.
    func (q *GenericQueue) Deq() Generic {
        obj := q.items[0]
        q.items = q.items[1:]
        return obj
    }
     
    // Len gets the current number of Generic items in the queue.
    func (q *GenericQueue) Len() int {
        return len(q.items)
    }
    

    使用以下指令产生代码:

    $ cat ./queue_generic.go | genny gen "Generic=string,int" > queue_generic_gen.go
    

    genny 会自动产生以下代码:

    // This file was automatically generated by genny.
    // Any changes will be lost if this file is regenerated.
    // see https://github.com/cheekybits/genny
     
    package example
     
    // StringQueue represents a queue of string types.
    type StringQueue struct {
        items []string
    }
     
    // NewStringQueue makes a new empty string queue.
    func NewStringQueue() *StringQueue {
        return &StringQueue{items: make([]string, 0)}
    }
     
    // Enq adds an item to the queue.
    func (q *StringQueue) Enq(obj string) *StringQueue {
        q.items = append(q.items, obj)
        return q
    }
     
    // Deq removes and returns the next item in the queue.
    func (q *StringQueue) Deq() string {
        obj := q.items[0]
        q.items = q.items[1:]
        return obj
    }
     
    // Len gets the current number of string items in the queue.
    func (q *StringQueue) Len() int {
        return len(q.items)
    }
     
    // IntQueue represents a queue of int types.
    type IntQueue struct {
        items []int
    }
     
    // NewIntQueue makes a new empty int queue.
    func NewIntQueue() *IntQueue {
        return &IntQueue{items: make([]int, 0)}
    }
     
    // Enq adds an item to the queue.
    func (q *IntQueue) Enq(obj int) *IntQueue {
        q.items = append(q.items, obj)
        return q
    }
     
    // Deq removes and returns the next item in the queue.
    func (q *IntQueue) Deq() int {
        obj := q.items[0]
        q.items = q.items[1:]
        return obj
    }
     
    // Len gets the current number of int items in the queue.
    func (q *IntQueue) Len() int {
        return len(q.items)
    }
    

    由本实例可知,对套件使用者来说,套件其实没有泛型程序的作用,而是在开发周期减少套件开发者重覆撰码的时间和心力。由于透过 genny 产生的程序代码立即可用,某种程度上的确可以加速开发过程。

    发展新语言

    ply 是一个实验性质的项目,主要是在 Go 语言上加上一些新的语法,藉此加强对泛型的支援。这个项目并没有变成社群主流,项目本身也停滞下来了。可以看看,但不太会用到实际要上线的程序代码中。