Category Archives: 函数式编程

函数式编程术语解析

翻译 · 原文地址

函数式编程蔚然成风,越来越多的开源项目、技术交流在使用函数式编程的术语降低开发或沟通成本,这无形中对不了解函数式编程的开发者造成了一定的学习门槛,翻译本文的初衷就是要普及函数式编程的基本知识,从新的角度扩展编程思维。至于为什么要使用 JavaScript 演示函数式编程,一方面是因为 JavaScript 的特性在很多方面与函数式编程浑然天成,另一方面是因为 JavaScript 是世界上最 XX 的语言……

Arity

指函数的参数数量,由 -ary-ity 这两个英文后缀拼接而成:

Higher-Order Functions

高阶函数,此类函数可以接收其他函数作为参数,也可以返回一个函数作为返回值:

Partial Application

偏函数,在原函数的基础上预填充(pre-filling)部分参数并返回的新函数:

JavaScript 中的 Function.prototype.bind() 函数是创建偏函数的最简单方式:

Currying

柯里化,将一个接收多个参数的函数转化为单参数函数的方式,转化后的函数每次只接收一个参数,然后返回一个新函数,新函数可以继续接收参数,直到接收到所有的参数:

Function Composition

函数合成,接收多个函数作为参数并返回一个新函数的方式,新函数按照传入的参数顺序,从右往左依次执行,前一个函数的返回值是后一个函数的输入值:

Purity

一个纯函数需要满足两个条件,第一是函数的返回值只能由输入值(函数接收的参数)决定,也就是说纯函数接收相同的参数会返回相同的值;第二是纯函数不会对自身作用域之外的运行环境产生副作用(side effects),比如说不会改变外部环境中变量的值,这会被认为是不安全的行为:

纯函数示例:

Side effects

如果函数或表达式与其自身作用域之外的可变数据(mutable data)发生了读写操作,那么此时函数和表达式就产生了副作用:

Idempotent

幂等,同一个函数使用相同的参数嵌套执行多次的结果与执行一次的结果相同:

f(f(f(x)))=f(x)f(…f(f(x))…)=f(x)

Point-Free Style

point-free style 是一种不显式向函数传递参数的代码风格,通常需要柯里化和高阶函数来实现:

point-free style 的函数看起来就像是一个赋值表达式,没有使用我们常见的 function=> 等来声明其接收的参数。

Predicate

断言,一个返回布尔值的函数:

Contracts

TODO

Guarded Functions

TODO

Categories

categories 内部都绑定了具体的函数用于约束或执行特定的逻辑,比如 Monoid。

Value

任何可以赋值给变量的值都可以称为 value:

Constant

常量,初始化后不能再次执行赋值操作的数据类型:

常量具有 referentially transparent 的特性,也就是说将程序中出现的常量替换为它们实际的值,并不会影响程序的结果。译者话外:实际上在 JavaScript 中的 const 所声明的常量并不是完全稳定的,使用 Immutable.js 演示更加恰当:

f(g()) === g

Functor

functor 都拥有 map 函数,并且在执行 map 之后会返回一个新的 functor:

JavaScript 中最常见的 functor 就是数组类型的实例:

Pointed Functor

pointed functor 都拥有 of 函数,用于接收和构建 functor。ES2015 提供了 Array.of 函数,所以数组实例就可以看成是 pointed functor:

Lift

lift 发生在你将值放入 functor 的时候,如果你将函数 lift 进了 Applicative Functor,那么就可以使用这个函数处理传递给这个 functor 的值。某些 lift 的实现拥有 lift 或 liftA2 函数,便于在 functor 上执行相关的函数:

lift 一个单参数的函数非常类似于 map 操作:

Referential Transparency

如果一个表达式可以被替换为实际的值而不影响程序的运行结果,那么我们就说这个表达式是 referentially transparent:

以上面代码为例,任何调用 greet() 的地方都可以替换为 "Hello World!" 而不影响程序的执行结果。

Equational Reasoning

如果一个应用由多个表达式组合而成,且每个表达式都没有 side effect,那么这个应用就可以由部分推导出整体。

Lambda

匿名函数,本质上是一个 value:

Lambda Calculus

数学的分支之一,使用函数创建通用的计算模型(universal model of computation)。

Lazy evaluation

惰性求值,是一种按需执行的求值策略,只有需要某个值时才会执行相关的表达式。在函数式编程语言中,这一特性可用于构造无限列表。

Monoid

Monoid,通过一个函数“合并”两个同类型数据后返回相同的数据类型。最简单的 monoid 就是两数相加:

这里的 + 就是上面所说的“合并”函数。Monoid 中存在恒等式的概念:

如果知道了一个函数的的恒等式和“合并”函数 compose,函数本身就是一个 monoid:

Monad

