Scalaではじめる末尾再帰

今回は、Scalaの末尾再帰について書いていきたいと思います。大学では型理論とかを学んだわけじゃないので割とそこらへんは雑です。

最近、再帰ロジックをプロダクションコードに導入するのが個人的に流行っているので、こういうテーマを選択しました。Scalaに関する末尾再帰の記事はそこそこ既に出揃っており、Scalaとして特に目新しいことは全く無いと思います。各セクションの下部、もしくは途中に参考資料のリンクを張っています。また、最下部に、全ての参考資料をまとめています。

## なぜ再帰で書くべきか

ツリーのような複雑な再帰データ構造は、メモリ効率の良い配列実装が一般的になっています。しかし人間からしてみると、**配列内部の状態と実際に構築されているツリーのイメージを結びつけることが困難**です。

![配列実装から木表現へのイメージ変換](https://qiita-image-store.s3.amazonaws.com/0/89550/ce8f5521-86cc-3c09-8f03-17fc85a2ed72.png)

そのためメモリ要件に特に厳しい制約が存在しない場合は、人間のイメージをできる限りそのまま表現したオブジェクトチェーンによるツリー構造をデザインした方が、ロジックの可読性を高めることができると考えられます。
再帰的データ型を用いることで、配列実装のデータ型を用いる時と比べ、以下のようなメリットを得ることができます（個人的感想）。

* **無制限なジャンプを制限する**
  * `while`ループを用いるようなジャンプ制御は、無制限なジャンプを可能にします。無制限なジャンプを使用したランダムアクセスが発生すると、存在しない値へのアクセス(`ArrayIndexOutOfRange`)や、意図しない制御への遷移など、バグの温床になります。)
* **再帰関数のロジックは直感的にわかりやすい**
  * `while`ループを用いるようなジャンプ制御では、カウンタ変数（例えば変数`i`,`j`のような）を導入して処理を行う。しかしカウンタ変数を用いたロジックは、本質的ではないのでわかりずらい。再帰ロジックであれば、思考をダイレクトに反映したロジックを記述しやすい。

ソフトウェア開発の現場では、再帰ロジックが使われることはあまり無いような気がします。弊社でも積極的に再帰を使用したロジックの記述はあまり見たことがありません。
しかし、リストやツリーをはじめとする再帰的データ型に対して、`while`ループのようなジャンプ制御を用いるより、再帰ロジックを用いた方がシンプルな記述になることが多いはずです。

しかし、再帰呼び出しは下手な実装を行ってしまうと、コールスタックを消費することによるスタックオーバーフローやメモリ不足を引き起こしてしまう可能性があります。
高い可用性が必須なプロダクション環境で、このようなエラーを発生させるロジックを採用することは危険を招きます。

そのため、再帰呼び出しをジャンプ制御に変換することができる末尾再帰パターンで記述される末尾再帰関数を実装する必要があります。

## 末尾再帰とは

Wikipediaによれば、

> 末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し （en:Tail call）という。呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある（#末尾呼出し最適化）。

* [末尾再帰 - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0)

ある関数が関数を呼び出す時、一般に呼び出し元と呼び出し先の両方の状態を保持する必要があるので、この情報をコールスタックに積んでいかなければなりません。これは再帰呼び出しでなくても再帰呼び出しでも変わらない点です。

再帰関数は`while`のようなジャンプ制御ではなく、関数内部で自分自身を再帰的に呼び出すことでループを表現します。その特性上、自分自身を大量に呼び出す必要があるケースが少なくありません。再帰呼び出しでもコールスタックを積んでいくので、メモリを消費してしまいスタックオーバーフローやメモリ不足に陥ることがあります。

再帰関数を、末尾再帰と呼ばれる再帰パターンで記述することで、言語によっては最適化を行えます。この最適化によって、コールスタックを消費する関数呼び出しではなく、ジャンプ制御に変換されます。ジャンプ制御に変換されることで、処理が高速になったり、スタックオーバーフローやメモリ不足に陥ることを防ぐことができます。

## Scalaにおける再帰と末尾再帰

では、Scalaにおける再帰と末尾再帰についてみていきましょう。

### Scalaで再帰を使うべき理由

配列などを用いた木構造の実装は非常にメモリ効率の良いものになりますが、前述したように実装理解が難しいと考えられます。また、配列を用いている以上、後の機能の追加や振る舞いの変更に対応しづらいかもしれません。

Scalaはオブジェクト指向と関数型のパラダイムを併せ持つ言語です。
そのため、豊かな表現力を持ったオブジェクトと、強力なパターンマッチである`match-case`式を用いた可読性の高い再帰関数を実装することが容易です。

### Scalaでの末尾最適化

