Practical exploration of functional programming under Go generics

background

As a programming paradigm, functional programming (FP) has the advantages of being stateless, side-effect free, concurrency-friendly, and highly abstracted. Currently popular programming languages ​​(C++, Python, Rust) all introduce functional features more or less, but they are rarely discussed in Golang, which is also a popular language.

The reason is that most of the complaints about Golang Functional Programming Brief ^[1] , GopherCon 2020: Dylan Meeus - Functional Programming with Go ^[2] focus on Go's lack of support for generics, making it difficult to write functions that are common between types. Code generation can only handle some known types, and cannot deal with the complexity caused by type combination (such as implementing a generic TypeA → TypeB map function).

The proposal for generics, spec: add generic programming using type parameters #43651 ^[3] , has been accepted by the Go team and plans to release Go 1.18 with generics support in early 2022, and now the master branch of the golang/go repository already supports generics.

This design has been proposed and accepted as a future language change. We currently expect that this change will be available in the Go 1.18 release in early 2022. Type Parameters Proposal ^[4]

Based on this important feature, we have reason to revisit whether functional features can become more useful than ever with the blessing of Go generics.

Overview

In this article, we will try to use Go generics to implement some common functional features step by step, so as to explore the advantages and disadvantages of Go generics.

Unless otherwise stated (such as in the comments // INVALID CODE!!!), the code in the article can be run (in order to shorten the space, some of the package maindeclarations and mainfunctions have been deleted, please add them yourself). You can build ^[5] a master version of go from source by yourself to get an early taste of Go's generics, or run a single file with the online compiler provided by The go2go Playground ^{[6] .}

generic syntax

The new syntax added for generics is described in the #Very high level overview ^[7] section of the proposal , here is a brief description of the syntax needed to read this article:

• A function name can be followed by square brackets containing a list of Type Parameters involved in the function:func F[T any](p T "T any") { ... }

• These type parameters can be used in function parameters and function bodies (as types)

• Custom types can also have type parameter lists:type M[T any] []T

• Each type parameter corresponds to a type constraint, the above anyis a predefined constraint matching any type

• Type constraints exist syntactically in interfacethe form , interfaceand embedding a type in Tcan indicate that the type must be T:

  type Integer1 interface {
      int
  }
  

• It doesn't make much sense to embed a single type, we can use |to describe the union of a type:

  type Integer2 interface {
      int | int8 | int16 | int32 | int64
  }
  

• ~TThe grammar can indicate that the "base type" of the type is T, for example, our custom type that type MyInt intdoes not satisfy the above Integer1constraints, but satisfies the following constraints:

  type Integer3 interface {
      ~int
  }
  

hint

"Underlying type" in the proposal is "underlying type", there is no authoritative translation yet, and it is used in this article for convenience only.

Higher order functions

In functional programming languages, 📖 Higher-order functions ^[8] are an important feature. A higher-order function is a function that satisfies at least one of the following conditions:

• accepts one or more functions as input
• output a function

Golang supports closures, so implementing higher-order functions is no problem:

func foo(bar func() string) func() string {
        return func() string {
                return "foo" + " " + bar()
        }
}

func main() {
        bar := func() string {
                return "bar"
        }
        foobar := foo(bar)
        fmt.Println(foobar())
}
// Output:
// foo bar

The filter operation is a classic application of higher-order functions. It accepts a function f( func (T) bool) and a linear table l( [] T), applies the function f to each element in l, and trueadds the element to a new linear table if the result is , otherwise discard the element, and finally return a new linear table.

Based on the generic syntax above, we can easily write a simple filter function:

func Filter[T any](f func(T "T any") bool, src []T) []T {
        var dst []T
        for _, v := range src {
                if f(v) {
                        dst = append(dst, v)
                }
        }
        return dst
}

func main() {
        src := []int{-2, -1, -0, 1, 2}
        dst := Filter(func(v int) bool { return v >= 0 }, src)
        fmt.Println(dst)
}
// Output:
// [0 1 2]

Trouble with code generation

In Go versions 1.17 or earlier, there are two ways to implement a generic Filter function:

1. Use interface{}with reflection, sacrificing a certain degree of type safety and operational efficiency
2. Implement different Filter variants for different data types, such as FilterInt, FilterStringetc. The disadvantage is that the redundancy is high and the maintenance is difficult

The disadvantage of method 2 can be avoided by code generation. Specifically, the same template is used to generate different implementations with data types as variables. We can see many examples of code ^[9] .

So, with code generation, don't we need generics?

the answer is negative:

1. Code generation can only generate code for known types. It is clear that this template is float64also valid for , but the author only generates a versionint for processing . interface{}how many cases of type switch)

   In generics, the new type constraint syntax can uniformly handle all types with the same "base type":

   type signed interface {
           ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~float32 | ~float64 | ~complex64 | ~complex128
   }
   
   func Neg[T signed](n T "T signed") T {
           return -n
   }
   
   func main() {
           type MyInt int
   
           fmt.Println(Neg(1))
           fmt.Println(Neg(1.1))
           fmt.Println(Neg(MyInt(1)))
   }
   // Output:
   // -1
   // -1.1
   // -1
   

