函数式编程简介(续)

  函数式编程       2016-07-07

高阶函数

我还记得在了解到FP以上的各种好处后想到:“这些优势都很吸引人,可是,如果必须非要用这种所有变量都是final的蹩脚语言,估计还是不怎么实用吧”。其实这样的想法是不对的。对于Java这样的指令式语言来说,如果所有的变量都是必须是final的,那么确实很束手束脚。然而对函数式语言来说,情况就不一样了。函数式语言提供了一种特别的抽象工具,这种工具将帮助使用者编写FP代码,让他们甚至都没想到要修改变量的值。高阶函数就是这种工具之一。

FP语言中的函数有别于Java或是C。可以说这种函数是一个全集:Java函数可以做到的它都能做,同时它还有更多的能力。首先,像在C里写程序那样创建一个函数:

  1. int add(int i, int j) {
  2. return i + j;
  3. }

看起来和C程序没什么区别,但是很快你就可以看出区别来。接下来我们扩展Java的编译器以便支持这种代码,也就是说,当我们写下以上的程序编译器会把它转化成下面的Java程序(别忘了,所有的变量都是final的):

  1. class add_function_t {
  2. int add(int i, int j) {
  3. return i + j;
  4. }
  5. }
  6. add_function_t add = new add_function_t();

在这里,符号add并不是一个函数,它是只有一个函数作为其成员的简单的类。这样做有很多好处,可以在程序中把add当成参数传给其他的函数,也可以把add赋给另外一个符号,还可以在运行时创建add_function_t的实例然后在不再需要这些实例的时候由系统回收机制处理掉。这样做使得函数成为和integer或是string这样的第一类对象。对其他函数进行操作(比如说把这些函数当成参数)的函数,就是所谓的高阶函数。别让这个看似高深的名字吓倒你(译者:好死不死起个这个名字,初一看还准备搬出已经尘封的高数教材……),它和Java中操作其他类(也就是把一个类实例传给另外的类)的类没有什么区别。可以称这样的类为“高阶类”,但是没人会在意,因为Java圈里就没有什么很强的学术社团。(译者:这是高级黑吗?)

那么什么时候该用高阶函数,又怎样用呢?我很高兴有人问这个问题。设想一下,你写了一大堆程序而不考虑什么类结构设计,然后发现有一部分代码重复了几次,于是你就会把这部分代码独立出来作为一个函数以便多次调用(所幸学校里至少会教这个)。如果你发现这个函数里有一部分逻辑需要在不同的情况下实现不同的行为,那么你可以把这部分逻辑独立出来作为一个高阶函数。搞晕了?下面来看看我工作中的一个真实的例子。

假设有一段Java的客户端程序用来接收消息,用各种方式对消息做转换,然后发给一个服务器。

  1. class MessageHandler {
  2. void handleMessage(Message msg) {
  3. // ...
  4. msg.setClientCode("ABCD_123");
  5. // ...
  6. sendMessage(msg);
  7. }
  8. // ...
  9. }

