¿Por qué los lenguajes de programación funcionales requieren recolección de basura?

14

¿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

Nicholas Grasevski
fuente
El lenguaje de programación Cat parece un ejemplo de una función, lenguaje basado en pila.
Petr Pudlák
1
Esta no es una pregunta de nivel de investigación, ya que la recolección de basura está cubierta en cursos de pregrado sobre lenguajes de programación (así como la necesidad de hacerlo). Pase a cs.stackexchange.com
Andrej Bauer el
Mi error. ¿Sabes la respuesta a mi pregunta?
Nicholas Grasevski
55
Creo que hay una respuesta de nivel de investigación para dar a esta pregunta, ya que recuerdo haber luchado con ella durante mis años de posgrado: todo en un lenguaje como Haskell parece una aplicación de función, que vive en la pila. Creo que explicar por qué los cierres son necesarios, por qué viven en el montón y quizás lo que los "datos que escapan del alcance de la función" tienen que ver con él sería una respuesta muy informativa (que no estoy seguro de estar calificado para dar, Desafortunadamente).
cody
2
λ-cálculo en combinadores conduce a una explosión de tamaño.
Martin Berger

Respuestas:

16

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:

  1. 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.

  2. La mayoría de las implementaciones no utilizan el recuento de referencias por dos razones.

    1. Admiten una forma de tipo puntero (por ejemplo, el refconstructor de tipos en ML), por lo que se pueden formar ciclos verdaderos en el montón.
    2. El conteo de referencias es mucho menos eficiente que la recolección de basura, ya que
      • requiere mucho espacio adicional para mantener los recuentos de referencia, y
      • actualizar los recuentos suele ser un trabajo perdido, y
      • Las actualizaciones de los recuentos crean un montón de contención de escritura que mata el rendimiento paralelo.
  3. 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).

  4. 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

  5. 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).

  6. Si desea una disciplina de pila real, puede usar sistemas de tipos basados ​​en "lógica ordenada" (esencialmente tipos lineales menos intercambio).

Neel Krishnaswami
fuente
2
¿No es la razón más básica para (2) que, incluso sin efectos secundarios observables, las implementaciones quieren tener un operador eficiente para la recursión (mutua), es decir, uno que realmente forme un ciclo en el montón?
Andreas Rossberg
@andreasrossberg: Pensé en mencionar eso, pero lo omití, ya que puedes usar el combinador y para la recursión.
Neel Krishnaswami