λ 演算

一般概念

• Alpha Equivalence
  指的是变元的名字无关。例如，$\lambda x.x$ 和 $\lambda y.y$ 等价。但自由变元的名字有关。
• Beta Reduction
  应用函数的过程。例如，$(\lambda x.x)2$ 得到 $2$。
• Currying
  把多元函数写成等价的一元函数形式。例如，$\lambda xy.xy$ 指的是 $\lambda x.(\lambda y.xy)$。
• Combinator 组合子
  不含自由变元的函数。
• Normal form
  无法进一步 beta-reduce 的形式。
• Diverge 发散
  不收敛到 beta normal form 的函数。例如，Omega 组合子 $(\lambda x.xx)(\lambda x.xx)$ 化简完了还是它自己。