哪种函数式编程语言最接近Lambda演算？

Question

哪种函数式编程语言在代码外观、感觉和行为上最接近于 λ演算的抽象？

- melwasul

---

我投票关闭此问题，因为这是主观的... - home

当然，这取决于您的要求，但我认为除非您的目标是学习λ演算（在这种情况下，您可能应该使用更直接的λ演算实现，而不是“真正”的编程语言），否则这并不重要。我也想听听关于这个问题的意见。 - sepp2k

@sepp2k：我的困境是这样的：我听说lc有多么重要，以及它是FP的根基，但当我尝试学习FP语言x、y、z时，它们似乎都避免直接与正式的lc进行比较。对于一个初学者来说，这很令人困扰和困惑。 - melwasul

@melwasul 只需学习您想要学习的语言即可。λ演算在创建函数式语言方面发挥了重要作用（因为它是灵感来源），但是，一个语言与LC的亲近程度不应成为选择要学习的编程语言的标准。 - sepp2k

我正在学习《小型计算机程序》并尝试将函数（例如p 132 insert-g）一边学习一边翻译成λ抽象。我看到了相似之处，想知道其他的FP语言是否也可以被翻译成lc。但是像Don Stewart（和其他人）所说的那样，当需要完成真实世界的任务时，FP语言会离开基本的λ演算，并不总是希望使用递归数学的整个Peano风格来编写GUI接口等。 - melwasul

当您希望硬件高效执行数学运算时，Peano风格并不适合。将CPU视为常见Lambda演算函数的硬件加速器。 - Don Stewart

Answer 1

这可能不是一个真正的答案，更像是对你实际想要什么的猜测。

通常，在λ演算中很少需要使用内容 - 你基本上只需要（一等）函数、函数应用和变量。现在，你很难找到一种不提供这些东西的语言...然而，当你试图学习它时，事情可能会变得混乱 - 例如，使用普通数字然后将它们与教堂数混淆非常容易。（我见过许多学生遇到这种情况，适应这种材料所需要的形式思维已经足够困难，将编码加入其中并不能真正帮助...）

正如Don所说，Scheme与“普通”的无类型λ演算非常接近，如果您正在学习《The Little Schemer》，那么它可能非常适合您。如果您真的想使用“正确”的LC，则需要确保仅使用函数（以上述问题为例）；但是，在阅读有关此主题的各种其他文本时，您将遇到一些其他问题。首先，大多数文本将使用惰性求值，在Scheme中您不会得到这种求值方式。其次，由于LC仅具有一元函数，因此缩短术语并使用例如λxyz.zxy而不是在此情况下的“真实”形式λx.(λy.(λz.((z x) y)))或(lambda (x) (lambda (y) (lambda (z) ((z x) y))))在Scheme中是非常常见的。（这称为Currying。）

所以，没错，Scheme与LC非常接近，但是这并不意味着什么，因为存在很多问题。Haskell可能是更好的选择，因为它既是惰性的，又可以对多个参数进行柯里化。但是，你要处理的是一种有类型的语言，这是一个相当沉重的负担，如果你尝试做TLS样式的示例，你会陷入严重的困境...

如果你想要得到所有的东西（懒惰、简写、无类型、足够接近Scheme），那么Racket有另一个值得考虑的点。从高层次上讲，它非常接近Scheme，但它更进一步，你可以快速地创建一个语言，它是将Racket语言限制为只有lambda表达式和函数应用。通过更多的工作，你甚至可以让它变得懒惰。这不是你现在应该尝试做的练习，但如果听起来像你想要的，请看一下我的课程（在课堂笔记中寻找“Schlac”），我们使用了一种正在做以上所有事情的语言，它非常受限，因此你只能获得基本的LC结构。例如，3是一个未绑定的标识符，直到你定义它。请注意，这不是某种解释器——它被编译成Racket代码，这意味着它运行得足够快，你甚至可以编写使用数字的代码。你也可以在那里获得该语言的实现，一旦你安装了它，如果你用#lang pl schlac开始文件，你就会得到这个语言。

- Eli Barzilay

Answer 2

Lambda演算是一种非常受限的编程模型。您只有函数，没有文字、内置算术运算符或数据结构。所有东西都被编码为函数。因此，大多数函数式语言试图通过扩展λ演算来使其更方便日常编程。

Haskell使用现代化的λ演算扩展System F作为其核心语言，并扩展了数据类型。（GHC随后进一步扩展了System Fc，支持类型相等强制转换）。

由于所有Haskell都可以直接在其核心语言中编写，并且其核心语言是类型化λ演算（具体而言，是二阶λ演算的扩展），因此可以说Haskell紧密遵循λ演算，除了其并发、并行和内存副作用的内置运算符（以及FFI）。这使得开发新的编译器优化显着更容易，并且也使给定程序的语义更易于理解。

另一方面，Scheme是未类型化λ演算的变体，扩展了副作用和其他非λ演算概念（例如并发原语）。可以说它紧密遵循未类型化λ演算。

这只对两类人有意义：学习 lambda 演算的人和编译器编写者。

- Don Stewart

---

你是不是在一开始想说的是无类型演算？ - sepp2k

实际上，无类型的LC作为计算模型是完全不受限制的，因此您可以使用它来表示从文字、字符串、函数到所有数据结构和算法的一切内容，只是直接处理所有这些东西可能是一种潜在的不方便形式。技术上讲，通过添加类型来限制它，但在您定义如何将lambda演算的语义应用于实践的上下文中，您很可能会使事情变得更容易。 - Timothy Swan