* [Scala @tailrecメモ(Hishidama's Scala @tailrec Memo)](http://www.ne.jp/asahi/hishidama/home/tech/scala/annotation/tailrec.html)

Scalaにおいても末尾再帰で書かれた再帰関数は、コンパイラによって最適化がかかり、最終的にジャンプ制御に変換してくれます。実際には、`while`ループに変換されるようです。

Scalaには`@scala.annotation.tailrec`というアノテーションが用意されており、このアノテーションを付与したメソッドは、コンパイル時に末尾再帰かどうかをチェックしてくれます。もしこのアノテーションを付与したメソッドが末尾再帰の形になっていなければ、コンパイル時にエラーになり、最適化がかかっているか、かかっていないかを確認することができます。また、Intellijではコンパイルせずとも末尾再帰になっているかなっていないかをチェックする機能があり、大変便利です。

Scalaでは、再帰関数は`recursive`や`go`という単純な名前のローカルメソッドとして定義されることが多いようです。ローカルメソッドであれば、メソッド内で閉じた名前空間が生成され、他のメソッドで`recursive`や`go`という名前が衝突することもありませんし、ローカルメソッドはコンパイル時にクラス内の`private final`なメソッドとして定義されるようなので、呼び出しの度に関数定義が評価されるということはありません。

以下によく使う末尾再帰をロジックに使うメソッドの例を示します。

```Scala
def f(...): T = {
  @scala.annotation.tailrec
  def recursive(...): T = {
    ???
  }
  recursive(...)
}
```

### 末尾最適化されない再帰

残念ながら、Scalaでは末尾最適化できない末尾再帰パターンも存在します。
ここからは、末尾最適化できない2つの再帰を紹介します。

#### 末尾相互再帰

相互再帰は、複数の関数がお互いを再帰呼び出ししている形式の再帰です。
相互再帰を構成する関数が二つだけの場合は以下のようになります。

```Scala
def f(...): T = {
  def foo(...): T = {
    ??? // 最後の計算ステップがfooの呼び出しもしくはbarの呼び出し
  }
  def bar(...): T = {
    ??? // 最後の計算ステップがbarの呼び出しもしくはforの呼び出し
  }
  // fooもしくはbarの呼び出し
}
```

しかし、`foo`の関数内の最後の計算ステップで自分自身が呼び出されないので、Scalaでは末尾最適化を行うことができません。

* [お気楽 Scala プログラミング入門 - 再帰定義](http://www.geocities.jp/m_hiroi/java/scala03.html)
* [お気楽 Scala プログラミング入門 - 継続渡しスタイル](http://www.geocities.jp/m_hiroi/java/scala23.html)
* [Trampoline で再帰処理の最適化](https://qiita.com/torao@github/items/4b224489c71bf460ad7c)

#### 継続渡しスタイルの再帰

And/Or条件式を模した以下の多分木を、複数のAnd条件の線形リストに分解するようなロジックを考えましょう。

```Scala
sealed trait Cond[T]
final case class And[T](conds: Cond[T]*) extends Cond[T]
final case class Or[T](conds: Cond[T]*) extends Cond[T]
final case class Elem[T](value: T) extends Cond[T]
```

And/Or条件式の多分木は、以下のようにして複数の線形リストに分解することが可能です。

![And/Or条件式の多分木分解](https://qiita-image-store.s3.amazonaws.com/0/89550/fb55c1e3-5f9e-d2d9-19ee-6dbff3018dcc.png)

これは、どのような条件式でも以下の形に分解できるということです。

```
(値 and 値 [and 値]*) (or (値 and 値 [and 値]*))*
```

入力に対する出力サンプルは以下のようになっています。

```Scala
val cond = And[Int](
    Elem[Int](1),
    And[Int](
        Elem[Int](2),
        And[Int](
            Elem[Int](5),
            Elem[Int](6)),
        Elem[Int](7)),
    And[Int](
        Elem[Int](3),
        Elem[Int](4)))

scala> Cond.recursive(cond)
res: List[List[Int]] = List(List(1, 2, 5, 6, 7, 3, 4))

val cond = And[Int](
  Elem[Int](1),
  Or[Int](
    Elem[Int](2),
    And[Int](
      Or[Int](
        And[Int](Elem(10), Elem(11), Elem(21)),
        And[Int](Elem(32), Elem(9), Elem(12)),
        Elem(14)),
      Elem[Int](6)),
    Elem[Int](7)),
  And[Int](
    Elem[Int](3),
    Elem[Int](4)))

scala> Cond.recursive(cond)
res: List[List[Int]] = List(List(1, 2, 3, 4), List(1, 10, 11, 21, 6, 3, 4), List(1, 32, 9, 12, 6, 3, 4), List(1, 14, 6, 3, 4), List(1, 7, 3, 4))
```

まずは通常の再帰での実装を見ていきましょう。

```Scala
object Cond {
  
  def recursive[T](cond: Cond[T]): List[List[T]] =
    cond match {
      case And(Elem(value)) => (value :: Nil) :: Nil
      case And(cond: Cond[T]) => recursive(cond)
      case And(Elem(value), conds @ _*) =>
        recursive(And(conds: _*)) map (value :: _)
      case And(cond: Cond[T], conds @ _*) =>
        for {
          headExpr <- recursive(cond)
          tailExpr <- recursive(And(conds: _*))
        } yield headExpr ++ tailExpr
      case Or(Elem(value)) => (value :: Nil) :: Nil
      case Or(cond: Cond[T]) => recursive(cond)
      case Or(Elem(value), conds @ _*) =>
        (value :: Nil) :: recursive(Or(conds: _*))
      case Or(cond: Cond[T], conds @ _*) =>
        recursive(cond) ++ recursive(Or(conds: _*))
    }

}
```

通常の再帰の実装では`recursive(And(conds: _*)) map (value :: _)`をはじめとする複数箇所で、末尾呼び出しが自分自身になっていないため、`@tailrec`アノテーションを付けるとコンパイルエラーが発生します。
そこで、継続渡しスタイルと呼ばれる再帰関数の手法を用いることにしましょう。継続渡しスタイルは、今現在の関数呼び出しの中で、次の再帰呼び出しの結果に対する処理を記述した「継続」を渡すものです。
単に値を次の再帰呼び出しに渡すようなアキュムレーターとは異なり、関数を渡すことになります。
継続渡しスタイルに書き直した実装は以下になります。

```Scala
object Cond {

  def recursive[T](cond: Cond[T], cont: List[List[T]] => List[List[T]]): List[List[T]] =
    cond match {
      case And(Elem(value)) => cont((value :: Nil) :: Nil)
      case And(cond: Cond[T]) =>
        recursive(cond, (stacks: List[List[T]]) => cont(stacks))
      case And(Elem(value), conds @ _*) =>
        recursive(
          And(conds: _*),
          (stacks: List[List[T]]) => cont(stacks map (value :: _)))
      case And(cond: Cond[T], conds @ _*) =>
        recursive(
          cond,
          (headStacks: List[List[T]]) => {
            val concatExpr = for {
              headExpr <- headStacks
              tailExpr <-
                recursive(
                  And(conds: _*),
                  (tailStacks: List[List[T]]) => tailStacks)
            } yield headExpr ++ tailExpr
            cont(concatExpr)
          }
        )
      case Or(Elem(value)) => cont((value :: Nil) :: Nil)
      case Or(cond: Cond[T]) =>
        recursive(cond, (stacks: List[List[T]]) => cont(stacks))
      case Or(Elem(value), conds @ _*) =>
        recursive(
          Or(conds: _*),
          (stacks: List[List[T]]) => cont((value :: Nil) :: stacks))
      case Or(cond: Cond[T], conds @ _*) =>
        recursive(
          cond,
          (headStacks: List[List[T]]) => {
            val tailStacks =
              recursive(
                Or(conds: _*),
                (tailStacks: List[List[T]]) => tailStacks)
            cont(headStacks ++ tailStacks)
          }
        )
    }

}
```

末尾関数呼び出しが全て自分自身になっていることが確認できます。
しかし、`@tailrec`アノテーションを付けるとコンパイルエラーになってしまいます。Haskellなどの言語では、継続渡しスタイルは末尾最適化されるそうなのですが、Scalaと継続渡しスタイルは相性が悪いようで末尾最適化を行うことができないようです。

* [お気楽 Scala プログラミング入門 - 継続渡しスタイル](http://www.geocities.jp/m_hiroi/java/scala23.html)

### トランポリン化による末尾最適化

「末尾最適化されない再帰」では、末尾相互再帰と、継続渡しスタイルの再帰があることを紹介しました。しかし、トランポリン化と呼ばれる方法によって、標準では最適化ができなかった末尾再帰であっても最適化可能になります。トランポリン化自体の詳細についてはあまりわからないので、以下に参考資料を載せておきます。

* [Stackless Scala With Free Monads](http://blog.higher-order.com/assets/trampolines.pdf)
* [トランポリン化でStackOverflowの回避](http://www.amazon.co.jp/dp/4844337769http://www.amazon.co.jp/dp/4844337769)
* [Trampolineで再帰処理の最適化](https://qiita.com/torao@github/items/4b224489c71bf460ad7c)

Scalaでトランポリン化を使って末尾再帰最適化を行うには、`scala.util.control.TailCalls`を使う必要があります。
使用例は公式ドキュメントに載ってます。`Stackless Scala With Free Monads`という論文に基づいた実装がなされており、スタックレスな末尾再帰を記述することが可能になっているみたいです。

* [Scala Standard Library 2.12.7 - scala.util.control.TailCalls](https://www.scala-lang.org/api/current/scala/util/control/TailCalls$.htm)

注意すべきは、このトランポリン化によって行う末尾最適化というのはScalaがコンパイル時に「`while`ループに自動的に変換してくれるようにする」のではなく、「既にスタックレスな再帰が記述できている」ということです。ですので、トランポリン化したスタックレス再帰は`@scala.annotation.tailrec`アノテーションを付与すれば分かると思いますが、Scalaはそれが末尾最適化可能であるということを認識できていません


#### 末尾相互再帰

末尾相互再帰の場合でも同様にスタックレス再帰として記述することが可能です。

```Scala
def f(...): T = {
  def foo(...): TailRec[T] = {
    ??? // 最後の計算ステップがfooの呼び出しもしくはbarの呼び出し
  }
  def bar(...): TailRec[T] = {
    ??? // 最後の計算ステップがbarの呼び出しもしくはforの呼び出し
  }
  // (fooもしくはbarの呼び出し).result
}
```

#### 継続渡しスタイルの再帰

継続渡しスタイルの再帰は、トランポリン化を使うことで継続渡しスタイルではない形式で記述することができます。再帰呼び出しの結果を`map`や`flatMap`などを使って扱うことができます。

```Scala
object Cond {

  import scala.util.control.TailCalls._

  def recursive[T](cond: Cond[T]): TailRec[List[List[T]]] =
    cond match {
      case And(Elem(value)) => done((value :: Nil) :: Nil)
      case And(cond: Cond[T]) =>
        tailcall { recursive(cond) }
      case And(Elem(value), conds @ _*) =>
        tailcall { recursive(And(conds: _*)) } map { exprs =>
          exprs map (value :: _)
        }
      case And(cond: Cond[T], conds @ _*) =>
        for {
          headExprs <- tailcall { recursive(cond) }
          tailExprs <- tailcall { recursive(And(conds: _*)) }
        } yield for {
          headExpr <- headExprs
          tailExpr <- tailExprs
        } yield headExpr ++ tailExpr
      case Or(Elem(value)) => done((value :: Nil) :: Nil)
      case Or(cond: Cond[T]) =>
        tailcall { recursive(cond) }
      case Or(Elem(value), conds @ _*) =>
        tailcall { recursive(Or(conds: _*)) } map { exprs =>
          (value :: Nil) :: exprs
        }
      case Or(cond: Cond[T], conds @ _*) =>
        for {
          leftExprs <- tailcall { recursive(cond) }
          rightExprs <- tailcall { recursive(Or(conds: _*)) }
        } yield leftExprs ++ rightExprs
    }

}
```

トランポリン化によって記述されたスタックレス再帰は、通常の再帰で書かれた場合とよく似ているのがわかります。トランポリン化によって変わったのが、再帰呼び出しの結果が`TailRec[T]`でラップされているぐらいなので、通常の再帰で書いた場合とあまり変わりません。

## まとめ

一般的な末尾再帰、再帰的データ型のメリット、Scalaにおける再帰、末尾最適化、末尾最適化できない再帰、トランポリン化によるスタックレス再帰について色々書きました。
簡単な再帰ロジックであれば、アキュムレータを使用することで、コンパイラによる末尾最適化の恩恵を受けることができます。実際コンパイラによる末尾最適化は、`while`への変換なので、速度的な面でいうと`@tailrec`できちんと末尾再帰として認識される再帰ロジックを記述した方が好ましいと考えられます。

実際、[トランポリン化とアキュムレータの性能比較](https://qiita.com/yyu/items/cd689bf8e61d103c72aa)で計測された結果によれば、常にアキュムレータを使用した方がトランポリン化よりかは高速のようです。

## 参考資料一覧

* [Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド](http://www.amazon.co.jp/dp/4844337769)
* [末尾再帰 - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0)
* [Scala @tailrecメモ(Hishidama's Scala @tailrec Memo)](http://www.ne.jp/asahi/hishidama/home/tech/scala/annotation/tailrec.html)
* [お気楽 Scala プログラミング入門](http://www.geocities.jp/m_hiroi/java/scala.html)
* [Trampoline で再帰処理の最適化](https://qiita.com/torao@github/items/4b224489c71bf460ad7c)
* [トランポリン化とアキュムレータの性能比較](https://qiita.com/yyu/items/cd689bf8e61d103c72aa)