[Golang] 程式設計教學:泛型 (Generics) 相關的議題

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    前言

    泛型 (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 語言上加上一些新的語法,藉此加強對泛型的支援。這個專案並沒有變成社群主流,專案本身也停滯下來了。可以看看,但不太會用到實際要上線的程式碼中。

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk