Rustで学ぶ不動点コンビネータ - 無名再帰とメモ化の実装

Situation

再帰関数を行う場合は、関数の名前を束縛して再帰を行うことで、比較的簡単に実装できます。

実際、再帰的にフィボナッチ数を表現する一般例は、下記のようなコードになります：

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

⚠：実際にフィボナッチ数列を扱う際はメモ化させると思いますが、詳細は フィボナッチ数列(今更聞けない) #Python - Qiita　を参照してください。

ただ、世の中には無名再帰というものがあり、関数の名前を束縛せずに再帰を行うことができます。

不動点コンビネータという、ラムダ計算や関数型言語でよく利用されるテクニックの一つで、今回はそのなかでもZコンビネータと呼ばれるものをRustで実装することで、関数の名前を束縛せずに再帰を行う方法を紹介します。また、今回はZコンビネータを実装する際に、メモ化を行うことで、パフォーマンスを改善する方法も紹介します。

• 不動点コンビネータ - Wikipedia
• 無名再帰 - Wikipedia

Complication

Zコンビネータ

実装するためのRustの基礎知識

不動コンビネータをRustで実装するには、いくつかRustの文法を把握しておく必要があります。

Rustのコードで出てくる内容	説明	参考リンク
<A,B>	Rustのジェネリクス。	ジェネリクス - Rust By Example 日本語版
'a	ライフタイム。Rustの型システムにおいて、参照の有効期間を指定するためのもの。	ライフタイム境界 - Rust By Example 日本語版
Trait	トレイト。Rustの型システムにおいて、特定の振る舞いを定義するためのもの。	トレイト：共通の振る舞いを定義する - The Rust Programming Language 日本語版
impl	トレイトの実装。特に型の定義において利用をすると、それが Traitを実装していることを要求できる。	impl Trait - Rust By Example 日本語版
'a + Trait	'aのlifetimeを持つ参照で、かつTraitを実装している型を要求できる。	rust-lang/rfcs#0599 default object bound
Fn Trait	関数の型を表すトレイト。Fn, FnMut, FnOnceの3つが有名だが、今回は可変な参照を持たないので、Fnのみを利用する。	Fn in std::ops - Rust
&	参照。	参照と借用 - The Rust Programming Language 日本語版
dyn	動的に決まるTraitを実装したStructを表したいときに利用する。	dynを利用してトレイトを返す - Rust By Example 日本語版
where	トレイト境界を指定するために利用する。特に、whereを利用すると、複数のトレイト境界を指定できる。	Where句 - Rust By Example 日本語版
Box	ヒープ上にデータを格納するためのスマートポインタ。主に、サイズがコンパイル時に決まらない型を扱いたいときに利用する。	Box, スタックとヒープ - Rust By Example 日本語版
ⅠⅠ	クロージャを定義するために利用する。クロージャは、関数のように振る舞うが、環境をキャプチャできる。	クロージャ - Rust By Example 日本語版
move	所有権をクロージャなどに移動させるために利用する。	move - Rust
*	参照外し（Dereferencing）を行うために利用する。	Derefトレイトでスマートポインタを普通の参照のように扱う - The Rust Programming Language 日本語版

実装例

不動点コンビネータは、再帰的な関数を定義するためのテクニックで、特に関数型言語でよく利用されます。Rustでも同様のことが可能です。

fn fix<'a, A, R>(
    f_for_fix: impl Fn(&dyn Fn(A) -> R, A) -> R + 'a,
) -> impl Fn(A) -> R + 'a
where
    A: 'a,
    R: 'a,
{
    fn inner<'b, A, R>(
        f_in_box: &'b dyn Fn(&dyn Fn(A) -> R, A) -> R,
    ) -> Box<dyn Fn(A) -> R + 'b>
    where
        A: 'b,
        R: 'b,
    {
        Box::new(|y| f_in_box(&*inner(f_in_box), y))
    }

    let f_boxed = Box::new(f_for_fix);
    move |x| f_boxed(&*inner(&*f_boxed), x)
}

fn main() {
    let fib_fixed = fix(|f, n| if n <= 1 { n } else { f(n - 1) + f(n - 2) });
    println!("Fibonacci of 10 using fixed-point combinator is: {}", fib_fixed(10));
}

解説

このコードは、Rustで不動点コンビネータを実装する例です。fix関数は、再帰的な関数を定義するためのものです（lifetimeは'aを持ちます）。
f_for_fixは、再帰的な関数を定義するためのクロージャで、引数として再帰的な関数(&dyn Fn(A) -> R)と、A型の値を受け取ります。戻り値は再帰関数dyn Fn(A) -> Rです。
f_for_fixのlifetimeは 'aで、これは最初に与えられたクロージャのlifetimeを示します。ここで引数を借用している理由は、所有権を移動させずに再帰的な関数を定義するためです。

