1.5 函数式程序设计与Lambda演算

数据流主要是搞系统结构的人发展起来的概念和技术，这方面的鼻祖之一是MIT的Jack Dennis，那还是20世纪60年代中期的事。它最初是作为异步控制模块的电路结构开始的，到1975年前后就已经在讨论数据流语言和数据流计算机了。但是一些搞软件和计算的人也与他们殊途同归，发展起一套称为“函数式程序设计(functional programming)”的理论，其虽然形式上不同，但实质上却是与数据流等价的。

函数式程序设计最初是作为保证程序正确性的一项措施而发起的，但是它的根源却可以追溯到20世纪30年代丘奇(曾是图灵的导师)等人对于计算理论的研究，特别是关于“λ演算(Lambda calculus)”的研究。

函数式程序设计的倡导者们认为，如果对于子程序的调用都能像函数计算一样没有副作用，那么程序的正确性就比较容易得到保证，因为程序(尤其是并发或并行的程序)的毛病往往出在副作用。函数计算是一种映射，给定一组输入，就返回一个值作为输出，在此过程中对于环境没有任何改变，也就是没有任何副作用。这样就不会互相牵制、互相影响，也不会因为有意外的环境变化而导致失败。

但是，一般的计算机程序却不是这样。首先，子程序在执行的过程中可能会改变全局量的值。还有，如果作为调用参数的变量是指针，或是实质上相当于指针的变量引用(reference)，那么其所指向的变量就可能改变。这些都发生在函数返回值以外，所以称为副作用。要确保无副作用，首先当然不能允许有全局量存在(Java就不允许，但是如果可以通过get()、set()之类的方法引用别的对象中的变量，则实质上与全局量无异)，同时还得保证函数调用时只能传变量的值，而不能传地址或变量引用(实质上就是地址)。也就是说必须是“by value”而不能是“by reference”。另外还有一种表述是：调用参数所涉及的变量(对象)，必须是“immutable”，即“不可更改”的。我们举个例子来说明。假定有一个字符串，在一个缓冲区s中，然后我们需要提供一个将字符串转换成大写的子程序。一般我们会怎么做呢？可能是这样：把缓冲区s作为参数传给一个子程序to_upper()，这个子程序扫描作为参数传下来的字符串，就地将这个字符串中的每个字符改成大写，直到行的末尾。这样，当子程序返回时，这个字符串就成了大写的字符串。这是典型的“mutable”(可更改)，一个原先就存在的字符串的内容被更改了。如果另外有一段程序预期这个字符串的内容是原始的内容，那么在to_upper()执行之前这个预期是成立的，但是在to_upper()执行之后就不成立了。这样，那段程序的运行结果就与时序有关，而这可能不是原先所考虑和预期的。那么“immutable”的调用是怎么做的呢？调用者会先复制一个副本，然后把这个副本作为参数传给子程序(这就是“by value”)。或者，虽然仍是把字符串的原件传给子程序，但是却将原件设置成“只读”，不让更改(这得要有措施保证)，这样，就不会有副作用了。而在子程序中，则另外分配一个缓冲区，把这个字符串拷贝过去并改成大写，最后将这新的字符串作为函数值返回，这样就不会有副作用了。

结合函数式程序设计的理论，人们开发出一些函数式程序设计语言，一方面从语言上保证函数式程序设计原理的实施，另一方面也为程序员进行函数式程序设计提供了方便。这些语言都是“陈述式(declarative)”的，而不是“指令式(imperative)”的。什么意思呢？所谓“declarative”，就是只要说明哪一个参数或变量(一定是局部变量)的值是来自哪一个函数的就行，并不需要像“imperative”的程序那样去给出一步步的操作指令(语句)。这就带来函数式程序设计的一个特点：程序的语句次序是无关紧要的，前后换一下也没有关系。之所以如此是因为：对于函数式程序设计，我们只需陈述函数间的调用关系，而执行时的操作顺序则自然地隐含于这些调用关系之间。设想，如果函数a()的输入来自b()的输出，而b()的输入来自c()的输出，那么对这两句话来说，你先说后面那句、后说前面那句意义是一样。实际上，这样的程序已经不能算是“程序”了，因为它并没有规定一步步的“程”和“序”。不过这种陈述式的风格未必能坚持到底，到了底层的函数内部，有时还是需要有点指令式程序的。那也不要紧，反正语言通过其编译器或解释器保证了无副作用。注意：一般CPU的指令系统都是指令式的，函数式程序设计语言的编译器会把陈述式的语句翻译成指令式的程序。实际上，陈述式的“程序”所表达的是怎样搭建数据流，就好比是电视机的电路图。按电路图装配电视机的时候，先装上这个元件还是那个元件没什么关系，反正把电路图中所有的元器件都装上就可以了。

