Jan Fan     About     Archive     Feed     English Blog

函数式编程(Functional Programming)简介

身边的朋友对函数式编程接触得比较少,而我的毕设正好又与它相关,于是便想写一篇文章来介绍一下什么是函数式编程(Functional Programming)。

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

先剧透一下,函数式编程最重要的是两点:

What is the essence of functional programming: is it equational reasoning(no side effect) or is it higher-order functions? There is no clear agreement about the answer to this question.

程序的状态

要解释函数式编程,就必须要明白它与我们平时使惯了的命令式编程(imperative programming)相比,差别在哪里。

首先要意识到,我们的程序是拥有“状态”的。 想一想我们调试C++程序的时候,经常会在某处设置一个断点。程序执行断点就暂停了,也就是说程序停留在了某一个状态上。

state

这个状态是由什么决定的? 这个状态首先包括了当前定义的全部变量。 比如使用过Matlab、R之类的科学计算语言的朋友会知道,在退出程序的时候它会让你选择是否要保存当前的session,如果保存了,下次打开时候它会从这个session开始继续执行,而不是清空一切重来。你之前定义了一个变量x = 1,现在这个x还在那里,值也没变。 扩展到通用型的编程语言,比如C/C++,这些程序的状态还要包括一些当前系统的状态,比如打开的文件、网络的连接、申请的内存等等。

为什么要先讲状态?因为有了状态,我们的程序才能不断往前推进。程序总是从当前的状态开始,一步步向目标靠拢的。

比如我写个程序,计算从1加到10的总和。 我先用Python来写。 命令式编程是通过修改变量的值来保存当前程序的状态。 sum为1的时候,代表程序现在在完成度为10%这个状态上,直到sum为55的时候,程序达到了最终的状态,目标达到了,程序结束了。

sum = 0
for i in range(1,11):
	sum += i

而函数式编程不一样,它是通过函数来保存程序的状态的,或者更准确一点,它是通过函数创建新的参数或返回值来保存程序的状态的。 函数一层层的叠加起来,其中每个函数的参数或返回结果来代表了程序的一个中间状态,过程式编程中对变量的修改在这里变成了一次的函数转换(一层的函数叠加)。

┌────────────┐ │ ┌────────────┐
│ assignment │ │ │  function  │
└────────────┘ │ └────────────┘
               │               
  a = a + 1;   │   return a+1; 
               │               

在这种范式里,“递归”就是最自然的程序表达方式。 下面是用Scheme写的两个版本,addup用函数的返回值来表示程序状态,addup2用函数的参数来表示程序状态。

