关于函数式编程(Functional Programming)的学习笔记Ⅰ

0.要点

1.背景知识

2.函数式编程(FP)

3.FP的特性

1.背景知识

在C# 3.0中加入的新特性中，最大头的一个就是Lambda表达式，微软利用这个Lambda表达式结合其它一些特性演绎了很多东西，Lambda表达式和扩展方法一起带来了Linq to Objects，从Lambda表达式推演出来的表达式树又是Linq to SQL等的基础。而另一门语言F#也在悄悄崛起，Lambda表达式和F#都归属于函数编程范畴。

我们肯定都知道冯．诺依曼，因为他是计算机之父，因为他的冯．诺依曼体系结构。我们肯定都知道阿兰.图灵，人工智能之父，著名的图灵奖堪称计算机业的诺贝尔。在这个时代还存在另外一个传奇人物：阿隆左·丘奇(Alonzo Church)，知道这个人的请举手，反正我是很晚才知道。1936年，图灵的一篇论文：论数字计算在决断难题中的应用，在这篇论文中，提出了图灵机的设想，这也是今天计算机的基础，因为他不仅仅提出了设想，还在理论上证明了这种机器是可以制造出来的，不过在这之前，还有一个Lambda演算的理论，该理论奠定后来的Lisp语言(值得注意的是，Lisp是我们拥有的第二个计算机高级语言，仅次于Forton之后)和函数编程的基础。

2.什么是函数式编程(Functional Programming)

函数式编程利用数学上的函数来避免状态(这个可是图灵机的基础，图灵机利用状态去判定下一步工作，而函数式编程却不需要状态)和可变的数据(今天，如果没有变量，我真的不知道我该怎么编写代码)。看起来非常的奇妙，但这一切都是Lambda演算赐予的。

Wiki百科的定义是：是种编程范型，它将电脑运算视为函数的计算。函数编程语言最重要的基础是 λ 演算（lambda calculus）。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。和命令式编程相比，函数式编程强调函数的计算比指令的运行重要。和过程化编程相比，函数式编程里，函数的计算可随时调用。

函数是函数式编程的基本单位，函数几乎被用于一切，包括最简单的计算，甚至变量都由计算取代。在函数式编程中，变量只是表达式的别名（这样我们就不必把所有东西打在一行里）。变量是不能更改的，所有变量只能被赋值一次。用 Java 的术语来说，这意味着所有单一变量都被声明为 final（或 C++ 的 const）。在函数式编程中没有非 final 的变量。

final int i = 5;
final int j = i + 3;

因为函数式编程中所有变量都是 final 的，所以可以提出这样两个有趣的表述：没有必要总是写出关键字 final，没有必要把变量再称为变量。那么现在我们对Java作出两个修改：在我们的函数式 Java 中所有变量默认都是 final的，我们将变量（variable）称为符号（symbol）。

就此你也许会质疑，用我们新创造的语言还能写出有些复杂度的程序吗？如果每个符号都是不可变更(non-mutalbe)的，那么就无法改变任何状态！其实事实并非完全如此。在阿隆左研究其 lambda 演算时，他并不想将某个状态维护一段时间以期未来对其进行修改。他关注的是对数据的操作（也通常被称为”演算体 caculating stuff”）。既然已被证明lambda演算与图灵机等价，它可以完成所有命令式编程语言能够完成的任务。那么，我们怎么才能做到呢？

答案是函数式程序能保存状态，只是它并非通过变量而是使用函数来保存状态。状态保存在函数的参数中，保存在堆栈上。如果你要保存某个状态一段时间并时不时地对其进行一些修改，可以写个递归函数。举个例子，我们写个函数来翻转 Java 的字符串。记住，我们声明的每个变量默认都是 final 的。

String reverse(String arg) {
	if(arg.length == 0) {
		return arg;
	}
	else {
	return reverse(arg.substring(1, arg.length)) + arg.substring(0,1);
	}
}

这个函数很慢因为它不断地调用自己，它还也是个嗜内存魔因为要持续分配对象。不过它的确是在用函数式风格。

3.函数式编程的特性

闭包和高阶函数
函数本身是first class对象，闭包是起函数作用并可以像对象一样操作的。
高阶函数是可以接受一个函数为参数，并可以返回一个函数。
延迟计算（lazy evaluation）
递归的计算机制
引用透明: 同样的输入返回同样的结果，与上下文无关。
没有副作用: 赋值后不能更改，既成为final

