你的分享就是我们的动力 ---﹥

函数式编程思想:以函数的方式思考(第2部分)

时间:2014-12-25 18:36来源:www.chengxuyuans.com 点击:
在这一文章系列的第一部分中,我一开始先讨论函数式编程的一些特征,并展示这些想法是如何在Java和其他的一些更加函数化的语言中体现出来的。在本篇文章中,我会通过谈论第一类函数(first-class function)、优化和闭包(closure)来继续我们的概念之旅。不过位于这一部分的主题之下的却是控制:你何时会希望用它,你何时会需要用它,以及你何时应该放弃用它。

第一类函数和控制


通过使用Functional Java库(参见资源一节),在上一篇文章中我使用函数式的isFactor()和factorsOf()方法来展示了一个数字分类器的实现,如清单1所示:

清单1. 数字分类器的函数式版本

import fj.F;
import fj.data.List;
import static fj.data.List.range;
import static fj.function.Integers.add;
import static java.lang.Math.round;
import static java.lang.Math.sqrt;

public class FNumberClassifier {

    public boolean isFactor(int number, int potential_factor) {
        return number % potential_factor == 0;
    }

    public List factorsOf(final int number) {
        return range(1, number+1).filter(new F() {
            public Boolean f(final Integer i) {
                return number % i == 0;
            }
        });
    }

    public int sum(List factors) {
        return factors.foldLeft(fj.function.Integers.add, 0);
    }

    public boolean isPerfect(int number) {
        return sum(factorsOf(number)) - number == number;
    }

    public boolean isAbundant(int number) {
        return sum(factorsOf(number)) - number > number;
    }

    public boolean isDeficiend(int number) {
        return sum(factorsOf(number)) - number < number;
    }
}   

 在isFactor()和factorsOf()方法中,我放弃了对框架的循环算法的控制——现在由框架来决定如何以最好的方式来遍历范围中的数据。如果框架(或者——如果选择了诸如Clojure或是Scala一类的函数式语言的话——语言)可以优化底层的实现的话,那么你会自动受益。虽然一开始的时候你可能不愿意放弃这么多的控制,但要注意到,这遵循的是编程语言和运行时(runtime)中的一个总的趋势:随着时间的推移,开发者会变得越来越抽象,会渐渐远离那些平台可以更加高效地对之加以处理的细节。我从不担心JVM上的内存管理,因为平台允许我忘记这件事。当然,这样行事的话偶尔也会使一些事情变得难办,但对于你从日常的编码中获得好处来说,做这样的取舍是没错的。函数式语言的构造,比如说高阶和第一类函数,其允许我攀上一座有更多级抽象的梯子,可以把更多的关注点放在代码做什么而不是如何做方面。

即使是使用Functional Java这一框架,在Java中使用这种风格来编写代码依然麻烦,因为该语言并未真正地具备了这样的语法和构造。在一种实现了函数式特性的语言中,函数式的代码编写看起来是什么样子的呢?

用Clojure实现的分类器

Clojure是一种为JVM设计的函数式的Lisp语言(参见资源一节)。考虑一下清单2中给出的用Clojure编写的数字分类器:

清单2. 数字分类器的Clojure实现

