函数式编程的另类指南(8)

By | November 4, 2013

The following part is not maintained anymore. Please go to 函数式程序设计的另类指南 for the whole translation.

以下内容不再更新,浏览全部翻译,请访问 函数式程序设计的另类指南


原文链接:Functional Programming For The Rest of Us
原文作者:Vyacheslav Akhmechet

惰性求值

当我们采用函数式哲学以后,就可以使用惰性(或延迟)求值这一技术。在并发一节,我们已经看过如下代码:

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

在一个命令式语言中,求值的顺序一目了然。因为每个函数都有可能改变外部状态,所以执行顺序必须首先是somewhatLongOperation1,然后somewhatLongOperation2,最后是concatenate。在函数式语言中,则不一定非要按照这个顺序。

我们之前讲到,如果没有函数会修改或依赖于全局变量,那么somewhatLongOperation1和somewhatLongOperation2就可以并发执行。但如果我们不想并发执行它们,就必须顺序执行它们么?不一定。只有当另一个函数需要s1和s2的时候,我们才会执行这两个函数。因此在concatenate被调用之前,我们不需要执行它们——我们甚至可以将它们的求值延迟到concatenate函数中实际用到它们的位置。如果我们将concatenate替换成另外一个函数,而这个函数带有一个条件分支。如果该分支每次只会使用两个参数中的一个,。那么我们可能永远没有必要对另一个参数求值。Haskell就是这样一门支持惰性求值的语言。Haskell不能保证每一行代码都会被按顺序执行,甚至不能保证所有代码都会被执行。这是因为只有当一段代码在需要使用的时候,Haskell才会运行那段代码。

惰性求值有利有弊。我们先来说说优点,然后再讨论如何克服缺点。

优化

惰性求值具有巨大的优化潜力。惰性编译器对待函数式代码就像数学家对待代数方程式一样:一些部分可以被约分从而不必执行,一些部分的顺序可以进行调整以提升效率,代码甚至可以被重整以降低错误。所有这些优化都能确保不会破坏代码原本的逻辑。这就是严格使用形式系统来表达程序的最大好处——代码依附于数学定律,因此可以用数学进行推理。

抽象控制结构

惰性求值提供了更高一级的抽象。这种抽象使得一些原来不可能的操作变得可行。比如下面这个控制结构:

unless(stock.isEuropean()) {
  sendToSEC(stock);
}

我们希望只有在stock为European的情况下才执行sendToSEC。那么应该如何实现unless?如果没有惰性求值,我们需要某种形式的宏。但是在像Haskell这样的语言中,则没必要这样做。我们可以将unless实现为一个函数:

void unless(boolean condition, List code) {
  if(!condition)
    code;
}

请注意,当分支条件是true的时候,code永远不会被执行。在执行顺序严格的语言中这样的代码是无法实现的,因为在unless调用之前,参数code已经被运行了。

无限的数据结构

惰性求值允许定义无限的数据结构。在执行顺序严格的语言中,这是很难实现的。比如一个Fibonacci数列。显然我们无法在有限的时间内计算出一个无穷列表,也不能在有限的内存里保存这个列表。Java只能定义一个Fibonacci函数来返回Fibonacci数列中某个指定位置的元素。但是Haskell可以将它抽象为一个无限的Fibonacci数列。因为该语言具有延迟的特性,所以这个数列中只有实际被用到的部分才会被求值。总之,惰性求值使我们可以抽象出许多问题,并从一个更高的层面来审视它们。(例如,我们可以在一个无穷列表上使用表处理函数)。

缺点

当然天下没有免费的午餐。惰性求值也有一些缺点。最大的问题其实就是“惰性”。许多现实问题都需要严格按顺序执行。例如下面这段代码:

System.out.println(”Please enter your name: “);
System.in.readLine();

惰性求值语言无法保证第一行会比第二行先执行!这意味着我们没法做IO操作,没法以任何有用的方式调用本地接口(因为它们相互依赖,所以必须被顺序执行),也没法与外界交互!如果引入允许顺序执行的特性,我们又将失去能够用数学进行代码推理的好处(并为此葬送与其相关的函数式编程的所有优点)。幸运的是,不是所有优点都没了。数学家们找到了许多技巧来保证,在一定函数设置下,代码可以按顺序执行。这样我们就赢得了两个世界。这些技巧包括:continuations,monads,还有uniqueness typing。在这篇文章中,我们只会讨论continuations。monads和uniqueness typing只能留到以后讨论。有趣的是,continuations除了能让代码以特定的顺序执行以外,还有很多其他优点。这点等一会儿就会提到。

Leave a Reply

Your email address will not be published. Required fields are marked *