纯无类型 lambda 演算是一个强大的概念。然而，构建一台供现实世界使用的机器或解释器通常被描述为（接近）不可能。我想对此进行调查。理论上是否可以构建一个相对较快的无类型 lambda 演算机？
我所说的相对较快通常是指在相似数量的资源（门、操作、物理空间、电力使用等）内，可以与现代类图灵架构相媲美，用于相似的任务范围。
我对机器的实现和架构层没有任何限制，除了它必须在物理上并且以某种方式在某种程度上可以现实地实现。对于如何处理 IO 也没有限制。
- 如果可能的话，主要挑战是什么？
- 如果不可能，为什么以及如何？
- 该领域的研究现状如何？
- 哪些领域和主题最相关？
关于基于 lambda 演算的计算机体系结构的可行性，我们了解多少？
涉及类似领域的问题：
- 函数式编程的机器模型 https://stackoverflow.com/questions/3968949/machine-model-for-functional-programming
- 采用图灵机作为主要模型的历史原因 https://cstheory.stackexchange.com/questions/3650/historical-reasons-for-adoption-of-turing-machine-as-primary-model-of-computation
首先，即使在现有架构上，也可以将 lambda 演算有效地编译为机器代码。毕竟，scheme 是 lambda 演算加上一点额外的东西，并且可以高效地编译。然而，scheme & co 是严格求值下的 lambda 演算。还可以在非严格求值下高效地编译 lambda 演算！关于这一点，请参阅 SPJ 的两本书以了解一些背景知识：http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html
另一方面，如果我们构建为函数式语言设计的硬件，我们可以将代码编译到该硬件上，并且确实做得很好。我所知道的最好的新东西是Reducer：http://www.cs.york.ac.uk/fp/reduceron/ http://www.cs.york.ac.uk/fp/reduceron/
Reduceron 的性能非常引人注目，其关键在于它是围绕并行图约简构建的，旨在利用 lambda 演算方程约简中明确的并行性机会。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