2. Code generation is difficult to deal with scenarios that require type combination. Let's look at another higher-order function map: accept a function f( func (T1) T2) and a linear table l1( []T1), apply the function f to each element in l1, and the returned result composes a new The linear table l2( []T2)

   If code generation is used, in order to avoid naming conflicts, we have to write strange names like MapIntInt, MapIntUint, MapIntString, and the amount of code generation will be greatly inflated due to the combination of types.

   We can find in the existing Go library that supports FP features:

   If you use generics, you just need to define a signature like this:

   func Map[T1, T2 any](f func(T1 "T1, T2 any") T2, src []T1) []T2
   

• Some ( hasgo ^[10] ) choose to implement map as a closed operation ( []T → []T), sacrificing expressiveness
• Some ( functional-go ^[11] ) force code generation to cause the number of interfaces to explode
• Some ( fpGo ^[12] ) choose to sacrifice type safety by implementing interface{}

sugar-free generics

Go's syntax is by no means concise and elegant among programming languages. Seeing <-the makes you secretly happy, but once you start to write real world code, the language will be difficult to hide the simplicity of the design. Generics are coming, and the rest of the language doesn't seem ready:

Closure syntax

The anonymous function form in Haskell is very concise:

filter (\x -> x >= 0) [-2, -1, 0, 1, 2]
-- Output:
-- [0,1,2]

In Golang, the type signature of the function cannot be omitted. No matter what signature the higher-order function requires, the caller always has to copy it completely when constructing the closure. Golang Functional Programming Brief ^[13]

func foo(bar func(a int, b float64, c string) string) func() string {
        return func() string {
                return bar(1, 1.0, "")
        }
}

func main() {
        foobar := foo(func(_ int, _ float64, c string) string {
                return c
        })
        foobar()
}

This problem can be attributed to the fact that the Go team ignored the feature of type inference, which improves efficiency and reduces redundancy, in order to maintain the so-called "high road to simplicity" (why is it not the case that generics are long overdue?). proposal: Go 2: Lightweight anonymous function syntax #21498 ^[14] proposed a proposal to simplify the syntax of closure invocation, but even if the proposal is accepted, we will only see it in Go 2 as soon as possible.

method type parameter

Chaining ^[15] (Method chaining) is a syntax for calling a function, each call returns an object, and then the method associated with the object can be called, which also returns an object. Chained calls can significantly eliminate the nesting of calls and are more readable. The GORM API we are familiar with makes extensive use of chained calls:

db.Where("name = ?", "jinzhu").Where("age = ?", 18).First(&user)

In functional programming, each higher-order function often only implements a simple function, and through their combination realizes complex data manipulation.

In the case where chaining is not possible, the composition of higher-order functions looks like this (this is just two levels of nesting):

Map(func(v int) int { return v + 1 },
   Filter(func(v int) bool { return v >= 0 },
      []int{-2, -1, -0, 1, 2}))

What if you use chained calls? We continue to use the previous filter and change it to the following form:

type List[T any] []T

func (l List[T]) Filter(f func(T) bool) List[T] {
        var dst []T
        for _, v := range l {
                if f(v) {
                        dst = append(dst, v)
                }
        }
        return List[T](dst "T")
}

