末尾再帰をループにできないRustプログラムの例

概要: 生存期間の関係で、ループでは書けないが末尾再帰では書けるアルゴリズムの例を挙げる。

単方向リンクリスト

次のような単純なリンクリストを考える。

struct List<T> {
    root: Option<Box<Node<T>>>,
}
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

backの実装

単方向リンクリストの末尾要素の取得は O(n) である。これは次のように書くことができる。

impl<T> List<T> {
    fn back(&self) -> Option<&T> {
        let mut node = if let Some(ref b) = self.root {
            b.as_ref()
        } else {
            return None;
        };
        while let Some(ref b) = node.next {
            node = b.as_ref();
        }
        Some(&node.value)
    }
}

これは末尾に到達するまでノードを操作し、最後のノードの値を取り出すだけのコードである。

push_backの実装

同じ要領でpush_backを書こうとすると以下のようになる。

impl<T> List<T> {
    fn push_back(&mut self, value: T) {
        let mut node : &mut Option<Box<Node<T>>> = &mut self.root;
        while let Some(ref mut b) = *node {
            node = &mut b.next;
        }
        *node = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
}

しかしこのコードは生存期間エラーが発生する。

rustc 1.17.0 (56124baa9 2017-04-24)
error[E0499]: cannot borrow `node.0` as mutable more than once at a time
  --> <anon>:23:24
   |
23 |         while let Some(ref mut b) = *node {
   |                        ^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
30 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> <anon>:24:13
   |
23 |         while let Some(ref mut b) = *node {
   |                        --------- borrow of `node` occurs here
24 |             node = &mut b.next;
   |             ^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `*node` because it is borrowed
  --> <anon>:26:9
   |
23 |           while let Some(ref mut b) = *node {
   |                          --------- borrow of `*node` occurs here
...
26 |           *node = Some(Box::new(Node {
   |  _________^ starting here...
27 | |             value: value,
28 | |             next: None,
29 | |         }));
   | |___________^ ...ending here: assignment to borrowed `*node` occurs here

error: aborting due to 3 previous errors

おそらく、このpush_back関数をループで書く方法は存在しない。これは生存期間のネストの深さを考察することで導くことができる。

生存期間のネスト

backもpush_backも、根ノードから順にノードを辿っていくという点は同様である。このとき、各ノードの参照は、直前のノードから借用した形になっている。したがって生存期間は以下のようにネストしていることになる。

ところでbackのループではnodeは共有参照の形で持っている。したがって上の図でnode1が生存している間も、node0の参照は有効である。共有参照の借用では、node1の生存期間を延長して解釈しても、node0の有効期間に影響を与えないので、これらの生存期間を以下のように延長して解釈する。

このように解釈すると、生存期間のネストを考えずにすむ。全てのノード参照が同じ生存期間を持つので、同じ変数に入れて管理することができる。

一方、push_backのループではnodeは排他参照の形で持っている。したがって上の図で実際にノードが有効な期間を図示すると以下のようになる。

各ノードが有効な期間がない、ということはないので、これらの生存期間は真にネストしているとみなすしかない。当然、同じ変数に入れて管理することはできない。

ネストの深さ

さらに、このネストの深さを考えると、これはリストの長さに応じて非有界に増加しうることがわかる。

ところが、Rustでは単一の関数呼び出しの中だけでは生存期間のネストを非有界に増やすことはできない。生存期間をレキシカルに管理するためのリージョンは有限個しかなく、単一の関数呼び出しの中では各リージョンのインスタンスは同時には1個ずつしか存在しえないからである。

したがってpush_backはループをもつ単一の関数では書けないだろう、ということになる。

push_backを書くには

unsafeを使うか、以下のように末尾再帰で書けばよい。

impl<T> List<T> {
    fn push_back(&mut self, value: T) {
        fn findlast<T>(node: &mut Option<Box<Node<T>>>)
                -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut b) = *node {
                findlast(&mut b.next)
            } else {
                node
            }
        }
        let node = findlast(&mut self.root);
        *node = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
}

最適化をかけて試してみたところ、どうやら末尾呼び出し最適化は行われる場合があるようなので、unsafeをつけるほどでもないときはこのように末尾再帰でよいかもしれない。

まとめ

再帰的なデータ構造に対する処理で、根から葉へとノードを辿るような処理を考える。辿ったノードを &mut で持つときは、この処理をループで書けない場合がある。この場合でも末尾再帰を使えば書くことができるし、条件によっては末尾呼び出し最適化も行われる。