令人惊讶的是，函数式程序设计与数据流结构之间竟是如此贴合一致。为什么这么说呢？我们不妨回到前面那个数据流：

      cat shakespeare/*.txt|normalize|sort|uniq ＞ vocabulary

如果我们把这数据流中的每个节点，例如cat，又如sort，都看成一个函数，并把节点之间的管道看成函数调用时的参数传递，“|”左边那个函数的输出成为右边那个函数的输入参数，那就可以把这个数据流写成如下的函数式：

      vocabulary=uniq(sort(normalize(cat(shakespeare/*.txt))))

就是说，cat()的输出作为normalize()的调用参数，而normalize()的输出又作为sort()的调用参数，余类推。

那么把数据流中的节点看成函数有没有道理呢？有。因为函数无非就是映射，把定义域上的一组参数映射到值域上的某一个点上；而数据流中的节点，则根据一组输入参数计算出一个输出值。因此，我们可以认为后者是前者的实现。而且，输入到节点的参数都是数据而不是地址，是“by value”；而任何一个节点都无法直接改变别的节点中的变量，所以那些变量都是“immutable”的；最后，这些节点没有共享变量，更没有全局变量，所以一个节点对一组输入数据的计算相当于一次无副作用的函数调用或函数计算。

因此，我们可以把一个数据流所进行的计算看成是对一个复合函数的循环调用；反过来，如果我们有一个复合函数式，那么把它实现出来就应该是一个数据流。

上面所涉及的几个函数都只有单个调用参数，而且函数的输出也只出现在一个函数的输入参数表中，这决定了与其对应的数据流乃是链状的数据流。可想而知，如果一个函数有多个输入参数，那么数据流中与这个函数对应的节点就起着汇聚的作用。而倘若要让数据流在某一节点上分叉，那就得把这函数的输出赋给一个临时变量，再让这个临时变量出现在多个函数的输入参数表中。

不过要是直接用上面这个函数式作为程序中的语句，则有个缺点：其形式上的次序与对应的数据流是反的，这有点不合一般人的思维习惯。而如果用面向对象的语言来表达，就可以写成例如下面这样的语句：

      vocabulary=cat(shakespeare/*.txt).normalize().sort().uniq()

这里面的语法和语义是这样：函数cat()的返回值是个某类型(比方说Words)的对象，输出的内容(字符串)就存在这个对象(数据结构)的内部变量(缓冲区)中。此外，这个类提供一个方法函数normalize()，其输入取自该对象内部的缓冲区，这个函数也返回一个某类型对象。这个某类型与前面的某类型可以是同一个类型，也可以是不同的类型，但是原理和模式是一样的：函数normalize()的输出写在该类对象的某个内部变量(缓冲区)中，这个类则提供一个方法函数sort()。此后可以类推，这个语句可以一直延伸下去。但是请注意，即使normalize()所返回的类型与其前面的cat()所返回的类型一样，即normalize()的输出与输入是同一个类型，却不是同一个对象，而只能是同一类型的两个不同实例，因为输入参数的内容是“immutable”(不可更改)的。可想而知，如果数据流中的节点分处于不同的机器，中间通过网络相连，那自然是满足这个条件的，因为下游节点接收到的数据只能是上游节点输出的一个副本，下游节点的输出不可能回过头去改变上游节点的输出。即使是在同一台机器上，只要进程间不共享内存而是通过报文传递(message passing)实现通信，那也自然是能满足这个条件的。

但是这里还有个问题。无论从上面的函数式看，还是从与之对应的程序语句看，其中对于函数的调用都像是单次的调用，如normalize()、uniq()，似乎就是单次的函数计算，可是实际上这些函数的输入都是序列，相同的函数计算要施加到输入序列中的每一个元素上。这就是为什么在Unix上，这些utility，即工具性软件内部的操作都是套在一个while循环中的。像这样依次施加在输入序列中每一个元素上的函数计算，在当年丘奇的理论中，就称为λ演算，即“Lambda calculus”。

所以，在Unix的shell命令行中，以“|”号分隔的程序名相当于数据流中各个节点的操作名，从而也相当于函数名，并且带有Lambda语义。换言之，作为脚本语言的shell，是带有Lambda语义的。可是，在Java一类的编程语言中呢？如果我们一如既往地把函数调用看成调用一次执行一次，那么要表述Lambda演算就得把while循环写进去。那样的话，要用函数式的语句来描述数据流就有困难了。反过来，要是我们把函数调用看成是Lambda演算，那么真要表达单次的函数计算时又有问题了。这提示我们，对于同一个函数，语言中对于函数调用应该有两种不同的语法，分别表示两种不同的语义。进一步，用来实现Lambda语义的while循环不宜放在具体函数的内部，而应该放在外面。但是，不应该要求程序员自己编写这个while循环，也不应该让这个循环显式地出现在程序中，而应该由编译器自动产生。传统的指令式编程语言大多忽视Lambda演算，这是因为从前的计算不太有这方面的要求(当然也不绝对，要不然shell就不会实现这样的语义了)。但是现在情况不同了，大数据的出现将Lambda演算的重要性提高到了前所未有的高度。

正是因为这样，Java语言才有了它新的版本——Java 8。较之老版本，Java 8主要的改进就是两个方面的扩充：一是增添了Lambda演算的语法和语义；二是提供了一个实现“流(Stream)”式计算的API。这里所说的“流”就是数据流。

将Lambda演算作为语言成分加进Java 8，意味着Java 8的编译器能解析按规定语法书写的Lambda演算语句，并能按规定的语义生成为此所需的程序结构，包括上述的while循环，以及在节点间传递数据的机制。而在此之前，当Java语言还不提供这样的语法和语义的时候，则需要有个“平台(platform)”或“框架(framework)”来提供这样的程序结构，而实际进行计算的函数，结构上也会因此而有所不同。实际上，Hadoop在某种意义上就是这样的平台和框架，而Spark则在Java尚未提供函数式程序设计的语法和语义的时候就采用了函数式的Scala语言。

不过编程语言中有了Lambda和Stream的语义和语法也不是就万事大吉了。其实编译器或解释器所生成的代码也是建立在系统底层的基础上，依靠底层支撑的。要是早期Unix没有提供pipe机制(当时还没有socket这些机制)，则Shell语言的数据流语义就根本无法实现。另一方面，Shell虽然提供了数据流的语法(用“|”代表管道)和语义，但具体的实现只是在单机上的，数据流中的节点都只是同一台机器上的独立进程，对于多机的环境它就不能支持了。再说，如前所述，在Shell搭建的数据流中一个节点只是一个并发进程，而没有更高的并行度。所以，即使Java 8有了这方面的语法和语义，也有如何从单机推广到多机、如何增加并行度的问题。一般这可以通过不同的(底层)库程序(library)加以实现。

至此，我们已经能够理解，函数式程序中的语句本来就不必像传统指令式程序中那样去一步一步细述如何操作，而且语句的次序也变得无关紧要，因为操作的次序已经蕴含在函数表达式即程序语句之中了。函数式程序就好比数据流的装配图，先装这个还是先装那个没有什么关系，只要按图施工把它装配完成，就可以开动运行了。而函数式程序设计语言的编译器(或解释器)，就起着“施工单位”的作用。细想Unix上的Shell，对于前面所述的那个命令行来说，不就是起着把cat、normalize、sort、uniq这些进程通过pipe装配在一起的作用吗？而Unix这个操作系统，则为此提供诸如pipe()、dup()、fork()等系统调用，使Shell能够有这样的装配能力。不过Unix上的Shell是在单机上装配的，而多机(集群)条件下则需要有跨机器的装配能力。