Compiling functional languages to C

Question

Suppose you're compiling a functional language to portable C, and suppose also that for various reasons you want precise rather than conservative garbage collection. There is no portable way (perhaps no way at all in the general case) for the garbage collector to figure out what is and isn't a pointer on the C stack. It seems to me there are two solutions to this problem:

1. Shadow stack. Make each C function maintain bookkeeping information about what is and isn't a pointer. This is the approach recommended by e.g. LLVM.

2. Take advantage of the fact that you are compiling a functional language, which means mainline code has no side effects. When the allocator detects out of memory, instead of calling the garbage collector itself, it aborts the current operation with a longjmp back to the main loop, which calls the garbage collector (in a context where the set of variables that may contain pointers is known in advance) then restarts the operation.

It seems to me that, if you are dealing with a pure functional language where the second approach is applicable, it must be more efficient than the first approach, as well as easier to mix with handwritten C.

Are there any problems I'm overlooking? Any references to existing discussion or implementations of this technique?

Answer 1

It is possible to design a pure FP language using a single data structure:

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR };

struct record
{
  record_type type;
  void *value;  
};

Programs and data can be represented using pairs of records:

struct pair
{
  record *car;
  record *cdr;
};

Here is how a simple expression - 2 * 3 - could be represented using 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;

This is the same as the Lisp expression: (* 2 3). Now you can define a machine that operates on pairs, treating the car as an operator and the cdr as operands. As we deal with only one data structure, precise GC is possible. See Lispkit Lisp for the architecture of such a VM.

Also read Lisp in Small Pieces before starting off with a serious attempt on writing an FP -> C compiler.

Answer 2

I think the most obvious thing you haven't described is how to handle persistent out-of-memory. As you've described it, suppose I have an operation that uses more memory than is available. Eventually I reach:

1. Start whatever stage of the operation takes us over the limit.
2. Run for a while.
3. Run out of memory.
4. Free all the memory allocated by this stage (there is nothing else to free).
5. Go to 1.

That is, an infinite loop. So at the least you want some sort of generational garbage collection that will allow you to detect the loop and exit.