单元测试

      因为函数式编程的每一个符号都是 final 的，没有函数产生过副作用。因为从未在某个地方修改过值，也没有函数修改过在其作用域之外的量并被其他函数使用（如类成员或全局变量）。这意味着函数求值的结果只是其返回值，而惟一影响其返回值的就是函数的参数。

     这是单元测试的理想环境。对被测试程序中的每个函数，你只需在意其参数，而不必考虑函数调用顺序，不用谨慎地设置外部状态。所有要做的就是传递代表了边际情况的参数。如果程序中的每个函数都通过了单元测试，你就对这个软件的质量有了相当的自信。而命令式编程就不能这样乐观了，在 Java 或 C++ 中只检查函数的返回值还不够——我们还必须验证这个函数可能修改了的外部状态。

调试

      如果一个函数式程序不如你期望地运行，调试也是轻而易举。因为函数式程序的 bug 不依赖于执行前与其无关的代码路径，你遇到的问题就总是可以再现。在命令式程序中，bug 时隐时现，因为在那里函数的功能依赖与其他函数的副作用，你可能会在和 bug 的产生无关的方向探寻很久，毫无收获。函数式程序就不是这样——如果一个函数的结果是错误的，那么无论之前你还执行过什么，这个函数总是返回相同的错误结果。沿着堆栈检查函数的参数和返回值，只要发现一个不尽合理的结果就进入那个函数然后一步步跟踪下去，重复这一个过程，直到它让你发现了 bug 的生成点。

并行

     函数式程序无需任何修改即可并行执行。不用担心死锁和临界区，因为你从未用锁！函数式程序里没有任何数据被同一线程修改两次，更不用说两个不同的线程了。这意味着可以不假思索地简单增加线程而不会引发折磨着并行应用程序的传统问题。

      事实既然如此，为什么并不是所有人都在需要高度并行作业的应用中采用函数式程序？嗯，他们正在这样做。爱立信公司设计了一种叫作 Erlang 的函数式语言并将它使用在需要极高抗错性和可扩展性的电信交换机上。还有很多人也发现了 Erlang 的优势并开始使用它。我们谈论的是电信通信控制系统，这与设计华尔街的典型系统相比对可靠性和可升级性要求高了得多。实际上，Erlang 系统并不可靠和易扩展，Java 才是。Erlang 系统只是坚如磐石。

      关于并行的故事还没有就此停止，即使你的程序本身就是单线程的，那么函数式程序的编译器仍然可以优化它使其运行于多个CPU上。请看下面这段代码：
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
      在函数编程语言中，编译器会分析代码，辨认出潜在耗时的创建字符串s1和s2的函数，然后并行地运行它们。这在命令式语言中是不可能的，因为在那里，每个函数都有可能修改了函数作用域以外的状态并且其后续的函数又会依赖这些修改。在函数式语言里，自动分析函数并找出适合并行执行的候选函数简单的像自动进行的函数内联化！在这个意义上，函数式风格的程序是“不会过时的技术(future proof)”(即使不喜欢用行业术语，但这回要破例一次)。硬件厂商已经无法让CPU运行得更快了，于是他们增加了处理器核心的速度并因并行而获得了四倍的速度提升。当然他们也顺便忘记提及我们的多花的钱只是用在了解决平行问题的软件上了。一小部分的命令式软件和 100% 的函数式软件都可以直接并行运行于这些机器上。

代码热部署

       过去要在 Windows上安装更新，重启计算机是难免的，而且还不只一次，即使是安装了一个新版的媒体播放器。Windows XP 大大改进了这一状态，但仍不理想（我今天工作时运行了Windows Update，现在一个烦人的图标总是显示在托盘里除非我重启一次机器）。Unix系统一直以来以更好的模式运行，安装更新时只需停止系统相关的组件，而不是整个操作系统。即使如此，对一个大规模的服务器应用这还是不能令人满意的。电信系统必须100%的时间运行，因为如果在系统更新时紧急拨号失效，就可能造成生命的损失。华尔街的公司也没有理由必须在周末停止服务以安装更新。

       理想的情况是完全不停止系统任何组件来更新相关的代码。在命令式的世界里这是不可能的。考虑运行时上载一个Java类并重载一个新的定义，那么所有这个类的实例都将不可用，因为它们被保存的状态丢失了。我们可以着手写些繁琐的版本控制代码来解决这个问题，然后将这个类的所有实例序列化，再销毁这些实例，继而用这个类新的定义来重新创建这些实例，然后载入先前被序列化的数据并希望载入代码可以恰当地将这些数据移植到新的实例。在此之上，每次更新都要重新手动编写这些用来移植的代码，而且要相当谨慎地防止破坏对象间的相互关系。理论简单，但实践可不容易。

       对函数式的程序，所有的状态即传递给函数的参数都被保存在了堆栈上，这使的热部署轻而易举！实际上，所有我们需要做的就是对工作中的代码和新版本的代码做一个差异比较，然后部署新代码。其他的工作将由一个语言工具自动完成！如果你认为这是个科幻故事，请再思考一下。多年来 Erlang工程师一直更新着他们的运转着的系统，而无需中断它。