(define (addup n)
  (if (= n 1)
    1
    (+ n (addup (- n 1))))

(addup 10)
(define (addup2 n sum)
  (if (= n 1)
    (+ sum 1)
    (addup2 (- n 1) (+ n sum))))

(addup2 10 0)

函数式编程的本质

弄清楚函数式编程是通过函数来构建程序的原理后,我们再回头来看函数式编程的两个本质:

  1. 高阶函数(higher-order functions)
  2. 没有副作用(no side effect)

高阶函数(higher-order functions)

如果仅仅是将命令式编程中对变量的修改变成函数的转换,那么函数式编程的抽象和表达能力将惨不忍睹,绝不会坐拥如此高的赞誉。

函数式编程是通过高阶函数(higher-order functions)的特性来使其具有更丰富多变的表达能力。

Functions that operate on other functions (accept them as arguments or return value) are called higher order functions.

Python就具有高阶函数的性质,比如

def twice(function, x):
    return function(function(x))
 
def f(x):
    return x + 3
 
print(twice(f, 7)) # 13

How, and when, do you use higher order functions? Well, I’m glad you asked. You write your program as a big monolithic blob of code without worrying about class hierarchies. When you see that a particular piece of code is repeated, you break it out into a function (fortunately they still teach this in schools). If you see that a piece of logic within your function needs to behave differently in different situations, you break it out into a higher order function.

比如一个常见的函数map,就是一个更高层更抽象的函数。

l = [1,2,3]
map(lambda x: 2*x, l) # => [2, 4, 6]

具有高阶函数性质的编程语言往往也会支持一等函数(First-class function),它是高阶函数概念上的超集。 指的是函数和其它数据类型处于平等地位,不搞特殊,可以把函数赋值给其他变量,也可以作为参数传入另一个函数,或者作为别的函数的返回值。

A programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.

高阶函数和一等函数让基于函数演变的函数式语言表达能力大增,使其能够用函数构建起更高层更抽象的模块来解决复杂的问题。

# 没有副作用(side effect)

高阶函数和一等函数许多编程语言都有,比如Python。 那函数式语言又有什么特别的呢?

side effect

函数式编程从它的源头λ演算开始,就是强调函数计算的纯粹性,每个函数的执行都是没有副作用(no side effect)的——函数所有功能就是返回一个新的值,没有其他行为,尤其是不得修改外部变量的值。 典型的长于计算,弱于I/O。

In a pure functional programming language, the following are prohibited:

  1. Assignments to variables(except as initialisations)
  2. Assignments to fields of heap-allocated records
  3. Calls to external functions that have visible effects: print, flush, gutter, exit

这又能带来什么好处呢?坏处倒是很容易找——总是新建变量多浪费空间啊。 这其实是一个非常强大的特点,它使得函数式编程各个独立的部分的执行顺序可以随意打乱。 而这在命令式编程风格的代码中是不可能的。

int x = 1;

void func_a() {
	x++;
}

void func_b() {
	x = x * 2;
}

// the order of execution is fixed, otherwise the result won’t be guaranteed.
func_a();
func_b();

执行顺序的自由使其得以衍生出一大堆非常有用的特性,比如无锁(lock-free)的并发操作、惰性求值(lazy evaluation),还有在编译器级别上的各种性能优化技术。 特别在并行技术上,Clojure, Haskell, F#, Scala, Erlang这些函数式语言都无一例外地支持强大的并发功能。

当然函数式语言不可能真的就不执行I/O,但它通过一些手段来把I/O的影响限制到最小,比如通过Continuations, Monad等技术。

函数式编程的其它特性

在抓住本质之后,这个时候再来理解函数式编程各种“花枝招展”的特性,就要容易得多了。

在这里笔者并不会逐一详细讲解列出的特性,笔者想着重说明的是自己对这些特性的理解和它们存在的作用,笔者假定读者对这些特性有一个起码的认识。

尾递归(Tail Recursion)

由于递归在函数式编程中被大量使用,如果任其发展,函数栈很快将爆炸。

tail call

于是函数式编程又有了尾递归(Tail Recursion)的特性。 只要程序编写者懂得更合理地设计递归方法,就能使大量的递归在同一个函数frame中被执行,而不需要为每次函数调用申请一个frame。

正因为JVM不支持尾递归,才使得基于JVM的函数式语言如Scala、Clojure广受诟病。

Effective Data Structures

因为没有赋值操作,所以函数式编程中每个变量都相当于Java的final或者C++的const。 即每个数值和数据结构都是不变量(immutability),一旦定义不能修改。

其实更严谨的它们已经不能叫作变量(variable)了,而应该叫作标识符(symbol),它们仅仅是与具体的数值和数据结构绑定在一起,方便引用而已,是不能修改数据的。

如果数据要变化,即使只是改变链表中的一个节点,也要新建一个新的链表。 这乍听起来在时空和空间的耗费上简直不可接受,但别着急,实际的耗费远比想象中的小,我们可以复用原来的数据结构以节省空间。 这就是Persistent data structure的概念了,这些数据结构也称作effectively immutable data structure。 用链表来作个例子就很明白了。

zs = xs ++ ys

list

Clojure语言全部的数据结构就都是immutable的,而且还保持了非常高效的新建和复制操作。

Domain Specific Languages(DSL)

DSL是针对某个特定领域或特定问题而创建的语言,它的一个指令可能是别的通用的编程语言的几十句甚至更多。使用DSL来解决特定问题可以大大地提升效率和减少犯错的机会。 DSL更是Lisp语言的“秘密武器”——Beating the Averages by Paul Graham 一些常见的DSL比如:

Lisp是最早的函数式编程语言,又叫做LISt Processing,即寓意是一种专门对列表(list)进行处理的语言。 list虽然字面上是线性的列表,但其实是tree的结构,因为它是可以嵌套的,即list中还可以有list。 tree是一种非常强大的结构,各种各样的代码到最后都是用抽象语法树(abstract syntax tree)来表示的。

list既是Lisp代码的基本结构,又可以作为一种表示数据的基本结构(这里可以联想到XML语言来帮助理解——把XML的尖括号替换成括号,去掉全部的属性值,就是用Lisp来表示数据的雏型了)。 这其实与函数式编程没有什么关系了,只是与Lisp的语言设计相关,但Lisp作为函数式编程的代表语言,所以它的特性也一直伴随着函数式编程被大众所认识。

数据和代码的结构一致,将大大提升编程语言的表达能力。 因为我们可以使用Lisp来设计DSL代码,相当于是在设计DSL的API;当使用DSL来解决特定问题时,再把DSL的代码当作数据,用Lisp的宏(macro)来解析。 宏不仅仅是一种字符串解析工具。因为Lisp解释型语言的本质,它能够随时随处解释Lisp代码,因此宏既拥有解析的能力,同时也有即时解释的能力,让DSL的实现变得异常简单。

如果尝试用别的语言来设计DSL。有两种做法。

  1. 设计新的DSL语法
  2. 是沿用该种语言的代码来描述DSL,也就是使用这个语言的类库,比如用网络库来解决网络通信问题。

第一种方法,因为数据与代码的结构不一致,它们只能把DSL当作字符串来解析,因此就需要额外的解析器(parser)和语义转换来把DSL转换成该种语言的代码。 第二种方法,因为要基于原来语言的语法,赋值要用这个套路、函数调用要用这个套路、不能使用原来语言没有的套路,从下到上全都是代码,数据只能按约定好的规则安放,DSL的表达能力很有限。

对Lisp的宏(Macro)感兴趣的朋友,笔者力荐这篇文章

Closure

闭包(closure)的基础是一等函数(First-class function)。

function startAt(x)
   function incrementBy(y)
       return x + y
   return incrementBy

variable closure1 = startAt(1)
variable closure2 = startAt(5)
closure1(3) // => 4
closure2(3) // => 8

但它也给语言的编译或解释带来了更多的困难。 因为内嵌函数(nested functions)可以存储在变量里,实例化之后并不需要马上执行,而通常的函数调用(比如C)的实例化和执行这两个过程是不分开的。在这种情况下,函数的信息(比如参数),在函数实例化之后仍需要保存。 函数的信息不能再储存在栈(stack),而要储存在堆(heap)里。 这也意味着函数式编程语言的runtime一般都具有垃圾回收(Garbage Collection)功能,当某个函数没有变量指向它时,GC再把它的内存回收。

最后

函数式编程,就像文章开首说的,是一种编程范式,并不一定得在Lisp、Haskell这类函数式语言上才能使用。 不是专门为函数式编程设计的编程语言,只要具备一定的特性,都可以用来编写函数式的程序的。比如Python, Ruby, Java 8等等。

觉得好吗,看官何不试试?

主要参考资料

Comments

多说 Disqus