Monad,是一个拥有 ofchain 函数的数据类型,chain 类似于 map,但它会输出非嵌套形式的结果:

在其他函数式编程语言中,of 也被称为 returnchain 也被称为 flatmapbind

Comonad

Comonad,拥有 extractextend 函数的数据类型:

Applicative Functor

Applicative Functor,是拥有 ap 函数的数据类型,ap 函数可以将 functor 中的值转化为其他 functor 中的同类型值:

这一特性对于多个 applicative functor 需要接收多个参数时,就显得很有用:

Morphism

态射,一个转换函数。

Isomorphism

同构转换,相同数据下不同结构之间的转换。举例来说,2D 坐标既可以存储为数组 [2, 3] 也可以存储为 { x: 2, y: 3 }

Setoid

Setoid,拥有 equals 函数的数据类型,可用于与其他同类型的数据进行比较。为 Array 类型添加 equals 函数使其成为 Setoid:

Semigroup

Semigroup,拥有 concat 函数的数据类型,可以与同类型数据进行合并:

Foldable

Foldable,拥有 reduce 函数的数据类型,可以将 Foldable 的实例转换为其他数据类型:

Traversable

TODO

Type Signatures

类型签名,在 JavaScript 中通常会在注释中写明当前函数的参数类型和返回值类型,虽然各种语言的类型签名不同,但通常与以下示例相似:

如果某个函数要作为参数传递给其他函数,那么在类型签名中需要使用括号包裹起这个函数的类型信息:

上面示例中的 ab 表示参数可以是任何数据类型的,但在下面的代码中,map 的类型签名表示: f 是一个函数,f 接收一个 a 类型的参数,返回一个 b 类型的值,同时 map 是一个柯里化的函数,其第二个接收一个列表形式的 a 类型参数,并返回列表形式的 b 类型参数:

Union type

联合类型,表示将多个类型信息放入一个类型变量中。JavaScript 中没有类型机制,所以让我们假设有一个类型变量 NumOrString,它表示 Number 或者 String 类型。+ 运算符在 JavaScript 中既可用于 Number,也可用于 String,所以我们使用 NumOrString 定义 + 的输入输出类型信息:

Product type

product type 同样包含多种基本类型:

Option

Option,是 union type 的特例,它只包含两种类型 SomeNone。Option 常用于表示那些不确定是否返回值的函数:

使用 chain 函数执行链式调用可以返回具体的 Option

某些语言中使用 Maybe 表示 Option,使用 Just 表示 Some,使用 Nothing 表示 Node

from:http://pinggod.com/2016/函数式编程术语解析/

Functor, Applicative, 以及 Monad 的图片阐释

这是个简单的值:

我们都知道怎么加一个函数应用到这个值上边:

很简单了. 我们来扩展一下, 让任意的值是在一个上下文当中. 现在的情况你可以想象一个可以把值放进去的盒子:

现在你把一个函数应用到这个值的时候, 根据其上下文你会得到不同的结果. 这就是 Functor, Applicative, Monad, Arrow 之类概念的基础. Maybe 数据类型定义了两种相关的上下文:

很快我们会看到对一个 Just a 和一个 Nothing 来说函数应用有何不同. 首先我们来说 Functor!

Functor

当一个值被封装在一个上下文里, 你就不能拿普通函数来应用:

就在这里 fmap 出现了. fmap is from the street, fmap is hip to contexts. fmap 知道怎样将一个函数应用到一个带有上下文的值. 你可以对任何一个类型为 Functor 的类型使用 fmap.

比如说, 想一下你想把 (+3) 应用到 Just 2. 用 fmap:

这是在幕后所发生的:

Bam! fmap 告诉了我们那是怎么做到的!

So then you’re like, 好吧 fmap, 请应用 (+3) 到一个 Nothing?

就像 Matrix 里的 Morpheus, fmap 就是知道要做什么; 你从 Nothing 开始, 那么你再由 Nothing 结束! fmap 是禅. So now you’re all like, 准确说究竟什么是 Functor? 嗯, Functor 就是任何能用 fmap 操作的数据类型. 因此 Maybe 是个 functor. 而且我们很快会看到, list 也是 functor.

这样上下文存在就有意义了. 比如, 这是在没有 Maybe 的语言里你操作一个数据库记录的方法:

但用 Haskell:

如果 findPost 返回一条 post, 我们就通过 getPostTitle 得到了 title. 如果返回的是 Nothing, 我们加e得到 Nothing! 非常简洁, huh? <$>fmap 的中缀表达式版本, 所以你经常是会看到:

另一个例子: 当你把函数应用到 list 时发生了什么?

List 仅仅是另一种让 fmap 以不同方式应用函数的上下文!

Okay, okay, 最后一个例子: 你把一个函数应用到另一个函数时会发生什么?

