50

GHCの設計は、「スパインレス、タグレスGマシン」の略であるSTGと呼ばれるものに基づいています。

現在、G-machineは、怠惰の実装方法を定義する「グラフ還元マシン」の略です。評価されていないサンクは式ツリーとして保存され、プログラムを実行するには、これらを通常の形式に縮小する必要があります。（ツリーは非巡回グラフですが、Haskellの広範な再帰は、Haskell式が一般的なグラフを形成することを意味します。したがって、ツリー削減ではなくグラフ削減になります。）

あまり明確ではないのは、「スパインレス」と「タグレス」という用語です。

  1. 「スパインレス」とは、関数適用に関数アプリケーションノードの「スパイン」がないことを指していると思います。代わりに、呼び出された関数に名前を付け、そのすべての引数を指すオブジェクトがあります。あれは正しいですか？

  2. 「タグレス」とは、コンストラクターノードがコンストラクターIDで「タグ付け」されていないことを指し、代わりに大文字小文字の表現はジャンプ命令を使用して解決されると思いました。しかし、今はそれが正しいかどうかわかりません。代わりに、ノードが評価状態でタグ付けされていないという事実を参照しているようです。誰かがこれらの解釈のどれが正しいか（もしあれば）を明確にすることができますか？

4

4 に答える 4

30

GHC wikiには、 MaxBolingbrokeによって書かれたSTGに関する紹介記事が含まれています。

STGマシンは、世界をリードするHaskellコンパイラであるGHCの重要な部分です。Haskell評価モデルを標準ハードウェアに効率的に実装する方法を定義します。この重要な役割にもかかわらず、GHCユーザーの間では一般的によく理解されていません。このドキュメントは、Haskellのソースコードがどのようにコンパイルされるかを示す一連の簡単な例によって、STGマシンの概要を最新の評価/適用ベースのポインタータグ付きの形で提供することを目的としています。

于 2012-08-25T02:01:24.970 に答える
16

私が正しければ、あなたは「スパインレス」について正しいです。これは基本的に、Burn、Peyton-Jones、Robsonによる1988年の記事「TheSpinelessG-Machine」で説明されています。読んだことがありますが、頭の中でそれほど新鮮ではありません。基本的に、Gマシンでは、式の先頭を指す上部のノードを除いて、すべてのスタックエントリがアプリケーションノードを指します。これらのアプリケーションノードは引数に間接的にアクセスし、一部のG-Machineの説明では、関数を適用する前にスタックが再配置されるため、スタックの最後のnノードがアプリケーションノードではなく引数を指すようになります。私が誤解しない限り、「スパインレス」の部分は、これらのアプリケーションノード（グラフのスパインと呼ばれる）をスタックに完全に配置しないようにすることです。

「タグなし」の部分に関しては、以前はより正確でしたが、ノードでタグを使用することは非常に古いことです。LISPのような動的に型付けされた言語がどのように実装されたかについて考えられますか？すべてのセルには、その値とタイプを示すタグが必要です。何かが必要な場合は、タグを調べてそれに応じて行動する必要があります。Haskellの場合、評価状態は型よりも重要であり、Haskellは静的に型付けされます。

STGマシンでは、タグは使用されません。タグは、おそらくOO言語のインスピレーションによって、関数ポインターのセットに置き換えられました。計算されていないノードの値が必要な場合、関数はそれを計算します。すでに計算されている場合、関数はそれを返します。これにより、クライアントコードをさらに複雑にすることなく、この関数で実行できる多くの創造性が可能になります。

この「タグレス」の部分は、SPJによる「ストックハードウェアでの関数型言語の実装」の記事で説明されています。

この「タグのない」ことにも反対があります。基本的に、これには関数ポインターが含まれます。これは、コンピューターアーキテクチャーの用語では間接的なジャンプです。また、間接ジャンプは分岐予測の障害であり、したがって一般的なパイプライン処理の障害になります。アーキテクチャがジャンプ引数にデータ依存関係があると見なしてパイプラインを停止するか、アーキテクチャが宛先を認識していないと想定してパイプラインを停止するためです。

于 2013-06-08T00:52:51.503 に答える
3

機能的なPLの実装に関するSPJの本を読みたいと思います。

于 2012-08-12T20:22:45.547 に答える
3

migleによる答えは、STGMのスピンレスとタグレスが何を意味するかということです。今日では、2つの機能の名前を理解しようとする価値はありません。名前は、Gマシン、Spineless Gマシン、およびSpinelessとTaglessGマシンのグラフ削減テクノロジの歴史に由来しているためです。

Gマシンは、スパインとタグの両方を使用します。スパインは、関数適用のルートノードから関数のノードまでのエッジのリストです。たとえば、「f e1 e2...en」の関数適用は次のように表されます。

root = AP left_n en
left_n = AP left_n-1 en-1 ...
left_2 = AP left_1 e1
left_1 = FUN f

Gマシンでは、スパインはleft_n-> left_n-1-> ...->left_2->left_1で構成されるエッジのリストです。それは文字通り関数適用の背骨です！

同じ機能アプリケーションには、タグAPとFUNがあります。

次の高度なGマシン、いわゆるスパインレスGマシンでは、最初のスロットがfを指し、2番目のスロットがe1、...を指し、 n+1番目のスロットはenを指します。この表現では、スパインは必要ありません。ただし、ブロックはスロット数などを指定する特別なタグを開始します。

スパインレスタグレスGマシンと呼ばれる最先端のGマシンでは、このようなタグは関数ポインタに置き換えられます。関数適用を評価することは、関数ポインタによってコードにジャンプすることです。

シモーネ・ペイトン・ジョーンズのSTGM論文が、ある抽象的なレベルでの編集/評価規則を示していないことを発見するのは残念です。したがって、人々がSTGMの本質を理解しにくいのは非常に自然なことです。

于 2017-03-02T11:46:46.660 に答える