將函數式語言編譯爲C

假設您正在將函數式語言編譯爲便攜式C語言，並且假設您因各種原因需要精確而非保守的垃圾收集。沒有可移植的方式（在一般情況下可能根本沒有辦法）讓垃圾收集器找出C堆棧上的指針和指針。在我看來，這個問題有兩種解決方案：將函數式語言編譯爲C

陰影堆棧。使每個C函數保持關於什麼是和不是指針的簿記信息。這是由例如推薦的方法LLVM。
利用您正在編譯的功能語言，這意味着主線代碼沒有副作用。當分配器檢測到內存不足時，不是調用垃圾收集器本身，而是使用longjmp中止當前操作回到調用垃圾回收器的主循環（在可能包含指針的變量集合已知的上下文中提前）然後重新開始操作。

在我看來，如果你正在處理一個純功能性語言，其中的第二種方法是適用的，它必須比第一種方法更有效，也更容易使用的手寫下

混合

我忽略了什麼問題嗎？任何提及此技術的現有討論或實施？

2011-08-08 rwallace

可能沒有幫助，但我試了第一次，同時爲我的計劃解釋程序編寫標記掃描。性能被吸引了，所以我最終得到了一個純粹的虛擬堆棧，它不在C運行時的堆棧之內，主要是因爲跨運行時堆棧自省幾乎是不可能的。性能也很糟糕，但在沒有gdb/ddd的情況下更容易調試。我決定做，因爲這是解釋器，當我到達編譯器的實現階段時（通常沒有完成），我們會解決它。 – Deleted

您打算如何重新啓動當前操作？不時保存檢查點，然後恢復最後一個檢查點（如何？） –

@ n.m .:在這方面問題的重要部分是「代碼沒有副作用」。提問者假設一種純粹的功能語言，所以沒有任何狀態會被修改。沒有必要「檢查」檢查點，當您跳轉到之前的狀態時，您不需要「撤消」任何更改，因爲語言無法進行更改。原則上，您在代碼中的位置告訴您關於程序狀態所需的一切。 –

我認爲你沒有描述的最明顯的事情是如何處理持續的內存不足。正如你所描述的那樣，假設我有一個使用比可用內存更多的操作。最終我達到了：

開始任何階段的操作使我們超過極限。
運行一段時間。
內存不足。
釋放所有由這個階段分配的內存（沒有別的東西是免費的）。
轉到1

也就是說，一個無限循環。所以至少你想要一些世代的垃圾收集，這將允許你檢測循環和退出。

來源

2011-08-08 09:17:10

，能夠使用一個單一的數據結構，以設計出純FP語言：

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR }; 

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

程序和數據可以使用pairsrecords來表示：

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作爲操作數處理。由於我們只處理一種數據結構，因此可以使用精確的GC。有關這種VM的體系結構，請參閱Lispkit Lisp。

在開始編寫FP-> C編譯器之前，還要仔細閱讀Lisp in Small Pieces。

來源

2011-08-08 09:11:47

將函數式語言編譯爲C

回答

相關問題