lambda演算
根据*，lambda演算（英语：lambda calculus，λ-calculus）是一套从数学逻辑中发展，以变量绑定和替换的规则，来研究函数如何抽象化定义、函数如何被应用以及递归的形式系统。
lambda项
lambda演算由 lambda 项的语言构成。基本的 lambda 项只包含以下三种：
| 语法 | 名称 | 描述 | Haskell语言中的相应表述 |
|---|---|---|---|
| a | 变量 | 表示参数或数学/逻辑值的字符或字符串 | a |
| (λx.M) | 抽象化 | 函数定义（M是一个lambda项）。 变量x在表达式中已被绑定。 |
(\x -> M) |
| (M N) | 应用 | 将函数应用于参数。 M 和 N 是 lambda 项。 | (M N) |
- 作为 lambda 项的变量无须声明
- lambda 抽象化是一种匿名函数的定义。
- lambda 应用即函数调用。
- 括号可以改变语义。
λx.((λx.x)x)的含义是\x -> ((\x -> x) x)，即整体是一个函数定义。(λx.(λx.x))x的含义是(\x -> (\x -> x)) x，即整体是一个函数应用。
两者的最终结果都是(λx.x)，即(\x -> x)，但是语义不同。
lambda演算
(λf.f 3)(λx.x+2) = (λx.x + 2) 3 = 3 + 2
(λx.λy.x - y) 7 2 = (λy.7 - y) 2 = 7 - 2
Haskell
(\f -> f 3)(\x -> x + 2) = (\x -> x + 2) 3 = 3 + 2
(\x -> \y -> x - y) 7 2 = (\y -> 7 - y) 2 = 7 - 2
Ω 与 Y 组合子
ω := λx.x x
Ω := ω ω
Y := λg.(λx.g (x x)) (λx.g (x x))