関数言語をC言語にコンパイルする

Question

関数言語をポータブルC言語にコンパイルし、さまざまな理由から、控えめなガベージコレクションではなく正確なものを望むと仮定します。ガベージコレクタがCスタック上のポインタの有無を把握するための移植可能な方法はありません（一般的にはまったくありません）。私にはこの問題の2つの解決策があるようです：

1. シャドースタック。各C関数がポインタの有無に関する情報を簿記情報として保持するようにします。これは、例えば、 LLVM。

2. 機能的な言語をコンパイルしていることを利用してください。つまり、メインラインコードには副作用がありません。アロケータがメモリ不足を検出すると、ガベージコレクタ自体を呼び出すのではなく、longjmpを持つ現在の操作をメインループにアボートします。メインループはガベージコレクタを呼び出します（ポインタを含む可能性のある変数のセットがわかっているコンテキストその後、操作を再開します。

あなたが第二のアプローチが適用され、純粋な関数型言語を扱っている場合、手書きのC.と混合する複数の第一の方法より効率的なだけでなく、より簡単でなければならない、と私には思わ

私は見落としている問題はありますか？このテクニックの既存の議論や実装への言及はありますか？

Answer 1

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

1. 操作のどの段階でも私が限界を超えて開始します。
2. しばらく実行してください。
3. メモリが不足しています。
4. この段階で割り当てられたすべてのメモリを解放します（空き領域はありません）。ある1

から

ゴー、無限ループ。だから少なくとも、ループを検出して終了する世代別ガベージコレクションが必要です。

Answer 2

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

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR }; 

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

プログラムおよびデータはrecordsのpairsを用いて表すことができる：ここでは

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で動作するマシンを定義して、carを演算子として扱い、cdrをオペランドとして扱うことができます。 1つのデータ構造のみを処理するので、正確なGCが可能です。このようなVMのアーキテクチャについては、Lispkit Lispを参照してください。

また、FP - > Cコンパイラを書くことに深刻な試みを始める前に、Lisp in Small Piecesも読んでください。