将函数式语言编译为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

回答

相关问题