Son programas en los lenguajes funcionales más propensos a tener desbordamientos de pila?

Question

Me estoy empezando a aprender ocaml, y estoy realmente apreciando el poder de la recursividad en el idioma. Sin embargo, una cosa que me preocupa es desbordamientos de pila.

Si ocaml usa la pila de llamadas de función, no el tiempo se desborde la pila? Por ejemplo, si tengo la siguiente función:

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

tiene que llegar a causar un desbordamiento de pila. Si tuviera que hacer lo que es equivalente en C ++ (utilizando la recursividad), sé que se desbordaría.

Así que mi pregunta no es, está integrado medidas para evitar que los lenguajes funcionales se desborde la pila? Si no, no son menos útiles como este, ya que el algoritmo de suma anterior, escrito en un estilo de procedimiento con un bucle, podía manejar cualquier número (dis-con respecto a desbordamiento de entero)?

Answer 1

Todas las implementaciones (dignas de ;-) lenguajes funcionales optimizar la recursión de cola, pero eso no es lo que estás haciendo aquí, ya que la llamada recursiva no es la última operación (que debe ser seguido por la adición).

Por lo tanto, uno pronto aprende a usar una función auxiliar que se cola recursiva (y toma la corriente total que se acumula como un argumento) por lo que el optimizador puede hacer su trabajo, es decir, neto de sintaxis posible O'Caml en la que I' 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 la cola puede golpear en (debido a que la recursividad es la última cosa que tiene que ocurrir!).

Answer 2

Los lenguajes funcionales tienen típicamente una pila mucho más grande. Por ejemplo, he escrito 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 vomitó. Sin embargo, su punto es válido. Stack-desbordamientos son todavía algo que tienes que tener en cuenta en los lenguajes funcionales.

Una de las estrategias que utilizan los lenguajes funcionales para mitigar su dependencia de la recursividad es el uso de optimización de llamada . Si la llamada a la siguiente recursión de la función actual es la última sentencia de la función, la llamada actual puede ser descartado de la pila y la llamada nueva instancia en su lugar. Las instrucciones de montaje que se generan serán básicamente los mismos que los de los bucles while-en el estilo imperativo.

Su función no es optimizable de llamada final debido a que la recursividad no es el último paso. Tiene que volver primero y luego se puede añadir x para el 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 3

Algunos lenguajes funcionales como Scheme especifican que recursividad debe ser optimizada para ser equivalente a la iteración; por lo tanto, una función recursiva de cola en el Esquema no dará lugar a un desbordamiento de pila, no importa cuántas veces se recursivamente (suponiendo, por supuesto, que no tenga también recursivo o participar en la recursión mutua en otros lugares, además del final).

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

Answer 4

Es ciertamente fácil para los principiantes a escribir recurrencias profundas que soplan la pila. Objetivo Caml es inusual, ya que las funciones de la biblioteca están List No apile-seguro para largas listas . Aplicaciones como Unison realidad han sustituido a la biblioteca estándar List Caml con una pila de fallos versión. La mayoría de las otras implementaciones hacer un mejor trabajo con la pila. (Negación:. Mi información describe Objetivo Caml 3,08; la versión actual, 3.11, puede ser mejor)

ml estándar de Nueva Jersey es inusual, ya que no utiliza una pila, por lo que su profunda recurrencias seguir adelante hasta que se le acaba el montón. Es descrito en el excelente libro de Andrew Appel Compilar con continuaciones .

No creo que hay un problema serio aquí; que es más un "punto de conciencia" que si usted va a estar escribiendo un montón de código recursivo, lo que es más probable que lo haga en un lenguaje funcional, que tiene que estar al tanto de las llamadas no cola y del tamaño de la pila como en comparación con el tamaño de los datos que va a ser procesado.

Answer 5

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