Category Archives: 函数式编程

函数式编程术语解析

函数式编程

翻译 · 原文地址

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

Arity

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

const sum = (a, b) => a + b;

const arity = sum.length;
console.log(arity); 
// => 2

Higher-Order Functions

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

const filter = (pred, xs) => {
    const result = [];
    for (let idx = 0; idx < xs.length; idx++) {
        if (pred(xs[idx])) {
            result.push(xs[idx]);
        }
    }
    return result;
};

const is = (type) => (x) => Object(x) instanceof type;

filter(is(Number), [0, '1', 2, null]); 
// => [0, 2]

Partial Application

偏函数，在原函数的基础上预填充（pre-filling）部分参数并返回的新函数：

// 下面是一个创建偏函数的辅助函数
const partial = (f, ...args) => (...moreArgs) => f(...args, ...moreArgs);

const add3 = (a, b, c) => a + b + c;

// 预填充 (add3, 2, 3) 三个参数，空置最后一个参数，返回一个新的函数
const fivePlus = partial(add3, 2, 3); // (c) => 2 + 3 + c

fivePlus(4); 
// => 9

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

const add1More = add3.bind(null, 2, 3); 
// => (c) => 2 + 3 + c

Currying

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

const sum = (a, b) => a + b;

sum(2, 3)
// => 6

const curriedSum = (a) => (b) => a + b;

curriedSum(40)(2) 
// => 42.

const add2 = curriedSum(2); 
// (b) => 2 + b

add2(10) 
// => 12

Function Composition

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

const compose = (f, g) => (a) => f(g(a))

const floorAndToString = compose((val) => val.toString(), Math.floor)

floorAndToString(121.212121) 
// => "121"

Purity

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

let greeting;
const greet = () => greeting = "Hi, " + window.name;

// greet() 执行时更改了外部环境的变量
greet(); 
// => "Hi, Brianne"

纯函数示例：

const greet = (name) => "Hi, " + name ;

greet("Brianne") 
// => "Hi, Brianne"

Side effects

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

let greeting;
const greet = () => greeting = "Hi, " + window.name;

// greet() 执行时更改了外部环境的变量
greet(); 
// => "Hi, Brianne"

// new Date() 是可变数据
const differentEveryTime = new Date();

// 这里表示系统接收到的输入值是不确定的，是一种可变数据
console.log("IO is a side effect!");

Idempotent

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

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

Math.abs(Math.abs(10))

sort(sort(sort([2,1])))

Point-Free Style

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

const map = (fn) => (list) => list.map(fn);
const add = (a) => (b) => a + b;

// Not points-free
// numbers 是一个显式传递的参数
const incrementAll = (numbers) => map(add(1))(numbers);

// Points-free
// add(1) 的返回值隐式传递给了 map，作为 map 的 list 参数
const incrementAll2 = map(add(1));

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

Predicate

断言，一个返回布尔值的函数：

const predicate = (a) => a > 2;

[1, 2, 3, 4].filter(predicate); 
// => [3, 4]

Contracts

TODO

Guarded Functions

TODO

Categories

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

Value

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

5
Object.freeze({name: 'John', age: 30}) // The `freeze` function enforces immutability.
(a) => a
[1]
undefined

Constant

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

const five = 5
const john = { name: 'John', age: 30 }

// 因为常量不可变，所以下面表达式一定为 true
john.age + five === ({ name: 'John', age: 30 }).age + (5)

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

const five = fromJS(5);
const john = fromJS({name: 'John', age: 30})

john.get('age') + five === ({ name: 'John', age: 30 }).age + (5)

f(g()) === g

Functor

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

object.map(x => x) === object

object.map(x => f(g(x))) === object.map(g).map(f)

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

[1, 2, 3].map(x => x); 
// => [1, 2, 3]

const f = x => x + 1;
const g = x => x * 2;

[1, 2, 3].map(x => f(g(x))); 
// => [3, 5, 7]
[1, 2, 3].map(g).map(f);     
// => [3, 5, 7]

Pointed Functor

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

Array.of(1) 
// => [1]

Lift

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

const mult = (a, b) => a * b;

const liftedMult = lift(mult); 
// => this function now works on functors like array

liftedMult([1, 2], [3]); 
// => [3, 6]
lift((a, b) => a + b)([1, 2], [3, 4]); 
// => [4, 5, 5, 6]

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

const increment = (x) => x + 1;

lift(increment)([2]); 
// => [3]
[2].map(increment); 
// => [3]

Referential Transparency

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

const greet = () => "Hello World!";

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

Equational Reasoning

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

Lambda

匿名函数，本质上是一个 value：

function(a){
    return a + 1;
};

(a) => a + 1;

// Lambda 常用语高阶函数中
[1, 2].map((a) => a + 1); 
// = [2, 3]

// Lambda 作为 value 被赋值给变量
let addOne = (a) => a + 1;

Lambda Calculus

数学的分支之一，使用函数创建通用的计算模型（universal model of computation）。

Lazy evaluation

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

const rand = function*() {
    while (true) {
        yield Math.random();
    }
}

const randIter = rand();
randIter.next().value; 
// 每次执行 next() 函数都会返回一个新的随机数
// 有且只有在执行 next() 的时候才会返回新值

Monoid

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

1 + 1; 
// => 2

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

1 + 0
// => 1
// 这里的 0 就是恒等式

// Monoid 还必须满足结合律
1 + (2 + 3) === (1 + 2) + 3; 
// => true

// 数组的 concat() 操作可以构造一个 monoid
[1, 2].concat([3, 4]); 
// => [1, 2, 3, 4]

// 空数组可以视为是恒等式
[1, 2].concat([]); 
// => [1, 2]

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

const identity = (a) => a;
const compose = (f, g) => (x) => f(g(x));

compose(foo, identity) ≍ compose(identity, foo) ≍ foo

Monad

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

['cat,dog', 'fish,bird'].chain((a) => a.split(',')) 
// => ['cat', 'dog', 'fish', 'bird']

['cat,dog', 'fish,bird'].map((a) => a.split(',')) 
// => [['cat', 'dog'], ['fish', 'bird']]

在其他函数式编程语言中，of 也被称为 return，chain 也被称为 flatmap 和 bind。

Comonad

Comonad，拥有 extract 和 extend 函数的数据类型：

const CoIdentity = (v) => ({
    val: v,
    extract() { return this.val },
    extend(f) { return CoIdentity(f(this)) }
})

// extract() 可以从 functor 中取值
CoIdentity(1).extract() 
// => 1

// extend() 可以返回新的 comonad
CoIdentity(1).extend(co => co.extract() + 1) 
// => CoIdentity(2)

Applicative Functor

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

[(a) => a + 1].ap([1]) 
// => [2]

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

const arg1 = [1, 2];
const arg2 = [3, 4];
const add = (x) => (y) => x + y;

const partiallyAppliedAdds = [add].ap(arg1); 
// => [(y) => 1 + y, (y) => 2 + y]

partiallyAppliedAdds.ap(arg2); 
// => [4, 5, 5, 6]

Morphism

态射，一个转换函数。

Isomorphism

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

const pairToCoords = (pair) => ({x: pair[0], y: pair[1]})
const coordsToPair = (coords) => [coords.x, coords.y]

coordsToPair(pairToCoords([1, 2])) 
// => [1, 2]

pairToCoords(coordsToPair({x: 1, y: 2})) 
// => { x: 1, y: 2 }

Setoid

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

Array.prototype.equals = (arr) => {
    const len = this.length
    if (len !== arr.length) {
        return false
    }
    for (let i = 0; i < len; i++) {
        if (this[i] !== arr[i]) {
            return false
        }
    }
    return true
}

[1, 2].equals([1, 2]) 
// => true
[1, 2].equals([0]) 
// => false

Semigroup

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

[1].concat([2]) 
// => [1, 2]

Foldable

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

const sum = (list) => list.reduce((acc, val) => acc + val, 0);
sum([1, 2, 3]) 
// => 6

Traversable

TODO

Type Signatures

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

// functionName :: firstArgType -> secondArgType -> returnType

// add :: Number -> Number -> Number
const add = (x) => (y) => x + y

// increment :: Number -> Number
const increment = (x) => x + 1

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

// call :: (a -> b) -> a -> b
const call = (f) => (x) => f(x)

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

// map :: (a -> b) -> [a] -> [b]
const map = (f) => (list) => list.map(f)

Union type

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

// add :: (NumOrString, NumOrString) -> NumOrString
const add = (a, b) => a + b;

add(1, 2); 
// => Number 3
add('Foo', 2); 
// => String "Foo2"
add('Foo', 'Bar'); 
// => String "FooBar"

Product type

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

// point :: (Number, Number) -> {x: Number, y: Number}
const point = (x, y) => ({x: x, y: y});

Option

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

// Naive definition
const Some = (v) => ({
    val: v,
    map(f) {
        return Some(f(this.val));
    },
    chain(f) {
        return f(this.val);
    }
});

const None = () => ({
    map(f){
        return this;
    },
    chain(f){
        return this;
    }
});

// maybeProp :: (String, {a}) -> Option a
const maybeProp = (key, obj) => typeof obj[key] === 'undefined' ? None() : Some(obj[key]);

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

// getItem :: Cart -> Option CartItem
const getItem = (cart) => maybeProp('item', cart);

// getPrice :: Item -> Option Number
const getPrice = (item) => maybeProp('price', item);

// getNestedPrice :: cart -> Option a
const getNestedPrice = (cart) => getItem(obj).chain(getPrice);

getNestedPrice({}); 
// => None()
getNestedPrice({item: {foo: 1}}); 
// => None()
getNestedPrice({item: {price: 9.99}}); 
// => Some(9.99)

某些语言中使用 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:

  > fmap (+3) (Just 2)
Just 5

这是在幕后所发生的:

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

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

  > fmap (+3) Nothing
Nothing

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

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

  post = Post.find_by_id(1)
if post
  return post.title
