哪些语言特性不能用 lambda 定义？

Question

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

lambda 没有涵盖哪些用例？

Answer 1

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

function id(x) {
    return x;
}

这个Java脚本程序是做什么的？没有。

但是，函数具有被调用的危险属性。

调用时，函数可能会做任何事情（条件适用）：

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);
```
当然是指衔尾蛇龙了：

想象一下龙像轮子一样永远旋转，试图吃掉自己的尾巴。无限循环。

也可以使用选择性估值（a.k.a。分支）创建终止循环。

顺序操作的力量可以通过组合函数得到：

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 应用程序）和获取变量值的能力（即 valuation）一起允许你编写任何可能的程序，你可以使用任何其他语言（如 C 或 Java）编写。

Lambda 演算抓住了可计算性的概念。

这意味着每个算法或 semi-algorithm 都可以用 lambda 演算表示（即每个可以解决的问题的解决方案或每个可以部分解决的问题的部分解决方案可以表示为lambda 演算）。

It seems like lambda can be used for almost anything (even if it seems more complicated), but it does have its limitations.

lambda 演算的唯一限制是您无法表达没有解决方案（甚至部分解决方案）的问题的解决方案。这种问题的一个例子是，“给定一个程序 P 是否 P 在所有输入上停止？”

换句话说，不可能编写一个函数 H 使得 H(P) = true 如果 P 停止所有输入，而 H(P) = false 否则。如果您确实设法编写了函数 H，那么它对于以下程序总是不正确的：

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

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

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

What are some use cases not covered by lambda?

lambda 演算未涵盖的唯一用例是能够计算不可计算的函数。但是，因为不可计算的函数有点 不可计算 我会说没有不被 lambda 演算涵盖的用例。

也就是说，没有人使用 lambda 演算来进行任何实际编程（就像没有人将图灵机用作实际计算机一样）。 lambda 演算和图灵机在功能上是相等的。然而，它们是非常不同的野兽。

大多数命令式编程语言，如 C 和 Java 都是基础语言d 在图灵机上。 Haskell 和 OCaml 等大多数函数式编程语言都基于 lambda 演算。一个好的程序员是其中任何一个方面的专家，而不是另一个方面的专家。一个伟大的程序员对两者都很满意。

哪些语言特性不能用 lambda 定义？

What language features can't be defined in terms of lambda?

lambda

language-features

functional-programming

language-design

怎么办？