Tail-Call-Optimierung in

Über Tail-Call-Optimierung

Jedes Mal, wenn eine Funktion aufgerufen wird, wird im Speicher ein neuer Stackframe angelegt, um die Argumente und lokalen Variablen der Funktion zu speichern. Dieser Stackframe wird freigegeben, wenn die Funktion zurückkehrt. Da Gleam rekursive Funktionsaufrufe anstelle einer Schleifensyntax verwendet, kann dies dazu führen, dass diese Stackframes viel Speicher belegen.

Um dieses Problem zu vermeiden, unterstützt Gleam die Tail-Call-Optimierung. Sie erlaubt es dem Compiler, den Stackframe der aktuellen Funktion wiederzuverwenden, wenn ein Funktionsaufruf das Letzte ist, was die Funktion tut. Das bedeutet, dass eine Funktion sich selbst unendlich oft aufrufen kann, ohne zusätzlichen Speicher zu verwenden.

Unoptimierte rekursive Funktionen lassen sich oft in tail-call-optimierte Funktionen umschreiben, indem man einen Akkumulator verwendet.

Ein Akkumulator ist eine Variable, die zusätzlich zu den Daten übergeben wird. Er wird verwendet, um den aktuellen Zustand der Ausführung der Funktion weiterzugeben, bis der Basisfall erreicht ist.

Akkumulatoren sollten vom Autor der Funktion initialisiert werden, nicht vom Benutzer der Funktion. Um das zu erreichen, deklariere zwei Funktionen: eine öffentliche Funktion, die nur die notwendigen Daten als Argumente entgegennimmt und den Akkumulator initialisiert, und eine private Funktion, die zusätzlich einen Akkumulator entgegennimmt.

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