func main() {
        l := List[int]([]int{-2, -1, -0, 1, 2} "int").
                Filter(func(v int) bool { return v >= 0 }).
                Filter(func(v int) bool { return v < 2 })
        fmt.Println(l)
}
// Output:
// [0 1]

Looks great, but why not use the map operation as an example? We can easily write a method signature like this:

// INVALID CODE!!!
func (l List[T1]) Map[T2 any](f func(T1 "T1]) Map[T2 any") T2) List[T2]

Unfortunately this code doesn't compile and we get the following error:

invalid AST: method must have no type parameter

The #No parameterized methods ^[16] section of the proposal clearly states that methods (that is, functions with receivers) do not support specifying type parameters individually:

This design does not permit methods to declare type parameters that are specific to the method. The receiver may have type parameters, but the method may not add any type parameters. 1 ^[17]

This decision is actually a compromise of last resort. Assuming we implement the above methods, it means that for an already instantiated List[T]object (say List[int]), there may be multiple versions of its Mapmethods : Map(func (int) int) List[int]or Map(func (int) string) List[string], when the user's code calls them, their code must be in some previous A moment is generated, so when should it be?

1. During compilation, more precisely, in the link phase of compilation, this requires the linker to traverse the entire call graph to determine how many versions are used in the program Map. The problem is with reflection: the user can reflect.MethodByNamedynamically call the object's methods with , so even if the entire call graph is traversed, we can't be sure how many versions the user's code calls.Map
2. During the runtime, when the method is called for the first time, yield is sent to the runtime, and the corresponding version of the function is generated and then resumed, which requires the runtime to support JIT (Just-in-time compilation), but Go does not currently support it, even if the future JIT Support is on the agenda, it's not something that can be done overnight

To sum up, the Go team chose not to support specifying type parameters for methods, which perfectly solves this problem🎉.

lazy evaluation

📖 Lazy Evaluation ^[18] (Lazy Evaluation) is another important functional feature. A loose description is: when an operation is defined, the calculation will not happen until we need the value. Its advantage is that the computation can be greatly optimized in terms of space complexity.

The following code shows a trivial Add function and its Lazy version, which does not evaluate the addend immediately, but returns a closure:

func Add(a, b int) int {
        return a + b
}

func LazyAdd(a, b int) func() int {
        return func () int {
                return a + b
        }
}

The above example does not capture the space-saving advantage of lazy evaluation. Based on the higher-order functions we implemented earlier, do the following:

l := []int{-2, -1, -0, 1, 2}
l = Filter(func(v int) bool { return v > -2 }, l)
l = Filter(func(v int) bool { return v < 2 }, l)
l = Filter(func(v int) bool { return v != 0 }, l)
fmt.Println(l)

During the calculation process, 3 new ones of length 5 will be generated []int, and the space complexity is O(3∗N). Although the constant is often omitted in the complexity analysis, when the program is actually running, the 3 here means that 3x the memory footprint.

Assuming that the evaluation of these higher-order functions is lazy, the calculation will only happen when evaluating fmt.Printlnthe parameters of , elements lare taken from the original , judged if v > -2, if v < 2, and finally executed v + 1, put into the new []int, space complexity remains the same is O(N), but no doubt we only used one `[]int`.

The introduction of generics has limited benefits for lazy evaluation, roughly as described above, but at least we can define interfaces that are generic to types:

// 一个适用于线性结构的迭代器接口
type Iter[T any] interface{ Next() (T, bool) }

// 用于将任意 slice 包装成 Iter[T]
type SliceIter[T any] struct {
        i int
        s []T
}

func IterOfSlice[T any](s []T "T any") Iter[T] {
        return &SliceIter[T]{s: s}
}

func (i *SliceIter[T]) Next() (v T, ok bool) {
        if ok = i.i < len(i.s); ok {
                v = i.s[i.i]
                i.i++
        }
        return
}

Then implement the lazy version of filter:

type filterIter[T any] struct {
        f   func(T) bool
        src Iter[T]
}

func (i *filterIter[T]) Next() (v T, ok bool) {
        for {
                v, ok = i.src.Next()
                if !ok || i.f(v) {
                        return
                }
        }
}

func Filter[T any](f func(T "T any") bool, src Iter[T]) Iter[T] {
        return &filterIter[T]{f: f, src: src}
}