inner関数は、再帰的な関数を実際に呼び出すための内部関数です。
f_for_innerは、再帰的な関数を定義するためのクロージャで、引数として再帰的な関数で、lifetime'bで借用されたTraitオブジェクト(&(dyn Fn(A) -> R, A))を受け取ります。戻り値は Box<dyn Fn(A) -> R>で、これはヒープ上に格納されるクロージャです。
inner関数の中で、Box::newを使ってクロージャをヒープ上に格納しています。ここで、&*f_in_boxは、借用された参照から参照外しを行いBoxの中のクロージャを取得し、それに対してさらに借用を重ねることで、所有権を移動させずに再帰させるようにしています
（&*f_in_box=&*Box<dyn Fn(A) -> R>=&dyn Fn(A) -> R）。

move |x| f_boxed(&*inner(&*f_boxed), x)は、クロージャを返す部分で、f_boxedを借用して、再帰的な関数を呼び出します。ここでmoveを使うことで、f_boxedの所有権をクロージャに移動させています（innerの内部でmoveを利用していないのは、借用の範囲で所有権を移動させていないため）。

ただし、呼び出し回数が増えれば増えるだけ、ヒープを利用するため、パフォーマンスが悪化する可能性があります（冒頭でも述べましたが、そもそも、この実装はメモ化を行っていないため、そちらのほうがボトルネックになると思いますが、メモ化を行うことでパフォーマンスを改善できる可能性があります）。

メモ化を加えたZコンビネータ

実装をするためのRustの基礎知識

メモ化を加えることで、再帰的な関数のパフォーマンスを改善できます。メモ化は、計算結果をキャッシュして、同じ入力に対して再計算を避ける手法です。

Rustのコードで出てくる内容	説明	参考リンク
HashMap	キーと値のペアを格納するためのデータ構造。メモ化のために利用します。	キーとそれに紐づいた値をハッシュマップに格納する - The Rust Programming Language 日本語版
Clone	RustのTraitの一つで、値を複製するためのもの。メモ化のために、値を複製できる必要があります。	クローン - Rust By Example 日本語版
RefCell	不変な参照を複数ヶ所(borrow)、もしくは、可変な参照(borrow_mut)を一箇所に持つことを共用することを、コンパイル時ではなく、実行時に制御するためのスマートポインタ。（個人的に、少し危険なスマートポインタですが、今回のケースではメモ化の更新のタイミングは他のlifetimeと重複しないめ、利用しても問題ないと判断しました）	RefCellと内部可変性パターン - The Rust Programming Language 日本語版

実装例

use std::collections::HashMap;
use std::cell::RefCell;
use num::BigUint;


fn fix_memoized<'a, A, R>(
    f_for_fix: impl Fn(&dyn Fn(A) -> R, A) -> R + 'a,
) -> impl Fn(A) -> R + 'a
where
    A: std::hash::Hash + Eq + Clone + 'a,
    R: Clone + 'a,
{
    let cache = RefCell::new(HashMap::<A, R>::new());

    fn inner<'b, A, R>(
        f: &'b dyn Fn(&dyn Fn(A) -> R, A) -> R,
        cache: &'b RefCell<HashMap<A, R>>,
    ) -> Box<dyn Fn(A) -> R + 'b>
    where
        A: std::hash::Hash + Eq + Clone + 'b,
        R: Clone + 'b,
    {
        Box::new(move |x| {
            if let Some(v) = cache.borrow().get(&x) {
                return v.clone();
            }
            let v = f(&*inner(f, cache), x.clone());
            let mut borrowed_cache = cache.borrow_mut();
            borrowed_cache.insert(x, v.clone());
            v
        })
    }

    let f_boxed = Box::new(f_for_fix);
    move |x| inner(&*f_boxed, &cache)(x)
}


fn main() {
    let fib_memoized = fix_memoized::<u32, BigUint>(|f, n| if n <= 1 { n.into() } else { f(n - 1) + f(n - 2) });
    println!("Fibonacci of 100 using memoized fixed-point combinator is: {}", fib_memoized(100));
}

解説

このコードは、Rustでメモ化を加えた不動点コンビネータを実装する例ですが、cache以外は、先ほどのZコンビネータと同様です。

ただ、cacheの利用の際にコピーを行う必要があるため、AとRの型に対して、Cloneトレイトを実装している必要があります。また、この実装ではRefCellを利用して、可変な参照を持つことができるようにしています。これにより、メモ化のキャッシュを更新することができます。