函数式编程初探

作者: 阮一峰

日期: 2012年4月 6日

诞生50多年之后,函数式编程(functional programming)开始获得越来越多的关注。

不仅最古老的函数式语言Lisp重获青春,而且新的函数式语言层出不穷,比如Erlang、clojure、Scala、F#等等。目前最当红的Python、Ruby、Javascript,对函数式编程的支持都很强,就连老牌的面向对象的Java、面向过程的PHP,都忙不迭地加入对匿名函数的支持。越来越多的迹象表明,函数式编程已经不再是学术界的最爱,开始大踏步地在业界投入实用。

也许继"面向对象编程"之后,"函数式编程"会成为下一个编程的主流范式(paradigm)。未来的程序员恐怕或多或少都必须懂一点。

但是,"函数式编程"看上去比较难,缺乏通俗的入门教程,各种介绍文章都充斥着数学符号和专用术语,让人读了如坠云雾。就连最基本的问题"什么是函数式编程",网上都搜不到易懂的回答。

下面是我的"函数式编程"学习笔记,分享出来,与大家一起探讨。内容不涉及数学(我也不懂Lambda Calculus),也不涉及高级特性(比如lazy evaluationcurrying),只求尽量简单通俗地整理和表达,我现在所理解的"函数式编程"以及它的意义。

我主要参考了Slava Akhmechet的"Functional Programming For The Rest of Us"

一、定义

简单说,"函数式编程"是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。

它属于"结构化编程"的一种,主要思想是把运算过程尽量写成一系列嵌套的函数调用。举例来说,现在有这样一个数学表达式:

  (1 + 2) * 3 - 4

传统的过程式编程,可能这样写:

  var a = 1 + 2;

  var b = a * 3;

  var c = b - 4;

函数式编程要求使用函数,我们可以把运算过程定义为不同的函数,然后写成下面这样:

  var result = subtract(multiply(add(1,2), 3), 4);

这就是函数式编程。

二、特点

函数式编程具有五个鲜明的特点。

1. 函数是"第一等公民"

所谓"第一等公民"(first class),指的是函数与其他数据类型一样,处于平等地位,可以赋值给其他变量,也可以作为参数,传入另一个函数,或者作为别的函数的返回值。

举例来说,下面代码中的print变量就是一个函数,可以作为另一个函数的参数。

  var print = function(i){ console.log(i);};

  [1,2,3].forEach(print);

2. 只用"表达式",不用"语句"

"表达式"(expression)是一个单纯的运算过程,总是有返回值;"语句"(statement)是执行某种操作,没有返回值。函数式编程要求,只使用表达式,不使用语句。也就是说,每一步都是单纯的运算,而且都有返回值。

原因是函数式编程的开发动机,一开始就是为了处理运算(computation),不考虑系统的读写(I/O)。"语句"属于对系统的读写操作,所以就被排斥在外。

当然,实际应用中,不做I/O是不可能的。因此,编程过程中,函数式编程只要求把I/O限制到最小,不要有不必要的读写行为,保持计算过程的单纯性。

3. 没有"副作用"

所谓"副作用"(side effect),指的是函数内部与外部互动(最典型的情况,就是修改全局变量的值),产生运算以外的其他结果。

函数式编程强调没有"副作用",意味着函数要保持独立,所有功能就是返回一个新的值,没有其他行为,尤其是不得修改外部变量的值。

4. 不修改状态

上一点已经提到,函数式编程只是返回新的值,不修改系统变量。因此,不修改变量,也是它的一个重要特点。

在其他类型的语言中,变量往往用来保存"状态"(state)。不修改变量,意味着状态不能保存在变量中。函数式编程使用参数保存状态,最好的例子就是递归。下面的代码是一个将字符串逆序排列的函数,它演示了不同的参数如何决定了运算所处的"状态"。

  function reverse(string) {

    if(string.length == 0) {

      return string;

    } else {

      return reverse(string.substring(1, string.length)) + string.substring(0, 1);

    }

  }

由于使用了递归,函数式语言的运行速度比较慢,这是它长期不能在业界推广的主要原因。

