Lo stack trabocca dalla profonda ricorsione in Java?

Dopo aver fatto esperienza con i linguaggi funzionali, sto iniziando a usare la ricorsione più in Java – Ma il linguaggio sembra avere uno stack di chiamate relativamente basso di circa 1000.

C’è un modo per aumentare lo stack delle chiamate? Come posso creare funzioni che sono milioni di chiamate profonde, come in Erlang?

Lo sto notando sempre di più quando faccio problemi con Project Euler.

Grazie.

Immagino che potresti usare questi parametri

-ss Stacksize per aumentare la dimensione dello stack nativo o

-oss Stacksize per aumentare le dimensioni dello stack Java,

La dimensione dello stack nativo predefinito è 128k, con un valore minimo di 1000 byte. La dimensione predefinita dello stack java è 400k, con un valore minimo di 1000 byte.

http://edocs.bea.com/wls/docs61/faq/java.html#251197

MODIFICARE:

Dopo aver letto il primo commento (Chuck’s), oltre a leggere la domanda e leggere altre risposte, vorrei chiarire che ho interpretato la domanda semplicemente come “aumentare le dimensioni dello stack”. Non intendevo dire che puoi avere stack infiniti, come nella programmazione funzionale (un paradigma di programmazione che ho solo graffiato la sua superficie).

Aumentare le dimensioni dello stack servirà solo come benda temporanea. Come altri hanno sottolineato, ciò che si vuole veramente è l’eliminazione della coda, e Java non ha questo per vari motivi. Tuttavia, puoi imbrogliare se vuoi.

Pillola rossa in mano? OK, in questo modo per favore.

Esistono modi in cui è ansible scambiare lo stack per l’heap. Ad esempio, anziché effettuare una chiamata ricorsiva all’interno di una funzione, restituire una infrastruttura lazy che effettua la chiamata quando viene valutata. È quindi ansible scaricare lo “stack” con for-construct di Java. Dimostrerò con un esempio. Considera questo codice Haskell:

map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = (fx) : map f xs 

Nota che questa funzione non valuta mai la coda della lista. Quindi la funzione in realtà non ha bisogno di effettuare una chiamata ricorsiva. In Haskell, in realtà restituisce un thunk per la coda, che viene chiamato se è mai necessario. Possiamo fare la stessa cosa in Java (questo usa le classi da Java funzionale ):

 public  Stream map(final F f, final Stream as) {return as.isEmpty() ? nil() : cons(ff(as.head()), new P1>() {public Stream _1() {return map(f, as.tail);}});} 

Nota che Stream consiste di un valore di tipo A e un valore di tipo P1 che è come un thunk che restituisce il resto dello stream quando viene chiamato _1 (). Sebbene sembri certamente una ricorsione, la chiamata ricorsiva alla mappa non viene creata, ma diventa parte della struttura del stream.

Questo può quindi essere svolto con un normale costrutto.

 for (Stream b = bs; b.isNotEmpty(); b = b.tail()._1()) {System.out.println(b.head());} 

