将函数式语言编译为C语言

Question

假设您正在为便携式C编译函数式语言,并且假设由于各种原因您需要精确而非保守的垃圾收集.对于垃圾收集器来说,没有可移植的方法(在一般情况下可能完全没有办法)来弄清楚什么是C堆栈上的指针而不是指针.在我看来,这个问题有两个解决方案:

1. 影子堆栈.使每个C函数保持关于什么是指针和不是指针的簿记信息.这是LLVM推荐的方法.

2. 利用您正在编译函数式语言的事实,这意味着主线代码没有副作用.当分配器检测到内存不足时,不是调用垃圾收集器本身,而是使用longjmp将当前操作中止回主循环,主循环调用垃圾收集器(在可能包含指针的变量集已知的上下文中)提前)然后重新开始操作.

在我看来,如果你正在处理第二种方法适用的纯函数式语言,它必须比第一种方法更有效,并且更容易与手写的C语言混合.

我有什么问题可以忽略吗？对此技术的现有讨论或实现的任何引用？

Answer 1

使用单一数据结构设计纯 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，将 视为car运算符，cdr将 视为操作数。由于我们只处理一种数据结构，因此精确的 GC 是可能的。有关此类 VM 的架构，请参阅Lispkit Lisp 。

在开始认真尝试编写 FP -> C 编译器之前，还请阅读《Lisp in Small Pieces》 。

Answer 2

我认为您没有描述的最明显的事情是如何处理持久内存不足。正如您所描述的，假设我有一个操作使用的内存多于可用内存。最终我到达：

1. 开始操作超出限制的任何阶段。
2. 跑一会儿。
3. 内存不足。
4. 释放此阶段分配的所有内存（没有其他可释放的内存）。
5. 转到1。

即无限循环。因此，至少您需要某种分代垃圾收集，以允许您检测循环并退出。