函数式，F#都做了哪些优化？

2023-11-01

非函数式语言中使用函数式风格的缺点：

函数式的优点，想必大家都已经非常了解了。我们来看看，一般语言使用函数式风格可能带来的问题：

变量默认是可变的。为了实现不可变性，开发者只能人为的规范不去改变变量的值，没有明确的变量修改提示，容易因失误改变变量的值。
为了实现不可变性，往往需要更多的变量来存储中间结果，产生大量的资源开销。又由于垃圾回收往往不是即时的，随着数据规模上升，可能会出现资源消耗问题。
使用递归来替代循环，如果语言没有对尾递归做优化，每次递归调用会变成真实的函数调用，影响性能。并且如果递归函数中有大量临时变量，还可能导致堆栈空间被快速侵蚀，引起性能和资源占用双重问题。
为了实现高阶函数，需要支持函数作为参数。在函数内调用函数如果不能做到内联，也会产生不必要的性能开销。如果函数调用在循环中，这些开销会累积从而影响性能。
柯里化的函数，需要将每个参数都包装成一个独立的函数，然后利用闭包进行函数的嵌套。这导致了过度包装，调用时则是层层解包，影响性能。
函数式的序列处理，如果不支持lazy模式，则会产生许多不必要的额外处理。这在结合短路模式时尤为明显。例如调用了map函数，再调用exists函数，map会先完成完整遍历得到全新的序列，然后交给exists做短路判断，影响性能。

F#如何解决上述问题

值默认不可变

为了解决第一个缺点，F#对值的可变性做了强制限制。

F#的值默认是不可变的。虽然你仍然可以使用mutable关键词将其设置为变量，但即使是可变的变量也采用了不同的赋值符号（<-）区别于绑定符号（=）。这样可以很大程度上减少犯错。

看如下例子：

let a = 1
a <- 2  //这将导致编译器报错，因为a不可变
a = 2  //只在let绑定中=才是绑定值，其余位置=是比较符，相当于==。因此此处是比较a与2的值，该表达式返回bool类型。很难用错。

尾递归优化和参数变量化

为了解决2和3，F#针对尾递归做了优化，并且将递归的参数编译为变量，递归的调用实际上被编译为了循环体内变量的更替。

尾递归函数的特点是：不保存任何中间值，下层递归结果不参与本层函数的计算，在本层函数的某些分支的终点（最后一句）调用递归。

判断一个递归函数是不是尾递归，有十分简单的规则：

看递归是不是会在最后一层返回该函数的某个参数（或其运算）作为结果，并且此次返回会一路返回到最上层，不会参与到中间任何一层的运算中。

尾递归，很容易总结出以下性质：

尾递归过程中的所有变化值都在参数中。
尾递归最重要返回的值也在参数中
尾递归除了参数之外没有任何新增的变量需要在进入下一层递归时保留。

因此，尾递归可以简单的优化成while循环。而出口点则在所有没有调用递归的分支上（相当于break）。所有有递归调用的分支，递归调用可以翻译为对参数对应的几个变量进行赋值，然后再次进入循环。

比如下面的例子：

//求1..i的和
let rec sum s i =  //s存储的是和， s和i被编译为变量
	match i with
	| 0 -> s //终止条件，相当于break，最终返回s
	| _ -> 
		sum (s + i) (i - 1)  //递归调用，被编译为s <- s + i，i <- i - 1，然后继续循环。当然为了考虑变量变更后值的问题，实际上还引入了临时变量，这里不展开了，可以看我上一篇文章。

sum 0 100  //计算从1到100的和

上述代码，差不多会被优化成：（示意，并不精确）

int s = 0;
int i = 100;
while (true)
{
    if (i == 0) break;
    s += i;
    i--;
}

从而既解决了递归嵌套的问题，又解决了临时变量的创建和释放问题。

FSharpFun<>

为了解决4和5：