这是个函数:

这是一个函数应用到另一个函数上:

结果就是又一个函数!

这就是函数复合! 就是说, f <$> g == f . g!

注意: 目前为止我们做的是将上下文当作是一个容纳值的盒子. But sometimes the box analogy wears a little thin. 特别要记住: 盒子是有效的记忆图像, 然呵又是你并没有盒子. 有时你的 “盒子” 是个函数.

Applicative

Applicative 把这带到了一个新的层次. 借助 applicative, 我们的 values 就被封装在了上下文里, 就像 Functor:

而我们的函数也被封装在了上下文里!

Yeah. Let that sink in. Applicative 并不是开玩笑. Control.Applicative 定义了 <*>, 这个函数知道怎样把封装在上下文里的函数应用到封装在上下文里的值:

也就是:

使用 <*> 能带来一些有趣的情形. 比如:

这里有一些是你能用 Applicative 做, 而无法用 Functor 做到的. 你怎么才能把需要两个参数的函数应用到两个封装的值上呢?

Applicative:

ApplicativeFunctor 推到了一边. “大腕儿用得起任意个参数的函数,” 他说. “用 <$><*> 武装之后, 我可以接受需要任何个未封装的值的函数. 然后我传进一些封装过的值, 再我就得到一个封装的值的输出! AHAHAHAHAH!”

An applicative watching a functor apply a function

一 applicative 看着一 functor 应用一函数

还有啦! 有一个叫做 liftA2 的函数也做一样的事:

Monad

如何学习 Monad:

  1. 拿个计算机科学的 PhD.
  2. 把她抛在一边, 因为这个章节里你用不到她!

Monads add a new twist.

Functor 应用函数到封装过的值:

Applicative 应用封装过的函数到封装过的值:

Monads 应用会返回封装过的值的函数到封装过的值. Monad 有个 >>= (念做 “bind”) 来做这个.

一起看个例子. Good ol’ Maybe is a monad:

Just a monad hanging out

Just a monad hanging out

假定 half 是仅对偶数可用的函数:

我们给它传入一个封装过的值会怎样?

我们要用到 >>=, 用来强推我们封装过的值到函数里去. 这是 >>= 的照片:

它怎么起作用的:

其中发生了什么?

如果你传进一个 Nothing 就更简单了:

酷! 我们来看另一个例子: 那个 IO monad:

明确的三个函数. getLine 获取用户输入而不接收参数:

readFile 接收一个字符串 (文件名) 再返回文件的内容:

putStrLn 接收一个字符串打印:

这三个函数接收一个常规的值 (或者不接收值) 返回一个封装过的值. 我们可以用 >>= 把一切串联起来!

Aw yeah! 我们不需要在取消封装和重新封装 IO monad 的值上浪费时间. >>= 为我们做了那些工作!

Haskell 还为 monad 提供了语法糖, 叫做 do 表达式:

结论

  • functor: 通过 fmap 或者 <$> 应用是函数到封装过的值
  • applicative: 通过 <*> 或者 liftA 应用封装过的函数到封装过的值
  • monads: 通过 >>= 或者 liftM 应用会返回封装过的值的函数到封装过的值

所以, 亲爱的朋友 (我想在这点上我们是朋友), 我想我们都一致认为 monad 是简单的而且是个高明的观念(tm). Now that you’ve wet your whistle on this guide, why not pull a Mel Gibson and grab the whole bottle. 看下 LYAH 上关于 Monad 的 章节. 很多东西我其实掩饰了因为 Miran 深入这方面做得很棒.

from:http://jiyinyiyong.github.io/monads-in-pictures/

http://www.ruanyifeng.com/blog/2015/07/monad.html

函数式程序设计的另类指南

函数式程序设计的另类指南

Authorized translation from the English language edition, entitled Functional Programming For The Rest of Us, by Slava Akhmechet.
Chinese simplified language version is translated by Yifan Peng. Part of the translation is from lihaitao(lihaitao@gmail.com)
Copyright (c) 2014 Yifan Peng.
All rights reserved.

本文中文简体字版由Slava Akhmechet授权。未经书面许可,请勿复制或抄袭。


目录


简介

程序员拖沓成性,每天到办公室以后,泡泡咖啡、查查邮箱、读读RSS上的回复,看看新闻,到技术网站点击一下最新的文章,然后在编程论坛的相关版面浏览公共讨论区,并不厌其烦地刷新页面,以免漏掉任何一条留言。午饭后盯着IDE没几分钟,再次检查邮箱,或者冲一杯新的咖啡。就这样不知不觉中,结束了一天。

