11

関数型言語をポータブルCにコンパイルしていると仮定します。また、さまざまな理由から、保守的なガベージコレクションではなく正確なガベージコレクションが必要であると仮定します。ガベージコレクターがCスタック上のポインターであるかどうかを把握するための移植可能な方法はありません（おそらく一般的な場合はまったく方法がありません）。この問題には2つの解決策があるように思われます。

  1. シャドウスタック。各C関数に、ポインターであるものとポインターではないものに関する簿記情報を保持させます。これは、LLVMなどで推奨されているアプローチです。

  2. 関数型言語をコンパイルしているという事実を利用してください。つまり、メインラインコードには副作用がありません。アロケータがメモリ不足を検出すると、ガベージコレクタ自体を呼び出す代わりに、longjmpを使用して現在の操作を中止し、メインループに戻ります。メインループは、ガベージコレクタを呼び出します（ポインタを含む可能性のある変数のセットがわかっている場合）。事前に）その後、操作を再開します。

2番目のアプローチが適用できる純粋な関数型言語を扱っている場合は、最初のアプローチよりも効率的であり、手書きのCと簡単に組み合わせることができる必要があるように思われます。

私が見落としている問題はありますか？この手法の既存の議論または実装への参照はありますか？

4

2 に答える 2

4

単一のデータ構造を使用して純粋FP言語を設計することが可能です。

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR };

struct record
{
  record_type type;
  void *value;  
};

pairsプログラムとデータは、以下を使用して表すことができますrecords。

struct pair
{
  record *car;
  record *cdr;
};

簡単な式--2 * 3を使用して表す方法は次のrecordsとおりです。

record r1;
r1.type = RT_NUMBER;
r1.value = &two; 

record r2;
r1.type = RT_NUMBER;
r1.value = &three; 

record opr1;
opr1.type = RT_NUMBER;
opr1.value = &OP_MULT; /* A machine op-code for multiplication. */

pair p_oprnds;
p_oprnds.car = &r1;
p_oprnds.cdr = &r2;

pair p;
p.car = opr1;
p.cdr = p_oprnds;

これはLisp式と同じです：(* 2 3)。これで、を演算子およびオペランドとしてpairs扱い、で動作するマシンを定義できます。1つのデータ構造のみを扱うため、正確なGCが可能です。このようなVMのアーキテクチャについては、LispkitLispを参照してください。carcdr

また、FP-> Cコンパイラの作成を真剣に試みる前に、Lisp inSmallPiecesをお読みください。

于 2011-08-08T09:11:47.490 に答える
1

あなたが説明していない最も明白なことは、永続的なメモリ不足を処理する方法だと思います。あなたがそれを説明したように、私が利用可能なより多くのメモリを使用する操作を持っていると仮定します。最終的に私は到達します：

  1. 操作のどの段階でも、制限を超えて開始します。
  2. しばらく実行します。
  3. メモリが不足しています。
  4. このステージで割り当てられたすべてのメモリを解放します（他に解放するものはありません）。
  5. 1に移動します。

つまり、無限ループです。したがって、少なくとも、ループを検出して終了できるようにする、ある種の世代別ガベージコレクションが必要です。

于 2011-08-08T09:17:10.440 に答える