Ottimizzazione delle chiamate in coda in

Informazioni su Ottimizzazione delle chiamate in coda

Ogni volta che viene chiamata una funzione, in memoria viene creato un nuovo stack frame per memorizzare gli argomenti e le variabili locali della funzione, e questo stack frame viene deallocato quando la funzione restituisce. Dato che Gleam usa chiamate di funzioni ricorsive invece della sintassi dei cicli, questo può comportare un notevole utilizzo di memoria da parte di questi stack frame.

Per evitare questo problema Gleam supporta l'ottimizzazione delle chiamate in coda, che permette al compilatore di riutilizzare lo stack frame della funzione corrente se una chiamata di funzione è l'ultima cosa che la funzione fa. Questo significa che una funzione può chiamare se stessa un numero infinito di volte senza usare memoria aggiuntiva.

Le funzioni ricorsive non ottimizzate spesso possono essere riscritte in funzioni con ottimizzazione delle chiamate in coda usando un accumulatore.

Un accumulatore è una variabile che viene passata insieme ai dati. Serve a trasmettere lo stato corrente dell'esecuzione della funzione, finché non si raggiunge il caso base.

Gli accumulatori dovrebbero essere inizializzati dall'autore della funzione, non dall'utente della funzione. Per ottenere questo, dichiara due funzioni: una funzione pubblica che prende solo i dati necessari come argomenti e inizializza l'accumulatore, e una funzione privata che prende anche un accumulatore.

// Count the length of a list without tail call optimisation
pub fn count(list: List(String)) -> Int {
  case list {
    [] -> 0
    [_, ..rest] -> {
      let amount = count(rest) // Non-tail recursive call
      amount + 1
    }
  }
}

// Count the length of a list with tail call optimisation
pub fn count(list: List(String)) -> Int {
  count_elements(list, 0)
}

fn count_elements(list: List(String), accumulator: Int) -> Int {
  case list {
    [] -> accumulator
    [_, ..rest] -> {
      let accumulator = accumulator + 1
      count_elements(rest, accumulator) // Tail recursive call
    }
  }
}