我最近用 lambda 演算编写了很多程序，我希望能够实时运行其中一些程序。然而，尽管趋势函数范式基于 lambda 演算和 B 约简规则，但我找不到一个不是玩具、不以效率为目的的评估器。函数式语言应该很快，但我所知道的那些语言实际上并不提供对范式的访问（请参阅 Haskell 的惰性求值器、Scheme 的闭包等），因此不能用作 LC 求值器。
这让我想知道：是否不可能有效地评估 lambda 演算项，是否只是一个历史事故/缺乏兴趣，没有人决定为其创建一个快速评估器，或者我只是错过了一些东西？
根据目前的知识水平，评估 lambda 项的最佳方法是所谓的最优图简化技术。该技术于 1989 年由 J.Lamping 在他的 POPL 文章“一种最优 lambda 演算简化算法 http://dl.acm.org/citation.cfm?id=96711”，然后经过几位作者的修改和完善。你可以在我与 S.Guerrini 的书中找到一项调查“”，剑桥理论计算机科学丛书第 45 期，1998 年。
术语“最优”是指共享的管理。在 lambda 演算中，有大量的重复，而归约的效率至关重要
基于避免重复工作。在一阶设置中，有向非循环
图（dags）足以管理共享，但是一旦您进入更高阶的设置，您就需要更复杂的图结构，包括
共享和取消共享。
在纯 lambda 项上，最佳图简化速度比所有其他已知的要快
缩减技术（环境机、超级组合器或其他）。
上面的书中给出了一些基准（参见第296-301页），其中我们
证明我们的实现优于 caml-light（前身）
ocaml）和 Haskell（非常慢）。
所以，如果你听到人们说它从未被证明是最佳的
减少速度比其他技术更快，但事实并非如此：事实证明
理论上和实验上。
函数式语言尚未以这种方式实现的原因是
在函数式编程的实践中，你很少使用函数
具有非常高的等级，并且当你这样做时，它们通常是线性的。
一旦你提高等级，lambda 的内在复杂性就会增加
条款可能会变得非常危险。拥有一项技术可以让你
减少时间 O(2^n) 而不是 O(2^(2^n)) 并不能使所有
实际上，这种差异是：两种计算都是不可行的。
我最近写了一篇短文试图解释这些问题：
”关于 lambda 项的有效约简 https://www.researchgate.net/publication/312462365_About_the_efficient_reduction_of_lambda_terms”。
在同一篇文章中，我还讨论了超优的可能性
减少技术。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
