什么语言功能不能用lambda来定义？ [英] What language features can't be defined in terms of lambda?
问题描述
有些用例不是由lambda覆盖？
lambda（即函数）本身并不是很有趣。以下是JavaScript中的一个函数：
function id（x）{return x; }
这个JavaScript程序做了什么？没有。
但是，函数具有可调用的危险性。
调用时，函数可能会潜在
// oops因此，一个lambda可以潜在地做任何事情。 / p>
想想看，每个C程序都是一个名为 main 的函数。
但是Aadit，您需要一些其他语言功能来实现lambda体。
- 如何声明，定义，更新和评估变量？
- 如果语句不使用
/ li>循环，您将如何重复一段代码任意次数而不是
- 对于
？ - 如何在不使用序列运算符的情况下编写连续的代码块？
- 如何在不使用基元
的情况下添加两个数字？ +运算符
如何？
确实。创建新功能（即 lambda abstraction ）和调用函数（即
然而，它已经足够接近了。
我们完全唯一需要的其他语言功能写任何程序（我的意思是任何程序）是获取变量值的权力（即估值）。
>其他语言功能为：
- 这三种功能中的一种固有功能。 / li>
- 或者可以从这三个功能派生出来。
让我们考虑一下：
-
声明变量的权力是lambda抽象中固有的： b
$ bfunction id（x）{//声明变量x
return x; //赋值变量x
}
-
定义变量viz-a-viz递归）在lambda应用程序中是固有的：
$ bid（something）; //让x：=函数id中的某些东西
-
可以从lambda抽象和选择性估值派生出决策：
$ b函数boolean_true（then_branch，else_branch）{
return then_branch;
}
函数boolean_false（then_branch，else_branch）{
return else_branch;
函数if_statement（boolean_condition，then_branch，else_branch）{
返回boolean_condition（then_branch，else_branch）;
}
-
可以通过吃你自己的尾巴，如下所示：
$ bfunction dragon（dragon）{
回龙（龙）; //无限循环
}
龙（龙）;
我当然指的是ouroboros龙：
想象一下，龙永远像一个轮子一样旋转，试图吃自己的尾巴。无限循环
也可以使用选择性估值（又称分支）创建终止循环。
-
顺序操作的能力可以通过合成函数来派生：
返回函数（x）{
return f（x，g（x））;
};
}
//替换（f，g）等价于（语句g;语句f）
//其中分号是序列运算符，如C
-
添加两个数字的功能可以通过将数字编码为函数来获得：
function zero（f，x）{// 0
return x;
函数add1（n）{// n + 1
返回函数（f，x）{
return f（n（f，x）） ;
};
函数add（m，n）{// m + n
返回函数（f，x）{
return m（f，n（f ， X））;
};
}
重申，创建新函数的权力（即 lambda abstraction ），调用函数的权力（即 lambda application ）和获取变量值的权力（即评估）一起允许您编写可以使用任何其他语言（例如C或Java）编写的每个可能的程序。
$ b
Lambda演算捕获这意味着每个算法或半算法都可以在lambda演算中表达出来（即每个可以解决的问题的解决方案）或者可以部分解决的每个问题的部分解决方案可以在lambda演算中表达）。
似乎可以使用lambda几乎任何东西（即使它看起来更复杂），但它有其局限性。
lambda演算的唯一限制是Ť你不能为没有解决方案的问题表达解决方案（甚至不是部分解决方案）。这样一个问题的一个例子是，给定程序 P 是否 P 在所有输入上暂停？换句话说，写一个函数 H 是不可能的，例如<$
$ b
c $ c> H（P）= true 如果 P 所有输入都暂停，并且 H（P）= false 否则。如果您设法编写函数 H ，那么对于以下程序它总是不正确的：
function P（x）{
return H（P）？ P（x）：x;
$ / code> 如果 H 认为 P 总是暂停，然后 P 进入无限循环。
如果 H 认为 P 并不总是停止，那么它总是会暂停。
lambda不包含哪些用例？
只有lambda演算未涵盖的用例才能够计算未计算的函数。但是，因为uncomputable函数有点不可用 ，所以我会说lambda演算中没有包含任何用例。
话虽如此，没有人使用lambda演算来做任何实际的编程（就像没有人使用图灵机作为实际的计算机一样）。 lambda微积分和图灵机在功率上都是相等的。然而，它们是完全不同的野兽。
大多数命令式编程语言（如C和Java）都基于图灵机。大多数函数式编程语言，如Haskell和OCaml都基于lambda演算。一个好的程序员是任何一个人的专家，但不是其他人。一位优秀的程序员对两者都很满意。
It seems like lambda can be used for almost anything (even if it seems more complicated), but it does have its limitations.
What are some use cases not covered by lambda?
A lambda (i.e. a function) by itself is not very interesting. Here's a function in JavaScript:
function id(x) {
return x;
}
What does this JavaScript program do? Nothing.
However, functions have a dangerous property of being invokable.
When invoked, a function can potentially do anything (conditions apply):
authorize_nuclear_attack(launch_codes); // oops
Hence, trivially a lambda can potentially do anything.
Think about it, every C program is a function called main.
But Aadit, you would need some other language feature to implement the body of a lambda.
- How would you declare, define, update and valuate variables?
- How would you make decisions without using an
ifstatement? - How would you repeat a block of code an arbitrary number of times without a
forloop? - How would you write a sequential block of code without a sequencing operator?
- How would you add two numbers without using a primitive
+operator?
How?
Indeed. The power to create new functions (i.e. lambda abstraction) and the power to invoke functions (i.e. lambda application) is not enough to write entire programs.
However, it's pretty darn close to enough.
The only other language feature that we absolutely require to write any program (and I do mean any program) is the power to get the value of a variable (i.e. valuation).
Every other language feature is:
- Either inherent in one of these three features.
- Or can be derived from these three features.
Let's consider:
The power to declare variables is inherent in lambda abstraction:
function id(x) { // declare variable x return x; // valuate variable x }The power to define variables (and update viz-a-viz recursion) is inherent in lambda application:
id(something); // let x := something in the body of the function idThe power to make decisions can be derived from lambda abstraction and selective valuation:
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); }The power to repeat can be derived by “eating your own tail” as follows:
function dragon(dragon) { return dragon(dragon); // infinite loop } dragon(dragon);I am of course referring to the ouroboros dragon:
Imagine the dragon spinning like a wheel forever, trying to eat its own tail. An infinite loop.
It's also possible to create a terminating loop using selective valuation (a.k.a. branching).
The power to sequence operations can be derived by composing functions:
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 CThe power to add two numbers can derived by encoding numbers as functions:
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)); }; }
To reiterate, the power to create new function (i.e. lambda abstraction), the power to invoke functions (i.e. lambda application) and the power to get the value of a variable (i.e. valuation) together allow you to write every possible program that you can write using any other language such as C or Java.
Lambda calculus captures the notion of computability.
This means that every algorithm or semi-algorithm can be expressed in the lambda calculus (i.e. the solution of every problem that can be solved or the partial solution of every problem that can be partially solved can be expressed in the lambda calculus).
It seems like lambda can be used for almost anything (even if it seems more complicated), but it does have its limitations.
The only limitation of the lambda calculus is that you can't express solutions to problems for which there are no solutions (not even partial solutions). An example of such a problem is, “given a program P does P halt on all inputs?”
In other words, it is impossible to write a function H such that H(P) = true if P halts on all inputs, and H(P) = false otherwise. If you do manage to write the function H then it would always be incorrect for the following program:
function P(x) {
return H(P) ? P(x) : x;
}
If H thinks that P always halts then P goes into an infinite loop.
If H thinks that P doesn't always halt then it always halts.
What are some use cases not covered by lambda?
The only use case not covered by the lambda calculus is being able to compute uncomputable functions. However, because uncomputable functions are a tad bit uncomputable I would say that there are no use cases which are not covered by the lambda calculus.
That being said, nobody uses the lambda calculus to do any actual programming (just like nobody uses a Turing machine as an actual computer). Both the lambda calculus and Turing machines are equal in power. However, they are very different beasts.
Most imperative programming languages like C and Java are based on the Turing machine. Most functional programming languages like Haskell and OCaml are based on the lambda calculus. A good programmer is an expert at either one but not the other. A great programmer is comfortable with both.
这篇关于什么语言功能不能用lambda来定义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