It can be seen that this version of filter only returns a Iter[T]( *filterIter[T]), and the actual operation *filterIter[T].Next()is performed in .

We also need Iter[T]a []Tfunction that will convert back to :

func List[T any](src Iter[T] "T any") (dst []T) {
        for {
                v, ok := src.Next()
                if !ok {
                        return
                }
                dst = append(dst, v)
        }
}

Finally implement an operation equivalent to the above, but the actual computation happens in List(i)the call of :

i := IterOfSlice([]int{-2, -1, -0, 1, 2})
i = Filter(func(v int) bool { return v > -2 }, i)
i = Filter(func(v int) bool { return v < 2 }, i)
i = Filter(func(v int) bool { return v != 0 }, i)
fmt.Println(List(i))

iterator of Map

Hashmap in Golang is a commonly used data structure like map[K]VSlice []T. If we can convert map to the above Iter[T], then map can directly use various high-order functions that have been implemented.

map[K]VThe iteration of can only be done for ... rangethrough , we cannot obtain an iterator by conventional means. Reflection certainly does, but it reflect.MapIter's too heavy . modern-go/reflect2 ^[19] provides a faster implementation ^[20] , but it is beyond the scope of this article, so it will not be expanded here, and interested friends can study it by themselves.

Topical application

Partial Application ^[21] (Partial Application) is an operation that fixes part of the parameters of a multi-argument function and returns a function that can accept the remaining part of the parameters.

Remark

Partial application is different from 📖 Currying ^[22] (Currying) Partial Function Application is not Currying ^[23] , Currying is a technology that uses multiple single-parameter functions to represent multi-parameter functions, and Go already supports multi-parameter functions In the case of functions, this article does not discuss the implementation of Currying for the time being.

We define a function type that takes a single argument and returns a value:

type FuncWith1Args[A, R any] func(A) R

A partial application of a function that accepts only one parameter is actually equivalent to evaluating:

func (f FuncWith1Args[A, R]) Partial(a A) R {
        return f(a)
}

After a function that accepts two parameters is partially applied, one parameter is fixed, and naturally returns one of the above FuncWith1Args:

type FuncWith2Args[A1, A2, R any] func(A1, A2) R

func (f FuncWith2Args[A1, A2, R]) Partial(a1 A1) FuncWith1Args[A2, R] {
        return func(a2 A2) R {
                return f(a1, a2)
        }
}

Let's try it out, wrap the filter we implemented before into one FuncWith2Args, fix two parameters from left to right, and finally get the result:

f2 := FuncWith2Args[func(int) bool, Iter[int], Iter[int]](Filter[int] "func(int) bool, Iter[int], Iter[int]")
f1 := f2.Partial(func(v int) bool { return v > -2 })
r := f1.Partial(IterOfSlice([]int{-2, -1, -0, 1, 2}))
fmt.Println(List(r))
// Output:
// [-1 0 1 2]

Type parameter deduction

We reluctantly realized partial application, but the process of Filterconverting to FuncWith2Argsis too cumbersome. In the above example, we completely specified the type parameters . Did you feel the helplessness brought by the closure syntax ^{[24] again?}

This time we are not powerless, the section #Type inference ^[25] in the proposal describes support for type parameter deduction. The conversion in the above example is unambiguous, so we remove the type parameter:

// INVALID CODE!!!
f2 := FuncWith2Args(Filter[int])

The compiler complains like this:

cannot use generic type FuncWith2Args without instantiation