5. 引用透明

引用透明(Referential transparency),指的是函数的运行不依赖于外部变量或"状态",只依赖于输入的参数,任何时候只要参数相同,引用函数所得到的返回值总是相同的。

有了前面的第三点和第四点,这点是很显然的。其他类型的语言,函数的返回值往往与系统状态有关,不同的状态之下,返回值是不一样的。这就叫"引用不透明",很不利于观察和理解程序的行为。

三、意义

函数式编程到底有什么好处,为什么会变得越来越流行?

1. 代码简洁,开发快速

函数式编程大量使用函数,减少了代码的重复,因此程序比较短,开发速度较快。

Paul Graham在《黑客与画家》一书中写道:同样功能的程序,极端情况下,Lisp代码的长度可能是C代码的二十分之一。

如果程序员每天所写的代码行数基本相同,这就意味着,"C语言需要一年时间完成开发某个功能,Lisp语言只需要不到三星期。反过来说,如果某个新功能,Lisp语言完成开发需要三个月,C语言需要写五年。"当然,这样的对比故意夸大了差异,但是"在一个高度竞争的市场中,即使开发速度只相差两三倍,也足以使得你永远处在落后的位置。"

2. 接近自然语言,易于理解

函数式编程的自由度很高,可以写出很接近自然语言的代码。

前文曾经将表达式(1 + 2) * 3 - 4,写成函数式语言:

  subtract(multiply(add(1,2), 3), 4)

对它进行变形,不难得到另一种写法:

  add(1,2).multiply(3).subtract(4)

这基本就是自然语言的表达了。再看下面的代码,大家应该一眼就能明白它的意思吧:

  merge([1,2],[3,4]).sort().search("2")

因此,函数式编程的代码更容易理解。

3. 更方便的代码管理

函数式编程不依赖、也不会改变外界的状态,只要给定输入参数,返回的结果必定相同。因此,每一个函数都可以被看做独立单元,很有利于进行单元测试(unit testing)和除错(debugging),以及模块化组合。

4. 易于"并发编程"

函数式编程不需要考虑"死锁"(deadlock),因为它不修改变量,所以根本不存在"锁"线程的问题。不必担心一个线程的数据,被另一个线程修改,所以可以很放心地把工作分摊到多个线程,部署"并发编程"(concurrency)。

请看下面的代码:

  var s1 = Op1();

  var s2 = Op2();

  var s3 = concat(s1, s2);

由于s1和s2互不干扰,不会修改变量,谁先执行是无所谓的,所以可以放心地增加线程,把它们分配在两个线程上完成。其他类型的语言就做不到这一点,因为s1可能会修改系统状态,而s2可能会用到这些状态,所以必须保证s2在s1之后运行,自然也就不能部署到其他线程上了。

多核CPU是将来的潮流,所以函数式编程的这个特性非常重要。

5. 代码的热升级

函数式编程没有副作用,只要保证接口不变,内部实现是外部无关的。所以,可以在运行状态下直接升级代码,不需要重启,也不需要停机。Erlang语言早就证明了这一点,它是瑞典爱立信公司为了管理电话系统而开发的,电话系统的升级当然是不能停机的。

(完)

珠峰培训

简寻

留言(60条)

热升级还真不是那么回事。不是所有 Erlang 代码都能热升级的。任何运行着对外提供有用的功能的系统,内部状态数量再少,也不可能是0。热升级的关键是把当前系统的状态从旧代码的能处理的格式转换成新代码能处理的格式。所以比较理想的处理方法是,不同的 Object 只用消息交互,而不是用直接调用对应 Object 的方法来模拟消息。这样,你只要发一个消息给要更新代码的 Object ,这个 Object 收到消息后,先转换内部状态,再用新的代码替换掉旧的代码,就完成了热更新。这也就是你按照 OTP 风格写应用时,总是需要实现一个 code_change 的函数,用来转换状态。热更新的根本上说是要正确实现 OO ,而不是函数式,不是无副作用(或者说程序总是通过副作用来提供功能的)。Erlang无非就是建立了 OTP 风格,把内部状态(也就是所谓的副作用)隔离起来,在代码更新的时候,容易处理一点,且一个 Object 更新不会影响到别的 Object 而已。

