【 0.1.6函数编程范式 】

1930s初，普林斯顿大学的逻辑学家阿伦佐·丘奇 (Alonzo Church，1903-1995) 开发出了一种新的形式系统(formal system)，即拉姆达运算/演算 (λ-calculus 、lambda calculus ，lambda即希腊字母λ)。由于任何一个可计算函数都能用λ演算来表达和求值，它等价于图灵机。λ演算决定或形成了函数式编程范式。函数式语言的典型代表有Lisp、Scheme、ML、Haskell和Erlang等等，λ演算是函数式编程语言共同的祖先。

 ★函数编程范式的核心观念：以λ表达式构造一切。

什么是λ表达式呢？

普通的数学函数如f(x)=x+1，功能是给其参数x加上1。为了将数学函数表示成计算机程序中常用的表达式，可以换一种写法：λx.( x+1)，读成“对于参数x，x+1”(假定操作符+已经被定义)。丘奇选择了λ，因此各种相关计算称为λ演算。Lambda，λ，仅仅表达的是数学"函数"的概念。

λ表达式极其简洁，由变量、操作符(假定被定义)、两个抽象符号λ和.(即点)，以及括号( )组成。合法的λ表达式的递归定义如下：

• 变量(和文字)是一个λ表达式。
• 操作符和λ表达式组成的表达式，是λ表达式。(可以纳入函数应用)
• 函数定义和函数应用是λ表达式。

各种编程语言，也引入了λ表达式。例如：

C#语言：(x) =>{ return x+1; }

Java语言：(x) ->{ return x+1; }

Scheme语言：(lambda (x) (+ x 1))

1.“归根结底”的含义

使用λ演算，可以对编程的元素进行了全新的描述。例如布尔值、与或非操作的定义，数字的定义等等，如例程0-4所示。布尔值true可以定义为函数T，被描述为在一对值x和y中选择前者，函数T的应用如((T 1) 2)则输出1；数字，参考[5.1.2自然数和丘奇数]中丘奇数的介绍。

当说到“以λ表达式构造一切”这一函数编程范式的核心观念时，是一种“归根结底”的态度，就如同命令思维的人认为：编程语言中的一切元素，归根结底都是0和1。这种归根结底的方式，其实与程序员的日常思考有相当大的距离，因为程序员需要的是true和false的概念（Scheme语言中的#t、#f）、是布尔类型的值。

正如人们习惯了手机、钢笔、书籍、素菜等等东西，当有人说它们归根结底都是原子或波，人们的反应是给他一个大白眼。程序员应该对归根结底的底层知识有大概的了解——需要一开始就知道编程的元素全部由拉姆达运算定义，程序员真正常用的是各种“高级”概念——true和false、int数字等。SICP练习2.6写到：『如果觉得将序对表示为过程还不足以令人如雷灌顶，那么请考虑，在一个可以对过程做各类操作的语言中，我们完全可以没有数』。事实上，((T 1) 2)输出1比没有数更加令人如雷灌顶，对错之分被表示为一个选择函数，不足以令人惊讶吗？

;;;例程 0-4 核心观念远离程序员
;;; 归根结底.rkt
(define T  (lambda (x) (lambda (y) x))   ) ;;; true
((T 1) 2) ;;; 输出1.
(define F  (lambda (x) (lambda (y) y))   );;; false
(define And  (lambda (x) (lambda (y) (x y) F)   ))
((And T) F ) ;;;#<procedure:f> (> 3 2) ;;; 输出 #t,这才是程序员需要的

正如代码都会变成0和1，这和程序员编写C、Java等语言代码又有什么直接关系呢。

因此，当讨论函数编程范式时，通常讨论该范式体现在程序员们眼中的“特征”而非拉姆达运算的语法和语义。例如：

• 数据的不变性。
• 使用递归作为循环的机制。
• 函数没有副作用和引用透明。参考[编程导论(Java )·3.1.2 方法]
• 支持高阶函数(higher-order functions) 和闭包(closures)。参考[2.3高阶函数]
• 支持惰性计算(lazy evaluation)。

2.学习函数式编程，从了解变量开始

3. 函数定义和函数应用

•  函数抽象：W是参数为变量x的λ表达式，则λx.W是λ表达式。这种表达式给出了一个函数的定义：W是函数体，形参就是变量x。
  λx.( x+1)
  λx. λy. ( x+y) ;;;表示 λx. (λy. ( x+y))
•  函数应用：有了f(x)=x+1，自然需要计算f(2)，即给函数一个(实际)参数进行求值。A、B是λ表达式，则 (A B) 也是λ表达式，表示将实参B带入函数A中。

---

下面的内容，将作为学习函数式编程的大图(big map)/鸟瞰图，以便在学习过程中知道自己身在何处。

0.1.1 λ表达式