Sono programmi in linguaggi funzionali più probabilità di avere overflow dello stack?

Question

Sto iniziando a imparare OCaml, e sono veramente apprezzare la potenza della ricorsione nella lingua. Tuttavia, una cosa che mi preoccupa è overflow dello stack.

Se OCaml utilizza lo stack per le chiamate di funzione, non sarà che alla fine overflow dello stack? Per esempio, se ho la seguente funzione:

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

deve infine causare uno stack overflow. Se dovessi fare la cosa equivalente in C ++ (utilizzando la ricorsione), so che sarebbe traboccare.

Quindi la mia domanda è, è costruito in misure di salvaguardia per evitare linguaggi funzionali dal traboccante la pila? In caso contrario, non sono forse meno utili come questo, dal momento che l'algoritmo di somma di cui sopra, scritto in uno stile procedurale con un ciclo for, in grado di gestire un numero qualsiasi (dis-per quanto riguarda integer overflow)?

Answer 1

Tutte le implementazioni (decenti di ;-) linguaggi funzionali ottimizzare ricorsione in coda, ma non è quello che stai facendo qui, dal momento che la chiamata ricorsiva non è l'ultima operazione (ha bisogno di essere seguita dall'aggiunta).

Quindi, si impara presto ad utilizzare una funzione ausiliaria che IS coda ricorsiva (e batte il totale corrente che viene accumulato come argomento) cosicché l'ottimizzatore può fare il suo lavoro, cioè, al netto di eventuali sintassi O'Caml in cui' m arrugginito:

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

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

Qui, la somma avviene come argomento per la chiamata ricorsiva, vale a dire, prima che la ricorsione in sé, e così l'ottimizzazione coda può calci in (perché la ricorsione è l'ultima cosa che deve accadere!).

Answer 2

I linguaggi funzionali in genere hanno uno stack molto più grande. Per esempio, ho scritto una funzione specificamente per testare i limiti dello stack in OCaml, ed è arrivato a oltre 10.000 chiamate prima che barfed. Tuttavia, il punto è valido. Stack-overflow sono ancora qualcosa che dovete guardare fuori per in linguaggi funzionali.

Una delle strategie che usano linguaggi funzionali per mitigare la loro dipendenza ricorsione è l'uso di ottimizzazione coda chiamata . Se la chiamata al successivo ricorsione della funzione corrente è l'ultima dichiarazione nella funzione, la chiamata in corso può essere scartato dalla pila e la nuova chiamata un'istanza al suo posto. Le istruzioni di montaggio che vengono generati saranno fondamentalmente lo stesso come quelli per while-loop in stile imperativo.

La vostra funzione non è tail-call ottimizzabile perché la ricorsione non è l'ultimo passo. Ha bisogno di tornare e poi si può aggiungere x al risultato. Di solito questo è facile andare in giro, basta creare una funzione di supporto che passa un accumulatore con gli altri parametri

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

Alcune lingue funzionali come Scheme specificano che ricorsione deve essere ottimizzate equivalenti ai iterazione; quindi, una funzione ricorsiva in coda in regime sarà mai comportare un overflow dello stack, non importa quante volte ricorsivamente (presumendo, naturalmente, che non si anche ricorsione o impegnarsi in ricorsione reciproca in altri luoghi oltre la fine).

La maggior parte delle altre lingue funzionali non richiedono la ricorsione in coda da attuare in modo efficiente; alcuni scelgono di farlo, altri no, ma è relativamente facile da implementare, quindi ci si aspetta che la maggior parte delle implementazioni di farlo.

Answer 4

E 'certamente facile per i novizi di scrivere ricorsioni profonde che soffiano lo stack. Obiettivo Caml è insolito in quanto Le funzioni di libreria List non sono stack sicuro per lunghi elenchi . Applicazioni come Unison hanno effettivamente sostituito la libreria standard di List Caml con una pila di sicurezza versione. La maggior parte delle altre implementazioni fare un lavoro migliore con la pila. (Disclaimer:. I miei dati descrivono Obiettivo Caml 3.08, la versione corrente, 3.11, può essere meglio)

standard ML del New Jersey è insolito in quanto non usa uno stack, così il vostro profondo ricorsioni Proseguire fino a corto di cumulo. E 'descritto nel libro eccellente di Andrew Appel compilazione con Continuazioni .

Non credo che ci sia un problema serio qui; è più un "punto di consapevolezza" che se avete intenzione di stare scrivendo un sacco di codice ricorsivo, che è molto più probabile da fare in un linguaggio funzionale, è necessario essere consapevoli di chiamate non-coda e di dimensione dello stack come rispetto alle dimensioni dei dati sarete elaborazione.

Answer 5

Questo è difficile - in linea di principio sì, ma i compilatori e runtime per linguaggi funzionali rappresentano il maggiore grado di ricorsione in linguaggi funzionali. Il più fondamentale è che la maggior parte dei tempi di esecuzione linguaggio funzionale richiedere uno stack molto più grande rispetto ai normali programmi iterativi avrebbe utilizzato. Ma in aggiunta a quello di un compilatore linguaggio funzionale è molto più in grado di trasformare il codice ricorsivo in un non-ricorsiva a causa dei vincoli molto rigorosi della lingua.