「函数式语言的运行速度比较慢」,据说 Haskell 的运行速度与 C++ 相当呢。

cool
读了阮哥翻译的《黑客与画家》才认识到Lisp威力有多大
既然阮哥已经开始学习函数式编程了,干脆把Paul Graham的所有巨著都翻了吧,呵呵
http://paulgraham.com/

推荐阮哥翻翻,SICP,译的相当好。最近有本中文的Lisp译著出版了。

引用依云的发言:

「函数式语言的运行速度比较慢」,据说 Haskell 的运行速度与 C++ 相当呢。

应该说的是递归速度慢。

递归都慢.所以常将递归改写为尾递归.然后编译器优化.将尾递归转化为迭代.

为什么3.2也列到函数式语言的优点里啊……明明只是一种fluent风格,最普遍的比如C++的cout << xxx << yyy << zzz

引用Shiina Luce的发言:

为什么3.2也列到函数式语言的优点里啊……明明只是一种fluent风格,最普遍的比如C++的cout

所謂接近自然語言應該是指 point-free style :
http://en.wikipedia.org/wiki/Point-free_style

即是運算過程不使用中間變數。

進一步的特色:
http://en.wikipedia.org/wiki/Concatenative_programming_language

好處是語法高度反映語義。

“它属于"结构化编程"的一种,主要思想是把运算过程尽量写成一系列嵌套的函数调用”,阮哥,这是谬误吧……这概念错了啊

这个博客的比较漂亮,模板可以共享吗?

同求阮哥多多翻译paul graham文章。

语义化对linq程序员表示毫无压力

其实我觉得数学已经开始真正地在很多行业流行起来了 :)

你看那些搞互联网的人,动不动就各种多元分析方法从嘴里冒出来,各种分析软件动不动就摆弄胰一下,条件熵啊互信息啊不少人都开始熟悉了,甚至各种预测方法都被挖出来尝试着研究用户行为。。。

对编程语言,更不在话下了。

这篇博客有点误导,只抓住了“函数“这个表面的特点,本质的地方没有体现出来

我想说的是这篇文章的质量不是很高,博主的对于函数式编程的概念不是很准确。
比如刚才那个merge(**).sort().***那个表达式,这跟函数式编程无关。

引用一回的发言:

应该说的是递归速度慢。



在erlang的官方文档的efficiency guid有说,现在erlang的递归,尾递归已经优化到差不多了,并且基于不用的硬件平台,递归可以比尾递归更快。

这个博客用什么搭建的,很不错!

if(string.length == 0) {
   return string;
} else {
   return reverse(string.substring(1, string.length)) + string.substring(0, 1);
}

其中string.length == 0是不是应该为string.length ==1呢?

其实未必的. 比如 (1 + 2) * 3 - 4 在 scheme 里面的写法是:
(- ( * ( + 1 2) 3) 4)
并不比原来更容易看.

函数式语言对开发者的要求比较高, 学习曲线比较陡, 像 C 语言学习了一段时间后写出来的程序就像模像样的了, 而函数式语言则很容易因为其灵活的语法控制不好程序的结构

最近在学习Mathematica,发现它的语法几乎就是函数式编程的语法。
而且如文中所说,函数式编程效率不是一般的高。

这里有一篇文章,作者用Mathematica和MATLAB分别处理同一个问题需要的代码量迥异:
http://blog.wolfram.com/2007/07/09/always-the-right-time-for-mathematica/

引用与非的发言:

最近在学习Mathematica,发现它的语法几乎就是函数式编程的语法。

Mathematica和Matlab绝非函数式编程。

Beekka这网站竟然挂了,好多博文配图都没了,好可惜。

“如果程序员每天所写的代码行数基本相同”,这句话成立的前提是“程序员编写代码的速度瓶颈在于打字速度”,这显然是在搞笑,我有理由相信,就算完成相同的功能,C代码量20倍与Lisp,那么使用两种语言开发完成的时间其实是几乎相同的。

