¿Qué impide que ghc traduzca Haskell a un lenguaje de programación concatenante como la lógica combinatoria y luego simplemente use la asignación de pila para todo? Según Wikipedia, la traducción del cálculo lambda a la lógica combinatoria es trivial y, además, los lenguajes de programación concatenantes pueden depender únicamente de una pila para la asignación de memoria. ¿Es factible hacer esta traducción y así eliminar la recolección de basura para idiomas como Haskell y ocaml? ¿Hay inconvenientes para hacer esto?
EDITAR: trasladado aquí /programming/39440412/why-do-functional-programming-languages-require-garbage-collection
functional-programming
haskell
Nicholas Grasevski
fuente
fuente
Respuestas:
Todos los siguientes comentarios se basan en la elección de una estrategia de implementación estándar que utiliza cierres para representar valores de función y un orden de evaluación de llamada por valor:
Para el cálculo lambda puro, la recolección de basura no es necesaria. Esto se debe a que no es posible formar ciclos en el montón: cada valor recientemente asignado solo puede contener referencias a valores asignados previamente, por lo que el gráfico de memoria forma un DAG, por lo que el recuento de referencias es suficiente para administrar la memoria.
La mayoría de las implementaciones no utilizan el recuento de referencias por dos razones.
ref
constructor de tipos en ML), por lo que se pueden formar ciclos verdaderos en el montón.Los lenguajes de tipo lineal pueden eliminar el recuento de referencia (esencialmente porque los recuentos son 0-1: el valor tiene una sola referencia o está inactivo y puede liberarse).
Sin embargo, la asignación de la pila aún no es suficiente. Esto se debe a que es posible formar valores de función que se refieren a variables libres (es decir, necesitamos implementar cierres de función), si asigna cosas en la pila, los valores vivos pueden entrelazarse con valores muertos, y esto causará una asintótica incorrecta. uso del espacio
Puede obtener los asintóticos correctos reemplazando una pila con una "pila de espagueti" (es decir, implemente la pila como una lista vinculada en el montón, de modo que pueda cortar los marcos muertos según sea necesario).
Si desea una disciplina de pila real, puede usar sistemas de tipos basados en "lógica ordenada" (esencialmente tipos lineales menos intercambio).
fuente