Ecco un altro esempio, visto che stavi parlando di Project Euler. Questo programma utilizza le funzioni reciprocamente ricorsive e non fa saltare lo stack, anche per milioni di chiamate:

 import fj.*; import fj.data.Natural; import static fj.data.Enumerator.naturalEnumerator; import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd; import fj.data.Stream; import fj.data.vector.V2; import static fj.data.Stream.*; import static fj.pre.Show.*; public class Primes {public static Stream primes() {return cons(natural(2).some(), new P1>() {public Stream _1() {return forever(naturalEnumerator, natural(3).some(), 2) .filter(new F() {public Boolean f(final Natural n) {return primeFactors(n).length() == 1;}});}});} public static Stream primeFactors(final Natural n) {return factor(n, natural(2).some(), primes().tail());} public static Stream factor(final Natural n, final Natural p, final P1> ps) {for (Stream ns = cons(p, ps); true; ns = ns.tail()._1()) {final Natural h = ns.head(); final P1> t = ns.tail(); if (naturalOrd.isGreaterThan(h.multiply(h), n)) return single(n); else {final V2 dm = n.divmod(h); if (naturalOrd.eq(dm._2(), ZERO)) return cons(h, new P1>() {public Stream _1() {return factor(dm._1(), h, t);}});}}} public static void main(final String[] a) {streamShow(naturalShow).println(primes().takeWhile (naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}} 

Un’altra cosa che puoi fare per scambiare lo stack per l’heap è usare più thread . L’idea è che invece di fare una chiamata ricorsiva, si crea un thunk che effettua la chiamata, si passa questo thunk a un nuovo thread e si lascia che il thread corrente esca dalla funzione. Questa è l’idea alla base di cose come Stackless Python.

Quello che segue è un esempio di ciò in Java. Mi scuso che è un po ‘opaco guardare senza le clausole import static :

 public static  Promise foldRight(final Strategy s, final F> f, final B b, final List as) {return as.isEmpty() ? promise(s, Pp(b)) : liftM2(f).f (promise(s, Pp(as.head()))).f (join(s, new P1>>() {public Promise _1() {return foldRight(s, f, b, as.tail());}}));} 

Strategy s è supportata da un pool di thread e la funzione promise passa un thunk al pool di thread, restituendo una Promise , che è molto simile a java.util.concurrent.Future , solo migliore. Vedere qui. Il punto è che il metodo sopra ripiega un datastructure destro ricorsivo a destra nello stack O (1) , che di solito richiede l’eliminazione di tail-call. Quindi abbiamo effettivamente ottenuto TCE, in cambio di una certa complessità. Chiameresti questa funzione come segue:

 Strategy s = Strategy.simpleThreadStrategy(); int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim(); System.out.println(x); // 49995000 

Nota che quest’ultima tecnica funziona perfettamente per la ricorsione non lineare. Cioè, verrà eseguito in algoritmi di stack costanti che non hanno chiamate tail.

Un’altra cosa che puoi fare è impiegare una tecnica chiamata trampolino . Un trampolino è un calcolo, reificato come una struttura di dati, che può essere attraversato. La libreria Java funzionale include un tipo di dati Trampoline che ho scritto, che consente in effetti di trasformare qualsiasi chiamata di funzione in una coda. Ad esempio, ecco un foldRightC che si piega a destra nello stack costante:

 public final  Trampoline foldRightC(final F2 f, final B b) {return Trampoline.suspend(new P1>() {public Trampoline _1() {return isEmpty() ? Trampoline.pure(b) : tail().foldRightC(f, b).map(ff(head()));}});} 

È lo stesso principio dell’utilizzo di più thread, tranne per il fatto che anziché richiamare ogni passaggio nel proprio thread, costruiamo ogni passo sull’heap, proprio come usare un Stream , e quindi eseguiamo tutti i passaggi in un singolo ciclo con Trampoline.run .

È compito della JVM decidere se ricorrere o meno alla ricorsione in coda – non so se qualcuno di loro lo sa, ma non dovresti fare affidamento su di esso. In particolare, cambiare le dimensioni dello stack sarebbe molto raramente la cosa giusta da fare, a meno che tu non avessi un limite rigido di quanti livelli di ricorsione avresti effettivamente utilizzato, e sapevi esattamente quanta parte dello stack occuperebbe ciascuno. Molto fragile

Fondamentalmente, non dovresti usare la ricorsione illimitata in una lingua che non è costruita per questo. Dovrai invece usare l’iterazione, temo. E sì, a volte può essere un leggero dolore 🙁

Se devi chiedere, probabilmente stai facendo qualcosa di sbagliato .

Ora, mentre probabilmente puoi trovare un modo per aumentare lo stack predefinito in java, permettimi di aggiungere i miei 2 cent in quanto hai davvero bisogno di trovare un altro modo per fare ciò che vuoi fare, invece di fare affidamento su uno stack maggiore.

Poiché le specifiche java non rendono obbligatorio per JVM implementare tecniche di ottimizzazione della ricorsione in coda, l’unico modo per aggirare il problema è ridurre la pressione dello stack, riducendo il numero di variabili / parametri locali che devono essere mantenuti traccia di, o idealmente, semplicemente riducendo il livello di ricorsione in modo significativo, o semplicemente riscrivendo senza ricorsione.

La maggior parte delle lingue funzionali ha il supporto per la ricorsione della coda. Tuttavia, la maggior parte dei compilatori Java non supporta questo. Invece fa un’altra chiamata di funzione. Ciò significa che ci sarà sempre un limite superiore al numero di chiamate ricorsive che puoi effettuare (dato che alla fine esaurirai lo spazio di stack).

Con la ricorsione in coda riutilizzi il frame dello stack della funzione che si sta verificando, quindi non hai gli stessi vincoli sullo stack.

Puoi impostarlo sulla riga di comando:

class java -Xss8M

Clojure, che gira su Java VM, vorrebbe molto implementare l’ottimizzazione delle chiamate tail, ma non è ansible a causa di una restrizione nel bytecode JVM (non conosco i dettagli). Di conseguenza, può solo aiutare se stesso con una speciale forma “recidiva”, che implementa alcune caratteristiche di base che ti aspetteresti da una corretta ricorsione della coda.

In ogni caso, ciò significa che la JVM attualmente non supporta l’ottimizzazione delle chiamate tail. Suggerisco vivamente di non utilizzare la ricorsione come costrutto di loop generale sulla JVM. La mia opinione personale è che Java non è un linguaggio sufficientemente avanzato.

Mi sono imbattuto nello stesso problema e ho finito per riscrivere la ricorsione in un ciclo for e questo ha fatto il trucco.

in eclipse se si utilizza, impostare -xss2m come argomenti vm.

o

-xss2m direttamente sulla riga di comando.

 java -xss2m classname