是否有可能构建一个相对较快的无类型 lambda 演算机？
纯无类型 lambda 演算是一个强大的概念。然而，构建一台供现实世界使用的机器或解释器通常被描述为（接近）不可能。我想对此进行调查。理论上是否可以构建一个相对较快的无类型 lambda 演算机？
我所说的相对较快通常是指在相似数量的资源（门、操作、物理空间、电力使用等）内，可以与现代类图灵架构相媲美，用于相似的任务范围。
我对机器的实现和架构层没有任何限制，除了它必须以某种方式在物理上和某种程度上现实地实现。对于如何处理 IO 也没有限制。
- 如果可能的话，主要挑战是什么？
- 如果不可能，为什么以及如何？
- 该领域的研究现状如何？
- 哪些领域和主题最相关？
关于基于 lambda 演算的计算机架构的可行性，我们了解多少？
涵盖类似领域的问题：
Pure untyped lambda calculus is a powerful concept. However, building a machine or interpreter for real-world use is often described as (close to) impossible. I want to investigate this. Is it theoretically possible to build a comparatively fast untyped lambda calculus machine?
By comparatively fast I generally mean comparable to modern Turing-like architectures for a similar range of tasks, within a similar amount of resources (gates, operations, physical space, power use, etc).
I place no limitations on the implementation and architectural layers of the machine, except that it must be physically and somewhat realistically realizeable in some way. No restrictions on how to handle IO either.
- If possible, what are the main challenges?
- If impossible, why and how?
- What is the state of research in this area?
- Which fields and subjects are most relevant?
How much is known about the feasibility of a computer architecture based around lambda calculus?
Questions covering similar ground:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，即使在现有架构上，也可以将 lambda 演算有效地编译为机器代码。毕竟，scheme 是 lambda 演算加上一点额外的东西，并且可以高效地编译。然而，计划& co 是严格评估下的 lambda 演算。还可以在非严格求值下高效地编译 lambda 演算！关于这一点，请参阅 SPJ 的两本书以了解一些背景知识： http: //research.microsoft.com/en-us/um/people/simonpj/papers/papers.html
另一方面，如果我们构建为函数式语言设计的硬件，我们也可以编译代码那个硬件确实做得很好。我所知道的最好的新东西是Reduceron：http://www.cs .york.ac.uk/fp/reduceron/
Reducer 性能的关键非常引人注目，它是围绕并行图缩减构建的，旨在利用 中明确的并行性机会。 lambda 演算方程的简化。
First, it is possible to compile the lambda calculus efficiently to machine code even on existing architectures. After all, scheme is the lambda calculus plus a bit extra, and it can be compiled efficiently. However, scheme & co are the lambda calculus under strict evaluation. It is also possible to compile the lambda calculus under non-strict evaluation efficiently! On this, see SPJ's two books for some background: http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html
On the other hand, it is also true that if we built hardware designed for functional languages, we could compile code to that hardware and do very well indeed. The best new stuff on this I know of is the Reduceron: http://www.cs.york.ac.uk/fp/reduceron/
The key to the performance of the Reduceron, which is quite compelling, is that it is built around parallel graph reduction, and aims to exploit the opportunities for parallelism made explicit in the reduction of lambda calculus equations.