F#中定义的函数是自动柯里化的。对于大于一个参数的柯里化的函数定义，F#采用了专门的泛型类来描述，那就是FSharpFun。同样如果函数作为参数，它的类型也是FSharpFun。其内部针对柯里化做出了优化，使得柯里化的函数可以用过InvokeFast方法进行优化调用。如果该函数调用存在优化版本，则相当于只调用了一次Invoke，从而避免了Invoke之后再Invoke的连锁调用。FSharpFun通过泛型来定义每个参数和返回值的类型。从而解决了柯里化的过度包装和性能消耗问题。这么做的副作用是只能支持有限个数的柯里化参数的函数，不过这不是什么大问题。

在F#中，函数可以被显式的声明为inline，从而可以内联到其他函数中。在F#6.0中，还引入了InlineIfLambda特性，来标记参数，使得lambda描述的匿名方法可以自动内联。不过该特性只能用在类的方法上，而不能用于一般的let绑定的函数。

Seq和Lazy

解决6其实是手到擒来的事情。大家都知道.Net架构有迭代器，而迭代器就是Lazy的，具有延时执行的特点。F#中针对序列处理的模块Seq，就等同于.Net中的IEnumerable。而Seq模块的函数，其本质就是迭代器。因而Seq的函数大都具有lazy的特性。

这里最好直接拿一个样例来举例，该例子中，takeWhile是取元素，直到不满足条件，exists是遍历直到出现第一个满足条件的。两个函数都是短路的。我们看看F#如何运行，会不会正确的短路掉。

//求n以内的质数
let primes n =
    let rec loop list i =
        match i with
        | _ when i > n ->
            list
        | _ ->
            let h = float i |> sqrt |> int
            list
            |> Seq.takeWhile (fun j -> j <= h)
            |> Seq.exists (fun j -> i % j = 0)
            |> function
                | true -> loop list (i + 1)
                | false -> loop (list @ [i]) (i + 1)
    loop [] 2

printfn "%A" (primes 100)

上面的代码打印了100以内的质数。其中list存储了递归至今的质数，i是当前测试的数。h是i的平方根。针对i要检测list中是否有可以整除的元素，遍历list的时候在元素大于h时应当终止本轮遍历并返回false（无整除元素），遍历到任何可以整除的元素时应当返回true。这两个短路条件返回的一个是true一个是false，因而无法写进同一个短路函数中。takeWhile和exists就作为两个短路函数先后调用了。

我们使用Seq的函数，实现lazy的运行。为了展示具体执行过程，我们添加一些打印内容。修改代码如下：

let primes n =
    let rec loop list i =
        match i with
        | _ when i > n ->
            list
        | _ ->
            printf "lv.%d --- " i
            let h = float i |> sqrt |> int
            list
            |> Seq.takeWhile (fun j -> printf "A-%d; " j; j <= h)
            |> Seq.exists (fun j -> printf "B-%d; " j; i % j = 0)
            |> function
                | true -> printfn ""; loop list (i + 1)
                | false -> printfn ""; loop (list @ [i]) (i + 1)
    loop [] 2

printfn "%A" (primes 100)

可以看出，仅仅增加了一下打印输出而已。我们看看执行结果：