else
  return nil
end

但用 Haskell:

  fmap (getPostTitle) (findPost 1)

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

  getPostTitle <$> (findPost 1)

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

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

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

  fmap (+3) (+1)

这是个函数:

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

结果就是又一个函数!

  > import Control.Applicative
> let foo = (+3) <$> (+2)
> foo 10
15

这就是函数复合! 就是说, 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 定义了 <*>, 这个函数知道怎样把封装在上下文里的函数应用到封装在上下文里的值:

也就是:

  Just (+3) <*> Just 2 == Just 5

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

  > [(*2), (+3)] <*> [1, 2, 3]
[2, 4, 6, 4, 5, 6]

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

  > (+) <$> (Just 5)
Just (+5)
> Just (+5) <$> (Just 4)
ERROR ??? WHAT DOES THIS EVEN MEAN WHY IS THE FUNCTION WRAPPED IN A JUST

Applicative:

  > (+) <$> (Just 5)
Just (+5)
> Just (+5) <*> (Just 3)
Just 8

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

  > (*) <$> Just 5 <*> Just 3
Just 15
An applicative watching a functor apply a function

一 applicative 看着一 functor 应用一函数

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

  > liftA2 (*) (Just 5) (Just 3)
Just 15

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 是仅对偶数可用的函数:

  half x = if even x
           then Just (x `div` 2)
           else Nothing

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

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

它怎么起作用的:

  > Just 3 >>= half
Nothing
> Just 4 >>= half
Just 2
> Nothing >>= half
Nothing

其中发生了什么?

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

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

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

  getLine :: IO String

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

  readFile :: FilePath -> IO String

putStrLn 接收一个字符串打印:

  putStrLn :: String -> IO ()

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

  getLine >>= readFile >>= putStrLn

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

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

  foo = do
    filename <- getLine
    contents <- readFile filename
    putStrLn contents

结论

  • 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);

在函数式编程中，编译器可以对代码进行分析，发现生成字符串s1和s2的函数可能非常耗时，于是对其并行运行。这种情况在命令式语言中是不可能出现的，因为每一个函数都有可能修改外部状态，而后续函数有可能依赖这些外部状态。在函数式语言里，自动分析哪些函数可以并发执行就像自动内联一样简单。从这个意义上说，具有函数式风格的程序是“不会过时的技术(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 square(int i) {
    return pow(i, 2);
  }
}
square_function_t square = new square_function_t();

正如你所见，我们只是简单地包装了一下原函数。在函数式编程中，这就是currying——快速便捷的包装一个函数。你专注于你的工作，而编译器为你生成具体的代码！那么什么时候用currying？很简单：当你想用适配器模式（包装）的时候。

惰性求值

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

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

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

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

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

优化

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

抽象控制结构

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

1
2
3
unless(stock.isEuropean()) {
  sendToSEC(stock);
}

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

1
2
3
4
void unless(boolean condition, List code) {
  if(!condition)
    code;
}

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

无限的数据结构

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

缺点

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

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

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

Continuations

Continuations对于程序设计的意义，就像《达芬奇密码》对人类历史的意义：揭露了人类有史以来最大的假象。恩，也许没那么牛。但它在概念上的突破性至少和开方负数的意义相同。

我们学习函数时，其实基于这样一个假设：函数只能将结果返回给调用者。在这个意义上continuation是广义的函数。一个函数不一定必须要返回到其调用者，它可以返回到程序的任何地方。continuation可以是函数的一个参数，我们通过这个参数指定函数返回位置。这个描述可能听起来很复杂，我们来看看下面的代码：

1
2
int i = add(5, 10);
int j = square(i);

函数add返回15，并赋值给i，即原始调用add的地方。然后在调用square的时候使用i。注意，延迟特性的编译器无法重新排列这些代码，因为第二行代码依赖于第一行的执行。但是我们可以用延续传递方式（Continuation Passing Style，CPS）重写这段代码，用它来指定add函数直接返回到square，而不是原来的调用者：

1
int j = add(5, 10, square);

这个例子中 add 有了另一个参数 —— 一个add在结束时需要调用的函数。这里square是add的continuation。这两段代码的结果都是j=225.

这个技巧可以用于迫使惰性语言顺序执行两个表达式。接下来我们看看这个（熟悉的）IO代码：

1
2
System.out.println("Please enter your name: ");
System.in.readLine();

这两行代码彼此独立，所以编译器会根据自己希望的顺序去执行他们。但是，如果我们用CPS来重写这段代码，它们之间便有了依赖关系，编译器会按顺序执行它们：

1
System.out.println("Please enter your name: ", System.in.readLine);

这里，println需要在结束后调用readLine并且返回readLine的结果。如此这两行就能保证被有序执行，并且readLine一定会被执行（因为整个运算以最后一个值作为返回值）。Java的println会返回void，但如果假设它返回的是一个readLine能接受的抽象值，我们就解决了这个问题！当然，像这样把函数串起来，会降低代码的可读性。不过这个可以避免。我们可以在程序语言中添加一些语法规则，使我们可以像原来那样按顺序输入代码，然后编译器自动把它们串起来。这样我们就可以按希望的顺序执行代码，并且保留一切函数式编程的好处（包括按数学逻辑来解释我们的代码）。如果说到这里还有点晕的话，那么记住，一个函数就是一个只有一个成员的类实例。如果将上面的代码重写成println和readline的类实例的话，可能就清楚多了。

如果我就此结束，那将仅仅涉及到continuation的皮毛。我们可以用CPS重写整个程序，使所有函数都有一个额外的continuation参数，然后将当前函数的执行结果传进去。我们也可以将函数看成一类特殊的continuation（函数总是返回值给调用者），然后将程序转换成CPS代码。这种转换很容易被自动化（事实上，许多编译器就是这么做的）。

当我们将一个程序转换为CPS以后，每一个指令都会有continuation，一个当前函数执行后调用的函数，也就是通常的程序中的返回地址。让我从上面的代码中挑一个指令，比如add(5,10)。在CPS中，add的continuation是add调用完毕后接下来要执行的函数，但是在非CPS的程序中，continuation是什么呢？我们当然可以把它转换成CPS后来解释，但有这个必要吗？

其实没有必要。仔细看一下CPS转换过程。如果你试着去为它写一个编译器，并且好好思考如何去做的话，你会意识到CPS根本不需要栈！没有函数会像传统程序那样“返回”，它只是在执行完毕之后调用另一个函数。因此我们不用在每次调用函数时把参数都压到栈中，然后再在调用结束时把它们弹出来。我们只需要把它们存到内存块中，然后使用跳转指令。我们永远不需要原始的参数。他们不会被再次用到，因为没有函数会返回！

所以，用CPS风格写成的程序没有栈，但每个函数却有一个额外的参数来调用下一个函数。而不以CPS方式写的程序没有额外的参数，但是有栈。栈中包含了什么？一些参数和一个指向函数返回地址的内存指针。看到关系了么？栈中包含的就是continuation信息！栈中指向返回地址的指针本质上和CPS里将被调用的函数是等价的。如果你想知道add(5,10)的continuation是什么，那么你只需要检查它被执行时的栈即可。

这的确很简单。continuation和栈上指向返回地址的指针是等价的。continuation被显式传递，所以它不一定必须是函数原来被调用的地方。如果你还记得continuation就是一个函数，并且函数在我们的程序语言被编译成一个类的实例的话，你会更理解二者是一样的。这意味着给定程序中任意时间和任意位置，你都可以得到一个当前的continuation（current continuation），即当前栈的信息。

好的，这样我们就知道了什么是current continuation。有什么用呢？当我们将current continuation保存在某处时，实际上是把程序的当前状态速冻起来。这类似于操作系统进入休眠状态。一个continuation对象包含在我们获得它的地方重新启动程序的必要信息。操作系统做线程间的上下文切换时也是如此。唯一的区别是它仍然继续保持着控制权。如果你需要一个continuation对象（在Scheme中，可以调用call-with-current-continuation函数），你就会得到一个包含current continuation的对象，即栈或者是在CPS中下一个要调用的函数）。你可以将这个对象存到变量中（或者磁盘上）。当你用这个continuation对象“重启”程序的时候，就可以将程序“转换”到你取得这个对象时的那个状态。这和切换回一个被挂起的线程或者唤醒休眠着的操作系统是一回事，而且你可以一遍又一遍的这样做。当操作系统被唤醒时，休眠信息就被销毁了。但如果那些信息没有被销毁，那么你也可以从同一个点一次又一次的唤醒操作系统。这就像时间停止一样。使用continuation，你就有了这个控制力！

Continuation应该在什么情况下使用呢？一般是在我们希望在一个先天就无状态的应用中模拟状态的时候。这样可以简化任务。Continuation很适合在Web应用程序中使用。微软的ASP.NET花了很大的功夫来模拟状态，以便在开发Web应用时少费周折。如果C#支持continuation，ASP.NET就不那么复杂了——你只需要保存一个continuation，当用户再次发送web请求时，重新启动它就可以了。对于程序员来说，web应用程序将不再有中断——程序只是简单的从下一行开始执行就可以了！

对于一些问题来说，continuation是一个非常有用的抽象工具。想到很多传统复杂的客户端将走向网络，continuation在未来会变得越来越重要。

模式匹配

模式匹配不是什么新特性。事实上，它和函数式编程的关系不大。为什么总是把它当做函数式编程的一个特性呢？这是因为函数式语言已经支持模式匹配一段时间了，而现代命令式语言还不行。

用一个例子来进一步了解模式匹配。下面是Java实现的斐波那契函数：

1
2
3
4
5
6
int fib(int n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return fib(n - 2) + fib(n - 1);
}

如果用我们上文构造的并且支持模式匹配的Java来写，实现如下

1
2
3
4
5
6
7
8
9
10
11
int fib(0) {
  return 1;
}
int fib(1) {
  return 1;
}
int fib(int n) {
  return fib(n - 2) + fib(n - 1);
}

