4

Haskell は本当に素晴らしい言語です。大好きです。しかし、C++ プログラマーとして、コンピューター アーキテクチャーに関する基本的な知識を持っているので、Haskell の実装の詳細を知りたいと思っています。

たとえば、map関数を意味します。私は文法、結果を知っています。ただし、この機能が実際にRAMでどのように機能するかを知りたいです。C ファミリー言語は、文法とコンピューターの動作の間のマッピングが非常に明確だからです。

では、関数型プログラミングの文法の背後にあるコンピューターの動作についてアイデアを持っている人はいますか? または、「C++ オブジェクト モデルの内部」など、これに関する本はありますか?

4

3 に答える 3

5

まず、警告: Haskell の基本的な特性の 1 つは、コンパイラがコンパイル中にコードの非常に根本的な変換を実行する可能性が高いことです。そのため、実際に実行されるコードは、作成したものとまったく似ていない可能性があります。

その警告はさておき、最初の概算では、すべての変数とすべてのデータ フィールドがヒープ オブジェクトへのポインターであると期待できます。これらのヒープ オブジェクトには、データ (整数、ブール値、文字、リスト ノードなど) を表すものもあれば、遅延のためにまだ実行されていない Haskell コードを表すものもあります。長く複雑な式を記述すると、すべてのサブ式がヒープ オブジェクトになり、最上位の式が下位の式を指します。したがって、プログラムの式グラフ全体がヒープ上のオブジェクト グラフになります。

(グラフ /= ツリー。ツリーには「ループ」がありません。Haskell では再帰が許可されているため、Haskell 式は必ずしも式ツリーではありません。)

大きな Haskell 式は、ヒープ オブジェクトの集まりになります。複雑なネストされたパターン マッチは、最適な順序で一連の単層パターンに脱糖されます。残りのプリミティブが 6 つになるまで、言語の他のすべてのシンタックス シュガーが取り除かれます。

  1. 変数を作成
  2. 変数を使用
  3. 関数の作成
  4. 通話機能
  5. データレコードの作成
  6. データレコードの検査

実際のビットとバイトがどのように機能するかを知りたい場合、それはコンパイラ次第です。GHC を意味する場合、おおよそ次のように機能します。

  • すべてのヒープ オブジェクトは、コードまたはデータのいずれかです。

  • データの場合は、値コンストラクター ID 番号と、そのコンストラクターのフィールドごとに 1 つのポインターが含まれます。

  • コード (つまり、まだ実行されていない部分式) の場合、関数のマシン コード ブロックへのポインターが 1 つと、関数の各引数 (カリー化なし) へのポインターが 1 つ含まれます。

  • 条件分岐、I/O 操作、またはヒープ オブジェクトで実行しようとするとseq、ランタイムはヒープ オブジェクトが指すコードにジャンプします。

  • オブジェクトがデータを表す場合、すぐに返されるコードを指します。

  • オブジェクトがコードを表す場合、関数を実際に実装するコードを指します。このコードは、関数の答えを計算し、答えを表すデータ オブジェクトで元のヒープ オブジェクトを上書きします。

  • いずれにせよ、制御が呼び出し元に戻ると、ヒープ オブジェクトは間違いなくデータ オブジェクトになり、コンストラクター ID やその他の必要なことを検査できるようになります。

于 2014-01-24T16:49:11.040 に答える
4

The basic idea to implement lazy functional languages is called Graph Reduction.

"The Implementation of Functional Programming Languages" is a detailed, if older book on the subject: http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

A more tutorial-like introduction: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

For more on how GHC is implemented, you might look at the "Spineless Tagless G-Machine" (STGM) papers, e.g.: http://www.dcc.fc.up.pt/~pbv/aulas/linguagens/peytonjones92implementing.pdf

于 2014-01-24T12:23:22.933 に答える
4

遅延グラフ削減を使用した関数型言語の実装について詳しく説明している非常に優れた本があります。

関数型言語の実装: チュートリアル。サイモン・ペイトン・ジョーンズとデビッド・レスター、1992年。

この本は、遅延グラフ削減を使用して厳密ではない関数型言語の実装を理解するための実用的なアプローチを提供します。この本は、読者がいくつかの重要なコンパイラを開発、変更、および実験するのを助けることによって、関数型言語の実装を「生き生きとさせる」のを助けるための実用的な実験資料のソースとなることを意図しています。

この本の珍しい側面は、読むだけでなく実行することを意図していることです。各実装手法の抽象的な説明を単に提示するのではなく、主要な各メソッドの完全に機能するプロトタイプのコードを提示し、それに対する一連の改善に取り組みます。すべてのコードは、機械可読形式で入手できます。

この本はThe Implementation of Functional Programming Languages、サイモン・ペイトン・ジョーンズ、1987年 (これも非常に興味深い) とは異なることに注意してください。

于 2014-01-24T19:35:03.373 に答える