¿Todos los lenguajes funcionales usan recolección de basura?

¿Existe un lenguaje funcional que permita utilizar la semántica de pila: destrucción determinista automática al final del alcance?

No es que yo sepa, aunque no soy un experto en programación funcional.

En principio, parece bastante difícil, porque los valores devueltos por las funciones pueden contener referencias a otros valores que se crearon (en la pila) dentro de la misma función, o podrían haberse pasado fácilmente como un parámetro o haber sido referenciados por algo pasado como un parámetro En C, este problema se trata permitiendo que se produzcan punteros colgantes (o más precisamente, un comportamiento indefinido) si el programador no hace las cosas bien. Ese no es el tipo de solución que los diseñadores de lenguaje funcional aprueban.

Sin embargo, hay posibles soluciones. Una idea es hacer que la vida útil del valor forme parte del tipo del valor, junto con referencias a él, y definir reglas basadas en tipos que eviten que los valores asignados por pila sean devueltos o referenciados por algo devuelto por un función. No he trabajado con las implicaciones, pero sospecho que sería horrible.

Para el código monádico, hay otra solución que es (en realidad o casi) monádica también, y podría dar una especie de IORef destruido automáticamente por determinación. El principio es definir acciones de "anidamiento". Cuando se combinan (utilizando un operador asociativo), definen un flujo de control de anidamiento: creo que "elemento XML", con los valores más a la izquierda que proporcionan el par externo de etiquetas de inicio y finalización. Estas "etiquetas XML" solo definen el orden de las acciones monádicas en otro nivel de abstracción.

En algún momento (en el lado derecho de la cadena de composición asociativa) necesita algún tipo de terminador para terminar el anidamiento, algo para llenar el agujero en el medio. La necesidad de un terminador es lo que probablemente significa que el operador de composición de anidamiento no es monádico, aunque de nuevo, no estoy completamente seguro, ya que no he trabajado en los detalles. Como todo lo que aplica el terminador es convertir una acción de anidación en una acción monádica normal compuesta, tal vez no, no necesariamente afecta al operador de composición de anidación.

Muchas de estas acciones especiales tendrían un paso nulo de "etiqueta final", y equivaldrían al paso "etiqueta inicial" con alguna acción monádica simple. Pero algunos representarían declaraciones variables. Estos representarían el constructor con la etiqueta de inicio y el destructor con la etiqueta de finalización. Entonces obtienes algo como ...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Traduciendo a una composición monádica con el siguiente orden de ejecución, cada etiqueta (no elemento) se convierte en una acción monádica normal ...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

Reglas como esta podrían permitir la implementación de RAII estilo C ++. Las referencias tipo IORef no pueden escapar de su alcance, por razones similares a las razones por las cuales los IORefs normales no pueden escapar de la mónada: las reglas de la composición asociativa no proporcionan forma de escapar a la referencia.

EDITAR : casi se me olvida decir: hay un área definida de la que no estoy seguro. Es importante asegurarse de que una variable externa no pueda hacer referencia a una interna, básicamente, por lo que debe haber restricciones sobre lo que puede hacer con estas referencias tipo IORef. Nuevamente, no he trabajado con todos los detalles.

Por lo tanto, la construcción podría, por ejemplo, abrir un archivo cuya destrucción se cierra. La construcción podría abrir un zócalo que cierra la destrucción. Básicamente, como en C ++, las variables se convierten en administradores de recursos. Pero a diferencia de C ++, no hay objetos asignados en el montón que no puedan destruirse automáticamente.

Aunque esta estructura admite RAII, aún necesita un recolector de basura. Aunque una acción de anidamiento puede asignar y liberar memoria, tratándola como un recurso, todavía hay todas las referencias a valores funcionales (potencialmente compartidos) dentro de esa porción de memoria y en otros lugares. Dado que la memoria podría asignarse simplemente en la pila, evitando la necesidad de un montón libre, la importancia real (si existe) es para otros tipos de gestión de recursos.

Entonces, lo que esto logra es separar la administración de recursos al estilo RAII de la administración de memoria, al menos en el caso en que RAII se base en un alcance de anidamiento simple. Todavía necesita un recolector de basura para la administración de memoria, pero obtiene una limpieza determinista automática segura y oportuna de otros recursos.

Si considera que C ++ es un lenguaje funcional (tiene lambdas), entonces es un ejemplo de un lenguaje que no utiliza una recolección de basura.

Tengo que decir que la pregunta está un poco mal definida porque supone que hay una colección estándar de "lenguajes funcionales". Casi todos los lenguajes de programación admiten cierta cantidad de programación funcional. Y, casi todos los lenguajes de programación admiten cierta cantidad de programación imperativa. ¿Dónde se traza la línea para decir cuál es un lenguaje funcional y cuál es un lenguaje imperativo, además de guiarse por prejuicios culturales y dogmas populares?

Una mejor manera de formular la pregunta sería: "¿es posible soportar la programación funcional en una memoria asignada a la pila". La respuesta es, como ya se mencionó, muy difícil. El estilo de programación funcional promueve la asignación de estructuras de datos recursivas a voluntad, lo que requiere una memoria de almacenamiento dinámico (ya sea recolección de basura o recuento de referencia). Sin embargo, existe una técnica de análisis del compilador bastante sofisticada llamada análisis de memoria basada en la región, mediante la cual el compilador puede dividir el montón en bloques grandes que pueden asignarse y desasignarse automáticamente, de manera similar a la asignación de la pila. La página de Wikipedia enumera varias implementaciones de la técnica, tanto para lenguajes "funcionales" como "imperativos".