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

Также прочитайте Lisp маленькими кусочками перед тем, как начать с серьезной попытки написания компилятора FP -> C.

Answer 2

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

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

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