λ (Lambda)

什么是函数式编程？

函数式编程是一种计算机编程范式，它依赖于模仿数学上的函数。函数式编程本质上是组合各种表达式，表达式包括一些值，变量和函数，函数会应用一些输入参数，然后会进行一些计算，一般会有返回值，函数式编程语言是基于 lambda 演算的。

函数的透明引用(Referential transparency):对于同一个函数，给它相同的参数，然后同样的返回值，表现的像数学上的函数一样。

什么是函数？

如果不用lambda这个词，可能大概知道函数是什么了。函数会用入参和返回值，函数定义了它的入参是什么，然后它的返回值是什么，例如一个加法函数(add)，有两个入参，有一个和的返回值。又例如我们有一个函数名为 f,有下面如下关系：

f(1) = A
f(2) = B
f(3) = C

输入的参数的集合是 {1, 2, 3}, 输出的集合的参数是 {A, B, C}, 一个重点是这些关系是怎么定义的，假设当入参是 1 的时候，函数的返回值一定是 A, 而不会出现 f(1) = X 或 f(1) = Z 这些情况。在前面提到的透明引用，当一个函数有相同的入参，返回值一定是相同的。下面的情况也是满足的，因为对于相同的入参，返回值是确定的，只不过是它们返回值刚好相同了

f(1) = A
f(2) = A
f(3) = A

lambda 结构

lambda 含有：表达式(expression)， 变量 和 抽象（abstraction）。expression 可以和变量和抽象，或者它们的组合。expression 可以是变量，这个变量有个名称，但是可以是函数的名称

abstractions 有两部分，head 和 body, head 是 λ(lambda),接着是变量名，body 是函数的其他表达式，如下:

λx.x

lambda λx.x 没有名字，它是一个匿名函数

ch1_1.png

α 等价 (Alpha equivalence)

这里的变量 x 没有什么特别的意思，它就是一个表示，可以替换成 y 或者 z, 它们都是同一个函数的，这里称这种为 α 等价

λx.x
λy.y
λz.z

β 化简 (Beta reduction)

当函数应用入参的时候，会把入参的表达式替换 body 内相应的值，消除 head 相关的入参，提供一个绑定变量的作用，这个过程称为 β 化简，例如

𝜆x.x

进行 β 化简，应用 2 替换 x，得到

(𝜆x.x)2
      2

Free variables

y 在 body 内，但是没有出现在 head 中，进行参数绑定，y 称为 Free variables

(𝜆𝑥.𝑥𝑦)𝑧
zy

Combinators

body 内出现的变量，在 head 参数中都出现过。就是 Combinators

最后

• 函数式编程基于表达式，它们可以包含变量，常量值，表达式组合其他表达式和函数
• 函数有 head body，表达了它需要的参数，和如何进行计算，返回结果
• 入参变量作为参数替换 body 出现位置相关的地方。都会生成同一个值
• 函数有一个或多个入参或返回值
• 函数把入参映射到返回值，对于同一个入参有相同返回值
• lambda 形如匿名函数 (𝜆𝑥.𝑥 + 1)
• lambda 演算是表达程序的抽象过程和应用

参考

• Raul Rojas. A Tutorial Introduction to the Lambda Calcu- lus
  http://www.inf.fu- berlin.de/lehre/WS03/alpi/lambda.pdf
• Haskell