Optimisation des appels terminaux en

À propos de Optimisation des appels terminaux

À chaque appel d'une fonction, un nouveau cadre de pile est créé en mémoire pour stocker les arguments et les variables locales de cette fonction, puis ce cadre de pile est libéré lorsque la fonction renvoie. Comme Gleam utilise des appels de fonction récursifs plutôt qu'une syntaxe de boucle, ces cadres de pile peuvent finir par consommer une grande quantité de mémoire.

Pour éviter ce problème, Gleam prend en charge l'optimisation des appels terminaux, qui permet au compilateur de réutiliser le cadre de pile de la fonction courante lorsqu'un appel de fonction est la dernière chose que fait la fonction. Une fonction peut donc s'appeler elle-même un nombre infini de fois sans utiliser de mémoire supplémentaire.

Les fonctions récursives non optimisées peuvent souvent être réécrites en fonctions optimisées pour les appels terminaux grâce à un accumulateur.

Un accumulateur est une variable transmise en plus des données. Il sert à transmettre l'état courant de l'exécution de la fonction, jusqu'à ce que le cas de base soit atteint.

L'accumulateur doit être initialisé par l'auteur de la fonction, et non par son utilisateur. Pour cela, on déclare deux fonctions : une fonction publique qui prend uniquement les données nécessaires en arguments et initialise l'accumulateur, et une fonction privée qui prend aussi un accumulateur.

// 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
    }
  }
}