lisp主要的问题在于周边库,lib没有,什么都需要自己开发,蛋疼.譬如网络io等...
目前纯粹的语言没有什么好讨论...
实现效率和成本是关键.

引用AnLuoRidge的发言:

Beekka这网站竟然挂了,好多博文配图都没了,好可惜。

额,原来只是暂时的……

这里也有一篇函数式编程的介绍.
楼主可以加上这个连接,这样的好文应该让更多的人看到.

http://erlang-china.org/study/yet-another-pf-guide.html

现在真正流行的原因, 我想不是文章中写的, 而是异步回调算法的流行.
C++, JAVA, PHP等等这些都引入了Lambda和闭包, 也都是为了方便的实现这个算法.

引用sokoban的发言:

这篇博客有点误导,只抓住了“函数“这个表面的特点,本质的地方没有体现出来

同意。

Lambda、闭包、惰性求值和Currying真的不算什么函数式编程的“高级特性”,倒不如说这些才是函数式编程的精髓所在。这篇文章竟然把本质的东西全部略过不提

由于使用了递归,函数式语言的运行速度比较慢,这是它长期不能在业界推广的主要原因。

这句话压根就是在误人啊。
静态类型并且支持编译器尾递归优化的函数式语言(ML、Haskell),效率有的时候甚至可以接近C。
而且,如果运行速度慢可以作为判断一种语言能不能推广的标准的话,那Perl、Python和Ruby这些动态类型语言还怎么在业界混下去?

function reverse(string) {

    if(string.length == 0) {

      return string;

    } else {

      return reverse(string.substring(1, string.length)) + string.substring(0, 1);

    }

  }
如果没理解错的话,这里返回条件if(string.length == 0)不正确。会不会死循环?

haskell不错的,不见楼主提及呢。静态化的语言不断引入动态特性,FP,而动态语言性能问题迟迟得不到解决,有点尴尬呀。

都在扯淡,翻译时都不理解内容,没有实践过,翻译内容都是广告用语。误导大部分“观众”,当然这里有些工程人员“观众”的技术水平确实还有待提高,自己不理解也要跟风

引用sokoban的发言:

这篇博客有点误导,只抓住了“函数“这个表面的特点,本质的地方没有体现出来

的确如此,可惜没有评分系统,不然这篇文章一定要大幅扣分。

大家别只顾着批评,本文标题最后两个字可是「初探」呀。

----------------------------------
对它进行变形,不难得到另一种写法:

  add(1,2).multiply(3).subtract(4)

------------------------------------
我看到这句话,想到了如果类里面的函数返回this对象,那就可以实现这个功能,不知道是不是这个意思

http://blog.sina.com.cn/s/blog_ac9074a201017yf7.html

俺的问题源自这里 http://stackoverflow.com/questions/12886036/deep-copying-a-graph-structure (那个已接受答案)。

请问,如何以pure functional programming方式维持public Node deepCopy(Map<Node, Node> isomorphism)中的isomorphism参数?最好邮件回复俺,谢谢。

引用Mead Lai的发言:

lisp主要的问题在于周边库,lib没有,什么都需要自己开发,蛋疼.譬如网络io等...
目前纯粹的语言没有什么好讨论...
实现效率和成本是关键.

所以其实《黑客与画家》里面Paul只负责写Viaweb的后台模板部分。前台和管理部分是C++等写的。

Haskell要开始在业界推广了,Simon Peyton-Jones等人成立了FP complete公司推广haskell,而且要出haskell的IDE。

另外lz下面的例子
----------------------------------
对它进行变形,不难得到另一种写法:

  add(1,2).multiply(3).subtract(4)

------------------------------------
用函数式的方式是:
flip (-) 4 ((*3) (1+2))
这里需要flip函数的原因是"-"这个符号有歧义。
或者按lz的原意是:
subtract (multiply (add 1 2) 3) 4

引用sokoban的发言:

Mathematica和Matlab绝非函数式编程。

