是否有可能建立一个相对快速的无类型lambda演算机？

Question

纯粹的无类型lambda演算是一个强大的概念.然而,构建用于实际使用的机器或解释器通常被描述为(接近)不可能.我想调查一下.理论上可以建立一个相对快速的无类型lambda演算机器吗？

相对较快,我通常意味着可以在类似数量的资源(门,操作,物理空间,电力使用等)内,对类似范围的任务进行现代图灵式架构的比较.

我对机器的实现和架构层没有任何限制,只是它必须在某种程度上在物理上和某种程度上可实现.对如何处理IO也没有限制.

• 如果可能,主要挑战是什么？
• 如果不可能,为什么以及如何？
• 这个领域的研究状况如何？
• 哪些领域和科目最相关？

关于基于lambda演算的计算机体系结构的可行性了解多少？

涉及类似理由的问题:

• 功能编程的机器模型
• 采用图灵机作为主要模型的历史原因

Answer 1

首先,即使在现有体系结构上,也可以有效地将lambda演算编译为机器代码.毕竟,scheme是lambda演算加上一点额外的,它可以有效地编译.然而,scheme&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/

Reduceron的性能关键是非常引人注目的,它是围绕并行图减少而构建的,旨在利用在减少lambda演算方程时明确的并行机会.