38

純粋な型指定されていないラムダ計算は強力な概念です。ただし、実世界で使用するためのマシンまたはインタープリターを構築することは、(ほぼ) 不可能であると説明されることがよくあります。これを調べたい。比較的高速な型指定されていないラムダ計算機を構築することは理論的に可能ですか?

比較的高速とは、一般に、同様の量のリソース (ゲート、操作、物理スペース、電力使用など) 内で、同様の範囲のタスクについて、最新のチューリングのようなアーキテクチャに匹敵することを意味します。

マシンの実装層とアーキテクチャ層に制限はありませんが、何らかの方法で物理的かつある程度現実的に実現可能でなければなりません。IO の処理方法にも制限はありません。

  • 可能であれば、主な課題は何ですか?
  • 不可能な場合、その理由と方法は?
  • この分野の研究はどのような状況ですか？
  • 最も関連性の高い分野と科目は?

ラムダ計算に基づくコンピューター アーキテクチャの実現可能性について、どの程度わかっていますか?

同様の根拠をカバーする質問:

4

1 に答える 1

22

第 1 に、既存のアーキテクチャ上でも、ラムダ計算を効率的にマシン コードにコンパイルできます。結局のところ、スキームはラムダ計算に少し余分なものを加えたものであり、効率的にコンパイルできます。ただし、scheme & co は厳密に評価されたラムダ計算です。非正格評価のラムダ計算も効率よくコンパイルできます！これについては、背景について SPJ の 2 冊の本を参照してください: http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html

一方、関数型言語用に設計されたハードウェアを構築した場合、そのハードウェアにコードをコンパイルして、実際に非常にうまく機能することも事実です。私が知っているこれに関する最高の新しいものはReduceronです：http://www.cs.york.ac.uk/fp/reduceron/

Reduceron のパフォーマンスの鍵は、非常に説得力がありますが、それが並列グラフ縮約を中心に構築されており、ラムダ計算方程式の縮約で明示された並列処理の機会を活用することを目的としていることです。

于 2011-05-18T17:02:44.310 に答える