The type parameter deduction in the proposal is only for function calls. FuncWith2Args(XXX)Although it looks like function call syntax, it is actually an instantiation of a type. The parameter type deduction for type instantiation ( #Type inference for composite literals ^[26] ) is also a Pending feature.

What if we write a function to instantiate this object? Unfortunately, it can't be done: what do we use to express the input? You can only write a function like this "listen to your words, listen to your words":

func Cast[A1, A2, R any](f FuncWith2Args[A1, A2, R] "A1, A2, R any") FuncWith2Args[A1, A2, R] {
        return f
}

But it works! When we pass in Filter directly, the compiler will implicitly convert it to one for us FuncWith2Args[func(int) bool, Iter[int], Iter[int]]! At the same time, because of the existence of function type parameter deduction, we do not need to specify any type parameters:

f2 := Cast(Filter[int])
f1 := f2.Partial(func(v int) bool { return v > -2 })
r := f1.Partial(IterOfSlice([]int{-2, -1, -0, 1, 2}))
fmt.Println(List(r))
// Output:
// [-1 0 1 2]

Variable type parameter

FuncWith1Args, FuncWith2ArgsThese names make us a little trance, as if back to the era of code generation. To handle more parameters, do we still have to write FuncWith3Args, FuncWith4Args...?

Yes, the section #Omissions ^[27] mentions: Go's generics do not support a variable number of type parameters:

No variadic type parameters. There is no support for variadic type parameters, which would permit writing a single generic function that takes different numbers of both type parameters and regular parameters.

Corresponding to the function signature, we also have no syntax to declare variadic parameters with different types.

type system

众多函数式特性的实现依赖于一个强大类型系统，Go 的类型系统显然不足以胜任，作者不是专业人士，这里我们不讨论其他语言里让人羡慕的类型类（Type Class）、代数数据类型（Algebraic Data Type），只讨论在 Go 语言中引入泛型之后，我们的类型系统有哪些水土不服的地方。

提示

其实上文的大部分问题都和类型系统息息相关，case by case 的话我们可以列出非常多的问题，因此以下只展示明显不合理那部分。

编译期类型判断

当我们在写一段泛型代码里的时候，有时候会需要根据 T 实际上的类型决定接下来的流程，可 Go 的完全没有提供在编译期操作类型的能力。运行期的 workaround 当然有，怎么做呢：将 T 转化为 interface{}，然后做一次 type assertion:

func Foo[T any](n T "T any") {
        if _, ok := (interface{})(n).(int); ok {
                // do sth...
        }
}

无法辨认「基础类型」

我们在 代码生成之困^[28] 提到过，在类型约束中可以用 ~T 的语法约束所有 基础类型为 T 的类型，这是 Go 在语法层面上首次暴露出「基础类型」的概念，在之前我们只能通过 reflect.(Value).Kind 获取。而在 type assertion 和 type switch 里并没有对应的语法处理「基础类型」:

type Int interface {
        ~int | ~uint
}

func IsSigned[T Int](n T "T Int") {
        switch (interface{})(n).(type) {
        case int:
                fmt.Println("signed")
        default:
                fmt.Println("unsigned")
        }
}

func main() {
        type MyInt int
        IsSigned(1)
        IsSigned(MyInt(1))
}
// Output:
// signed
// unsigned

乍一看很合理，MyInt 确实不是 int。那我们要如何在函数不了解 MyInt 的情况下把它当 int 处理呢？答案是还不能：#Identifying the matched predeclared type^[29] 表示这是个未决的问题，需要在后续的版本中讨论新语法。总之，在 1.18 中，我们是见不到它了。

类型约束不可用于 type assertion

一个直观的想法是单独定义一个 Signed 约束，然后判断 T 是否满足 Signed:

type Signed interface {
        ~int
}

func IsSigned[T Int](n T "T Int") {
        if _, ok := (interface{})(n).(Signed); ok {
                fmt.Println("signed")
        } else {
                fmt.Println("unsigned")
        }
}

但很可惜，类型约束不能用于 type assertion/switch，编译器报错如下：

interface contains type constraints

尽管让类型约束用于 type assertion 可能会引入额外的问题，但牺牲这个支持让 Go 的类型表达能力大大地打了折扣。

总结

函数式编程的特性不止于此，代数数据类型、引用透明（Referential Transparency）等在本文中都未能覆盖到。总得来说，Go 泛型的引入：

1. 使的部分 函数式特性能以更通用的方式被实现
2. 灵活度比代码生成更高 ，用法更自然，但细节上的小问题很多
3. 1.18 的泛型在引入 type paramters 语法之外并没有其他大刀阔斧的改变，导致泛型和这个语言的其他部分显得有些格格不入，也使得泛型的能力受限。至少在 1.18 里，我们要忍受泛型中存在的种种不一致
4. 受制于 Go 类型系统的表达能力，我们无法表示复杂的类型约束，自然也 无法实现完备的函数式特性

参考资料