两者有什么区别？编译器为我们实现了分支。

这有什么大不了的？的确没什么。有人注意到很多函数都包含非常复杂的switch语句（函数式程序中尤其如此）并且觉得这是一种很好的抽象方式。我们将函数拆分成多个，然后通过函数参数实现模式（有点象重载）。当编译器调用函数的时候，会比较传入的参数和定义中的参数，然后选择匹配的那个执行。通常来说，编译器会选择最佳匹配。比如，int fib(int n)也可以在当n为1时被匹配，但因为int fib(1)是最佳匹配，所以编译器不会选择int fib(int n)。

模式匹配通常比例子中揭示的更加复杂。比如，高级模式匹配系统允许我们这样做：

1
2
int f(int n < 10) { ... }
int f(int n) { ... }

模式匹配在什么时候适用？当有一大堆case的时候！每次当你需要写一个包含嵌套if的复杂结构时，模式匹配都可以用更少的代码取得更好的效果。一个很好的例子闪现在我脑海里。这就是所有Win32平台都提供的标准WinProc函数（即使它通常被抽象了）。一般来说一个好的模式匹配系统既可以检查集合，也可以检查简单值。比如，当传给函数一个数组后，可以设计这样一个模式：当首元素为1并且第三个元素大于3的时候，该模式被匹配。

模式匹配的另一个好处就是，当你需要添加或者改变条件时，不用去检查这个庞大的函数。而只需要添加（或修改）相应的那个模式定义。这样Gof书上的一大部分设计模式就没用了。条件越复杂，模式匹配就越有用。一旦你熟悉了模式匹配，就会开始奇怪：没有它的这些年你是怎么挨过来的。

闭包（Closure）

我们已经讨论了纯函数式语言的很多功能——所谓“纯”函数式语言就是实现了lambda演算并且不包含与Church范式矛盾的特性。但是函数式语言并不仅限于lambda演算。虽然实现一个自我证明的系统非常有用，它可以让我们以数学的方式来思考程序，但是可能在实际中它没有什么用处。所以很多语言选择支持部分函数式元素，但又不严格遵守那些教条。一些语言（比如Common Lisp）不要求变量是final的。你可以随时修改变量。它们的函数也不仅依赖于函数的参数。函数可以访问外部状态。但这些语言的确包含了函数式特性，比如高阶函数。在非纯粹的函数式语言里以函数作为参数传递，和在lambda演算系统中有些不同，它需要一种被称为词法闭包（lexical closure）的有趣特性。让我们来看看这段例子代码。记住，这回变量不是final的，并且函数可以引用其作用域外的变量：