再进一步假设,整个系统改变了,现在需要发给两个服务器而不再是一个了。系统其他部分都不变,唯独客户端的代码需要改变:额外的那个服务器需要用另外一种格式发送消息。应该如何处理这种情况呢?我们可以先检查一下消息要发送到哪里,然后选择相应的格式把这个消息发出去:

  1. class MessageHandler {
  2. void handleMessage(Message msg) {
  3. // ...
  4. if(msg.getDestination().equals("server1") {
  5. msg.setClientCode("ABCD_123");
  6. } else {
  7. msg.setClientCode("123_ABC");
  8. }
  9. // ...
  10. sendMessage(msg);
  11. }
  12. // ...
  13. }

可是这样的实现是不具备扩展性的。如果将来需要增加更多的服务器,上面函数的大小将呈线性增长,使得维护这个函数最终变成一场噩梦。面向对象的编程方法告诉我们,可以把MessageHandler变成一个基类,然后将针对不同格式的消息编写相应的子类。

  1. abstract class MessageHandler {
  2. void handleMessage(Message msg) {
  3. // ...
  4. msg.setClientCode(getClientCode());
  5. // ...
  6. sendMessage(msg);
  7. }
  8. abstract String getClientCode();
  9. // ...
  10. }
  11. class MessageHandlerOne extends MessageHandler {
  12. String getClientCode() {
  13. return "ABCD_123";
  14. }
  15. }
  16. class MessageHandlerTwo extends MessageHandler {
  17. String getClientCode() {
  18. return "123_ABCD";
  19. }
  20. }

这样一来就可以为每一个接收消息的服务器生成一个相应的类对象,添加服务器就变得更加容易维护了。可是,这一个简单的改动引出了很多的代码。仅仅是为了支持不同的客户端行为代码,就要定义两种新的类型!现在来试试用我们刚才改造的语言来做同样的事情,注意,这种语言支持高阶函数:

  1. class MessageHandler {
  2. void handleMessage(Message msg, Function getClientCode) {
  3. // ...
  4. Message msg1 = msg.setClientCode(getClientCode());
  5. // ...
  6. sendMessage(msg1);
  7. }
  8. // ...
  9. }
  10. String getClientCodeOne() {
  11. return "ABCD_123";
  12. }
  13. String getClientCodeTwo() {
  14. return "123_ABCD";
  15. }
  16. MessageHandler handler = new MessageHandler();
  17. handler.handleMessage(someMsg, getClientCodeOne);

在上面的程序里,我们没有创建任何新的类型或是多层类的结构。仅仅是把相应的函数作为参数进行传递,就做到了和用面向对象编程一样的事情,而且还有额外的好处:一是不再受限于多层类的结构。这样做可以做运行时传递新的函数,可以在任何时候改变这些函数,而且这些改变不仅更加精准而且触碰的代码更少。这种情况下编译器其实就是在替我们编写面向对象的“粘合”代码(译者:又称胶水代码,粘接代码)!除此之外我们还可以享用FP编程的其他所有优势。函数式编程能提供的抽象服务还远不止于此。高阶函数只不过是个开始。

Currying

我遇见的大多数码农都读过“四人帮”的那本《设计模式》。任何稍有自尊心的码农都会说这本书和语言无关,因此无论你用什么编程语言,当中提到的那些模式大体上适用于所有软件工程。听起来很厉害,然而事实却不是这样。
函数式语言的表达能力很强。用这种语言编程的时候基本不需要设计模式,因为这种语言层次已经足够高,使得使用者可以以概念编程,从而完全不需要设计模式了。以适配器模式为例(有人知道这个模式和外观模式有什么区别吗?怎么觉得有人为了出版合同的要求而硬生生凑页数?)(译者:您不愧是高级黑啊)。对于一个支持currying技术的语言来说,这个模式就是多余的。
在Java中最有名的适配器模式就是在其“默认”抽象单元中的应用:类。在函数式语言中这种模式其实就是函数。在这个模式中,一个接口被转换成另外一个接口,让不同的用户代码调用。接下来就有一个适配器模式的例子:

  1. int pow(int i, int j);
  2. int square(int i)
  3. {
  4. return pow(i, 2);
  5. }

上面的代码中square函数计算一个整数的平方,这个函数的接口被转换成计算一个整数的任意整数次幂。在学术圈里这种简单的技术就被叫做currying(因为逻辑学家哈斯凯尔·加里用其数学技巧将这种技术描述出来,于是就以他的名字来命名了)。在一个FP语言中函数(而不是类)被作为参数进行传递,currying常常用于转化一个函数的接口以便于其他代码调用。函数的接口就是它的参数,于是currying通常用于减少函数参数的数量(见前例)。
函数式语言生来就支持这一技术,于是没有必要为某个函数手工创建另外一个函数去包装并转换它的接口,这些函数式语言已经为你做好了。我们继续拓展Java来支持这一功能。

  1. square = int pow(int i, 2);

上面的语句实现了一个平方计算函数,它只需要一个参数。它会继而调用pow函数并且把第二个参数置为2。编译过后将生成以下Java代码:

  1. class square_function_t {
  2. int square(int i) {
  3. return pow(i, 2);
  4. }
  5. }
  6. square_function_t square = new square_function_t();

从上面的例子可以看到,很简单的,函数pow的封装函数就创建出来了。在FP语言中currying就这么简单:一种可以快速且简单的实现函数封装的捷径。我们可以更专注于自己的设计,编译器则会为你编写正确的代码!什么时候使用currying呢?很简单,当你想要用适配器模式(或是封装函数)的时候,就是用currying的时候。

惰性求值

惰性求值(或是延迟求值)是一种有趣的技术,而当我们投入函数式编程的怀抱后这种技术就有了得以实现的可能。前面介绍并发执行的时候已经提到过如下代码:

  1. String s1 = somewhatLongOperation1();
  2. String s2 = somewhatLongOperation2();
  3. String s3 = concatenate(s1, s2);

在指令式语言中以上代码执行的顺序是显而易见的。由于每个函数都有可能改动或者依赖于其外部的状态,因此必须顺序执行。先是计算somewhatLongOperation1,然后到somewhatLongOperation2,最后执行concatenate。函数式语言就不一样了。

在前面讨论过,somewhatLongOperation1和somewhatLongOperation2是可以并发执行的,因为函数式语言保证了一点:没有函数会影响或者依赖于全局状态。可是万一我们不想要这两个函数并发执行呢?这种情况下是不是也还是要顺序执行这些函数?答案是否定的。只有到了执行需要s1、s2作为参数的函数的时候,才真正需要执行这两个函数。于是在concatenate这个函数没有执行之前,都没有需要去执行这两个函数:这些函数的执行可以一直推迟到concatenate()中需要用到s1和s2的时候。假如把concatenate换成另外一个函数,这个函数中有条件判断语句而且实际上只会需要两个参数中的其中一个,那么就完全没有必要执行计算另外一个参数的函数了!Haskell语言就是一个支持惰性求值的例子。Haskell不能保证任何语句会顺序执行(甚至完全不会执行到),因为Haskell的代码只有在需要的时候才会被执行到。

除了这些优点,惰性求值也有缺点。这里介绍了它的优点,我们将在下一章节介绍这些缺点以及如何克服它们。

代码优化

惰性求值使得代码具备了巨大的优化潜能。支持惰性求值的编译器会像数学家看待代数表达式那样看待函数式程序:抵消相同项从而避免执行无谓的代码,安排代码执行顺序从而实现更高的执行效率甚至是减少错误。在此基础上优化是不会破坏代码正常运行的。严格使用形式系统的基本元素进行编程带来的最大的好处,是可以用数学方法分析处理代码,因为这样的程序是完全符合数学法则的。

抽象化控制结构

惰性求值技术提供了更高阶的抽象能力,这提供了实现程序设计独特的方法。比如说下面的控制结构:

  1. unless(stock.isEuropean()) {
  2. sendToSEC(stock);
  3. }

程序中只有在stock为European的时候才执行sendToSEC。如何实现例子中的unless?如果没有惰性求值就需要求助于某种形式的宏(译者:用if不行么?),不过在像Haskell这样的语言中就不需要那么麻烦了。直接实现一个unless函数就可以!

  1. void unless(boolean condition, List code) {
  2. if(!condition)
  3. code;
  4. }

请注意,如果condition值为真,那就不会计算code。在其他严格语言(见严格求值)中这种行为是做不到的,因为在进入unless这个函数之前,作为参数的code已经被计算过了。

无穷数据结构

惰性求值技术允许定义无穷数据结构,这要在严格语言中实现将非常复杂。例如一个储存Fibonacci数列数字的列表。很明显这样一个列表是无法在有限的时间内计算出这个无穷的数列并存储在内存中的。在像Java这样的严格语言中,可以定义一个Fibonacci函数,返回这个序列中的某个数。而在Haskell或是类似的语言中,可以把这个函数进一步抽象化并定义一个Fibonacci数列的无穷列表结构。由于语言本身支持惰性求值,这个列表中只有真正会被用到的数才会被计算出来。这让我们可以把很多问题抽象化,然后在更高的层面上解决它们(比如可以在一个列表处理函数中处理无穷多数据的列表)。

不足之处

俗话说天下没有免费的午餐™。惰性求值当然也有其缺点。其中最大的一个就是,嗯,惰性。现实世界中很多问题还是需要严格求值的。比如说下面的例子:

  1. System.out.println("Please enter your name: ");
  2. System.in.readLine();

在惰性语言中没人能保证第一行会中第二行之前执行!这也就意味着我们不能处理IO,不能调用系统函数做任何有用的事情(这些函数需要按照顺序执行,因为它们依赖于外部状态),也就是说不能和外界交互了!如果在代码中引入支持顺序执行的代码原语,那么我们就失去了用数学方式分析处理代码的优势(而这也意味着失去了函数式编程的所有优势)。幸运的是我们还不算一无所有。数学家们研究了不同的方法用以保证代码按一定的顺序执行(in a functional setting?)。这一来我们就可以同时利用到函数式和指令式编程的优点了!这些方法有continuations,monads以及uniqueness typing。这篇文章仅仅介绍了continuations,以后再讨论monads和uniqueness typing。有意思的是呢,coutinuations处理强制代码以特定顺序执行之外还有其他很多出处,这些我们在后面也会提及。

本文最后更新于2016-07-07 22:31:56