如果你浏览的网站很对路的话,每隔几天都会发现一些很有挑战性的文章——你很难快速通读它们,于是将之束之高阁,直到有一天突然发现自己已经有了一个长长的链接列表和一个堆满了PDF文件的目录。这时你会幻想到一个人迹罕至的森林木屋,苦读一年以学会这些技术。当然,每天清晨当你沿着林中小溪散步的时候,如果有人帮你带饭、清理垃圾就更好了。

我不知道你的列表是什么,但我的列表却包含了一大堆关于函数式程序设计的文章。这些文章都很难读懂。它们用枯燥的学院派语言写成,即使“在华尔街行业浸淫十年的专家”也不能理解函数式程序设计都在探讨些什么。如果你去问花旗集团或德意志银行的项目经理1,为什么选择了JMS 而不是Erlang,他们可能会说:不能在产业级的应用中使用学院派语言。但问题是,一些最复杂、有着最严格需求的系统却是用函数式程序设计元素写成的。所以,这些说法不能让人信服。

的确,有些关于函数式程序设计的文章和论文很难理解,但它们原本并不是这么晦涩。产生隔阂的原因完全是历史性的。函数式程序设计的概念并不难理解。本文就是“简易的函数式程序设计导论”,是一座沟通命令式(imperative)思维模式和函数式程序设计的桥梁。去冲杯咖啡回来继续读下去吧。可能你的同事很快就会开始取笑你对函数式编程发表的观点了。

那么什么是函数式程序设计呢?它是怎么产生的?它可以被驾驭吗?如果它真如其倡导者所言那么有用,为什么没有在行业中得到广泛使用呢?为什么好像只有那些博士才使用它?最重要的是,为什么它就TMD这么难学?闭包(closure)、continuation、currying、惰性赋值(lazy evaluation)、no side effects business究竟是些什么东西?一个项目如果没有大学参与,能不能使用函数式语言?为什么它看上去那么不友好、不亲切?我们马上会解答这些疑问。首先让我来解释实际应用和学术文章之间,有着产生巨大隔阂的原因。其实答案简单得就像在公园散一次步。

信步游园

启动时间机器,我们来到两千多年前的一个公园里。具体时间大约是公元前380年的一个春光明媚的周日。在雅典城外的橄榄树树荫里,柏拉图(Plato)和一个英俊的奴隶小男孩正朝着学院走去。那天天气很好,晚饭也不错。他们边走边讨论一个哲学问题。

为了使问题更有教育意义,柏拉图小心地挑选着词句:“瞧这两个学生,你认为谁更高呢?”小男孩看了看那两个站在水池中的人,说,“他们俩差不多高”。柏拉图问:“你说‘差不多’是什么意思?”。“恩……我在这儿看他们是一样高的,不过我肯定如果走近些就会看出他们的差别。”

柏拉图笑着把这个孩子引向正确的思路。“那么你是说,这个世界上没有完全相同的两个东西了?”小男孩想了一会儿回答,“对。我想即使我们看不到,任何事物之间总有一些区别。”正中下怀!“那么如果这世上没有完全相同的两个东西,你怎么理解‘完全’相等这个概念呢?”小男孩有点被问住了,说:“我不知道”。

这就是我们第一次尝试理解数学的本源。柏拉图提出,世界上所有的事情都只是趋近于完美。他同时也意识到,尽管我们无法真正碰触到完美的事情,但是我们可以理解它。因此完美的数学仅存在于另一个世界中,而我们可以通过和那个世界的某种联系在一定程度上认知它。比如,虽然我们无法看到绝对完美的圆,但是我们知道什么是圆,并且能够用公式表达它。那什么是数学呢?为什么宇宙可以用数学定理来描述?数学可以描述宇宙中的所有现象吗?2

数学哲学是一个很复杂的课题。像大多数哲学学科一样,它更倾向于提出问题而不是给出答案。很多得出的共识都围绕着一个事实:数学真的是个谜。我们首先给出一些基本的、互不冲突的原理,以及一些可以操作这些原理的规则;然后我们组合这些规则生成更复杂的规则。数学家把这种方法叫做“形式系统”或“微积分”。如果愿意,我们可以很快为俄罗斯方块写出一个形式系统。实际上,一款俄罗斯方块游戏本身就是一个形式系统,只不过游戏采用了非数学的表现形式。

半人马阿尔法行星上的毛毛生物文明不能理解我们对于俄罗斯方块或者圆的范式,因为它们唯一可以感知世界的器官可能只有嗅觉。他们也许永远不会发现俄罗斯方块的范式,但很可能会有一个圆的范式。而我们也可能无法知道如何通过嗅觉描述一个圆,因为我们的嗅觉没有那么灵敏。可是一旦我们能理解那一范式的表示形式(比如通过各种传感器和标准解码技术来理解这种语言),其底层的概念就可被任何智能文明所理解。

