λ演算

姜智浩 Lv4
  2025-04-01 11:45:14 2025-04-01 11:45:14 Created   2025-04-01 09:27:02 2025-04-01 09:27:02 Updated      2.6k Words  10 Mins  

在B站看到了有人讲解λ演算 很感兴趣 于是去了解了一下
原视频：https://www.youtube.com/watch?v=RcVA8Nj6HEo&t=44s
原视频很精彩 图文描述 我也是看了这个视频写的 推荐观看

什么是λ演算

λ演算（Lambda Calculus）是一种用于研究函数定义、函数应用和递归的数学逻辑系统 由阿隆佐·丘奇（Alonzo Church）在 1930 年代提出。它是计算理论的基础之一 并在编程语言的设计中发挥了重要作用 特别是对函数式编程语言（如 Haskell、Lisp 和 ML）有深远的影响

诶 这里学过python的人肯定想到了 python中有个lambda表达式 是不是和这个λ演算相关呢
没错 Python 中的 lambda 表达式确实与 λ（Lambda）演算有关系 但它只是 λ演算的一个简单应用 并没有完全实现 λ演算的全部概念 这里不过多叙述 只是告诉大家他们之间确实有关系

λ演算的基本概念

λ演算由三种基本表达式组成：

  • 变量：例如 x、y，代表某个值。
  • λ抽象（Lambda Abstraction）：用于定义匿名函数，例如 λx.x+1 表示“输入 x，返回 x+1”
  • 函数应用（Function Application）：用于调用函数，例如 (λx.x+1) 2，表示将 2 代入 λx.x+1，结果为 3

λ表达式

在λ演算中 主要有三类样式：

  • 括号：()
  • 变量：x, y, z…
  • “λ”和”.”:λ和.总是成对出现

这样 我们就有了三个模版：

  • (_ _)
  • a
  • (λa._)

这里的下划线可以填入上述任意模块 a是一个变量 我们可以像搭积木一样进行构造
例如：
((λa.y)(λx.(λc.e)))
并且 这些变量也可以是一个函数

结合代码理解

上述的a其实就是一个变量 并且他也可以看成一个函数
现在我们重点看看( _ _ ) 和 ( λa._ )

(_ _)可以理解为

1
2
3
4
5
6
7
8
9
10
#以(ab)为例
#将左边的a看成一个函数
#右边的b就是这个函数a的输入

#为了方便理解 我们定义一个函数 叫a
def a(x):
    return y

#先别管变量output 右边的a(b)等价于λ演算中的(ab)
output = a(b)

(λa._)可以理解为

1
2
3
#以(λx.y)为例
def fun(x):
    return y

这些就是λ表达式的内容

λ图

有很多种可视化λ图

  1. Tromp图表：https://tromp.github.io/cl/diagrams.html
  2. David C Keenan的λ演算图形符号：https://dkeenan.com/Lambda/
  3. de Bruijn索引：https://en.wikipedia.org/wiki/De_Bruijn_index
  4. Vex（Wayne Citrin，Richard Hall，Benjamin Zorn）：https://www.researchgate.net/publication/2726047_Programming_with_Visual_Expressions
  5. 视觉λ演算（Viktor Massalõgin）：https://github.com/bntre/visual-lambda

λ演算的计算规则

λ演算主要有三个计算规则：

  1. α-变换（Alpha Conversion）
  2. β-规约（Beta Reduction）
  3. η-变换（Eta Conversion）

α-变换（Alpha Conversion）

简单来说就是变量重命名

λx.x = λy.y

只要不影响表达式的意义 就可以更改变量名称 就像你可以随意地取变量名

β-规约

函数应用的计算
我们来看这样的一个式子：

((λx.x+2)3)

根据前文的理解
我们逐步进行分析
首先来看内层的(λx.x+2)
这个意思相当于是 我们定义个一个函数叫x 函数的返回值是x + 2

1
2
3
#(λx.x+2)
def x(x):
    return x + 2

接下来我们看外层 还记得前面说的

引用

以(ab)为例
将左边的a看成一个函数
右边的b就是这个函数a的输入

现在把刚才的(λx.x+2)看成a 把3看成b

于是 ((λx.x+2)3)就可以用python写成

1
2
3
4
def x(x):
    return x + 2
    
output = x(3)

其用数学符号就是

3 + 2

综上 ((λx.x+2)3)等价于 3 + 2

η-变换

函数等价转换
先给出定义

λx.fx 等价于 f

只要 f 在所有输入 x 上都保持不变 那么 λx. f x 和 f 是等价的
什么意思呢
以f(x) = x + 3为例

假设有f(x) = x + 3
在 λ 形式下 他可以表示为

f = λx. x + 1

那么 λx.fx 等价于 f 即

λx. (λx. x + 1) x ≡ λx. x + 1

自由变量与束缚变量

定义

  • 束缚变量（Bound Variable）
    如果一个变量 x 出现在 λx.M 这样的函数定义中 并且 x 是由 λx 绑定的 则 x 是束缚变量
    简单理解：变量被 λ 绑定 就称为束缚变量

  • 自由变量（Free Variable）
    如果一个变量 x 在 λ 表达式中出现 但没有被任何 λ 绑定 则 x 是自由变量
    简单理解：变量没有被 λ 绑定 它就是自由变量

自由变量

1
λx. y  // 变量 y 是自由变量

束缚变量

1
λx. x  // 变量 x 是束缚变量

组合子

在λ演算中，组合子（Combinator） 是指 没有自由变量 的 λ 表达式 也就是说 组合子是 只包含束缚变量 的 λ 表达式 它们是纯粹的函数抽象 不依赖于外部环境 因此它们可以被认为是“自给自足”的函数