lv.2 ---
lv.3 --- A-2;
lv.4 --- A-2; B-2;
lv.5 --- A-2; B-2; A-3;
lv.6 --- A-2; B-2;
lv.7 --- A-2; B-2; A-3;
lv.8 --- A-2; B-2;
lv.9 --- A-2; B-2; A-3; B-3;
lv.10 --- A-2; B-2;
lv.11 --- A-2; B-2; A-3; B-3; A-5;
lv.12 --- A-2; B-2;
lv.13 --- A-2; B-2; A-3; B-3; A-5;
lv.14 --- A-2; B-2;
lv.15 --- A-2; B-2; A-3; B-3;
lv.16 --- A-2; B-2;
lv.17 --- A-2; B-2; A-3; B-3; A-5;
lv.18 --- A-2; B-2;
lv.19 --- A-2; B-2; A-3; B-3; A-5;
lv.20 --- A-2; B-2;
lv.21 --- A-2; B-2; A-3; B-3;
lv.22 --- A-2; B-2;
lv.23 --- A-2; B-2; A-3; B-3; A-5;
lv.24 --- A-2; B-2;
lv.25 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.26 --- A-2; B-2;
lv.27 --- A-2; B-2; A-3; B-3;
lv.28 --- A-2; B-2;
lv.29 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.30 --- A-2; B-2;
lv.31 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.32 --- A-2; B-2;
lv.33 --- A-2; B-2; A-3; B-3;
lv.34 --- A-2; B-2;
lv.35 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.36 --- A-2; B-2;
lv.37 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.38 --- A-2; B-2;
lv.39 --- A-2; B-2; A-3; B-3;
lv.40 --- A-2; B-2;
lv.41 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.42 --- A-2; B-2;
lv.43 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.44 --- A-2; B-2;
lv.45 --- A-2; B-2; A-3; B-3;
lv.46 --- A-2; B-2;
lv.47 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7;
lv.48 --- A-2; B-2;
lv.49 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7;
lv.50 --- A-2; B-2;
lv.51 --- A-2; B-2; A-3; B-3;
lv.52 --- A-2; B-2;
lv.53 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.54 --- A-2; B-2;
lv.55 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.56 --- A-2; B-2;
lv.57 --- A-2; B-2; A-3; B-3;
lv.58 --- A-2; B-2;
lv.59 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.60 --- A-2; B-2;
lv.61 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.62 --- A-2; B-2;
lv.63 --- A-2; B-2; A-3; B-3;
lv.64 --- A-2; B-2;
lv.65 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.66 --- A-2; B-2;
lv.67 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.68 --- A-2; B-2;
lv.69 --- A-2; B-2; A-3; B-3;
lv.70 --- A-2; B-2;
lv.71 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.72 --- A-2; B-2;
lv.73 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.74 --- A-2; B-2;
lv.75 --- A-2; B-2; A-3; B-3;
lv.76 --- A-2; B-2;
lv.77 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7;
lv.78 --- A-2; B-2;
lv.79 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.80 --- A-2; B-2;
lv.81 --- A-2; B-2; A-3; B-3;
lv.82 --- A-2; B-2;
lv.83 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.84 --- A-2; B-2;
lv.85 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.86 --- A-2; B-2;
lv.87 --- A-2; B-2; A-3; B-3;
lv.88 --- A-2; B-2;
lv.89 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.90 --- A-2; B-2;
lv.91 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7;
lv.92 --- A-2; B-2;
lv.93 --- A-2; B-2; A-3; B-3;
lv.94 --- A-2; B-2;
lv.95 --- A-2; B-2; A-3; B-3; A-5; B-5;
lv.96 --- A-2; B-2;
lv.97 --- A-2; B-2; A-3; B-3; A-5; B-5; A-7; B-7; A-11;
lv.98 --- A-2; B-2;
lv.99 --- A-2; B-2; A-3; B-3;
lv.100 --- A-2; B-2;
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97]

这里A表示进入了takeWhile的条件函数，B表示进入了exists的条件函数。由于是延迟执行的，所以我们看到A和B成功被合并到一次迭代中，A、B交替执行，而不是一股脑执行完A再一股脑执行B。从而只要A或者B有一个达到了短路条件，整个过程都会短路返回。

例如：

对于4，我们遍历已存在的质数列表[2; 3]，遍历2时，进入takeWhile的条件，发现它不小于4的平方根，不满足短路条件；继而进入exists，发现2可以整除4，满足短路条件，于是返回false，不再遍历剩下的元素3。
对于5，我们遍历已存在的质数列表[2; 3]，进入A发现满足2<根号5，进入B发现2不能整除5；继续遍历3，发现3已经不满足小于根号5了，短路触发，从而B不再执行，返回true。

利用上面特性，F#也成功解决了序列处理的短路的问题。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)