11

假设您正在将一种函数式语言编译为可移植的 C，并且还假设由于各种原因您想要精确而不是保守的垃圾收集。垃圾收集器没有可移植的方式（在一般情况下可能根本没有办法）来确定 C 堆栈上什么是指针，什么不是指针。在我看来，这个问题有两种解决方案：

  1. 阴影堆栈。让每个 C 函数维护有关什么是指针和不是指针的簿记信息。这是例如 LLVM 推荐的方法。

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

在我看来，如果您正在处理适用于第二种方法的纯函数式语言，它必须比第一种方法更有效，并且更容易与手写 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将car视为运算符，将cdr视为操作数。由于我们只处理一种数据结构，精确的 GC 是可能的。有关此类 VM 的体系结构，请参阅Lispkit Lisp。

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

于 2011-08-08T09:11:47.490 回答
1

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

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

也就是无限循环。因此，至少您需要某种分代垃圾收集，让您能够检测到循环并退出。

于 2011-08-08T09:17:10.440 回答