(ns nealford.perfectnumbers)
(use \'[clojure.contrib.import-static :only (import-static)])
(import-static java.lang.Math sqrt)

(defn is-factor? [factor number]
  (= 0 (rem number factor)))

(defn factors [number]
  (set (for [n (range 1 (inc number)) :when (is-factor? n number)] n)))

(defn sum-factors [number]
    (reduce + (factors number)))

(defn perfect? [number]
  (= number (- (sum-factors number) number)))

(defn abundant? [number]
  (< number (- (sum-factors number) number)))

(defn deficient? [number]
  (> number (- (sum-factors number) number)))

清单2中的大部分代码都很容易就能理解,就算你不是一个死忠的Lisp开发者——特别是如果你能学会从里向外的阅读方式的话。例如,is-factor?方法用到两个参数,并在number被factor相除时询问余数是否为0。同样地,perfect?、abundant?和deficient? 方法也应该很容易解读,特别是如果你以清单1中的Java实现为参考的话。

sum-factors方法使用了内置的reduce方法,sum-factors一次减少列表中的一个元素,使用的是每个元素上作为第一个参数提供的函数(在本例中是+)来实现的。reduce这一方法在一些语言和框架中以不同的面目出现;你在清单1的Functional Java版本中看到的是相应的foldLeft()方法。factors方法返回一个数字列表,所以我一次处理列表中的一个数字,把每个元素和累计的总和相加,所得的结果就是reduce的返回值。你可以看到,一旦你习惯了从高阶和第一类函数的角度来考虑问题,你就可以reduce(语带双关,消除)掉代码中不少的干扰。

factors方法可能看起来就像是随机的符号集合,不过一旦你了解了列表解析(list comprehension)的话,你就知道其中的道理了,列表解析是Clojure中几个强大的列表操纵功能之一。如前所述,最容易理解factors的方式是从内往外读。不要让有冲突的语言术语把自己搞迷糊了。Clojure中的for关键字不是表示for循环,而是要把它看作是所有的过滤和转换构造的始祖。在本例中,我要求它使用is-factor?这一断言(这就是我清单2中先一步定义的is-factor方法——注意第一类函数的大量使用)来过滤从1到(number+1)的数值范围,然后返回匹配的数字。从这一操作中返回的是一个数字列表,这些数字满足我的筛选条件,我强制把这些数字放在一个set中以去掉重复的数字。

尽管学习一门新语言是一件麻烦事,但在理解功能性语言的特点时,你也会从中收获良多。

优化

切换到函数式风格上的一个好处是能够利用语言或是框架提供的高阶函数支持,但是在我们不想放弃控制的时候该怎么办呢?在早先的例子中,我把迭代机制的内部行为比作内存管理器的内部工作:大部分时间你都会很高兴不用操心这些细节,但偶尔你也需要关心它们,比如说在进行优化或是类似的调整的时候。

在我在“以函数的方式思考,第1部分”给出的数字分类器的两个Java版本中,我优化了明确因子的那部分代码。最初的直白实现使用了取模(%)运算符,这异常的效率低下,从2开始直到目标数字本身,检查其中的每一个数字来判定其是否为一个因子。因为注意到因子是成对出现的,因此你可以优化这一算法。例如,如果你查找的是28的因子的话,那么当你找到2时,你也得到了14,如果你能成对地获得因子的话,那么你只需要以目标数字的平方根为上限值来检查因子。

这一在Java版本中很容易实现的优化在Functinal Java版本中看起来是不可能的,因为我没有直接控制迭代机制的实现。但是学习函数式思考的一部分就是需要放弃这类控制的观念,这样才能让你施加另一种观念。

我可以以函数的方式来重述最初的问题:从1到number过滤所有的因子,只保留那些符合我的isFactor()断言的因子。这就是清单3中的实现:

清单3. isFactor()方法

public List factorsOf(final int number) {
    return range(1, number+1).filter(new F() {
        public Boolean f(final Integer i) {
            return number % i == 0;
        }
    });
}

尽管从声明的角度来说,清单3的代码很优雅,但却是相当低效的,因为它对每个数字都进行了检查。一旦了解了优化做法(成对获得因子,只检查以平方根为上限的数字),我就可以这样来重述该问题:

1. 从1到目标数字的平方根过滤出该数字的所有因子。
2. 使用这些因子中的每一个来除目标数字,以此来获得对称的因子,并把它加入到因子列表中。

脑子里有了这个目标后,我就可以使用Functional Java库来写出factors()方法的优化版本了,如清单4所示:

清单4. 优化后的因子查找方法

public List factorsOfOptimzied(final int number) {
    List factors =
        range(1, (int) round(sqrt(number)+1))
        .filter(new F() {
            public Boolean f(final Integer i) {
                return number % i == 0;
            }});
    return factors.append(factors.map(new F() {
                                      public Integer f(final Integer i) {
                                          return number / i;
                                      }}))
                                      .nub();
}

清单4中的代码基于我前面陈述的算法,用到了一些Functional Java框架要求的时髦的语法。首先,我采用了从1到目标数字的平方根加1这一范围(以确保我能捕获所有的因子);接着,我像前一个版本一样基于取模运算符的用法来过滤结果;然后我把这一过滤后的列表存放在factors变量中;第四步(从内向外读),我用到了这一因子列表并执行map()函数,该函数通过针对每个元素执行我的代码块来产生一个新的列表(把每个元素都映射到一个新的值上)。我的因子清单中包含了以目标数字的平方根为上限的所有因子,我需要使用目标数字来除以每个因子以获得它的对称因子,而这就是发送给map()方法的代码块要做的事情。第五步,现在我得到了一个对称因子列表,我把它追加到最初的列表中;作为最后的一步,我必须考虑的一个实情是,我把因子存放在List而不是Set中,List方法很方便于这些类型的操作,但我的算法的一个边际效应是,当出现一个刚好是整数的平方时,列表中就会有重复的条目。例如,如果目标数字是16的话,4这一平方根整数最终就会在因子列表中出现两次。为了能够继续使用便利的List方法,我只需要在最后调用它的nub()方法来去掉所有的重复项就可以了。

仅仅是因为你在使用诸如函数式编程一类的高级抽象的时候常常要放弃实现细节中的知识并不意味着,在你必须要这样做的时候,你不能下入到细节中并使用它。Java平台为你屏蔽掉了几乎所有的底层的东西,但如果你够坚决的话,你还是可以挖出一条通向你要去的底层的地道来的。同样地,在函数式编程构造中,你通常会愿意放弃细节,把握抽象;但细节很重要时,你也保留有一些不这样做的权利。

到目前为止,在我展示的所有Functional Java代码中,看起来明显不同寻常的部分是块的语法,其用到了泛型和匿名内部类,就像是某种类型的伪代码块,闭包类型的构造。闭包是函数式语言中一种常见的功能特性,是什么让它们在这一领域中变得如此有用呢?

是什么让闭包如此特殊?


  

闭包是一种函数,该函数携有到其内部被引用的所有变量的一个隐式绑定。换句话说,该函数(或方法)封装了其引用的东西的上下文。作为函数式语言和框架中的一种可移植的执行机制,闭包经常被用来作为转换代码传递给诸如map()一类的高阶函数。Functional Java使用匿名的内部类来模仿一些“真正”的闭包行为,但它们不能完全达到闭包的效果,因为Java不支持闭包。不过这意味着什么呢?

清单5. 说明闭包的Groovy代码

def makeCounter() {
  def very_local_variable = 0
  return { return very_local_variable += 1 }
}

c1 = makeCounter()
c1()
c1()
c1()
c2 = makeCounter()

println \"C1 = ${c1()}, C2 = ${c2()}\"
// output: C1 = 4, C2 = 1

makeCounter()方法先使用一个适当的名字来定义了一个局部变量,然后返回一个使用了该变量的代码块。请注意,makeCounter()方法的返回类型是一个代码块而非一个变量。该代码块递增局部变量的值并返回该变量值后就不再做别的事情了。我在这一代码中放置了显式的return调用,在Groovy中这两个return都是可选的,不过如果没有它们的话,这段代码及越发隐秘了!

为了执行makeCounter()方法,我把这一代码块赋值给一个C1变量,然后调用它三次。我使用Groovy的语法糖来执行代码块,做法是把一对括号放在代码块变量的边上。接下来,我再次调用makeCounter(),把这一代码块的一个新实例赋值给C2。最后,和C2一起,我再次执行了C1。可以注意到,每个代码块都记录了一个单独的very_local_variable实例,这就是封装上下文的意思。尽管局部变量是在方法内部定义的,但代码块与该变量绑定了起来,因为代码块引用了该变量,这意味着代码块实例在其存活期内要记住该变量。

清单6给出了用Java能够实现的最接近同一行为的做法。

清单6. Java版本的MakeCounter

public class Counter {
    private int varField;

    public Counter(int var) {
        varField = var;
    }

    public static Counter makeCounter() {
        return new Counter(0);
    }

    public int execute() {
        return ++varField;
    }

Counter类还有可能的几种变体,但依然要卡在自己管理状态这关上。而这就说明了为什么闭包的使用体现了函数式的思维方式:允许运行时管理状态,其不是迫使你去处理域的创建和小心地对待状态(包括在多线程环境中使用代码的那种可怕情景),而是让语言或是框架在无形中为你管理状态。

我们最终会在一个即将发布的Java版本中迎来闭包(谢天谢地这一讨论不在本文范围之内),它们在Java中的出现将会带来两个受欢迎的好处。首先,它会在促进框架和库的编写者的语法的同时极大地简化他们的能力要求;其次,其会为所有运行在JVM上的语言的闭包支持提供一个低层面的公共特性。尽管许多的JVM语言都支持闭包,但它们都必须要实现自己的版本,这使得在语言之间传递闭包变得很繁琐。如果Java语言定义出了一种唯一的模式的话,那么所有其他的语言就都可以利用它。

结论


放弃对低层面细节的控制是软件开发中的大势所趋。我们很高兴能够卸下垃圾收集、内存管理和硬件差异等方面的责任。函数式编程代表了下一个抽象方面的飞跃:把更多单调乏味的细节,比如说遍历、并发和状态等尽可能地割让给运行时。这并不意味着在需要的时候你不能拿回控制权——但除非是你想要这样做,而不是被迫这样做。

在接下来的文章中,我会通过介绍局部套用(currying)和部分方法(partial method)的应用来继续探索Java及其近亲中的函数式编程构造。

资源


学习资料

1. The Productive Programmer(Neal Ford,O\'Reilly Media,2008):Neal Ford的最新著作进一步阐述了这一系列中的许多主题。

2. Monads:Monads是函数式编程语言中一个传奇式的颇为恐怖的主题,在这一系列的后续部分中会提及。

3. Scala:Scala是一种现代的、位于JVM之上的函数式语言。

4. Clojure:Clojure是一种现代的、运行在JVM上的函数式Lisp语言。

5. Podcast: Stuart Halloway on Clojure:更多地了解Clojure,关于为什么它会被迅速采用以及在普及率方面快速飙升,在这里你可以找出两个主要的原因。

6. Functional Java:Functional Java是一个框架,其为Java加入了许多的函数式语言构造。

7. “Practically Groovy: Metaprogramming with closures, ExpandoMetaClass, and categories”(Scott Davis,developerWorks,June 2009):了解Groovy中的闭包。

8. 浏览technology bookstore来查找一些关于这些和另外一些技术主题的书籍。

9. developerWorks Java technology zone:可以找到几百篇关于Java编程的各个方面的文章。

获得产品和技术

下载IBM产品评估版本或是浏览 IBM SOA Sandbox中的在线使用,动手操作DB2?, Lotus?, Rational?, Tivoli?, and WebSphere?方面的应用开发工具和中间件产品。

讨论

试一试developerWorks blogs ,加入 developerWorks社区。

关于作者


\"\"Neal Ford是一家全球性的IT咨询公司ThoughtWorks的软件架构师和Meme Wrangler。他还设计并编写了一些应用、教材、杂志文章、课件和视频/DVD演示,他是一些跨多种技术的书籍的作者或是编辑,其中包括了最近出版的这本The Productive Programmer。他的工作重点是设计和构建大型的企业级应用,他还是全球范围的开发者大会上的一位国际知名的演讲者。你可看看他的网站。

转载注明地址:http://www.chengxuyuans.com/software_design/86275.html