cps.rs

// 失敗する例 (オリジナル: https://gist.github.com/cohama/73a90d99fa036030393727ecd51fcb13)
// 何が起きているのかを明示するため若干修正済み。

fn main() {
    let k0 = |r| println!("{:?}", r);       // このクロージャの型を仮に K0 とする
  
    repeat_cps(10, "hello", Box::new(k0));  // repeat_cps::<&'static str, (), K0> がインスタンス化される
}

// 型パラメータを持つ場合、それらの型「すべて」が確定したときに関数は初めて実体化される（C++と同じ）。
fn repeat_cps<A, B, K: Fn(A) -> B>(n: i32, x: A, k: Box<K>) -> B {
    if n == 0 {
        k(x)
    } else {
        // ここで生成されるクロージャの型は k に依存するため、それを明示するために K1<K> と表記する。
        let k1 = move |z| k(z);

        // repeat_cps::<&'static str, (), K1<K>> が実体化される
        repeat_cps(n - 1, x, Box::new(k1))
    }
}

// 要は、repeat_cps が実体化されるたびに（K の型が異なる）repeat_cps が無限に実体化される。
// repeat_cps<&'static str, (), K0> が実体化される
// => repeat_cps<&'static str, (), K1<K0>> が実体化される
// => repeat_cps<&'static str, (), K2<K1<K0>>> が実体化される
// ...
// 結果としてコンパイルが停止せずエラーとなる:
// > error: reached the type-length limit while instantiating `<std::boxed::Box<T>><[closure@src/main.rs:17:18: 17:31 k:std::bo...`
// > |
// >  = note: consider adding a `#![type_length_limit="2097152"]` attribute to your crate

// ---------------------------------------------------------------------------------------------------

// 要はクロージャの型がすべて別々に与えられてしまうのが問題なので、トレイトオブジェクトを用いて
// Fn(A) -> B を実装しているという情報以外を無視してしまえば良い。

// ただし、Rustではトレイトオブジェクトに対する生存期間を意識する必要があることに注意。
// 今回の場合、次の2つのバリエーションが有効である（省略可能な生存期間もあえて明示的に記載している）。

fn repeat_cps1<'a, A, B>(n: i32, x: A, k: Box<Fn(A) -> B + 'a>) -> B {
    // ...
}

fn repeat_cps2<A: 'static, B: 'static>(n: i32, x: A, k: Box<Fn(A) -> B + 'static>) -> B {
    // ...
}

// TODO: ライフタイムの説明

memo.rs

#![allow(dead_code)]
#![allow(unused_variables)]

// Rust 1.19 段階ではユーザ定義型への Fn/FnMut/FnOnce の実装は Nightly 必須なので注意。
#![feature(unboxed_closures)]
#![feature(fn_traits)]

#[derive(Clone, Copy)]
struct Foo<'a>(&'a usize);

impl<'a, 'b> FnOnce<(&'b str,)> for Foo<'a> {
    type Output = ();
    extern "rust-call" fn call_once(self, args: (&'b str,)) {
        self.call(args)
    }
}

impl<'a, 'b> FnMut<(&'b str,)> for Foo<'a> {
    extern "rust-call" fn call_mut(&mut self, args: (&'b str,)) {
        self.call(args)
    }
}

impl<'a, 'b> Fn<(&'b str,)> for Foo<'a> {
    extern "rust-call" fn call(&self, args: (&'b str,)) {
        println!("{:?}", args.0);
    }
}

fn hoge(x: &str) {
    println!("{:?}", x);
}

fn main() {
    repeat_cps1(10, "hello", Box::new(hoge));
    repeat_cps1(10, "hello", Box::new(&hoge));
    repeat_cps1(10, "hello", Box::new(Foo(&42)));
    repeat_cps1(10, "hello", Box::new(|x| {
        println!("{:?}", x);
    }));
    let y = &42;
    repeat_cps1(10, "hello", Box::new(|x| {
        y; // クロージャは参照をキャプチャしている
        println!("{:?}", x);
    }));
    
    repeat_cps2(10, "hello", Box::new(hoge));
    //repeat_cps2(10, "hello", Box::new(&hoge));
    //repeat_cps2(10, "hello", Box::new(Foo(&42)));
    repeat_cps2(10, "hello", Box::new(|x| {
        println!("{:?}", x);
    }));
    //let y = &42;
    //repeat_cps2(10, "hello", Box::new(|x| {
    //    y; // クロージャは参照をキャプチャしている
    //    println!("{:?}", x);
    //}));

    // この場合は A: 'static を満たさないので違法
    //let y = "hello".to_owned();
    //repeat_cps2(10, y.as_str(), Box::new(|x|{ println!("{:?}", x); }));
}

fn repeat_cps1<'a, A, B>(n: i32, x: A, k: Box<Fn(A) -> B + 'a>) -> B {
    if n == 0 {
        k(x)
    } else {
        repeat_cps1(n - 1, x, Box::new(move |z| k(z)))
    }
}

fn repeat_cps2<A: 'static, B: 'static>(n: i32, x: A, k: Box<Fn(A) -> B>) -> B {
    if n == 0 {
        k(x)
    } else {
        repeat_cps2(n - 1, x, Box::new(move |z| k(z)))
    }
}