Оптимізація хвостових викликів у

Про концепцію Оптимізація хвостових викликів

Щоразу, коли ми викликаємо функцію, в памʼяті створюється новий стековий фрейм, у якому зберігаються аргументи та локальні змінні цієї функції. Коли функція повертає значення, цей стековий фрейм звільняється. Оскільки Gleam використовує рекурсивні виклики функцій замість синтаксису циклів, ці стекові фрейми можуть займати великий обсяг памʼяті.

Щоб уникнути цієї проблеми, Gleam підтримує оптимізацію хвостових викликів: вона дозволяє компілятору повторно використати стековий фрейм поточної функції, якщо виклик функції є останньою дією, яку виконує функція. Це означає, що функція може викликати себе нескінченну кількість разів, не витрачаючи додаткової памʼяті.

Неоптимізовані рекурсивні функції часто можна перетворити на функції з оптимізацією хвостових викликів, скориставшись акумулятором.

Акумулятор - це змінна, яку передають разом із даними. У ньому зберігається поточний стан виконання функції, доки не буде досягнуто базового випадку.

Акумулятор має ініціалізувати автор функції, а не її користувач. Щоб цього досягти, оголосимо дві функції: публічну, яка приймає лише потрібні дані як аргументи й ініціалізує акумулятор, і приватну, яка додатково приймає акумулятор.

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