Implementazione runtime di ricorsività Java rispetto ad altri/linguaggi funzionali?

Question

Mi piace la ricorsione, ma a Java si incontra un vicolo cieco ad un certo punto. Per esempio. Ho avuto un caso in cui la ricorsione con ~ 100K iterazioni non avrebbe funzionato (StackOverflowError). Purtroppo ho dovuto passare al fastidioso "ciclo imperativo" per i motivi di limite dello stack di runtime.

Mi chiedo come altre lingue (specialmente funzionali) ignorino lo stack-overflow durante il runtime? Immagino che i runtime linguistici funzionino in modo particolare meglio di questo problema perché la ricorsione è il core-concept ...

Qualcuno ha qualche informazione o risorse esterne?

Answer 1

La maggior parte delle lingue ha ottimizzazioni del compilatore per tail recursion. Ricorsione di coda significa che la chiamata ricorsiva dovrebbe essere l'ultima chiamata del metodo ricorsivo. Il compilatore può quindi ottimizzare questo in un ciclo, evitando che si verifichino errori di overflow dello stack.

Non sono sicuro che tutte le implementazioni di javac implementino la ricorsione in coda. Non è qualcosa che è richiesto dalle specifiche. Tuttavia, è una tecnica di ottimizzazione importante per qualsiasi programma ricorsivo, quindi suppongo che le implementazioni mainstream forniscano la ricorsione della coda.

È possibile eseguire il test da soli eseguendo un (semplice) programma non ricorsivo che genera uno StackOverflowError e rendendolo ricorsivo in coda (calcolo di un factorial, ad esempio).

EDIT: in precedenza, in Java, è stato inserito question about tail recursion, come indicato in un commento dall'utente sje397. Dai un'occhiata anche a Stephen C's answer a questa domanda, che fornisce alcune informazioni aggiuntive.

Answer 2

È possibile aumentare Java Dimensione stack con:

java -Xss1024k MyProgram 

(aumenterà la dimensione dello stack di java fino a 1024 KB.) ma in generale non è una buona idea usare quel profondo ricorsione. Prova a fare una soluzione iterativa.

Answer 3

"la ricorsione con iterazioni ~ 100K" è qualcosa che dovrebbe essere evitato, non solo in Java. Funziona solo grazie all'ottimizzazione delle chiamate tail, che non è sempre possibile. Quindi è meglio non abituarsi all'eccessiva ricorsione in primo luogo.

ricorsione è uno di quei concetti persone tendono a farne un utilizzo eccessivo la prima volta che a imparare, perché sembra semplicemente troppo freddo per non sfoggiare ovunque ...

Answer 4

Si tratta di un follow-up a @Ronald risposta di Wildenberg:

Non sono sicuro se tutte le implementazioni di javac implementino la ricorsione della coda. Non è qualcosa che è richiesto dalle specifiche.

La risposta breve è che non lo supportano.

La risposta più lunga è che l'ottimizzazione della ricorsione in coda è un problema complicato in Java a causa della progettazione JVM. Leggi this blog entry di John Rose @ Oracle dove parla di questo problema. La spinta principale del post di blog è una proposta di estensione bytecode per supportare chiamate "hard" tail. Ma l'ultimo paragrafo suggerisce perché l'implementazione di chiamate "soft" (cioè trasparenti) è difficile.L'ottimizzazione delle chiamate di coda interferisce con la capacità della JVM di acquisire una traccia dello stack e questo ha "implicazioni" per l'architettura di sicurezza Java.

Questo Sun Bug Database Entry fornisce ulteriori dettagli sul problema. Leggi anche i commenti.

Sembra che il modo di implementare la ricorsione in coda sulla JVM corrente sia implementarlo nel front-end del compilatore. Apparentemente Scala lo fa.

Answer 5

Come altre persone hanno menzionato, il supporto per una corretta ricorsione della coda aiuta. Ma da solo non è abbastanza per supportare la ricorsione profonda. E nonostante ciò che i programmatori BLUB potrebbero pensare, la ricorsione profonda è un adattamento naturale per alcune attività, come l'elaborazione di strutture di dati profondamente ricorsive.

Le strategie per supportare la ricorsione profonda (non di coda) sono spesso sussunte da strategie per supportare continuazioni di prima classe. Potresti trovare Implementation Strategies for First-Class Continuations (Clinger et al) interessante.

Poche strategie al largo della parte superiore della mia testa:

• CPS-convertire il vostro programma o in altro modo heap-allocare telai di continuazione (svantaggio: perde alcuni vantaggi prestazionali della pila)
• su stack overflow, copiare lo stack in un blocco di memoria separato e reimpostare il puntatore dello stack sulla base; in underflow, copia il vecchio stack in
• in overflow dello stack, alloca una nuova regione dello stack dall'heap e reimposta il puntatore dello stack lì; su underflow, tornare alla fine del vecchio stack
• in overflow dello stack, creare un nuovo thread per continuare a eseguire il calcolo e attendere il risultato del thread (svantaggi: la creazione di un thread può essere costosa (ma i thread di lavoro possono essere memorizzato nella cache) e lo spostamento di un calcolo su thread può causare havok con archiviazione locale thread ecc.