1
2
3
4
5
6
7
8
9
Function makePowerFn(int power) {
  int powerFn(int base) {
    return pow(base, power);
  }
  return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9

函数makePowerFn返回了一个函数。这个函数有一个参数，并对这个参数进行幂运算。如果我们对square(3)求值会发生什么？变量power其实已经不在powerFn的作用域中了，因为makePowerFn已经返回，所以它的栈已经消失了。那么square是怎么执行的？一定是这个语言以某种方式将power的值保存起来以便square使用。如果我们创建另一个函数cube，为参数的立方运算会怎么样？运行环境必须存储两个power，每个我们用makePowerFn生成的函数（square和cube）各使用一个。存储这些值的现象就叫做闭包。闭包不只保存宿主函数的参数。例如，closure可能会是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Function makeIncrementer() {
  int n = 0;
  int increment() {
    return ++n;
  }
}
Function inc1 = makeIncrementer();
Function inc2 = makeIncrementer();
inc1(); // returns 1;
inc1(); // returns 2;
inc1(); // returns 3;
inc2(); // returns 1;
inc2(); // returns 2;
inc2(); // returns 3;

运行时已经保存了n，所以递增器可以访问它。更重要的是，运行时为每个递增器都保存了一个n的拷贝，即使这些拷贝应该在makeIncrementer返回时消失。那么这些代码是被如何编译的？闭包运算又是怎么工作的？让我们去幕后看看。

一点常识会很有帮助，首先局部变量不再由简单的作用域规则限定，它们的生命周期也不确定。那么由此可以得出它们不再被保存在栈上，而是堆中·8(#note8)。这样一来，闭包的实现就与我们前面讨论的函数一样了，只是它还有一个指向周围变量的引用。

1
2
3
4
5
class some_function_t {
  SymbolTable parentScope;
  // ...
}

当闭包引用了一个不在其作用域的变量时，它便会查找其父作用域中的引用。这样闭包将函数式和面向对象程序设计相结合。每当你创建一个包含了状态的类，并且把它传到别处的时候，想想闭包吧。闭包就是一个可以在运行时创建并获取“成员变量”的对象，只是你不必亲自去做这些！

接下来如何？

这篇文章仅介绍了函数式程序设计的一些皮毛。即是所谓的抛砖引玉吧。未来我打算写一写关于分类理论（category theory），单一体（monad），函数数据结构（functional data structure），函数式程序设计中的类型系统，FP并发，函数式数据库等等。如果我能（在学习的过程中）写出这些主题的一半，我想我的人生就完整了。与此同时，Google是我们的好朋友。

意见或建议？

如果你有任何问题、意见、或建议，请发送邮件至coffeemug@gmail.com。我非常愿意听到您的反馈。

  1. 当我2005年秋天找工作的时候，我真的常常问这个问题。让人惊讶的是，我看到了很多茫然的面孔。你得想想，这帮年薪30万美金的人对于大部分他们能接触到的工具都有一个很好的理解。
  2. 这是一个有争议的问题。物理学家和数学家一直被迫承认，他们还不完全清楚宇宙万物所遵循的规则是否都可以被数学描述。
  3. 我非常讨厌那种仅给出一串日期、名字、事件的历史课。对我来说，历史是那些改变历史的人的生活，是他们行动背后的动机，是他们影响世人的方式。因此，我写的这一节并不能涵盖所有的历史细节。我只介绍那些与函数式程序设计相关的人和事。
  4. 我在学习函数式程序设计的时候，很不喜欢术语lambda，因为我搞不清楚它到底是什么意思。本文中，lambda就是一个函数，一个方便使用的希腊字母。当谈到函数式编程的时候，如果你听到“lambda”，在脑子里把它翻译成“函数”就行了。
  5. 有趣的是，Java中的字符串就是不可变的。讨论为什么会出现这样离经叛道的设计可能更有趣，但是这会打断我们当前的话题。
  6. 几乎所有的函数式语言编译器都会尽可能的将递归优化为迭代。这中优化被称为尾递归优化（tail call optimization）。
  7. 相反的情况未必成立。尽管有时可以证明两段代码等价，但无法找到一种普世方法可以证明所有情况。
  8. 这其实不比存在栈中慢，因为如果你引入了垃圾回收器，那么内存分配便成为了一个O(1)操作。

from :http://blog.pengyifan.com/articles/functional-programming-for-the-rest-of-us/

 

康托尔、哥德尔、图灵——永恒的金色对角线

函数式编程, 计算理论
我看到了它，却不敢相信它[1]。
——康托尔
计算机是数学家一次失败思考的产物。
——无名氏
哥德尔的不完备性定理震撼了20世纪数学界的天空，其数学意义颠覆了希尔伯特的形式化数学的宏伟计划，其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科，深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型，进而作出了可计算理论和现代计算机的奠基性工作，著名的停机问题给出了机械计算模型的能力极限，其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐，跟图灵同时代的天才，则从另一个抽象角度提出了lambda算子的思想，与图灵机抽象的倾向于硬件性不同，丘齐的lambda算子理论是从数学的角度进行抽象，不关心运算的机械过程而只关心运算的抽象性质，只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型，其体现出来的数学抽象美开出了函数式编程语言这朵奇葩，Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界，虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言[2]，然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…
然而，这一切的一切，看似不很相关却又有点相关，认真思考其关系却又有点一头雾水的背后，其实隐隐藏着一条线，这条线把它们从本质上串到了一起，而顺着时光的河流逆流而上，我们将会看到，这条线的尽头，不是别人，正是只手拨开被不严密性问题困扰的19世纪数学界阴沉天空的天才数学家康托尔，康托尔创造性地将一一对应和对角线方法运用到无穷集合理论的建立当中，这个被希尔伯特称为“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”、被罗素称为“19世纪最伟大的智者之一”的人，他在集合论方面的工作终于驱散了不严密性问题带来的阴霾，仿佛一道金色的阳光刺破乌云，19世纪的数学终于看到了真正严格化的曙光，数学终于得以站在了前所未有的坚固的基础之上；集合论至今仍是数学里最基础和最重要的理论之一。而康托尔当初在研究无穷集合时最具天才的方法之一——对角线方法——则带来了极其深远的影响，其纯粹而直指事物本质的思想如洪钟大吕般响彻数学和哲学的每一个角落[3]。随着本文的展开，你将会看到，刚才提到的一切，歌德尔的不完备性定理，图灵的停机问题，lambda算子理论中神奇的Y combinator、乃至著名的罗素悖论、理发师悖论等等，其实都源自这个简洁、纯粹而同时又是最优美的数学方法，反过来说，从康托尔的对角线方法出发，我们可以轻而易举地推导出哥德尔的不完备性定理，而由后者又可以轻易导出停机问题和Y combinator，实际上，我们将会看到，后两者也可以直接由康托尔的对角线方法导出。尤其是Y combinator，这个形式上绕来绕去，本质上捉摸不透，看上去神秘莫测的算子，其实只是一个非常自然而然的推论，如果从哥德尔的不完备性定理出发，它甚至比停机问题还要来得直接简单。总之，你将会看到这些看似深奥的理论是如何由一个至为简单而又至为深刻的数学方法得出的，你将会看到最纯粹的数学美。
图灵的停机问题(The Halting Problem)
了解停机问题的可以直接跳过这一节，到下一节“Y Combinator”，了解后者的再跳到下一节“哥德尔的不完备性定理”
我们还是从图灵著名的停机问题说起，一来它相对来说是我们要说的几个定理当中最简单的，二来它也最贴近程序员。实际上，我以前曾写过一篇关于图灵机的文章，有兴趣的读者可以从那篇开始，那篇主要是从理论上阐述，所以这里我们打算避开抽象的理论，换一种符合程序员思维习惯的直观方式来加以解释。
停机问题
不存在这样一个程序（算法），它能够计算任何程序（算法）在给定输入上是否会结束（停机）。
那么，如何来证明这个停机问题呢？反证。假设我们某一天真做出了这么一个极度聪明的万能算法（就叫God_algo吧），你只要给它一段程序（二进制描述），再给它这段程序的输入，它就能告诉你这段程序在这个输入上会不会结束（停机），我们来编写一下我们的这个算法吧：
bool God_algo(char* program, char* input)
{
if(<program> halts on <input>)
return true;
return false;
}
这里我们假设if的判断语句里面是你天才思考的结晶，它能够像上帝一样洞察一切程序的宿命。现在，我们从这个God_algo出发导出一个新的算法：
bool Satan_algo(char* program)
{
if( God_algo(program, program) ){
   while(1); // loop forever!
   return false; // can never get here!
}
else
   return true;
}
正如它的名字所暗示的那样，这个算法便是一切邪恶的根源了。当我们把这个算法运用到它自身身上时，会发生什么呢？
Satan_algo(Satan_algo);
我们来分析一下这行简单的调用：
显然，Satan_algo(Satan_algo)这个调用要么能够运行结束返回（停机），要么不能返回（loop forever）。
如果它能够结束，那么Santa_algo算法里面的那个if判断就会成立（因为God_algo(Santa_algo,Santa_algo)将会返回true），从而程序便进入那个包含一个无穷循环while(1);的if分支，于是这个Satan_algo(Satan_algo)调用便永远不会返回（结束）了。
而如果Satan_algo(Satan_algo)不能结束（停机）呢，则if判断就会失败，从而选择另一个if分支并返回true，即Satan_algo(Satan_algo)又能够返回（停机）。
总之，我们有：
Satan_algo(Satan_algo)能够停机=> 它不能停机
Satan_algo(Satan_algo)不能停机=> 它能够停机
所以它停也不是，不停也不是。左右矛盾。
于是，我们的假设，即God_algo算法的存在性，便不成立了。正如拉格朗日所说：“陛下，我们不需要（上帝）这个假设”[4]。
这个证明相信每个程序员都能够容易的看懂。然而，这个看似不可捉摸的技巧背后其实隐藏着深刻的数学原理（甚至是哲学原理）。在没有认识到这一数学原理之前，至少我当时是对于图灵如何想出这一绝妙证明感到无法理解。但后面，在介绍完了与图灵的停机问题“同构”的Y combinator之后，我们会深入哥德尔的不完备性定理，在理解了哥德尔不完备性定理之后，我们从这一同样绝妙的定理出发，就会突然发现，离停机问题和神奇的Y combinator只是咫尺之遥而已。当然，最后我们会回溯到一切的尽头，康托尔那里，看看停机问题、Y combinator、以及不完备性定理是如何自然而然地由康托尔的对角线方法推导出来的，我们将会看到这些看似神奇的构造性证明的背后，其实是一个简洁优美的数学方法在起作用。
Y Combinator
了解Y combinator的请直接跳过这一节，到下一节“哥德尔的不完备性定理”。
让我们暂且搁下但记住绕人的图灵停机问题，走进函数式编程语言的世界，走进由跟图灵机理论等价的lambda算子发展出来的另一个平行的语言世界。让我们来看一看被人们一代一代吟唱着的神奇的Y Combinator…
关于Y Combinator的文章可谓数不胜数，这个由师从希尔伯特的著名逻辑学家Haskell B.Curry（Haskell语言就是以他命名的，而函数式编程语言里面的Curry手法也是以他命名）“发明”出来的组合算子（Haskell是研究组合逻辑(combinatory logic)的）仿佛有种神奇的魔力，它能够算出给定lambda表达式（函数）的不动点。从而使得递归成为可能。事实上，我们待会就会看到，Y Combinator在神奇的表面之下，其实隐藏着深刻的意义，其背后体现的意义，曾经开出过历史上最灿烂的数学之花，所以MIT的计算机科学系将它做成系徽也就不足为奇了[5]。
当然，要了解这个神奇的算子，我们需要一点点lambda算子理论的基础知识，不过别担心，lambda算子理论是我目前见过的最简洁的公理系统，这个系统仅仅由三条非常简单的公理构成，而这三条公理里面我们又只需要关注前两条。
以下小节——lambda calculus——纯粹是为了没有接触过lambda算子理论的读者准备的，并不属于本文重点讨论的东西，然而要讨论Y combinator就必须先了解一下lambda（当然，以编程语言来了解也行，但是你会看到，丘齐最初提出的lambda算子理论才是最最简洁和漂亮的，学起来也最省事。）所以我单独准备了一个小节来介绍它。如果你已经知道，可以跳过这一小节。不知道的读者也可以跳过这一小节去wikipedia上面看，这里的介绍使用了wikipedia上的方式
lambda calculus
先来看一下lambda表达式的基本语法(BNF)：
<expr> ::= <identifier>
<expr> ::= lambda <identifier-list>. <expr>
<expr> ::= (<expr> <expr>)
前两条语法用于生成lambda表达式（lambda函数），如：
lambda x y. x + y
haskell里面为了简洁起见用“/”来代替希腊字母lambda，它们形状比较相似。故而上面的定义也可以写成：
/ x y. x + y
这是一个匿名的加法函数，它接受两个参数，返回两值相加的结果。当然，这里我们为了方便起见赋予了lambda函数直观的计算意义，而实际上lambda calculus里面一切都只不过是文本替换，有点像C语言的宏。并且这里的“+”我们假设已经是一个具有原子语义的运算符[6]，此外，为了方便我们使用了中缀表达（按照lambda calculus系统的语法实际上应该写成“(+ x y)”才对——参考第三条语法）。
那么，函数定义出来了，怎么使用呢？最后一条规则就是用来调用一个lambda函数的：
((lambda x y. x + y) 2 3)
以上这一行就是把刚才定义的加法函数运用到2和3上（这个调用语法形式跟命令式语言(imperative language)惯用的调用形式有点区别，后者是“f(x, y)”，而这里是“(f x y)”，不过好在顺序没变:) ）。为了表达简洁一点，我们可以给(lambda x y. x + y)起一个名字，像这样：
let Add = (lambda x y. x + y)
这样我们便可以使用Add来表示该lambda函数了：
(Add 2 3)
不过还是为了方便起见，后面调用的时候一般用“Add(2, 3)”，即我们熟悉的形式。
有了语法规则之后，我们便可以看一看这个语言系统的两条简单至极的公理了：
Alpha转换公理：例如，“lambda x y. x + y”转换为“lambda a b. a + b”。换句话说，函数的参数起什么名字没有关系，可以随意替换，只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。
Beta转换公理：例如，“(lambda x y. x + y) 2 3”转换为“2 + 3”。这个就更简单了，也就是说，当把一个lambda函数用到参数身上时，只需用实际的参数来替换掉其函数体中的相应变量即可。
就这些。是不是感觉有点太简单了？但事实就是如此，lambda算子系统从根本上其实就这些东西，然而你却能够从这几个简单的规则中推演出神奇无比的Y combinator来。我们这就开始！
递归的迷思
敏锐的你可能会发现，就以上这两条公理，我们的lambda语言中无法表示递归函数，为什么呢？假设我们要计算经典的阶乘，递归描述肯定像这样：
f(n):
 if n == 0 return 1
 return n*f(n-1)
当然，上面这个程序是假定n为正整数。这个程序显示了一个特点，f在定义的过程中用到了它自身。那么如何在lambda算子系统中表达这一函数呢？理所当然的想法如下：
lambda n. If_Else n==0 1 n*<self>(n-1)
当然，上面的程序假定了If_Else是一个已经定义好的三元操作符（你可以想象C的“?:”操作符，后面跟的三个参数分别是判断条件、成功后求值的表达式、失败后求值的表达式。那么很显然，这个定义里面有一个地方没法解决，那就是<self>那个地方我们应该填入什么呢？很显然，熟悉C这类命令式语言的人都知道应该填入这个函数本身的名字，然而lambda算子系统里面的lambda表达式（或称函数）是没有名字的。
怎么办？难道就没有办法实现递归了？或者说，丘齐做出的这个lambda算子系统里面根本没法实现递归从而在计算能力上面有重大的缺陷？显然不是。马上你就会看到Y combinator是如何把一个看上去非递归的lambda表达式像变魔术那样变成一个递归版本的。在成功之前我们再失败一次，注意下面的尝试：
let F = lambda n. IF_Else n==0 1 n*F(n-1)
看上去不错，是吗？可惜还是不行。因为let F只是起到一个语法糖的作用，在它所代表的lambda表达式还没有完全定义出来之前你是不可以使用F这个名字的。更何况实际上丘齐当初的lambda算子系统里面也并没有这个语法元素，这只是刚才为了简化代码而引入的语法糖。当然，了解这个let语句还是有意义的，后面还会用到。
一次成功的尝试
在上面几次失败的尝试之后，我们是不是就一筹莫展了呢？别忘了软件工程里面的一条黄金定律：“任何问题都可以通过增加一个间接层来解决”。不妨把它沿用到我们面临的递归问题上：没错，我们的确没办法在一个lambda函数的定义里面直接（按名字）来调用其自身。但是，可不可以间接调用呢？
我们回顾一下刚才不成功的定义：
lambda n. If_Else n==0 1 n*<self>(n-1)
现在<self>处不是缺少“这个函数自身”嘛，既然不能直接填入“这个函数自身”，我们可以增加一个参数，也就是说，把<self>参数化：
lambda self n. If_Else n==0 1 n*self(n-1)
上面这个lambda算子总是合法定义了吧。现在，我们调用这个函数的时候，只要加传一个参数self，这个参数不是别人，正是这个函数自身。还是为了简单起见，我们用let语句来给上面这个函数起个别名：
let P = lambda self n. If_Else n==0 1 n*self(n-1)
我们这样调用，比如说我们要计算3的阶乘：
P(P, 3)
也就是说，把P自己作为P的第一个参数（注意，调用的时候P已经定义完毕了，所以我们当然可以使用它的名字了）。这样一来，P里面的self处不就等于是P本身了吗？自身调用自身，递归！
可惜这只是个美好的设想，还差一点点。我们分析一下P(P, 3)这个调用。利用前面讲的Beta转换规则，这个函数调用展开其实就是（你可以完全把P当成一个宏来进行展开！）：
IF_Else n==0 1 n*P(n-1)
看出问题了吗？这里的P(n-1)虽然调用到了P，然而只给出了一个参数；而从P的定义来看，它是需要两个参数的（分别为self和n）！也就是说，为了让P(n-1)变成良好的调用，我们得加一个参数才行，所以我们得稍微修改一下P的定义：
let P = lambda self n. If_Else n==0 1 n*self(self, n-1)
请注意，我们在P的函数体内调用self的时候增加了一个参数。现在当我们调用P(P, 3)的时候，展开就变成了：
IF_Else 3==0 1 3*P(P, 3-1)
而P(P, 3-1)是对P合法的递归调用。这次我们真的成功了！
不动点原理
然而，看看我们的P的定义，是不是很丑陋？“n*self(self, n-1)”？什么玩意？为什么要多出一个多余的self？DRY！怎么办呢？我们想起我们一开始定义的那个失败的P，虽然行不通，但最初的努力往往是大脑最先想到的最直观的做法，我们来回顾一下：
let P = lambda self n. If_Else n==0 1 n*self(n-1)
这个P的函数体就非常清晰，没有冗余成分，虽然参数列表里面多出一个self，但我们其实根本不用管它，看函数体就行了，self这个名字已经可以说明一切了对不对？但很可惜这个函数不能用。我们再来回想一下为什么不能用呢？因为当你调用P(P, n)的时候，里面的self(n-1)会展开为P(n-1)而P是需要两个参数的。唉，要是这里的self是一个“真正”的，只需要一个参数的递归阶乘函数，那该多好啊。为什么不呢？干脆我们假设出一个“真正”的递归阶乘函数：
power(n):
 if(n==0) return 1;
 return n*power(n-1);
但是，前面不是说过了，这个理想的版本无法在lambda算子系统中定义出来吗（由于lambda函数都是没名字的，无法自己内部调用自己）？不急，我们并不需要它被定义出来，我们只需要在头脑中“假设”它以“某种”方式被定义出来了，现在我们把这个真正完美的power传给P，这样：
P(power, 3)
注意它跟P(P, 3)的不同，P(P, 3)我们传递的是一个有缺陷的P为参数。而P(power, 3)我们则是传递的一个真正的递归函数power。我们试着展开P(power, 3):
IF_Else 3==0 1 3*power(3-1)
发生了什么？？power(3-1)将会计算出2的阶乘（别忘了，power是我们设想的完美递归函数），所以这个式子将会忠实地计算出3的阶乘！
回想一下我们是怎么完成这项任务的：我们设想了一个以某种方式构造出来的完美的能够内部自己调用自己的递归阶乘函数power，我们发现把这个power传给P的话，P(power, n)的展开式就是真正的递归计算n阶乘的代码了。
你可能要说：废话！都有了power了我们还要费那事把它传给P来个P(power, n)干嘛？直接power(n)不就得了？! 别急，之所以设想出这个power只是为了引入不动点的概念，而不动点的概念将会带领我们发现Y combinator。
什么是不动点？一点都不神秘。让我们考虑刚才的power与P之间的关系。一个是真正可递归的函数，一个呢，则是以一个额外的self参数来试图实现递归的伪递归函数，我们已经看到了把power交给P为参数发生了什么，对吧？不，似乎还没有，我们只是看到了，“把power加上一个n一起交给P为参数”能够实现真正的递归。现在我们想考虑power跟P之间的关系，直接把power交给P如何？
P(power)
这是什么？这叫函数的部分求值(partial evaluation)。换句话说，第一个参数是给出来了，但第二个参数还悬在那里，等待给出。那么，光给一个参数得到的是什么呢？是“还剩一个参数待给的一个新的函数”。其实也很简单，只要按照Beta转换规则做就是了，把P的函数体里面的self出现处皆替换为power就可以了。我们得到：
IF_Else n==0 1 n*power(n-1)
当然，这个式子里面还有一个变量没有绑定，那就是n，所以这个式子还不能求值，你需要给它一个n才能具体求值，对吧。这么说，这可不就是一个以n为参数的函数么？实际上就是的。在lambda算子系统里面，如果给一个lambda函数的参数不足，则得到的就是一个新的lambda函数，这个新的lambda函数所接受的参数也就是你尚未给出的那些参数。换句话来说，调用一个lambda函数可以分若干步来进行，每次只给出一部分参数，而只有等所有参数都给齐了，函数的求值结果才能出来，否则你得到的就是一个“中间函数”。
那么，这跟不动点定理有什么关系？关系大了，刚才不是说了，P(power)返回的是一个新的“中间函数”嘛？这个“中间函数”的函数体我们刚才已经看到了，就是简单地展开P(power)而已，回顾一遍：
IF_Else n==0 1 n*power(n-1)
我们已经知道，这是个函数，参数n待定。因此我们不妨给它加上一个“lambda n”的帽子，这样好看一点：
lambda n. IF_Else n==0 1 n*power(n-1)
这是什么呢？这可不就是power本身的定义？（当然，如果我们能够定义power的话）。不信我们看看power如果能够定义出来像什么样子：
let power = lambda n. IF_Else n==0 1 n*power(n-1)
一模一样！也就是说，P(power)展开后跟power是一样的。即：
P(power) = power
以上就是所谓的不动点。即对于函数P来说power是这样一个“点”：当把P用到power身上的时候，得到的结果仍然还是power，也就是说，power这个“点”在P的作用下是“不动”的。
可惜的是，这一切居然都是建立在一个不存在的power的基础上的，又有什么用呢？可别过早提“不存在”这个词，你觉得一样东西不存在或许只是你没有找到使它存在的正确方法。我们已经看到power是跟P有着密切联系的。密切到什么程度呢？对于伪递归的P，存在一个power，满足P(power)=power。注意，这里所说的“伪递归”的P，是指这样的形式：
let P = lambda self n. If_Else n==0 1 n*self(n-1) // 注意，不是self(self,n-1)
一般化的描述就是，对任一伪递归F（回想一下伪递归的F如何得到——是我们为了解决lambda函数不能引用自身的问题，于是给理想的f加一个self参数从而得到的），必存在一个理想f（F就是从这个理想f演变而来的），满足F(f) = f。
那么，现在的问题就归结为如何针对F找到它的f了。根据F和f之间的密切联系（F就比f多出一个self参数而已），我们可以从F得出f吗？假设我们可以（又是假设），也就是说假设我们找到了一根魔棒，把它朝任意一个伪递归的F一挥，眼前一花，它就变成了真正的f了。这根魔棒如果存在的话，它具有什么性质？我们假设这个神奇的函数叫做Y，把Y用到任何伪递归的函数F上就能够得到真正的f，也就是说：
Y(F) = f
结合上面的F(f) = f，我们得到：
Y(F) = f = F(f) = F(Y(F))
也就是说，Y具有性质：
Y(F) = F(Y(F))
性质倒是找出来了，怎么构造出这个Y却又成了难题。一个办法就是使用抽象法，这是从工程学的思想的角度，也就是通过不断迭代、重构，最终找到问题的解。然而对于这里的Y combinator，接近问题解的过程却显得复杂而费力，甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而，在这整个Y combinator介绍完了之后我们将会介绍著名的哥德尔不完备性定理，然后我们就会发现，通过哥德尔不完备性定理证明中的一个核心构造式，只需一步自然的推导就能得出我们的Y combinator。而且，最美妙的是，还可以再往下归约，把一切都归约到康托尔当初提出的对角线方法，到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙，我们由简单得无法再简单的lambda calculus系统的两条公理居然能够导出如此复杂如此令人目眩神迷的Y Combinator，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。
让我们先来看一看Y combinator的费力而复杂的工程学构造法，我会尽量让这个过程显得自然而流畅[7]：
我们再次回顾一下那个伪递归的求阶乘函数：
let P = lambda self n. If_Else n==0 1 n*self(n-1)
我们的目标是找出P的不动点power，根据不动点的性质，只要把power传给P，即P(power)，便能够得到真正的递归函数了。
现在，关键的地方到了，由于：
power = P(power) // 不动点原理
这就意味着，power作为一个函数（lambda calculus里面一切都是函数），它是自己调用了自己的。那么，我们如何实现这样一个能够自己调用自己的power呢？回顾我们当初成功的一次尝试，要实现递归，我们是通过增加一个间接层来进行的：
let power_gen = lambda self. P(self(self))
还记得self(self)这个形式吗？我们在成功实现出求阶乘递归函数的时候不就是这么做的？那么对于现在这个power_gen，怎么递归调用？
power_gen(power_gen)
不明白的话可以回顾一下前面我们调用P(P, n)的地方。这里power_gen(power_gen)展开后得到的是什么呢？我们根据刚才power_gen的定义展开看一看，原来是：
P(power_gen(power_gen))
看到了吗？也就是说：
power_gen(power_gen) => P(power_gen(power_gen))
 
现在，我们把power_gen(power_gen)当成整体看，不妨令为power，就看得更清楚了：
power => P(power)
这不正是我们要的答案么？
OK，我们总结一下：对于给定的P，只要构造出一个相应的power_gen如下：
let power_gen = lambda self. P(self(self))
我们就会发现，power_gen(power_gen)这个调用展开后正是P(power_gen(power_gen))。也就是说，我们的power_gen(power_gen)就是我们苦苦寻找的不动点了！
铸造Y Combinator
现在我们终于可以铸造我们的Y Combinator了，Y Combinator只要生成一个形如power_gen的lambda函数然后把它应用到自身，就大功告成：
let Y = lambda F.
let f_gen = lambda self. F(self(self))
return f_gen(f_gen)
稍微解释一下，Y是一个lambda函数，它接受一个伪递归F，在内部生成一个f_gen（还记得我们刚才看到的power_gen吧），然后把f_gen应用到它自身（记得power_gen(power_gen)吧），得到的这个f_gen(f_gen)也就是F的不动点了（因为f_gen(f_gen) = F(f_gen(f_gen))），而根据不动点的性质，F的不动点也就是那个对应于F的真正的递归函数！
如果你还觉得不相信，我们稍微展开一下看看，还是拿阶乘函数说事，首先我们定义阶乘函数的伪递归版本：
let Pwr = lambda self n. If_Else n==0 1 n*self(n-1)
让我们把这个Pwr交给Y，看会发生什么（根据刚才Y的定义展开吧）：
Y(Pwr) =>
 let f_gen = lambda self. Pwr(self(self))
 return f_gen(f_gen)
Y(Pwr)的求值结果就是里面返回的那个f_gen(f_gen)，我们再根据f_gen的定义展开f_gen(f_gen)，得到：
Pwr(f_gen(f_gen))
也就是说：
Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen))
我们来看看得到的这个Pwr(f_gen(f_gen))到底是不是真有递归的魔力。我们展开它（注意，因为Pwr需要两个参数，而我们这里只给出了一个，所以Pwr(f_gen(f_gen))得到的是一个单参（即n）的函数）：
Pwr(f_gen(f_gen)) => If_Else n==0 1 n*f_gen(f_gen) (n-1)
而里面的那个f_gen(f_gen)，根据f_gen的定义，又会展开为Pwr(f_gen(f_gen))，所以：
Pwr(f_gen(f_gen)) => If_Else n==0 1 n* Pwr(f_gen(f_gen)) (n-1)
看到加粗的部分了吗？因为Pwr(f_gen(f_gen))是一个接受n为参数的函数，所以不妨把它令成f（f的参数是n），这样上面的式子就是：
f => If_Else n==0 1 n*f(n-1)
完美的阶乘函数！
哥德尔的不完备性定理
了解哥德尔不完备性定理的可以跳到下一节，“大道至简——康托尔的天才”
然而，漫长的Y Combinator征途仍然并非本文的最终目的，对于Y combinator的构造和解释，只是给不了解lambda calculus或Y combinator的读者看的。关键是马上你会看到Y combinator可以由哥德尔不完备性定理证明的一个核心构造式一眼瞧出来！
让我们的思绪回到1931年，那个数学界风起云涌的年代，一个名不经传的20出头的学生，在他的博士论文中证明了一个惊天动地的结论。
在那个年代，希尔伯特的数学天才就像太阳的光芒一般夺目，在关于数学严格化的大纷争中希尔伯特带领的形式主义派系技压群雄，得到许多当时有名望的数学家的支持。希尔伯特希望借助于形式化的手段，抽掉数学证明中的意义，把数学证明抽象成一堆无意义的符号转换，就连我们人类赖以自豪的逻辑推导，也不过只是一堆堆符号转换而已（想起lambda calculus系统了吧：）)。这样一来，一个我们日常所谓的，带有直观意义和解释的数学系统就变成了一个纯粹由无意义符号表达的、公理加上推导规则所构成的形式系统，而数学证明呢，只不过是在这个系统内玩的一个文字游戏。令人惊讶的是，这样一种做法，真的是可行的！数学的意义，似乎竟然真的可以被抽掉！另一方面，一个形式系统具有非常好的性质，平时人们证明一个定理所动用的推导，变成了纯粹机械的符号变换。希尔伯特希望能够证明，在任一个无矛盾的形式系统中所能表达的所有陈述都要么能够证明要么能够证伪。这看起来是个非常直观的结论，因为一个结论要么是真要么是假，而它在它所处的领域/系统中当然应该能够证明或证伪了（只要我们能够揭示出该系统中足够多的真理）。
然而，哥德尔的证明无情的击碎了这一企图，哥德尔的证明揭示出，任何足够强到蕴含了皮亚诺算术系统（PA）的一致（即无矛盾）的系统都是不完备的，所谓不完备也就是说在系统内存在一个为真但无法在系统内推导出的命题。这在当时的数学界揭起了轩然大波，其证明不仅具有数学意义，而且蕴含了深刻的哲学意义。从那时起这一不完备性定理就被引申到自然科学乃至人文科学的各个角落…至今还没有任何一个数学定理居然能够产生这么广泛而深远的影响。
哥德尔的证明非常的长，达到了200多页纸，但其中很大的成分是用在了一些辅助性的工作上面，比如占据超过1/3纸张的是关于一个形式系统如何映射到自然数，也就是说，如何把一个形式系统中的所有公式都表示为自然数，并可以从一自然数反过来得出相应的公式。这其实就是编码，在我们现在看来是很显然的，因为一个程序就可以被编码成二进制数，反过来也可以解码。但是在当时这是一个全新的思想，也是最关键的辅助性工作之一，另一方面，这正是“程序即数据”的最初想法。
现在我们知道，要证明哥德尔的不完备性定理，只需在假定的形式系统T内表达出一个为真但无法在T内推导出（证明）的命题。于是哥德尔构造了这样一个命题，用自然语言表达就是：命题P说的是“P不可在系统T内证明”（这里的系统T当然就是我们的命题P所处的形式系统了），也就是说“我不可以被证明”，跟著名的说谎者悖论非常相似，只是把“说谎”改成了“不可以被证明”。我们注意到，一旦这个命题能够在T内表达出来，我们就可以得出“P为真但无法在T内推导出来”的结论，从而证明T的不完备性。为什么呢？我们假设T可以证明出P，而因为P说的就是P不可在系统T内证明，于是我们又得到T无法证明出P，矛盾产生，说明我们的假设“T可以证明P”是错误的，根据排中律，我们得到T不可以证明P，而由于P说的正是“T不可证明P”，所以P就成了一个正确的命题，同时无法由T内证明！
如果你足够敏锐，你会发现上面这番推理本身不就是证明吗？其证明的结果不就是P是正确的？然而实际上这番证明是位于T系统之外的，它用到了一个关于T系统的假设“T是一致（无矛盾）的”，这个假设并非T系统里面的内容，所以我们刚才其实是在T系统之外推导出了P是正确的，这跟P不能在T之内推导出来并不矛盾。所以别担心，一切都正常。
那么，剩下来最关键的问题就是如何用形式语言在T内表达出这个P，上面的理论虽然漂亮，但若是P根本没法在T内表达出来，我们又如何能证明“T内存在这个为真但无法被证明的P”呢？那一切还不是白搭？
于是，就有了哥德尔证明里面最核心的构造，哥德尔构造了这样一个公式：
N(n) is unprovable in T
这个公式由两部分构成，n是这个公式的自由变量，它是一个自然数，一旦给定，那么这个公式就变成一个明确的命题。而N则是从n解码出的货真价实的（即我们常见的符号形式的）公式（记得哥德尔的证明第一部分就是把公式编码吗？）。”is unprovable in T”则是一个谓词，这里我们没有用形式语言而是用自然语言表达出来的，但哥德尔证明了它是可以用形式语言表达出来的，大致思路就是：一个形式系统中的符号数目是有限的，它们构成这个形式系统的符号表。于是，我们可以依次枚举出所有长度为1的串，长度为2的串，长度为3的串… 此外根据形式系统给出的语法规则，我们可以检查每个串是否是良构的公式（well formed formula，简称wff，其实也就是说，是否符合语法规则，前面我们在介绍lambda calculus的时候看到了，一个形式系统是需要语法规则的，比如逻辑语言形式化之后我们就会看到P->Q是一个wff，而->PQ则不是），因而我们就可以枚举出所有的wff来。最关键的是，我们观察到形式系统中的证明也不过就是由一个个的wff构成的序列（想想推导的过程，不就是一个公式接一个公式嘛）。而wff构成的序列本身同样也是由符号表内的符号构成的串。所以我们只需枚举所有的串，对每一个串检查它是否是一个由wff构成的序列（证明），如果是，则记录下这个wff序列（证明）的最后一个wff，也就是它的结论。这样我们便枚举出了所有的可由T推导出的定理。然后为了表达出”X is unprovable in T”，本质上我们只需说“不存在这样一个自然数S，它所解码出来的wff序列以X为终结”！这也就是说，我们表达出了“is unprovable in T”这个谓词。
我们用UnPr(X)来表达“X is unprovable in T”，于是哥德尔的公式变成了：
UnPr( N(n) )
现在，到了最关键的部分，首先我们把这个公式简记为G(n)——别忘了G内有一个自由变量n，所以G现在还不是一个命题，而只是一个公式，所以谈不上真假：
G(n): UnPr( N(n) )
又由于G也是个wff，所以它也有自己的编码g，当然g是一个自然数，现在我们把g作为G的参数，也就是说，把G里面的自由变量n替换为g，我们于是得到一个真正的命题：
G(g): UnPr( G(g) )
用自然语言来说，这个命题G(g)说的就是“我是不可在T内证明的”。看，我们在形式系统T内表达出了“我是不可在T内证明的”这个命题。而我们一开始已经讲过了如何用这个命题来推断出G(g)为真但无法在T内证明，于是这就证明了哥德尔的不完备性定理[8]。
哥德尔的不完备性定理被称为20世纪数学最重大的发现（不知道有没有“之一”:) ）现在我们知道为真但无法在系统内证明的命题不仅仅是这个诡异的“哥德尔命题”，还有很多真正有意义的明确命题，其中最著名的就是连续统假设，此外哥德巴赫猜想也有可能是个没法在数论系统中证明的真命题。
从哥德尔公式到Y Combinator
哥德尔的不完备性定理证明了数学是一个未完结的学科，永远有需要我们以人的头脑从系统之外去用我们独有的直觉发现的东西。罗杰·彭罗斯在《The Emperor’s New Mind》中用它来证明人工智能的不可实现。当然，这个结论是很受质疑的。但哥德尔的不完备性定理的确还有很多很多的有趣推论，数学的和哲学上的。哥德尔的不完备性定理最深刻的地方就是它揭示了自指（或称自引用，递归调用自身等等）结构的普遍存在性，我们再来看一看哥德尔命题的绝妙构造：
G(n): UnPr( N(n) )
我们注意到，这里的UnPr其实是一个形式化的谓词，它不一定要说“X在T内可证明”，我们可以把它泛化为一个一般化的谓词，P：
G(n): P( N(n) )
也就是说，对于任意一个单参的谓词P，都存在上面这个哥德尔公式。然后我们算出这个哥德尔公式的自然数编码g，然后把它扔给G，就得到：
G(g): P( G(g) )
是不是很熟悉这个结构？我们的Y Combinator的构造不就是这样一个形式？我们把G和P都看成一元函数，G(g)可不正是P这个函数的不动点么！于是，我们从哥德尔的证明里面直接看到了Y Combinator！
至于如何从哥德尔的证明联系到停机问题，就留给你去解决吧:) 因为更重要的还在后面，我们看到，哥德尔的证明虽然巧妙至极，然而其背后的思维过程仍然飘逸而不可捉摸，至少我当时看到G(n)的时候，“乃大惊”“不知所从出”，他怎么想到的？难道是某一个瞬间“灵光一现”？一般我是不信这一说的，已经有越来越多的科学研究表明一瞬间的“灵感”往往是潜意识乃至表层意识长期思考的结果。哥德尔天才的证明也不例外，我们马上就会看到，在这个神秘的构造背后，其实隐藏着某种更深的东西，这就是康托尔在19世纪80年代研究无穷集合和超限数时引入的对角线方法。这个方法仿佛有种神奇的力量，能够揭示出某种自指的结构来，而同时，这又是一个极度简单的手法，通过它我们能够得到数学里面一些非常奇妙的性质。无论是哥德尔的不完备性定理还是再后来丘齐建立的lambda calculus，抑或我们非常熟悉的图灵机理论里的停机问题，其实都只是这个手法简单推演的结果！
大道至简——康托尔的天才
“大道至简”这个名词或许更多出现在文学和哲学里面，一般用在一些模模糊糊玄玄乎乎的哲学观点上。然而，用在这里，数学上，这个名词才终于适得其所。大道至简，看上去最复杂的理论其实建立在一个最简单最纯粹的道理之上。
康托尔在无穷集合和超限数方面的工作主要集中在两篇突破性的论文上，这也是我所见过的最纯粹最美妙的数学论文，现代的数学理论充斥了太多复杂的符号和概念，很多时候让人看不到最本质的东西，当然，不否认这些东西很多也是有用的，然而，要领悟真正的数学美，像集合论和数论这种纯粹的东西，真的非常适合。不过这里就不过多谈论数学的细节了，只说康托尔引入对角线方法的动机和什么是对角线方法。
神奇的一一对应
康托尔在研究无穷集合的时候，富有洞察性地看到了对于无穷集合的大小问题，我们不能再使用直观的“所含元素的个数”来描述，于是他创造性地将一一对应引入进来，两个无穷集合“大小”一样当且仅当它们的元素之间能够构成一一对应。这是一个非常直观的概念，一一对应嘛，当然个数相等了，是不是呢？然而这同时就是它不直观的地方了。对于无穷集合，我们日常的所谓“个数”的概念不管用了，因为无穷集合里面的元素个数本就是无穷多个。不信我们来看一个小小的例子。我们说自然数集合能够跟偶数集合构成一一对应，从而自然数集合跟偶数集合里面元素“个数”是一样多的。怎么可能？偶数集合是自然数集合的真子集，所有偶数都是自然数，但自然数里面还包含奇数呢，说起来应该是二倍的关系不是？不是！我们只要这样来构造一一对应：
1 2 3 4 …
2 4 6 8 …
用函数来描述就是 f(n) = 2n。检验一下是不是一一对应的？不可思议对吗？还有更不可思议的，自然数集是跟有理数集一一对应的！对应函数的构造就留给你解决吧，提示，按如下方式来挨个数所有的有理数：
1/1  1/2  2/1  1/3  2/2  3/1  1/4  2/3 3/2 4/1 …
用这种一一对应的手法还可以得到很多惊人的结论，如一条直线上所有的点跟一个平面上所有的点构成一一对应（也就是说复数集合跟实数集合构成一一对应）。以致于连康托尔自己都不敢相信自己的眼睛了，这也就是为什么他在给戴得金的信中会说“我看到了它，却不敢相信它”的原因。
然而，除了一一对应之外，还有没有不能构成一一对应的两个无穷集合呢？有。实数集合就比自然数集合要“大”，它们之间实际上无法构成一一对应。这就是康托尔的对角线方法要解决的问题。
实数集和自然数集无法构成一一对应？！
我们只需将实数的小数位展开，并且我们假设实数集能够与自然数集一一对应，也就是说假设实数集可列，所以我们把它们与自然数一一对应列出，如下：
1  a10.a11a12a13…
2  a20.a21a22a23…
3  a30.a31a32a33…
4 …
5 …
（注：aij里面的ij是下标）
现在，我们构造一个新的实数，它的第i位小数不等于aii。也就是说，它跟上面列出的每一个实数都至少有一个对应的小数位不等，也就是说它不等于我们上面列出的所有实数，这跟我们上面假设已经列出了所有实数的说法相矛盾。所以实数集只能是不可列的，即不可与自然数集一一对应！这是对角线方法的最简单应用。
对角线方法——停机问题的深刻含义
对角线方法有很多非常奇妙的结论。其中之一就是文章一开始提到的停机问题。我想绝大多数人刚接触停机问题的时候都有一个问题，图灵怎么能够想到这么诡异的证明，怎么能构造出那个诡异的“说停机又不停机，说不停机又停机”的悖论机器。马上我们就会看到，这其实只是对角线方法的一个直接结论。
还是从反证开始，我们假设存在这样一个图灵机，他能够判断任何程序在任何输入上是否停机。由于所有图灵机构成的集合是一个可列集（也就是说，我们可以逐一列出所有的图灵机，严格证明见我以前的一篇文章《图灵机杂思》），所以我们可以很自然地列出下表，它表示每个图灵机分别在每一个可能的输入（1,2,3,…）下的输出，N表示无法停机，其余数值则表示停机后的输出：
     1    2     3    4   …
