是否有可能建立一个相对较快的无类型lambda微积分机器？ [英] Is it possible to build a comparatively fast untyped lambda calculus machine?

问题描述

纯粹的无类型lambda微积分是一个强大的概念。然而，为现实世界使用而建立机器或解释器通常被描述为（接近）不可能的。我想调查一下。理论上讲，建立一个相对较快的无类型lambda微积分机器是可能的吗？

通过相对较快的速度，我通常意味着可以与类似的任务范围内的现代图灵式架构相比，类似的资源（门，操作，物理空间，电源使用等）。

我没有限制机器的实现和体系结构层，除了它在某种程度上必须在物理上和某种程度上是现实的。如何处理IO也没有限制。

• 如果可能，主要挑战是什么？


• 如果不可能，为什么和如何？


• 这方面的研究状况如何？


• 哪些领域和主题最相关？ li>
  

基于lambda微积分的计算机架构的可行性有多少？

<涵盖类似理由的问题：

• 以图灵机为主要计算模式>采用图灵机作为主要模型的历史原因

解决方案

首先，可以有效地将lambda演算编译为机器c即使在现有架构上也是如此。毕竟，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 /

Reduceron的性能关键在于其周围并行图减少，并且旨在利用并行的机会明确地减少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:

• Machine model for functional programming
• Historical reasons for adoption of the Turing machine as the primary model

解决方案

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.

这篇关于是否有可能建立一个相对较快的无类型lambda微积分机器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！