组合子 之所以叫这个名字 是因为它们不依赖外部的变量或环境 只能依赖自己定义的参数 并且可以通过组合多个组合子来构建复杂的计算 组合子本质上是 λ 演算中的基础构建模块 类似于函数式编程中的高阶函数

恒等组合子

恒等组合子就是一个接受一个参数并返回这个参数的组合子 它的定义非常简单：

1
I = λx. x

作用：恒等组合子返回输入参数本身 不做任何改变

I 5 → 5

K 组合子

K 组合子（又叫 K 函数或常量函数）接受两个参数 但只返回第一个参数 它的定义是：

1
K = λx. λy. x

作用：返回第一个参数 忽略第二个参数

K 5 10 → 5

在这个例子中 K 5 返回的是一个函数 λy. 5 再与任何第二个参数（比如 10）结合时 结果依然是 5

S 组合子

S 组合子（又叫 S 函数）比较复杂 接受三个参数 并执行一些组合操作 它的定义如下：

1
S = λx. λy. λz. (x z) (y z)

作用：S 组合子将输入的两个函数 x 和 y 应用于相同的参数 z 并将结果作为两个函数的输出

S (λx. x + 1) (λx. x * 2) 3 → (λx. x + 1) 3 (λx. x * 2) 3
→ 3 + 1 3 * 2
→ 4 6

S 组合子可以用于组合多个函数，使得它们的输入可以共享。

组合子的性质

组合子通常具有一些有用的性质 它们可以与其他组合子进行组合 以实现更加复杂的计算 几个重要的性质包括：

  1. 函数应用
    组合子是纯粹的 λ 演算表达式 它们的行为仅依赖于传入的参数 可以通过函数应用来将它们的计算结果传递给其他组合子 进一步构建复杂的计算

  2. 无外部依赖
    组合子是完全自足的 它们的定义仅依赖于它们自己内部的参数 不需要从外部环境引入其他变量 这使得它们在编程语言和计算机科学中非常重要 尤其是在函数式编程中

  3. 高阶函数
    组合子本质上是高阶函数（Higher-Order Function）它们可以作为输入传递给其他函数 或者返回作为结果 例如，S 组合子通过两个输入函数生成新的函数 具有高度的抽象能力

λ演算的作用

说了这么多 大家应该会进行一些关于λ演算的计算了 可λ演算有什么用呢 感觉就是换个抽象的形式进行计算
其实λ演算本质上是换了一种抽象的方式来进行计算 但它的意义远不止于此

计算理论的基础

λ演算与图灵机（Turing Machine）一样 是计算理论的两大核心模型之一 它们都能表达可计算函数 但λ演算采用的是纯粹的函数变换 而图灵机基于状态和存储

  • 通过 λ演算 可以定义所有可计算的函数 因此它是图灵完备的
  • 计算机科学家用它来研究可计算性、算法复杂度等问题

影响现代编程语言

λ演算是函数式编程的理论基础 影响了 Haskell、Lisp、ML、Scala、JavaScript（匿名函数、箭头函数）、Python（Lambda 表达式）等编程语言 例如

  • 匿名函数（Lambda 表达式）
1
2
add = lambda x, y: x + y
print(add(2, 3))  # 输出 5
  • 高阶函数（函数可以作为参数传递）
1
2
3
4
def apply_func(f, x):
    return f(x)

print(apply_func(lambda x: x * 2, 10))  # 输出 20

现代语言的 闭包（Closure）、惰性求值、纯函数 等概念都源于 λ演算

形式化数学 & 逻辑推理

λ演算被用作数学逻辑的基础，特别是在构造主义数学和类型理论中。例如：

  • Curry-Howard 对应：λ演算中的函数和逻辑推理中的证明之间存在对应关系 程序可以被视为数学证明
  • 依赖类型（Dependent Types）：Coq、Agda 这些数学证明工具都基于λ演算的扩展形式

递归与无变量编程

λ演算能够表示 递归，即使它本身没有显式的循环结构。例如，阶乘可以用 Y 组合子（Y Combinator）来实现：

1
2
factorial = \f. \n. if n == 0 then 1 else n * (f (n - 1))
Y factorial 5   -- 计算 5!

编译器优化

λ演算提供了转换和简化代码的规则 例如：

  • β-规约（函数应用） 可以减少计算步骤 优化执行效率
  • α-变换（变量重命名） 可避免变量名冲突
  • η-变换（函数简化） 可以减少不必要的函数包装 提高性能

许多编译器（如 GHC Haskell、Scala、Lisp 解释器）都会用 λ演算作为中间表示（IR）帮助优化代码

并发 & 分布式计算

λ演算的无状态特性使其非常适用于并发计算和分布式系统 例如：

  • MapReduce（Google 的大规模数据处理模型）依赖于 λ演算的映射与归约思想
  • Actor Model（Erlang、Akka）与函数式编程紧密相关 受λ演算启发
  • Title: λ演算
  • Author: 姜智浩
  • Created at : 2025-04-01 11:45:14
  • Updated at : 2025-04-01 09:27:02
  • Link: https://super-213.github.io/zhihaojiang.github.io/2025/04/01/20250401λ演算/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
λ演算
  1. 什么是λ演算
  2. λ演算的基本概念
    1. λ表达式
    2. 结合代码理解
  3. λ图
  4. λ演算的计算规则
    1. α-变换（Alpha Conversion）
    2. β-规约
    3. η-变换
  5. 自由变量与束缚变量
    1. 自由变量
    2. 束缚变量
  6. 组合子
    1. 恒等组合子
    2. K 组合子
    3. S 组合子
    4. 组合子的性质
  7. λ演算的作用
    1. 计算理论的基础
    2. 影响现代编程语言
    3. 形式化数学 & 逻辑推理
    4. 递归与无变量编程
    5. 编译器优化
    6. 并发 & 分布式计算