For The Best Thing In The World

Work Hard to Enjoy Them. bloom energy

实现golang泛型

公众号

betterGo

天下苦golang久矣！

今亡亦死，举大计亦死，等死，死国可乎

背景

然而生活中，接收了没有泛型，似乎也挺美好的样子，直到某一天，你发现你又要对slice进行删除操作了，明明你前几天才做过的，明明…

泛型可以不用，但泛型库函数不能没有，我不想再写for了。美好的Map, Reduce，uniq…，你们在哪里？

于是，betterGo诞生了

Implement golang generic by code generating like C++ template (monomorphization)

通过代码生成的方式，像C++ template一样，实现golang泛型函数（术语叫monomorphization）

正如之前文章里说的，我起了个头，验证了可行性后，后续就交给

详情

C++的template实现的泛型，可以简单理解为在编译阶段，识别出其类型，不同的调用都实例化到具体的类型（就是每个泛型库函数都根据调用者的调用参数类型生成一份代码），go自然也可以这样子做。

但，我们没有影响力，不像七牛云一样有知名度（他们自己造了一套语法，转译成golang语法），造语法是不可能的：

  • IDE 不支持，总不能别人用了这个库，写的代码编译不了，需要调用工具转换后才能跑吧
  • 不可能有人会用的。。

因此，需要暗度陈仓。

先提供interface{}的库函数

golang通过 interface{}可以实现”泛型”，但是性能太差，以至于go的作者robpike自己都。。。没眼看。

image-20200626192615460

但没关系，我们可以提供这些函数给用户先使用，在开发，编译，调试都能正常使用，使用如下：

"github.com/PioneerIncubator/betterGo/enum" //引用betterGo的库
func mul(a, b int) (c int) {
	c = a * b
	return
}
out := enum.Reduce(a, mul, 1).(int)

这些测试例子可在项目的test目录中找到。

转译

之后只需要调用一下我们的工具，转换成具体类型的函数即可，自然，我们也会将调用方的函数改变：

	out := enum.ReduceAMulInt(a, mul, 1) //这时的enum包就是用户项目自己目录里的包了

生成的Reduce函数如下，会在调用方的目录utils/enum/reduce.go里：

package enum

func ReduceAMulInt(argname_1 int, argname_2 func(int, int) int, argname_3 int) int {
	lenSlice := len(argname_1)
	switch lenSlice {
	case 0:
		return 0
	case 1:
		return argname_1[1]
	}
	out := argname_2(argname_3, argname_1[0])
	next := argname_1[1]
	for i := 1; i < lenSlice; i++ {
		next = argname_1[i]
		out = argname_2(out, next)
	}
	return out
}

编译

这时编译就是特例化版本函数的二进制了。

至于生成的代码，可以git checkout .全部扔掉，开发依然使用interface{}版本的代码。

后记

虽然go2 泛型明年就要出了，但也很悬- -，有兴趣可以参与开发这个项目哈，玩玩也行。

支持的函数

  • find(slice, default \ nil, fun)
    • Returns the first element for which fun returns a truthy value. If no such element is found, returns default.
  • map(slice, fun)
    • Returns a list where each element is the result of invoking fun on each corresponding element of enumerable.
  • all?(slice, fun \ fn x -> x end)
    • Returns true if fun.(element) is truthy for all elements in enumerable.
  • any?(slice, fun \ fn x -> x end)
    • Returns true if fun.(element) is truthy for at least one element in enumerable.
  • uniq_by(slice, fun)
    • Enumerates the enumerable, by removing the elements for which function fun returned duplicate elements.

项目细节：

betterGo实现了我认为Go所缺失的部分

Real Generic

为用户提供了可以直接用在代码中的真正的interface{}。

在部署之前，仅需要使用translator生成确定类型的代码，这种方式并不会影响你的代码性能。

下面是已经实现的所有泛型函数：

  • enum.Reduce
  • enum.Map

实现

使用Go AST来分析你使用泛型函数的代码，生成确定类型的函数并替换掉你原先的调用语句

实际上所做的事

加入我们

背景

现在的Go语言不支持泛型（像C++中的template、Java中的interface）

目前，为实现泛型的需求，在Go语言中往往有如下几种方式1：

  1. Interface （with method） 优点：无需三方库，代码干净而且通用。 缺点：需要一些额外的代码量，以及也许没那么夸张的运行时开销。
  2. Use type assertions 优点：无需三方库，代码干净。 缺点：需要执行类型断言，接口转换的运行时开销，没有编译时类型检查。
  3. Reflection 优点：干净 缺点：相当大的运行时开销，没有编译时类型检查。
  4. Code generation 优点：非常干净的代码(取决工具)，编译时类型检查（有些工具甚至允许编写针对通用代码模板的测试），没有运行时开销。 缺点：构建需要第三方工具，如果一个模板为不同的目标类型多次实例化，编译后二进制文件较大。

betterGo就是通过code generation来实现泛型

如何使用

如果你想使用betterGo来通过自动生成代码的方式实现泛型，可以看下面的例子：

在项目中包含了测试用例，例如，需要使用泛型的代码是test/map/map.go，如果想用interface{} 的函数就是enum.Map 这样子用。

如果想生成具体类型的函数，就运行这行命令：go run main.go -w -f test/map/map.go

然后你发现 test/map/map.go 改变了，enum.Map 变成了: enum.MapOriginFn(origin, fn)

然后你看项目目录下生成了： utils/enum/map.go，就是具体类型的函数

参与项目

如果想和我们一起完成项目的开发，可以直接看代码，找到AST相关的包，尝试理解相关函数的作用，很容易就可以理解这个项目以及代码了。

如果想从理论出发的话，可以简单看看这本书：https://github.com/chai2010/go-ast-book ，其实他也就是把AST包里的代码简单讲讲。

想参与具体开发可以参考项目接下来的TODO List

技术思路

  1. 导入需要操作的文件/目录

  2. 通过AST进行语法分析

    AST能分析出每条语句的性质，如：

    • GenDecl (一般声明)：包括import、常量声明、变量声明、类型声明
    • AssignStmt(赋值语句)：包括赋值语句和短的变量声明(a := 1)
    • FuncDecl(函数声明)
    • TypeAssertExpr(类型断言)
    • CallExpr(函数调用语句)

  3. 当分析到包含变量的值/类型的语句时(AssignStmt、FuncDecl)会对变量的值和类型进行记录，并建立二者之间的映射关系，以便于在后续环节中能够通过变量名获取变量的类型

  4. 当发现函数调用语句(CallExpr)时，会检查该函数是否为我们提供的函数，如果是，则通过上一步中记录的参数名对应的类型生成专门处理该类型的一份代码，并存储到指定路径下（如果之前已经生成过相同类型的代码则不重复生成）

  5. 将原代码中的原来的函数调用语句替换成新的函数调用语句，使其调用上一步中新生成的函数，并更新import的包

Reference

[1] Go有什麽泛型的实现方法? - 达的回答 - 知乎