我最近一直在写很多 lambda 演算的程序，我希望我可以实时运行其中的一些程序。然而，尽管趋势函数范式是基于 lambda 演算和 B 归约法则，但我找不到一个不是玩具的求值器，不是为了提高效率。函数式语言应该很快，但我所知道的那些实际上并不提供对正常形式的访问(请参阅 Haskell 的惰性求值器、Scheme 的闭包等)，所以不要像 LC 求值器一样工作。
这让我想知道:是否不可能有效地评估 lambda 演算项，这只是一个历史事故/缺乏兴趣，没有人决定为其创建一个快速评估器，还是我只是遗漏了什么？
最佳答案
就目前的知识水平而言，评估 lambda 项的最佳方法是所谓的最佳图缩减技术。该技术于 1989 年由 J.Lamping 在他的 POPL 文章“An algorithm for optimal lambda calculus reduction”中介绍，然后由几位作者进行了修改和改进。您可以在我与 S.Guerrini 合着的书“The optimal implementation of functional programming languages”中找到一项调查，剑桥理论计算机科学丛书第 45 期，1998 年。
术语“最佳”指的是共享管理。在 lambda 演算中，你有很多重复，减少的效率至关重要 基于避免重复工作。在一阶设置中，有向无环 图(dags)足以管理共享，但是一旦进入更高阶设置，您就需要更复杂的图结构，包括 共享和取消共享。
在纯 lambda 项上，最优图缩减比所有其他已知的都快 减少技术(环境机器、 super 组合器或其他)。 上面的书中给出了一些基准(参见第 296-301 页)，我们在其中 证明我们的实现优于 caml-light(前身 ocaml)和 Haskell(真的很慢)。 所以，如果你听到人们说它从未被证明是最优的 减少比其他技术更快，这是不正确的:两者都被证明 在理论上和实验上。
函数式语言尚未以这种方式实现的原因是 在函数式编程的实践中，你很少使用函数式 排名非常高，当你这样做时，它们通常是线性的。 一旦你提高等级，lambda 的内在复杂性 条件可能变得危险地高。有一种技术可以让你 及时减少一项 O(2^n) 而不是 O(2^(2^n)) 并不能使所有 这种差异在实践中:两种计算都是不可行的。
我最近写了一篇短文试图解释这些问题: “About the efficient reduction of lambda terms”。 在同一篇文章中，我还讨论了超优的可能性 还原技术。
关于algorithm - 是否可以有效地评估 lambda 演算项？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31223539/