lambda - 无法使用lambda定义哪些语言功能？

Question

似乎lambda几乎可以用于任何事物（即使看起来更复杂），但它确实有其局限性。

lambda未涵盖哪些用例？

Answer 1

一个lambda（即一个函数）本身并不是很有趣。这是JavaScript中的函数：

function id(x) {
    return x;
}

此JavaScript程序做什么？没有。

但是，功能具有可调用的危险特性。

调用后，函数可能会做任何事情（有条件的情况下）：

authorize_nuclear_attack(launch_codes); // oops

因此，琐碎的lambda可以做任何事情。

考虑一下，每个C程序都是一个称为main的函数。

但是Aadit，您需要其他一些语言功能来实现lambda的主体。


您将如何声明，定义，更新和评估变量？
在不使用if语句的情况下如何做出决定？
您如何在没有for循环的情况下任意重复代码块？
没有排序运算符，您将如何编写顺序代码块？
如何在不使用原始+运算符的情况下将两个数字相加？


怎么样？

确实。创建新函数（即lambda抽象）的能力和调用函数（即lambda应用程序）的能力不足以编写整个程序。

但是，这足够接近了。

我们绝对需要编写任何程序（我的意思是任何程序）的唯一其他语言功能是获得变量值（即估值）的能力。

其他所有语言功能包括：


这三个功能之一固有的。
或者可以从这三个功能中派生。


让我们考虑一下：


声明变量的能力是lambda抽象所固有的：

function id(x) { // declare variable x
    return x;    // valuate variable x
}

定义变量（和更新viz-a-viz递归）的能力是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抽象），调用函数的能力（即lambda应用程序）和获取变量值的能力（即评估）一起使您可以编写所有可能的程序。使用任何其他语言（例如C或Java）编写。

Lambda微积分捕捉了可计算性的概念。

这意味着可以在lambda演算中表达每种算法或半算法（即可以在lambda演算中表达可以解决的每个问题的解决方案或可以部分解决的每个问题的部分解决方案）。


似乎lambda几乎可以用于任何事物（即使看起来更复杂），但它确实有其局限性。


lambda演算的唯一局限性在于，您无法针对没有解决方案的问题（甚至不是部分解决方案）表达解决方案。这样的问题的一个示例是：“给定程序P P是否在所有输入上都停止了？”

换句话说，如果H停止所有输入，而H(P) = true停止，则无法编写P这样的函数。如果您确实编写了函数H(P) = false，则对于以下程序它将总是不正确的：

function P(x) {
    return H(P) ? P(x) : x;
}

如果H认为H总是停止，则P进入无限循环。

如果P认为H并不总是停止，那么它总是会停止。


lambda未涵盖哪些用例？


Lambda演算未涵盖的唯一用例是能够计算不可计算的函数。但是，由于不可计算的功能有点不可计算，我要说的是，没有lambda演算未涵盖的用例。

话虽如此，没有人使用lambda演算来进行任何实际编程（就像没有人将Turing机器用作实际计算机一样）。拉姆达演算和图灵机的功率相等。但是，它们是完全不同的野兽。

大多数命令式编程语言（例如C和Java）都基于Turing机器。大多数功能编程语言（例如Haskell和OCaml）都基于lambda演算。一个好的程序员在任何一个方面都是专家，而不是另一个。优秀的程序员对这两者都很满意。