函数式编程与尾调用学习

函数式编程

函数式编程: 函数式编程最常见的技术就是对一个集合做Map、Reduce和Filter操作，map对集合成员做了映射操作，生成新的集合；reduce就是降维操作，化整为零；filter顾名思义通过过滤器生成新的集合。

其特点是把函数当成变量来用.

递归

递归算法在使用栈（stack，先进后出）来执行数据操作的时候是非常方便的，它比循环操作更快，并且代码的简洁性好。

递归带来的效率问题主要是函数调用带来的额外开销（函数的入栈出栈），以及栈容量的限制（次数太多可能会stack overflow）

递归算法：

优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。

循环算法：

优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

系统栈（也叫核心栈、内核栈）是内存中属于操作系统空间的一块区域，其主要用途为： (1)保存中断现场，对于嵌套中断，被中断程序的现场信息依次压入系统栈，中断返回时逆序弹出； (2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
用户栈是用户进程空间中的一块区域，用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
我们编写的递归程序属于用户程序，因此使用的是用户栈。

柯里化

也就是把接受多个参数的方法变换成接受第一个参数的方法，并且返回接受余下的参数而且返回结果的新方法。将多参数的函数转换成单参数的形式

例如:

def inc(x):
    def incx(y):
        return x+y
    return incx
 
inc2 = inc(2)
inc5 = inc(5)
 
print inc2(5) # 输出 7
print inc5(5) # 输出 10

尾调用/尾递归

某个函数的最后一步是调用另一个函数,这就是尾调用.

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。这就叫做”尾调用优化”（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。这就是”尾调用优化“的意义。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。如果其递归函数的第一个参数是需要返回的计算结果或者是中间变量.

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生”栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。

// 使用for循环执行
func factorialFor(n int) int {
	if n == 1 {
		return 1
	}
	res := 1
	for i := 2; i <= n; i++ {
		res = res * i
	}
	return res
}

// 递归, 内存占用O(n) 因为需要保存n个调用记录(中间结果)
func factorial(n int) int {
  if n == 1 {return 1}
  return n * factorial(n - 1)
}

// 尾递归, 理论上内存占用 O(1) 只需要保留一个调用记录, 实际上到go1.13都没有进行优化, 依旧是O(n) , 测试执行会比上面的快一点, 是因为函数调用尾递归调用中在管理stack frames上开销小一点. 
func factorial(n,total int) int{
    if n == 1 { return total}
    return factorial(n-1, n*total)
}

// 测试结果:
BenchmarkTailRecursive/For:-8         	68877586	        17.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkTailRecursive/Rec:-8         	10000900	       119 ns/op	       0 B/op	       0 allocs/op
BenchmarkTailRecursive/Tail:-8        	11536790	       102 ns/op	       0 B/op	       0 allocs/op

似乎for循环更快. 因为减少了递归调用的压栈/出栈操作和函数调用的开销.

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数

可用通过外层再包装一层函数来隐藏尾递归优化的多出来的参数

1
2
3

func Factorial(n int) int{
    return factorial(n, 1)
}

也可以通过柯里化来做:

func currying(fn func, total int){
    return func(fn func, n int) {
        return fn(n,total)
    }
}

const Factorial = currying(factorial,1)

// 调用: Factorial(5)

当然如果像python那样支持默认参数值的,就可以通过默认参数设置默认值隐藏第二个参数了.

go的尾调用(tail calls)优化

当你要使用递归的时候，你需要意识到栈内存是一直增加的，直到遇到你设置好的 anchor 时，它的内存才开始下降。当我们说 Go 并没有优化递归操作时，我们需要承认一个事实，Go 并没有尝试着去优化栈内存无限增加这一操作, Go 没有 tail calls 进行任何优化, 调用栈并没有销毁。

// 通过chan去模拟尾递归, 这个调用栈会被优化, 因为每个goroutine执行完就返回了, 其会被销毁.
func RecursiveChannel(number int, product int, result chan int) {
    product = product + number
    if number == 1 {
        result <- product
        return
    }
    Go RecursiveChannel(number-1, product, result)
}

汇编:
— prog list "TailRecursive" —
0018 (./main.go:17) TEXT TailRecursive+0(SB),$24-24

0019 (./main.go:17) MOVQ number+0(FP),CX

0020 (./main.go:17) LOCALS ,$0
0021 (./main.go:17) TYPE number+0(FP){int},$8
0022 (./main.go:17) TYPE product+8(FP){int},$8
0023 (./main.go:17) TYPE ~anon2+16(FP){int},$8

0024 (./main.go:19) MOVQ product+8(FP),AX
0025 (./main.go:19) ADDQ CX,AX

0026 (./main.go:21) CMPQ CX,$1
0027 (./main.go:21) JNE ,30

0028 (./main.go:23) MOVQ AX,~anon2+16(FP)
0029 (./main.go:23) RET ,

0030 (./main.go:26) MOVQ CX,BX
0031 (./main.go:26) DECQ ,BX

0032 (./main.go:26) MOVQ BX,(SP)
0033 (./main.go:26) MOVQ AX,8(SP) // 依旧不断地把参数压栈, 并未重复利用栈返回
0034 (./main.go:26) CALL ,TailRecursive+0(SB)

0035 (./main.go:26) MOVQ 16(SP),BX

0036 (./main.go:26) MOVQ BX,~anon2+16(FP)
0037 (./main.go:26) RET ,

func main() {
    result := make(chan int)
    RecursiveChannel(4, 0, result)
    answer := <-result
    fmt.Printf("Recursive: %d\n", answer)
}

幂等性(纯函数)

在学习这种编程思想的时候, 发现有一种代码书写理念很有意义: 尽可能地将输入/输出数据的控制权交给调用者, 尽量避免在执行者内部创建输入/输出数据. 代码本身只执行功能, 不影响输入输出, 确保功能方法是幂等的

在计算机程序中，如果一个函数满足下面的几个条件，那么这个函数就是一个纯函数：

这个函数在相同的参数下一定会产生相同的结果。即函数的返回值不依赖于任何隐藏在函数内的信息或者状态，而这些隐藏的内容在程序的运行期还可能会变化。且函数不应依赖于任何从 I/O 设备中输入的信息。
对函数的返回结果进行操作不会引起任何语义上的副作用或者输出，比如导致可变对象的变化或者输出数据到 I/O 设备去。

例如下面的代码test的方法就不够好, 这个方法在内部创建的一个数组并把这个数组返回输出给调用者. 这样就违反了上面的理念: 使用相同的a多次调用test返回的slice切片不是同一个slice.

func test(a []int) []int{
    b:= make([]int,len(a))
    for k,v:=range a{
        b[k] = v*3+34
    }
    return b
}

其实我们可以通过改写这个方法:

func test(in []int, out []int){
    for k,v:=range in{
        out[k] = v*3+34
    }
}

而 test的调用者负责创建这个out的数组. 那如果传递的参数不是指针或slice/map/chan结构该怎么做?我个人理解这种情况要么改成传递指针, 要么干脆就违反幂等, 因为导出是指针真的就有点丑且容易出错了..

// 幂等的写法容易出错
func test(in int, out *int) {
    (*out) = in * 3
}
// 正常的写法更不容易出错
func test(in int) int {
    return in * 3
}

函数是数据

把函数看作是一种数据类型使用, 这种思想就是数学上的变量方程的一种提现, 比如: f(x) = f(x-1) + 2这样的递推式. 使用这种思想, 可以很好的契合递归调用的思路. 利用计算机中的栈的天然递归特性, 来高效的完成方程式的求解. 在go实际开发中, 一个很好的应用例子就是配置参数的初始化与默认值设置. 这样的好处是由调用者自己控制使用什么,不用什么,设置什么, 如果没有设置也会有默认值,并且在增加变动配置项的时候不再需要去改动原有的代码逻辑(startServer不需要修改), 保持了代码的可扩展性和最小变化性.

func main() {
	// ...
	startServer(
		WithPort(8080),
		WithTimeout(1 * time.Second),
	)
}

type Config struct {
	port    int
	timeout time.Duration
}

type ServerOpt func(*Config)

// 柯里化
func WithPort(port int) ServerOpt {
	return func(cfg *Config) {
		cfg.port = port
	}
}

func WithTimeout(timeout time.Duration) ServerOpt {
	return func(cfg *Config) {
		cfg.timeout = timeout
	}
}

func startServer(opts ...ServerOpt) {
	cfg := &Config{
	    port : 80,
	    timeout: 300,
	}
	for _, fn := range opts {
		fn(cfg)
	}

	// ...
}

函数式应用思考

在对数组进行遍历处理的时候,我们可以考虑多种方法:

使用递推/尾递归的方式,虽然这样效率慢很多,go也没有进行尾递归优化, 但是却充分提现了函数式的思想, 将需要的输出数据由调用者控制.
使用遍历的方式

使用数学函数递推公式的方式

// 使用尾递归
func sum1(x int ,a []int) int {
	if len(a) == 0 {
		return x
	}
    return sum1(x+a[0], a[1:])
}
func Sum1(a []int) int {
    f:= func() int {
    		return sum1(0,a)
    }
    return f()
}

// 使用递推, 上面的sum1就比下面的sum2好, 因为下面的不满足尾递归的形式, 不能充分进行尾递归优化来减少调用栈.
func sum2(x int, a []int) int {
	if len(a) == 0 {
		return x
	}
  return x + sum2(a[0], a[1:])
}
func Sum2(a []int) int {
    return sum2(0,a)
}

// 使用遍历
func Sum3(a []int) int{
    var sum int
    for _, v:=range a{
        sum += v
    }
    return sum
}

// 使用数学函数递推公式
func sum4(x *int, a []int) func(x *int, a[]int) {
    if len(a) == 0{
        return nil
    }
    (*x) = (*x) + a[0]
    return sum4(x,a[1:])
}

func Sum4(a []int) int{
    var x int
    sum4(&x, a)
    return x
}

当然对于这个简单的场景, 使用遍历还是最快的, 毕竟函数调用中栈的切换是个开销:

func BenchmarkSum(b *testing.B) {
	cases := []struct{
		Num  []int
		Ept int
	}{
		{Num: []int{1,2,3,4,5,6,7,8,9,10}, Ept: 55},
	}
	for _, c := range cases {
		b.Run(fmt.Sprintf("Sum1:"), func(b *testing.B){
			for i := 0; i <b.N; i++ {
				Sum1(c.Num)
			}
		})
		b.Run(fmt.Sprintf("Sum2:"), func(b *testing.B){
			for i := 0; i <b.N; i++ {
				Sum2(c.Num)
			}
		})
		b.Run(fmt.Sprintf("Sum3:"), func(b *testing.B){
			for i := 0; i <b.N; i++ {
				Sum3(c.Num)
			}
		})
		b.Run(fmt.Sprintf("Sum4:"), func(b *testing.B){
			for i := 0; i <b.N; i++ {
				Sum4(c.Num)
			}
		})
	}
}

测试结果:

goos: linux
goarch: amd64
pkg: test
BenchmarkSum/Sum1:-8         	19798750	        62.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkSum/Sum2:-8         	18605296	        64.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkSum/Sum3:-8         	100000000	        11.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkSum/Sum4:-8         	18347358	        66.7 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	test	4.983s

函数式编程与尾调用 学习