M1  N    1    N    N   …
M2  2    0     N    0   …
M3  0    1     2    0    …
M4  N    0     5    N   …
…
M1，M2，M3 … 是逐一列出的图灵机，并且，注意，由于程序即数据，每个图灵机都有唯一编码，所以我们规定在枚举图灵机的时候Mi其实就代表编码为i的图灵机，当然这里很多图灵机将会是根本没用的玩意，但这不要紧。此外，最上面的一行1 2 3 4 … 是输入数据，如，矩阵的第一行代表M1分别在1，2，3，…上面的输出，不停机的话就是N。
我们刚才假设存在这样一个图灵机H，它能够判断任何程序在任何输入上能否停机，换句话说，H(i,j)（i是Mi的编码）能够给出“Mi(j)”是N（不停）呢还是给出一个具体的结果（停）。
我们现在来运用康托尔的对角线方法，我们构造一个新的图灵机P，P在1上的输出行为跟M1(1)“不一样”，在2上的输出行为跟M2(2)“不一样”，…总之P在输入i上的输出跟Mi(i)不一样。只需利用一下我们万能的H，这个图灵机P就不难构造出来，如下：
P(i):
if( H(i, i) == 1 ) then // Mi(i) halts
return 1 + Mi(i)
else // if H(i, i) == 0 (Mi(i) doesn’t halt)
    return 0
