lambda(即函数)本身并不是很有趣。这是 JavaScript 中的一个函数:
function id(x) {
return x;
}
这个 JavaScript 程序是做什么的?没有什么。
然而,函数具有可调用的危险特性。
调用时,函数可能会执行以下操作anything(有条件):
authorize_nuclear_attack(launch_codes); // oops
因此,简单来说 lambda 可以潜在地做任何事情。
想想看,每个 C 程序都是一个函数,称为main
.
但是 Aadit,您需要一些其他语言功能来实现 lambda 的主体。
- 您将如何声明、定义、更新和评估变量?
- 如果不使用
if
陈述?
- 如何在没有
for
loop?
- 如果没有排序算子?
- 如何在不使用原语的情况下将两个数字相加
+
操作员?
How?
的确。创建新功能的能力(即lambda 抽象)和调用函数的能力(即拉姆达应用)不足以编写整个程序。
然而,它已经非常接近足够了。
我们唯一的其他语言功能绝对地要求写any程序(我的意思是any程序)是获取变量值的能力(即估值).
所有其他语言功能是:
- 要么是这三个特征之一所固有的。
- 或者可以从这三个特征推导出来。
让我们考虑一下:
-
声明变量的能力是 lambda 抽象所固有的:
function id(x) { // declare variable x
return x; // valuate variable x
}
-
定义变量(并更新可视化递归)的能力是 lambda 应用程序固有的:
id(something); // let x := something in the body of the function id
-
决策权可以从 lambda 抽象中派生出来,可选择的估价:
function boolean_true(then_branch, else_branch) {
return then_branch;
}
function boolean_false(then_branch, else_branch) {
return else_branch;
}
function if_statement(boolean_condition, then_branch, else_branch) {
return boolean_condition(then_branch, else_branch);
}
-
重复的力量可以通过以下方式得出“吃自己的尾巴”如下:
function dragon(dragon) {
return dragon(dragon); // infinite loop
}
dragon(dragon);
我当然指的是衔尾蛇龙:
想象一下,龙像轮子一样永远旋转,试图吃掉自己的尾巴。无限循环。
也可以使用以下命令创建终止循环可选择的估值(又名分支)。
-
排序操作的能力可以通过组合函数来获得:
function substitution(f, g) { // S combinator from SKI combinator calculus
return function (x) {
return f(x, g(x));
};
}
// substitution(f, g) is equivalent to (statement g; statement f)
// where the semicolon is the sequencing operator like in C
-
两个数字相加的幂可以通过将数字编码为函数来导出:
function zero(f, x) { // 0
return x;
}
function add1(n) { // n + 1
return function (f, x) {
return f(n(f, x));
};
}
function add(m, n) { // m + n
return function (f, x) {
return m(f, n(f, x));
};
}
重申一下,创建新功能的权力(即lambda 抽象),调用函数的能力(即拉姆达应用)以及获取变量值的能力(即估值)一起允许您编写可以使用任何其他语言(例如 C 或 Java)编写的所有可能的程序。
Lambda 演算捕捉了可计算性的概念。
这意味着每个算法或半算法都可以用 lambda 演算来表达(即每个可以解决的问题的解或每个可以部分解决的问题的部分解都可以用 lambda 演算来表达)。
看起来 lambda 几乎可以用于任何事情(即使它看起来更复杂),但它确实有其局限性。
lambda 演算的唯一限制是您无法表达没有解决方案(甚至不是部分解决方案)的问题的解决方案。这种问题的一个例子是,“给定一个程序P
does P
停止所有输入?”
也就是说,不可能写出一个函数H
这样H(P) = true
if P
停止所有输入,并且H(P) = false
否则。如果您确实编写了该函数H
那么对于以下程序来说它总是不正确的:
function P(x) {
return H(P) ? P(x) : x;
}
If H
认为P
然后总是停止P
进入无限循环。
If H
认为P
并不总是停止然后它总是停止。
lambda 未涵盖哪些用例?
lambda 演算未涵盖的唯一用例是能够计算不可计算的函数。然而,由于不可计算的函数有点不可计算的我想说,没有任何用例是 lambda 演算所涵盖的。
话虽这么说,没有人使用 lambda 演算来进行任何实际编程(就像没有人使用图灵机作为实际计算机一样)。 lambda 演算和图灵机的能力是相等的。然而,它们是非常不同的野兽。
大多数命令式编程语言(例如 C 和 Java)都基于图灵机。大多数函数式编程语言(例如 Haskell 和 OCaml)都基于 lambda 演算。一个好的程序员是其中一个方面的专家,但不是另一个方面的专家。优秀的程序员对两者都感到满意。