末尾呼び出し最適化 の

末尾呼び出し最適化について

関数が呼び出されるたびに、その関数の引数とローカル変数を保存するための新しいスタックフレームがメモリ内に作成され、関数が戻るとこのスタックフレームは解放されます。Gleamはループ構文ではなく再帰関数呼び出しを使うため、これらのスタックフレームによって大量のメモリが使用されることがあります。

この問題を避けるために、Gleamは末尾呼び出し最適化をサポートしています。これは、関数が最後に行う処理が関数呼び出しである場合に、コンパイラーが現在の関数のスタックフレームを再利用できるようにするものです。つまり、関数は追加のメモリを一切使わずに、無限に自分自身を呼び出せるということです。

最適化されていない再帰関数は、_アキュムレーター_を使うことで、末尾呼び出し最適化された関数に書き換えられることがよくあります。

アキュムレーターは、データに加えて渡される変数です。これは、ベースケースに到達するまで、関数の実行の現在の状態を渡すために使われます。

アキュムレーターは、関数の利用者ではなく、関数の作成者が初期化する必要があります。そのためには、2つの関数を宣言します。必要なデータだけを引数に取り、アキュムレーターを初期化する公開関数と、アキュムレーターも受け取る非公開関数です。

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