也就是说，如果Mi(i)停机，那么P(i)的输出就是Mi(i)+1，如果Mi(i)不停机的话，P(i)就停机且输出0。这就保证了P(i)的输出行为跟Mi(i)反正不一样。现在，我们注意到P本身是一个图灵机，而我们上面已经列出了所有的图灵机，所以必然存在一个k，使得Mk = P。而两个图灵机相等当且仅当它们对于所有的输入都相等，也就是说对于任取的n，有Mk(n) = P(n)，现在令n=k，得到Mk(k)=P(k)，根据上面给出的P的定义，这实际上就是：
Mk(k) = P(k) =
1+Mk(k) if Mk(k) halts
0       if Mk(k) doesn’t halt
看到这个式子里蕴含的矛盾了吗？如果Mk(k)停机，那么Mk(k)=1+Mk(k)；如果Mk(k)不停机，则Mk(k)=0（给出结果0即意味着Mk(k)停机）；不管哪种情况都是矛盾。于是我们得出，不存在那样的H。
这个对角线方法实际上说明了，无论多聪明的H，总存在一个图灵机的停机行为是它无法判断的。这跟哥德尔定理“无论多‘完备’的形式化公理系统，都存在一个‘哥德尔命题’是无法在系统内推导出来的”从本质上其实是一模一样的。只不过我们一般把图灵的停机问题称为“可判定问题”，而把数学的称为“可证明问题”。
等等！如果我们把那个无法判定是否停机的图灵机作为算法的特例纳入到我们的H当中呢？我们把得到的新的判定算法记为H1。然而，可惜的是，在H1下，我们又可以相应地以同样的手法从H1构造出一个无法被它（H1）判定的图灵机来。你再加，我再构造，无论你加多少个特例进去，我都可以由同样的方式构造出来一个你无法够到的图灵机，以彼之矛，攻彼之盾。其实这也是哥德尔定理最深刻的结论之一，哥德尔定理其实就说明了无论你给出多少个公理，即无论你建立多么完备的公理体系，这个系统里面都有由你的那些公理出发所推导不到的地方，这些黑暗的角落，就是人类直觉之光才能照射到的地方！
本节我们从对角线方法证明了图灵的停机问题，我们看到，对角线方法能够揭示出某种自指结构，从而构造出一个“悖论图灵机”。实际上，对角线方法是一种有深远影响的方法，哥德尔的证明其实也是这个方法的一则应用。证明与上面的停机问题证明如出一辙，只不过把Mi换成了一个形式系统内的公式fi，具体的证明就留给聪明的你吧:)我们现在来简单的看一下这个奇妙方法的几个不那么明显的推论。
罗素悖论
学过逻辑的人大约肯定是知道著名的罗素悖论的，罗素悖论用数学的形式来描述就是：
R = {X:X不属于X};
这个悖论最初是从康托尔的无穷集合论里面引申出来的。当初康托尔在思考无穷集合的时候发现可以称“一切集合的集合”，这样一个集合由于它本身也是一个集合，所以它就属于它自身。也就是说，我们现在可以称世界上存在一类属于自己的集合，除此之外当然就是不属于自己的集合了。而我们把所有不属于自己的集合收集起来做成一个集合R，这就是上面这个著名的罗素悖论了。
我们来看R是否属于R，如果R属于R，根据R的定义，R就不应该属于R。而如果R不属于R，则再次根据R的定义，R就应该属于R。
这个悖论促使了集合论的公理化。后来策梅罗公理化的集合论里面就不允许X属于X（不过可惜的是，尽管如此还是没法证明这样的集合论不可能产生出新的悖论。而且永远没法证明——这就是哥德尔第二不完备性定理的结论——一个包含了PA的形式化公理系统永远无法在内部证明其自身的一致（无矛盾）性。从而希尔伯特想从元数学推出所有数学系统的一致性的企图也就失败了，因为元数学的一致性又得由元元数学来证明，后者的一致性又得由元元元数学来证明…）。
这里我们只关心罗素是如何想出这个绝妙的悖论的。还是对角线方法！我们罗列出所有的集合，S1,S2,S3 …
    S1  S2  S3 …