机器辅助的推理和优化

      函数式语言的一个有趣的属性就是他们可以用数学方式推理。因为一种函数式语言只是一个形式系统的实现，所有在纸上完成的运算都可以应用于用这种语言书写的程序。编译器可以用数学理论将转换一段代码转换为等价的但却更高效的代码。多年来关系数据库一直在进行着这类优化。没有理由不能把这一技术应用到常规软件上。

       另外，还能使用这些技术来证明部分程序的正确，甚至可能创建工具来分析代码并为单元测试自动生成边界用例！对稳固的系统这种功能没有价值，但如果你要设计心房脉冲产生器 (pace maker)或空中交通控制系统，这种工具就不可或缺。如果你编写的应用程序不是产业的核心任务，这类工具也是你强于竞争对手的杀手锏。

高阶函数

   函数式语言提供了不同的抽象工具它会使你忘记你曾经习惯于修改变量。高阶函数就是这样一种工具。

     创建函数的方式和 C 中相似:
       int add(int i, int j) 
            {return i + j;}
现在扩展我们的 Java 编译器使其支持这种记法。当我们输入上述代码后编译器会把它转换成下面的Java代码（别忘了，所有东西都是 final 的）：
     class add_function_t {
          int add(int i, int j) {
                return i + j;
          }
      }

      add_function_t add = new add_function_t();
     这里的符号 add 并不是一个函数。这是一个有一个成员函数的很小的类。我们现在可以把 add 作为函数参数放入我们的代码中。还可以把它赋给另一个符号。

     我们在运行时创建的 add_function_t 的实例如果不再被使用就将会被垃圾回收掉。这些使得函数成为第一级的对象无异于整数或字符串。（作为参数）操作函数的函数被称为高阶函数。别让这个术语吓着你，这和 Java 的 class 操作其它 class（把它们作为参数）没有什么区别。我们本可以把它们称为“高阶类”但没有人注意到这个，因为 Java 背后没有一个强大的学术社区。

      如果你发现在那个函数里一些逻辑动作根据情况有变，就把他提取成高阶函数。高阶函数只是开始!

惰性求值

      惰性（或延迟）求值这一技术可能会变得非常有趣一旦我们采纳了函数式哲学。在讨论并行时已经见过下面的代码片断：

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

       在一个命令式语言中求值顺序是确定的，因为每个函数都有可能会变更或依赖于外部状态，所以就必须有序的执行这些函数：首先是
somewhatLongOperation1，然后 somewhatLongOperation2，最后 concatenate，在函数式语言里就不尽然了。

       前面提到只要确保没有函数修改或依赖于全局变量，somewhatLongOperation1 和 somewhatLongOperation2 可以被并行执行。但是如果我们不想同时运行这两个函数，还有必要保证有序的执行他们呢？答案是不。我们只在其他函数依赖于s1和s2时才需要执行这两个函数。我们甚至在concatenate调用之前都不必执行他们——可以把他们的求值延迟到concatenate函数内实际用到他们的位置。如果用一个带有条件分支的函数替换concatenate并且只用了两个参数中的一个，另一个参数就永远没有必要被求值。在 Haskell 语言中，不确保一切都（完全）按顺序执行，因为 Haskell 只在必要时才会对其求值。

       惰性求值优点众多，但缺点也不少。我不在这里列出，有兴趣的朋友可以在这里看。

参考资料：

http://www.cnblogs.com/yuyijq/archive/2008/08/02/1258604.html

http://zh.wikipedia.org/zh-cn/%E5%87%BD%E6%95%B8%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80

http://erlang-china.org/study/yet-another-pf-guide.html