Matlab不是函数式语言,Mathematica可不一样的(至少支持11种编程范式),没了解清楚之前,话不要说那么满
http://zh.wikipedia.org/wiki/%E5%87%BD%E6%95%B8%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80

http://www.oschina.net/translate/scala-expressiveness

http://en.wikipedia.org/wiki/List_of_multi-paradigm_programming_languages

引用sokoban的发言:

Mathematica和Matlab绝非函数式编程。

Mathematica不是纯函数式语言(haskell那种),但确实是函数式语言。Mathematica对函数式编程的支持是主流的数学软件中最好的。
可以参考Mathematica中的这些函数:Function、Map、MapThread、Scan、Apply、Fold、Nest、FixedPoint、Select、InverseFunction、Composition、Identity、Operate、Through……

如何将LZ说的
subtract(multiply(add(1,2), 3), 4)
优化成
add(1,2).multiply(3).subtract(4)

PS:不污染window对象,不用function的prototype进行扩展。

引用sokoban的发言:

Mathematica和Matlab绝非函数式编程。

Matlab当然不是,但是Mathematica还是强调函数式编程的,看那些精短的例子就知道了,很多问题可以一句话解决,就是一直套用函数,但是有时会出现性能问题,不过节省人的时间.

引用levi的发言:

的确如此,可惜没有评分系统,不然这篇文章一定要大幅扣分。

作者说了,也是初学,总结出自己认为的函数式编程是什么。有不足,在评论点出来让大家知道就好了。如果有时间也可以写一个文章更全面的来介绍,我觉得这样比单纯的批评好一些。

Java也支持函数式编程,比如:
StringUtils.capitalize(StringUtils.lowerCase(StringUtils.trim("abc")));

函数式编程的确很适合多核,再也不用考虑并发导致的蛋疼的并发问题了。

博客只是作者学习的记录,自己的认识,没规定要达到什么水平吧?
虽然不知有些理解是否正确,反正我是收获了很多,了解到不少新知识,谢谢博主。

难怪中国搞不出OS.CPU。计算机不只是数学,是工科,说白了就是“干活干活”。现在都流行发论文、并且带点数学公式的论文貌似更牛逼。
除了计算机,也有不少经管类专业喜欢玩弄“数学”。。。

最近在学习函数式编程,看了作者的学习心得,颇有收获,感谢

merge([1,2],[3,4]).sort().search("2")这个是什么意思?没看懂

谢谢楼主分享!

写成函数式方式,其中某个程序报错了,排错和捕捉异常不方便 这应该算是它的一个小缺点吧

引用stephen的发言:

“如果程序员每天所写的代码行数基本相同”,这句话成立的前提是“程序员编写代码的速度瓶颈在于打字速度”,这显然是在搞笑,我有理由相信,就算完成相同的功能,C代码量20倍与Lisp,那么使用两种语言开发完成的时间其实是几乎相同的。

非常赞同,写代码只是一部分

太酷了,多谢解惑!

浅显易懂,多谢分享

引用climber的发言:

merge([1,2],[3,4]).sort().search("2")这个是什么意思?没看懂

就是字面上的意思了,合并,然后排序,接着搜索。

引用yansha的发言:

function reverse(string) {

    if(string.length == 0) {

      return string;

    } else {

      return reverse(string.substring(1, string.length)) + string.substring(0, 1);

    }

  }
如果没理解错的话,这里返回条件if(string.length == 0)不正确。会不会死循环?

同意啊 看了半天 觉得永远出不来啊

引用a的发言:

同意啊 看了半天 觉得永远出不来啊

会不会死循环自己去试一下就知道了。js基础啊。

c语言的代码长是因为它没有提供足够的抽象,跟过程不过程没关系。拿matlab跟lisp比比,也没那么夸张吧。

此外,执行方式比起复杂度或者其他东西更占主要原因。你好意思拿个脚本语言和编译语言比嘛?

感谢编写如此通俗易懂的入门教程,点赞

函数式编程都用英语单词作为函数名的吗?
那英语不好或不会的人岂不是就是望洋兴叹?!

我用汉语拼音表示可否?

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接