Trampolining
Ricorsione sicura per lo stack
Trampolining è una lezione Scala for Backend Engineering & Functional Programming gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Scala for Backend Engineering & Functional Programming, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Il limite di @tailrec
@tailrec ottimizza solo una funzione che chiama direttamente sé stessa. Non può gestire la ricorsione reciproca (due funzioni che si chiamano a vicenda), che continua a far crescere lo stack. Il trampolining risolve il problema.
Il problema della ricorsione reciproca
Si considerino isEven e isOdd, definite l'una in termini dell'altra. Con un numero grande questa implementazione causa un overflow dello stack e nessuna delle due funzioni può essere annotata con @tailrec.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}Che cos'è un trampoline?
Un trampoline trasforma le chiamate ricorsive in dati. Anziché chiamare sé stessa, una funzione restituisce una descrizione del passaggio successivo. Un ciclo di controllo esegue ripetutamente questi passaggi, mantenendo lo stack piatto.
TailRec nella libreria standard
Scala fornisce scala.util.control.TailCalls con il tipo TailRec. Utilizzi done(x) per un risultato finale e tailcall(...) per rimandare la chiamata successiva.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done e tailcall
I due elementi fondamentali:
done(value)racchiude la risposta finale.tailcall(expr)rimanda una chiamata che restituisce unTailRec.
La chiamata a .result esegue il ciclo del trampoline e produce il valore.
Sicurezza rispetto allo stack
Poiché ogni tailcall restituisce il controllo al ciclo di controllo invece di annidare una chiamata Java, lo stack della JVM non cresce con la profondità della ricorsione. L'esempio precedente gestisce 100.000 passaggi senza overflow.
Trampolining della ricorsione su sé stessi
I trampoline funzionano anche con una ricorsione profonda ordinaria su sé stessi, quando non è facile utilizzare un accumulatore. Qui un conto alla rovescia profondo rimane sicuro rispetto allo stack.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Combinare i risultati con flatMap
TailRec supporta map e flatMap, quindi è possibile eseguire operazioni dopo una chiamata rimandata mantenendo la sicurezza rispetto allo stack.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}Come funziona il ciclo di controllo
Concettualmente, .result esegue un ciclo: prende il passaggio corrente; se è done, ne restituisce il valore; se è una chiamata rimandata, valuta un livello e continua. Il tutto utilizzando una quantità costante di spazio nello stack.
Trampolining nelle librerie di effetti
Librerie come Cats Effect e ZIO applicano internamente il trampolining alle catene di flatMap, consentendo di costruire programmi di effetti profondamente annidati senza overflow dello stack. Il trampolining è alla base degli effetti funzionali sicuri rispetto allo stack.
Quando utilizzare il trampolining
Usi un trampoline quando:
- hai una ricorsione reciproca che non può essere espressa come un'unica funzione ricorsiva in coda;
- la ricorsione è troppo profonda per lo stack e un accumulatore non è adatto.
Per la semplice ricorsione su se stessa, preferisci prima @tailrec con un accumulatore.
Controllo rapido
Verifica la tua comprensione dei trampoline.
Riepilogo
Hai imparato i trampoline:
- rendono sicure per lo stack le ricorsioni reciproche e molto profonde;
- usa
TailCalls:done(x)etailcall(...), quindi.result; TailRecsupportamap/flatMap;- sono alla base delle librerie di effetti sicure per lo stack.
Impara Scala con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 39
- Lezioni
- 143
Domande Frequenti
La lezione «Trampolining» è gratuita?
Sì — il testo completo di «Trampolining» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Scala for Backend Engineering & Functional Programming, passa a CoddyKit PRO. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Cosa imparerò in «Trampolining»?
Ricorsione sicura per lo stack Eserciti Scala for Backend Engineering & Functional Programming con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Scala for Backend Engineering & Functional Programming?
Non è richiesta alcuna esperienza precedente. Scala for Backend Engineering & Functional Programming su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Trampolining»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Scala for Backend Engineering & Functional Programming?
Sì. Ogni lezione Scala for Backend Engineering & Functional Programming include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.