Компиляция функциональных языков на C

Предположим, вы компилируете функциональный язык для переносимого C, и предположите также, что по разным причинам вам нужна точная, а не консервативная сборка мусора. Нет никакого переносного способа (возможно, вообще никакого способа в общем случае) для сборщика мусора, чтобы выяснить, что есть и не является указателем на стек C. Мне кажется, что есть две проблемы:

Теневой стек. Сделать каждую функцию C поддерживать бухгалтерскую информацию о том, что есть и не является указателем. Это подход, рекомендованный, например, LLVM.
Воспользуйтесь тем, что вы компилируете функциональный язык, что означает, что код основной линии не имеет побочных эффектов. Когда распределитель обнаруживает вне памяти, вместо вызова сборщика мусора он прерывает текущую операцию с longjmp обратно в основной цикл, который вызывает сборщик мусора (в контексте, где известен набор переменных, которые могут содержать указатели заранее), а затем перезапускает операцию.

Мне кажется, что если вы имеете дело с чистым функциональным языком, где применим второй подход, он должен быть более эффективным, чем первый подход, а также проще смешиваться с рукописным C.

Есть ли какие-то проблемы, с которыми я сталкиваюсь? Любые ссылки на существующее обсуждение или реализации этой техники?

Ответ 1

Я думаю, что наиболее очевидная вещь, которую вы не описали, - это то, как обрабатывать постоянную нехватку памяти. Как вы описали, предположим, что у меня есть операция, которая использует больше памяти, чем доступно. В конце концов я достигаю:

Запуск любой стадии операции приведет нас к пределу.
Запустите некоторое время.
Недостаточно памяти.
Освободите всю память, выделенную этим этапом (больше нечего освобождать).
Перейдите к 1.

То есть бесконечный цикл. Поэтому, по крайней мере, вам нужна какая-то коллективная сборка мусора, которая позволит вам обнаружить цикл и выйти.

Ответ 2

Можно создать чистый язык 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. См. Lispkit Lisp для архитектуры такой виртуальной машины.

Также прочитайте Lisp в Small Pieces, прежде чем начинать с серьезной попытки записать компилятор FP → C.