有趣的是,即便宇宙中从没有过智能文明,俄罗斯方块和圆的范式仍然存在,只是没有人发现它们而已。如果一种智能文明出现了,他应该能发现一些形式系统来描述宇宙的规律。但他还是不大可能搞一个俄罗斯方块, 因为宇宙中再没有和它相似的东西。在现实世界中这类无用的形式系统或迷题的例子数不胜数,俄罗斯方块只是其中一个典型的例子。我们甚至不能确定自然数是否是对客观世界的完整近似。比如我们可以很容易的想出一个特别大的数字,它无法表达我们世界中的任何事物,因为我们的世界有限的,而这个数近乎无穷。

历史一瞥3

再次启动时间机器,这次我们回到二十世纪30年代。大萧条正在蹂躏着那个新旧交替的时代。空前的经济下滑影响着几乎所有阶层的家庭。只有少数人还能够保持着饥谨危机前的安逸,比如普林斯顿大学的数学家们。

歌特式的新办公室给普林斯罩上天堂般的幸福光环。来自世界各地的逻辑学家被邀请到此成立一个新学部。那时的美国人民已很难弄到一块面包,但是在普林斯顿,你可以在高高的穹顶下、精致雕凿的木质墙饰边,整日的品茶讨论,或在楼外的林荫中款款慢步。

阿隆左·丘奇(Alonzo Church)就是其中一位享受这种近于奢华的数学家。他在普林斯顿获得本科学位后被邀继续留在研究生院攻读。阿隆左认为普林斯顿的建筑过于浮华,所以他很少一边喝茶一边与人讨论数学,他也不喜欢到林中散步。他有些孤僻,因为似乎只有独自一人时,他才能以最高的效率工作。尽管如此,他仍与另一些同样居住在普林斯顿的人保持着联系,比如阿兰·图灵(Alan Turing),约翰·冯·诺依曼(John von Neumann),和库尔特·冈特(Kurt Gödel)。

这四个人都对形式系统很感兴趣。他们致力于解决抽象的数学难题,而不太留意现实的世界。这些难题的共同之处就是计算:如果计算机能有无限的计算能力,哪些问题可以被解决?哪些问题可以被自动解决?哪些问题依旧无法解决?为什么不能被解决?基于不同设计的各种计算机是否具有相同的计算能力?

通过和其它人的合作,阿隆左·丘奇提出了一个被称为lambda演算的形式系统。这个系统本质上是一种程序设计语言。它可以运行在具有无限计算能力的机器上。lambda演算由一些函数构成,这些函数的输入输出也是函数。函数用希腊字母lambda标识,因此整个形式系统也叫lambda4。通过这一形式系统,阿隆左就可以对上述诸多问题进行推理并给出结论性的答案。

在同一时间,阿兰·图灵也在进行着相似的工作。他提出了一个完全不同的形式系统(现在被称为图灵机),并使用这一系统得出了和阿隆左相似的结论。事后证明,图灵机和lambda的演算能力是等价的。

我们的故事本可到此结束。如果第二次世界大战没有在那时打响,我现在就可以歇笔,而你也可以浏览下一个页面了。那时整个世界笼罩在战争的火光和硝烟之中,美国陆军和海军大量使用炮弹。为了改进炮弹的精确度,部队雇佣了大批数学家通过计算微分方程来给出弹道发射的轨迹。很显然这项工作人力浩繁,因此人们开始着手开发各种设备来攻克这个难关。第一个解出了弹道轨迹的机器是IBM的Mark I——它重达5吨,有75万个部件,每秒可以完成三次操作。

竞争当然没有就此结束。1949年,EDVAC(Electronic Discrete Variable Automatic Computer)被推出并获得了巨大的成功。这是冯·诺依曼架构的第一个具体实现,实际上也是图灵机的第一个实现。而与此同时,阿隆左·丘奇则没有那么幸运。

二十世纪五十年代,一位MIT的教授John McCarthy(也是普林斯顿毕业生)对阿隆左·丘奇的工作产生了兴趣。1958年,他发布了Lisp语言(List Processing language)。Lisp的不同之处在于,它在冯·诺依曼计算机上实现了阿隆左·丘奇的lambda演算!很多计算机科学家开始意识到Lisp的表达能力。1973年,MIT人工智能实验室的一帮程序员开发了被称为Lisp机器的硬件,于是阿隆左的lambda演算系统终于在硬件上实现了!

函数式程序设计

函数式程序设计是对阿隆左·丘奇思想的一种实现。但并非所有的lambda演算都被实现了,因为lambda演算原本不是为有物理限制的计算机设计的。因此,函数式程序设计和面向对象程序设计一样,只是一系列理念,而不是严格的使用手册。如今有很多种函数式编程语言,它们各自采用了不同的方法。在本文中,我将使用Java来编写函数式程序,并且解释函数式语言的常用特性(的确,如果你有受虐倾向,你可以用Java写出函数式程序)。在下面几章中,我将会对Java稍作修改,以使其成为一个可用的函数式编程语言。那我们开始吧。

