Compilación de lenguajes funcionales a C

Question

Supongamos que está compilando un lenguaje funcional para C portátil, y suponga también que por diversas razones desea una recolección de basura precisa en lugar de conservadora. No existe una forma portátil (quizás de ninguna manera en el caso general) para que el recolector de basura descubra qué es y qué no es un puntero en la pila C. Me parece que hay dos soluciones para este problema:

1. Shadow stack. Haga que cada función C mantenga la información de contabilidad sobre lo que es y no es un puntero. Este es el enfoque recomendado por, p. LLVM.

2. Aproveche el hecho de que está compilando un lenguaje funcional, lo que significa que el código principal no tiene efectos secundarios. Cuando el asignador detecta falta de memoria, en lugar de llamar al recolector de basura, aborta la operación actual con una vuelta larga al ciclo principal, que llama al recolector de basura (en un contexto donde se conoce el conjunto de variables que pueden contener punteros) de antemano) luego reinicia la operación.

Me parece que, si se trata de un lenguaje funcional puro, donde el segundo enfoque es aplicable, debe ser más eficiente que el primer enfoque, así como más fácil de mezclar con manuscrito C.

¿Hay algún problema que tenga en cuenta? ¿Alguna referencia a la discusión existente o implementaciones de esta técnica?

Answer 1

Creo que lo más obvio que no ha descrito es cómo manejar la falta de memoria persistente. Como lo ha descrito, supongamos que tengo una operación que utiliza más memoria de la disponible. Eventualmente alcanzo:

1. Comience cualquier etapa de la operación que nos lleve al límite.
2. Corre por un tiempo.
3. Se ha quedado sin memoria.
4. Libere toda la memoria asignada por esta etapa (no hay nada más que liberar).
5. Ir a 1.

Es decir, un bucle infinito.Por lo menos, quiere algún tipo de recolección de basura generacional que le permita detectar el bucle y salir.

Answer 2

Es posible diseñar un lenguaje FP puro usando una única estructura de datos:

typedef enum record_type { RT_SYMBOL, RT_NUMBER, RT_PAIR }; 

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

programas y los datos pueden ser representadas usando pairs de records:

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

Aquí es cómo una simple expresión - 2 * 3 - podría representarse usando 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; 

Esto es lo mismo que la expresión de Lisp: (* 2 3). Ahora puede definir una máquina que opera en pairs, tratando el car como operador y el cdr como operandos. Como manejamos solo una estructura de datos, es posible un CG preciso. Ver Lispkit Lisp para la arquitectura de tal máquina virtual.

Lea también Lisp in Small Pieces antes de comenzar con un intento serio de escribir un compilador FP -> C.