S1 0   1  1 …
S2 1   1   0 …
S3 0   0   0 …
…    …
右侧纵向列出所有集合，顶行横向列出所有集合。0/1矩阵的(i,j)处的元素表示Si是否包含Sj，记为Si(j)。现在我们只需构造一个新的0/1序列L，它的第i位与矩阵的(i,i)处的值恰恰相反：L(i) = 1-Si(i)。我们看到，这个新的序列其实对应了一个集合，不妨也记为L，L(i)表示L是否包含Si。根据L的定义，如果矩阵的(i,i)处值为0（也就是说，如果Si不包含Si），那么L这个集合就包含Si,否则就不包含。我们注意到这个新的集合L肯定等于某个Sk（因为我们已经列出了所有的集合），L = Sk。既然L与Sk是同一集合，那么它们肯定包含同样的元素，从而对于任意n，有L(n) = Sk(n)。于是通过令n=k，得到L(k) = Sk(k)，而根据L的定义，L(k) = 1- Sk(k)。这就有Sk(k) = 1-Sk(k)，矛盾。
通过抽象简化以上过程，我们看到，我们构造的L其实是“包含了所有不包含它自身的集合的集合”，用数学的描述正是罗素悖论！
敏锐的你可能会注意到所有集合的数目是不可数的从而根本不能S1,S2…的一一列举出来。没错，但通过假设它们可以列举出来，我们发现了一个与可列性无关的悖论。所以这里的对角线方法其实可以说是一种启发式方法。
同样的手法也可以用到证明P(A)（A的所有子集构成的集合，也叫幂集）无法跟A构成一一对应上面。证明就留给聪明的你了:)
希尔伯特第十问题结出的硕果
希尔伯特是在1900年巴黎数学家大会上提出著名的希尔伯特第十问题的，简言之就是是否存在一个算法，能够计算任意丢番图方程是否有整根。要解决这个问题，就得先严格定义“算法”这一概念。为此图灵和丘齐分别提出了图灵机和lambda calculus这两个概念，它们从不同的角度抽象出了“有效（机械）计算”的概念，著名的图灵——丘齐命题就是说所有可以有效计算出来的问题都可以由图灵机计算出来。实际上我们已经看到，丘齐的lambda calculus其实就是数学推理系统的一个形式化。而图灵机则是把这个数学概念物理化了。而也正因为图灵机的概念隐含了实际的物理实现，所以冯·诺依曼才据此提出了奠定现代计算机体系结构的冯·诺依曼体系结构，其遵循的，正是图灵机的概念。而“程序即数据”的理念，这个发端于数学家哥德尔的不完备性定理的证明之中的理念，则早就在黑暗中预示了可编程机器的必然问世。
对角线方法——回顾
我们看到了对角线方法是如何简洁而深刻地揭示出自指或递归结构的。我们看到了著名的不完备性定理、停机问题、Y Combinator、罗素悖论等等等等如何通过这一简洁优美的方法推导出来。这一诞生于康托尔的天才的手法如同一条金色的丝线，把位于不同年代的伟大发现串联了起来，并且将一直延续下去…
P.S
1. lambda calculus里面的“停机问题”
实际上lambda calculus里面也是有“停机问题”的等价版本的。其描述就是：不存在一个算法能够判定任意两个lambda函数是否等价。所谓等价当然是对于所有的n,有f(n)=g(n)了。这个问题的证明更加能够体现对角线方法的运用。仍然留给你吧。
2. 负喧琐话(http://blog.csdn.net/g9yuayon)是个非常不错的blog:)。g9的文字轻松幽默，而且有很多名人八卦可以养眼，真的灰常…灰常…不错哦。此外g9老兄还是个理论功底非常扎实的牛。所以，anyway，看了他的blog就知道啦！最初这篇文章的动机也正是看了上面的一篇关于Y Combinator的铸造过程的介绍，于是想揭示一些更深的东西，于是便有了本文。
3. 文章起名《康托尔、哥德尔、图灵——永恒的金色对角线》其实是为了纪念看过的一本好书GEB，即《Godel、Escher、Bach-An Eternal Golden Braid》中文译名《哥德尔、埃舍尔、巴赫——集异璧之大成》——商务印书馆出版。对于一本定价50元居然能够在douban上卖到100元的二手旧书，我想无需多说。另，幸福的是，电子版可以找到:)
4. 其实很久前想写的是一篇《从哥德尔到图灵》，但那篇写到1/3不到就搁下了，一是由于事务，二是总觉得少点什么。呵呵，如今把康托尔扯进来，也算是完成当时扔掉的那一篇吧。
5. 这恐怕算是写得最曲折的一篇文章了。不仅自己被这些问题搞得有点晕头转向（还好总算走出来），更因为要把这些东西自然而然的串起来，也颇费周章。很多时候是利用吃饭睡觉前或走路的时间思考本质的问题以及如何表达等等，然后到纸上一气呵成。不过同时也锻炼了不拿纸笔思考数学的能力，呵呵。
6. 关于图灵的停机问题、Y Combinator、哥德尔的不完备性定理以及其它种种与康托尔的对角线之间的本质联系，几乎查不到完整系统的深入介绍，一些书甚至如《The Emperor’s New Mind》也只是介绍了与图灵停机问题之间的联系（已经非常的难得了），google和baidu的结果也是基本没有头绪。很多地方都是一带而过让人干着急。所以看到很多地方介绍这些定理和构造的时候都是弄得人晕头转向的，绝大部分人在面对如Y Combinator、不完备性定理、停机问题的时候都把注意力放在力图理解它是怎么运作的上面了，却使人看不到其本质上从何而来，于是人们便对这些东东大为惊叹。这使我感到很不痛快，如隔靴搔痒般。这也是写这篇文章的主要动机之一。
Reference
[1] 《数学——确定性的丧失》
[2] 也有观点认为函数式编程语言之所以没有广泛流行起来是因为一些实际的商业因素。
[3] Douglas R.Hofstadter的著作《Godel, Escher, Bach: An Eternal Golden Braid》（《哥德尔、艾舍尔、巴赫——集异璧之大成》）就是围绕这一思想写出的一本奇书。非常建议一读。
[4] 《数学——确定性的丧失》
[5] 虽然我觉得那个系徽做得太复杂，要表达这一简洁优美的思想其实还能有更好的方式。
[6] 关于如何在lambda calculus系统里实现“+”操作符以及自然数等等，可参见这里，这里，和这里。
[7] g9的blog（负暄琐话）http://blog.csdn.net/g9yuayon/ 上有一系列介绍lambda calculus的文章（当然，还有其它好文章:)），非常不错，强烈推荐。最近的两篇就是介绍Y combinator的。其中有一篇以javaScript语言描述了迭代式逐步抽象出Y Combinator的过程。
[8] 实际上这只是第一不完备性定理，它还有一个推论，被称为第二不完备性定理，说的是任一个系统T内无法证明这个系统本身的一致性。这个定理的证明核心思想如下：我们前面证明第一不完备性定理的时候用的推断其实就表明 Con/T -> G(g) （自然语言描述就是，由系统T的无矛盾，可以推出G(g)成立），而这个“Con/T -> G(g)”本身又是可以在T内表达且证明出来的（具体怎么表达就不再多说了）——只需要用排中律即可。于是我们立即得到，T里面无法推出Con/T，因为一旦推出Con/T就立即推出G(g)从而推出UnPr(G(g))，这就矛盾了。所以，Con/T无法在T内推出（证明）。
from:http://blog.csdn.net/pongba/article/details/1336028
Free Web Hosting