¿Los programas en lenguajes funcionales tienen más probabilidades de tener desbordamientos de pila?

Question

Estoy empezando a aprender ocaml, y estoy realmente apreciando el poder de recursión en el idioma. Sin embargo, una cosa que me preocupa es el desbordamiento de la pila.

Si ocaml usa la pila para llamadas a funciones, ¿no se desbordará eventualmente la pila? Por ejemplo, si tengo la siguiente función:

let rec sum x = 
    if x > 1 then f(x - 1) + x 
    else x;; 

eventualmente debe causar un desbordamiento de la pila. Si tuviera que hacer lo equivalente en C++ (usando recursividad), sé que se desbordaría.

Así que mi pregunta es, ¿existe una protección integrada para evitar que los lenguajes funcionales desborden la pila? Si no es así, ¿no son menos útiles de este modo, ya que el algoritmo de suma anterior, escrito en un estilo de procedimiento con un ciclo for, podría manejar cualquier número (desbordamiento de entero des-relacionado)?

Answer 1

Todas las implementaciones decentes de ;-) idiomas funcionales optimizan la recursividad de cola, pero eso no es lo que estás haciendo aquí, ya que la llamada recursiva no es la ÚLTIMA operación (debe ir seguida de la suma).

Entonces, uno pronto aprende a usar una función auxiliar que ES cola recursiva (y toma el total actual acumulado como argumento) para que el optimizador pueda hacer su trabajo, es decir, neto de la posible sintaxis de O'Caml en la que 'm oxidado:

let sum x = 
    aux(x)(0);; 

let rec aux x accum = 
    if x > 1 then aux(x - 1)(accum + x) 
    else (accum + x);; 

en este caso, la suma pasa como argumento a la llamada recursiva, es decir, ante la propia recursividad, y por lo tanto la optimización de cola puede patear (debido a que la recursividad es la última cosa que tiene que ocurrir !).

Answer 2

Algunos lenguajes funcionales como Scheme especifican que tail recursiondebe estar optimizado para ser equivalente a la iteración; por lo tanto, una función recursiva de la cola en Scheme nunca resultará en un desbordamiento de la pila, sin importar cuántas veces recurra (suponiendo, por supuesto, que no se repita o se repita recíprocamente en otros lugares además del final).

La mayoría de los otros lenguajes funcionales no requieren que la recursión de cola se implemente de manera eficiente; algunos optan por hacerlo, otros no, pero es relativamente fácil de implementar, por lo que espero que la mayoría de las implementaciones lo hagan.

Answer 3

Los lenguajes funcionales suelen tener una pila MUCHO más grande. Por ejemplo, escribí una función específicamente para probar los límites de la pila en OCaml, y llegó a más de 10.000 llamadas antes de que estallara. Sin embargo, tu punto es válido. El desbordamiento de pila sigue siendo algo que hay que tener en cuenta en los lenguajes funcionales.

Una de las estrategias que usan los lenguajes funcionales para mitigar su dependencia de la recursión es el uso de tail-call optimization. Si la llamada a la siguiente recursión de la función actual es la última declaración en la función, la llamada actual puede descartarse de la pila y la nueva llamada crear una instancia en su lugar. Las instrucciones de ensamblaje que se generan serán básicamente las mismas que las de while-loops en estilo imperativo.

Su función no es optimizable porque la recursión no es el último paso. Necesita regresar primero y luego puede agregar x al resultado.Por lo general, esto es fácil de recorrer, que acaba de crear una función auxiliar que pasa a un acumulador junto con los otros parámetros

let rec sum x = 
    let sum_aux accum x = 
    if x > 1 then sum_aux (accum + x) (x - 1) 
    else x 
    in sum_aux 0 x;; 

Answer 4

Esto es complicado - en principio sí, pero los compiladores y tiempos de ejecución de los lenguajes funcionales en cuenta el mayor grado de recursión en los lenguajes funcionales. El más básico es que la mayoría de los tiempos de ejecución de lenguaje funcional requieren una pila mucho más grande que la que usarían los programas iterativos normales. Pero además de eso, un compilador de lenguaje funcional es mucho más capaz de transformar código recursivo en no recursivo debido a las restricciones mucho más estrictas del lenguaje.

Answer 5

Es ciertamente fácil para los novatos escribir recursiones profundas que explotan la pila. El objetivo Caml es inusual en que las funciones de biblioteca List no son apilables para listas largas. Las aplicaciones como Unison han reemplazado la biblioteca estándar Caml List con una versión apilable. La mayoría de las otras implementaciones hacen un mejor trabajo con la pila. (Descargo de responsabilidad: mi información describe Objective Caml 3.08; la versión actual, 3.11, puede ser mejor.)

Standard ML of New Jersey es inusual en que no usa una pila, por lo que sus recursiones profundas continúan hasta que se quede sin montón . Se describe en el excelente libro de Andrew Appel Compiling with Continuations.

No creo que haya un problema serio aquí; es más un "punto de conciencia" de que si vas a escribir un montón de código recursivo, que es más probable que hagas en un lenguaje funcional, debes tener en cuenta las llamadas sin cola y el tamaño de la pila como en comparación con el tamaño de los datos que procesará.