lambda演算被设计用来解决计算问题,所以函数式程序设计主要用于处理计算。正如它的名字那样,程序用函数来完成所有操作。函数是函数式程序设计的基本单位。它几乎无处不在。即使最简单的计算也由函数构成。甚至变量(variable)都由函数取代。在函数式编程中,变量只是表达式的别名(这样我们就不必把所有东西打在一行里)。变量是不能被更改的并且只能被赋值一次。在Java中,这意味着所有变量都要被声明为final(或C++中的const)。在函数式编程中没有非final的变量。

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

因为函数式编程中的所有变量都是final的,所以可以提出这样两个有趣的假设:(1)没有必要总是写出关键字final,(2)没有必要再把变量称为变量。那么现在我们对Java作出两个修改:(1)在我们的函数式Java中,所有变量默认都是final的,(2)我们将变量称为符号(symbol)。

现在你可能会奇怪,用我们新创造的语言还能写出复杂的程序吗?如果每个符号都是不可变(non-mutalbe)的,我们就无法改变任何事情的状态!其实事实并非如此。在阿隆左研究lambda演算时,他并不想维护某个状态,并且在未来修改它。他关注的是如何对数据进行操作(这也通常被称为“演算体(caculating stuff)”。不管怎么说,既然lambda演算已被证明与图灵机等价,命令式程序能做的事情它应该也能做。但是我们应该怎么做呢?其实函数式程序也能保存状态,只是它使用的是函数,而不是变量。函数式程序将状态保存在函数的参数中,而这些参数又保存在“栈”上。如果你想保存某个状态并且想每隔一段时间就去修改它,你可以写个递归函数。比如,我们可以写个能够翻转Java字符串的函数。记住,我们声明的每个变量默认都是final的5

1
2
3
4
5
6
7
String reverse(String arg) {
  if(arg.length == 0) {
    return arg;
  } else {
    return reverse(arg.substring(1, arg.length)) + arg.substring(0,1);
  }
}

这个函数很慢而且特别消耗内存6。它慢是因为它不停的调用自己,而它耗内存是因为它不断的分配对象。但是它确实是一个典型的函数式函数。你可能会问,怎么会有人这样写程序呢?下面就让我慢慢道来。

函数式编程的优点

你可能会认为我根本无法对上面那个变态的函数给出合理的解释。我开始学习函数式编程时,也这么想。不过事实证明我错了。有许多很好的理由来支持这样的写法,当然其中一些是主观因素。比如,有人号称函数式程序易于理解。我不会拿这些理由出来说事,因为小孩子都知道:情人眼里出西施。不过我还能找到很多客观理由。

单元测试

因为函数式编程的每一个符号都是final的,所以没有函数能产生副作用。因为你不能在某个地方修改值,也不能在一个函数中修改其作用域外别的函数使用的值(比如类成员或全局变量),所以计算(或者运行)一个函数,只能得到它的返回值,而唯一可以改变该返回值的是这个函数的参数。

对单元测试者来说,这是梦寐以求的。你可以测试程序中的每个函数,并且只关心它的输入参数。你不用理会函数的调用关系,也不用精心设置外部状态。唯一需要做的就是把需要测试的极端情况输入给函数。比起使用命令式编程,如果函数式程序中的每个函数都通过了单元测试,那么你会对整个程序的质量有更大的信心。在Java或C++中,只检查函数的返回值是不够的——我们还必须验证这个函数可能修改的外部状态。但是在函数式程序中,这种情况永远不会发生。

调试

如果一段函数式程序没有按照你所希望的那样执行,调试起来也是轻而易举。因为函数式程序中的bug与之前执行的代码无关,所以你总是可以复现遇到的问题。在命令式程序中,有些bug会时隐时现,这是由于该函数可能会依赖其他函数提供的外部状态,而那些其他的函数可能才是问题的关键。因此你必须一并检查它们。而这种调试看似和这个Bug并无直接关系。函数式程序则不同——如果一个函数的返回值错了,它永远是错的,这与你之前运行了什么代码无关。

一旦你复现了问题,寻其根源将毫不费力甚至颇有乐趣。给你的程序打个断点,然后看看栈中的情况。和命令式编程一样,你可以检查栈里每一次函数调用的参数。在命令式编程中,这是不够的,因为函数依赖于成员变量、全局变量、以及其他类的状态(这些类还可能依赖其他的成员变量、全局变量、甚至更多其他的类)。函数式程序里函数依赖于它的参数,而那些信息就在你的面前!另外,在命令式程序里,只检查一个函数的返回值不能够让你确信这个函数已经可以正常工作了。你还需要逐个检查一堆作用域外的对象来看看它们是否也处于正常的状态。而对函数式程序,你要做的所有事就是查看其返回值!

沿着堆栈检查函数的参数和返回值,只要有返回值出现问题,就进入那个函数然后一步步跟踪下去。重复这个过程,你就能发现bug的位置。

并发

函数式程序就是为并发而生的。因为用不到锁(lock),所以永远不必担心死锁和竞争条件(race condition)。在函数式程序中,没有任何数据会被同一个线程修改两次,更不用说被两个不同的线程修改了。这意味着你可以不假思索地添加线程而不用担心困扰并发程序设计的常见问题。

如果这样,那么为什么没有人在大型并发应用中运用函数式编程呢?其实是有的。爱立信公司设计了一种函数式语言(Erlang)[http://www.erlang.org/],用于需要极高抗错性和可扩展性的电话交换机上。其他公司也意识到了Erlang的优势,并开始使用它。我们所说的程控交换和电信通信控制系统,需要比传统的华尔街系统更易扩展和可靠。实际上,Erlang系统并不具有很高的扩展性和可靠性——Java系统才是——但是Erlang系统坚如磐石。

并发的故事并未就此结束。即使你的程序本身就是单线程的,函数式程序的编译器仍然可以对其进行优化,使其运行于多个CPU上。来看下面这段代码。

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

在函数式编程中,编译器可以对代码进行分析,发现生成字符串s1s2的函数可能非常耗时,于是对其并行运行。这种情况在命令式语言中是不可能出现的,因为每一个函数都有可能修改外部状态,而后续函数有可能依赖这些外部状态。在函数式语言里,自动分析哪些函数可以并发执行就像自动内联一样简单。从这个意义上说,具有函数式风格的程序是“不会过时的技术(future proof)”(尽管我很讨厌流行用语,但这回也要破例使用一次)。硬件厂商已经无法让CPU运行得更快了。他们只能靠增加内核数量,用并发来成倍的提高速度。当然他们没有提醒我们,只有当处理并发问题的时候,我们花的钱才会物有所值。命令式程序中只有很小一部分是可以并发的,但是在函数式程序中,所有函数天生都是可并发的。

代码热部署

过去,如果要在Windows上安装更新,就必须不断地重启计算机。即使只是安装了一款新版媒体播放器,也必须重启。Windows XP大大改进了这个问题,但仍不理想(今天工作的时候,我运行了一下Windows Update,结果除非我重启系统,那个烦人的图标会一直出现在我的系统托盘上)。Unix系统一直以来有一个更好的架构:安装更新时只需停止与其相关的组件,而不是整个操作系统。即使如此,对于大型的服务器应用程序来说,这仍旧无法让人接受。程控交换系统需要100%的时间都在运行。因为如果由于升级而无法接通紧急电话,那很可能会要人命的。同样,华尔街的公司也没有理由必须在周末暂停系统来更新软件。

理想的情况是,在完全不停止系统任何组件的情况下来更新相关的代码。在命令式程序的世界里,这是不可能的。想想在Java运行过程中卸载一个类并且加载一个新的类。即使我们真的可以这样做,这个类的所有实例也都不能用了,因为这个类的状态丢失了。我们需要复杂的版本控制代码来恢复这些状态:需要把运行中实例的都序列化,销毁它们,用新的类创建新的实例,最后载入先前被序列化的数据,并祈祷着加载代码确实能将数据迁移到新的实例中。更痛苦的是,每一次改变代码的时候,我们都必须手动编写这些迁移程序。这些迁移代码不仅要迁移实例,而且还不能破坏对象间的关系。这些听来理论上可行,但实践起来可不容易。

在函数式程序中,所有的状态都存储在栈中,并且通过参数传递给函数。这使得热部署轻而易举!实际上,我们需要做的只是比较一下工作中的代码和新版本的代码,然后部署变化的部分。剩下的工作将由一个语言工具自动完成!如果你觉得这是科幻小说,我建议你再想想。这么多年来,Erlang工程师始终在运转着的系统上直接升级

机器辅助证明和优化

函数式语言的一个有趣的特性就是它们可以用数学方式进行推理。因为函数式语言只是一个形式系统的实现,所以只要是这个形式系统能够完成的数学运算(即使只是写在纸上),用其函数式语言也可以完成。举个例子来说,编译器可以把一段代码转变成另一段运行结果相同但是更高效的代码,然后在数学上证明二者是等价的7。多年来关系数据库一直在进行着类似的优化。没有理由说这种技术无法应用在常规软件上。

另外,你可以通过这些技术来证明你的一部分程序理论上是正确的。甚至可以写一个工具来分析代码并自动生成单元测试的边界用例!这个功能对于需要设计一个坚如磐石的系统来说是无价的。如果你要设计一个心脏起搏器或者交通控制系统,这种代码分析工具是必不可少的。即便你的程序不是这样人命关天,这些工具也是你击败竞争对手的杀手锏。

高阶函数

我记得即使在了解了上面种种优点之后,自己旧会想“恩,这些的确不错,但是如果让我在一个什么都是final的语言中编程的话,我宁可不用它。”其实你误解了我的意思。将所有变量都声明为final确实显得蹩脚,但是只有在像Java这样的命令式语言中,才会如此;在函数式语言中则不会。函数式语言提供了不同的抽象工具来让你忘记你曾经习惯于修改变量。高级函数就是这样一种工具。

函数式语言中的函数不同于Java或C中的函数。除了Java能做的事,它的功能更宽泛。因此函数式语言中的函数是Java或C中函数的超集。我们模仿C语言来定义一个函数:

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

与C语言代码不同,现在我们扩展Java编译器使其支持这种记法。当我们输入上述代码后,编译器会把它转换成下面的Java代码(别忘了,所有变量都是 final 的):

1
2
3
4
5
6
7
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中把一个类作为参数传递给另一个类,以实现类之间的操作没有任何区别。类似第一级类对象,我们把包含高阶函数的类叫做高阶类。其实没有人关心这个名字,因为Java背后没有一个强大的学术社区。

那么应该在什么时候使用高阶函数呢?又怎么用呢?我很高兴你会问到这个问题。在写一大堆代码的时候不考虑任何类层次结构。当遇到重复的代码时,把重复的部分提取成函数(幸运的是现在学校还在教这个)。当看到函数中的一段逻辑会在不同的状况下有不同的行为时,就把这个逻辑片段提取成高阶函数。有点晕?下面是我工作中遇到的一个例子。

假设有一段Java代码,它接收一段信息,将其以多种方式转换,然后转发至其他服务器上。

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

现在想象一下,我们要将信息转发至两个服务器。除了第二台服务器需要另一种格式的client code外,其他一切都不变。我们应该怎么办?可以根据要转发到哪台服务器来修改client code的格式,比如

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

但是这种方法不备可扩展性。如果更多的服务器加入,这个函数的长度将线性地增长。再更新代码时就会变得很麻烦。采用面向对象的方法,我们会定义一个父类MessageHandler,然后在派生类中具体实现生成client code的操作:

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

现在我们可以对每一个服务器实例化一个合适的类。添加服务器的操作变得容易维护了。但对于如此简单的修改却需要添加大量的代码。为了支持不同的client code,我们创建了两个新的类型!下面用我们修改过的、支持高阶函数的语言来实现同样的功能:

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

我们没有建立新的类型与类层次构,而只是把适当的函数作为参数传入,就完成了与面向对象一样的功能。这个方案有很多优势。我们不再局限于类的层次结构中:我们可以在运行时传入新的函数,并且随时以更少的代码更大的粒度修改它们:我们的编译器能够自动高效地生成面向对象的代码(将函数转换为函数类)。并且我们获得了函数式编程的所有好处。当然函数式语言提供的抽象性远不止于此,高阶函数仅仅是个开始。

Currying

我认识的很多人都读过四人帮(GOF)的《设计模式》。任何自恋的程序员都会告诉你,这本书中讨论的模式在软件工程中具有通用性,它和使用哪门语言无关。这个说法显得颇为高深,但是有违现实。

函数式编程极具表达能力。你不需要在函数式语言中使用设计模式,因为这种高级程序设计语言可以让你只进行概念编程,从而不再需要设计模式。适配器(Adapter)模式就是这样的一个例子(适配器和外观模式(Facade)有什么区别?某人可能需要在这里高谈扩论了)。一旦语言有了叫作currying的技术,我们就不再需要适配器模式了。

适配器模式最有名的应用是Java的“默认”抽象单元——类。在函数式编程里,这个模式被应用到函数上。适配器模式将一个接口转换为另一个接口。这里有一个适配器模式的例子:

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

上面的代码把一个整数幂运算接口转换成为了一个平方接口。在学术圈中,这样的用法被称之为currying(得名于逻辑学家Haskell Curry,他曾将相关的数学理论形式化)。因为在函数式编程中,函数——而不是类——作为参数进行传递,因此可以用currying把函数适配到其他接口。又因为函数的接口就是其参数列表,所以currying可以减少参数的数量(如上例所示)。

因为函数式语言内建了这一技术,所以不用手动地创建一个包装了原函数的类。函数式语言会为你代劳。和之前一样,我们来扩展一下我们的语言来支持这个技术:

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

编译器会自动为我们创建一个只有一个参数的square函数。它会在第二个参数为2的情况下调用pow函数。这段代码会编译成如下Java代码:

1
2
3
4
5
6
class square_function_t {
  int